練習でも、 問題を読む 制約を見る 〜10: O(n!) 15〜20: O(2^n) 30〜40: O(2^(n/2)) 50: O(n^4)程度, DP, グラフ 〜10^14: O(√n) 考えて 適当に分割してみる サブ問題に再帰的に分割できる？ 小さな場合を制約式のようなものに展開する 一旦考えなおす さら…

不等式の場合、それは順序関係で、 順序関係で有向グラフにするという考え方はありだ。 循環があるかの判定(dfs/bfsでおｋ)で矛盾があるかが判定できる 矛盾がない場合それはDAGということなので、DAGとして色々考えられる グラフにしよう

http://apps.topcoder.com/stat?c=problem_statement&pm=11704&rd=14729 問題 命令列が与えられる "right X", "left X" (X: nat, X 右・左にX度回転する。 "forward X", "backward X" (X: nat, 1 現在の方向に対して前・後にX進む。これらの命令を入れ替える…

http://apps.topcoder.com/stat?c=problem_statement&pm=11808&rd=14729 問題 整数座標が何個か与えられる(1(0,0) /\ (i <> j -> (X_i, Y_i) <> (X_j, Y_j)))。 上下左右の整数座標にのみ進むことが出来る。 このとき、点(0,0)から出発し、与えられた座標を…

http://apps.topcoder.com/stat?c=problem_statement&pm=11805&rd=14731 追記: (コメント/Editorialより) 想定解(とこの解答)は間違っているらしい Editorial読んでたのに、そのことに気づかない程度の英語力！ 問題 N(1 i番目の兵士は砦0から砦iへ向かいた…

DAGの最小パス被覆 パス被覆(path cover)とは、あるグラフのパスの集合であって、そのグラフの全ての点がそのパスに含まれているものをいう。 最小パス被覆とは、パス被覆の中で、パスの数が最小のものをいう。 DAGの最小パス被覆は二部グラフの最大マッチン…

頂点被覆(vertex cover)とは、あるグラフの点のサブセットであって、全ての辺がその点に接しているものをいう。 最小点被覆とは、点被覆の大きさをできるだけ少なくするもので、一般の場合では(決定問題に"グラフCに大きさk以下の頂点被覆があるか"として変…