問題 tdpc.contest.atcoder.jp 解法 まず強連結成分分解して, DAG の形にします(下のコードでは SCC ライブラリを使わないで Warshall-Floyd を使っていますが)。そしたら, DAG のあるノードに訪れたとすると, そのノードに含まれる頂点数(強連結成分の数)分…

問題 mujin-pc-2016.contest.atcoder.jp 解法 正しい括弧列は, 「'(' の数が ')' の数を下回ることなく進んでいき, 最終的に '(' と ')' の数が等しくなる文字列」と解釈することも出来ます。これ結構よく出るので覚えておいたほうが良いです。そう考えると,…

unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。 まとめ 基本的にチェイン法っていうのでやってるっぽい vector > みたいのをイメージするとわかりやすい 詳細 まとめで書いたように, 基本的には vec…

MUJIN プログラミングチャレンジ に参加しました。企業紹介がとても面白かったです。 問題 mujin-pc-2016.contest.atcoder.jp 解法 C は「奇数長 閉路」でぐぐったら答えがわかった— マヨ子@だがしかし可視化 (@mayoko_) 2016年2月27日ググりましょう。する…

問題 codeforces.com 解法 準備として, 各文字列 wi を反転させて, 小文字化します。やりたいことは, dp[now] = (now 文字目以降を wi を使って表現できるか？) というものです。ただ, あとで dp 復元するために, dp[now] = (now 文字目から復元が不可能なら…

問題 codeforces.com 解法 直前の 2 要素が 0 の時, またその時のみ数列のすべての値が 0 になります。それ以外の場合は, 普通のフィボナッチ数列と同じように, 指数オーダーで発散します。調べてみると, 大体 100 個程度あれば絶対値が 10^9 を超えてきそう…

問題 No.348 カゴメカゴメ - yukicoder 解法 それぞれの輪について, 輪 ch が輪 v に覆われているならば, v -> ch に辺を貼る, ということをやって木グラフを作れば, 木 DP に落とし込める, というのは簡単にわかります。問題は木グラフをどう作るかなんです…

問題 TopCoder Statistics - Problem Statement 解法 見た目がハミルトンパスに見えますが, 実はオイラー路の問題になります。蟻本の p205 に書いてあるようなグラフを作るようなイメージです。二部グラフ (U, W) を作るのですが, board[i][j] == '#' ならば…

問題 TopCoder Statistics - Problem Statement 解法 区間 DP で解くことが出来ます。dp[l][r] = (区間 [l, r] において得ることの出来るスコアの最大値) とします。区間 [l, r] の中では, 最後に残るのは, l 番目と r 番目の数です。最後に m 番目(l 区間の…

問題 TopCoder Statistics - Problem Statement 解法 まず, Jiro 君が今 Ciel さんのいる場所を特定する方法を考えてみます。 Ciel さんは最初, 0, 1, ..., n-1 のいずれかにいる可能性があります。この集合を S としましょう。そこで Ciel さんが "taxi" と…

D は問題文が理解できないので桁 DP だよねということだけ言っといて退散します。 というかこの問題, 趣旨的に tourist を助けて欲しいという問題になっていますが絶対 tourist のほうが早く解けるんだよなぁ。 問題 codeforces.com 解法 まず, toR[i][j] = …

問題 TopCoder Statistics - Problem Statement 解法 最終的には, スターグラフにして, その中心みたいな頂点を capital にすることになりますね。 Star Graph -- from Wolfram MathWorldグラフは木 + 1 本の辺, という形をしていて, 1 つだけ閉路があります…

何もわかってなかった僕が言うのもなんなんですが何も考えず脳筋 dfs で通ってしまうのはちょっとアレですね… 問題 TopCoder Statistics - Problem Statement 解法 結局脳筋 dfs (各頂点からスタートして, パスの長さが 4 になるようなものがあるのかを調べ…

問題 TopCoder Statistics - Problem Statement 解法 まず, りんごの木の位置は 0 に固定しても問題ないです。他の 2 つの初期位置を動かしましょう。これで O(n^2) みたいな感じになるので, あとは O(1) で木の最小距離 x を求められるようにしたいです。り…

問題 www.codeforces.com 解法 kmjp さんの解法を参考にしました。kmjp.hatenablog.jpまず, この問題では 「グラフに辺を 1 本加えた時出来る閉路について, 特に u, v を含む閉路の平均長」を求める問題であることに注意します。depth[u] u, v の lca が u …

このこどふぉ, なんとなく DDPC 本戦が想起される(B が priority_queue を使ったほげで, C が高速化出来る dp) 問題 codeforces.com 解法 pick するなら, 残っているもののうち一番でかいのを取ってくるのが最適です。これを考えると, pick されるものとして…

問題 codeforces.com 解法 二分探索します。check(x) = (担当する人が最大で x 日働いて良い場合の, 各問題の人の割り振りを表す配列。割り振れない時は ひとつ目の要素を -1 にする) とすると, 以下のようにすれば最小コストで担当者を割り振れます(前準備…

問題 codeforces.com 解法 まず空いてるマスのすべてを 'X' にし, 'X' となっている好きな点から幅優先探索して '.' を広げていけば良いです。 string field[505]; bool done[505][505]; int n, m, k; int main() { cin.tie(0); ios::sync_with_stdio(false)…

問題設定ちょっと不自然な気がして最初誤読しました。普通上におけるのは体積の小さいものではなかろうか…？ 問題 codeforces.com 解法 素直に dp 解法を取ろうとすると, dp[i] = max(dp[j], j > i, vj > vi) + vi (vi は i の体積) となりますが, これを普…

問題 codeforces.com 解法 dp[now][d] = (now 個の括弧を使った文字列の内, '(' の数が ')' の数を下回ることが一度もなく, '(' の数が now までで ')' の数を d 個上回っているようなものの数) とします。これは簡単な dp で計算できますね。で, 入力文字列…

問題 discovery2016-final.contest.atcoder.jp 解法 valid な括弧列は木構造になっています。例えば入力例 3 では, でっかい括弧から, 小さい括弧 2 つに向かって辺が伸びている木グラフであると考えることが出来ます。一つの頂点は 2 つの括弧 () に対応し…

問題 discovery2016-final.contest.atcoder.jp 解法 ある時間 t までに得られる最大の美味しさを priority_queue で管理します。時間 t には, t 個のビュッフェを取ることが出来ますが, どのように取るのが良いかというと, 美味しさが大きいものから取るのが…

本が 10^6 グラムってそれ 1 トンやんけ！ 問題 TopCoder Statistics - Problem Statement 解法 Tomek 君が最初に押し付ける本を決めたら, 後は両者とも, 貪欲に「できるだけ重い本を相手に押し付ける」というのが最適です。そうしないと, 余計に重い本を相…

問題 TopCoder Statistics - Problem Statement 解法 見えない部分の得点が小さい順に a1, a2, ..., aK であるとすると, 見えない部分については, 順番に a1, a2, ..., aK というように投げていくのが最適です(例えば 1 箇所に集中狙いのような投げ方では, …

問題 TopCoder Statistics - Problem Statement 解法 45 度回転させることを考えます。もとの x, y に対して, x' = x+y, y' = x-y とすると, 各移動に対して, x', y' の遷移は以下のようになります。 x++ -> x'++, y'++ x-- -> x'--, y'-- y++ -> x'++, y'--…

問題 TopCoder Statistics - Problem Statement 解法 d[i][j] = (i 番目の場所の高さを altitude[j] にするようなもので, 0 番目から i 番目に行くのにかかる最小コスト) というのを dijkstra で計算します。グラフは, まず d[0][i] = abs(altitude[0]-altit…

問題 TopCoder Statistics - Problem Statement 解法 直前 K 個 の頂点の次数の偶奇がわかっていれば, dp に持っていけそうです。dp[now][restEdge][atLeast][flag] というように状態を与えます。 now 番目の頂点を見ていて, 残り貼る辺の数は restEdge で, …

問題 TopCoder Statistics - Problem Statement 解法 3 つ連続になっているものを全部並べて, あと左側と右側にプラス要素があったら添える, ということをやれば良いだけです。真ん中 only に値があるものは, これだと全く無視されますが, 他になんの値もな…

問題 codeforces.com 解法 k 乗の和は, k+1 乗の多項式になります。なんで, って人は下の記事を読みましょう。 yama-taku.scienceということで, ラグランジュ補間しましょう。 mayokoex.hatenablog.com ラグランジュ補間は次数 k に対して O(k^2) かかるのが…

問題 codeforces.com 解法 0 の子 v の部分木それぞれの葉から, すべてのアリが頂点 v に到達するまで, 何秒かかるかを調べます。各頂点の v からの距離 d が等しい頂点同士は, 同時に v に向かって行くといつかどこかの頂点でおなじ頂点で重なるので, どち…