2017-05-17

AOJ 1611 ダルマ落とし

dp[l][r] = {lからrまでの区間の状態}と持ってDPする、区間DPの問題。
この問題ではdp[l][r] = {lからrまでの区間で叩ける最大のブロック数}とする。
dp[l+1][r-1]の区間が全てのブロックを叩き出すことができ、l番目とr番目のブロックの重さの差が1以下のときdp[l][r] = r-l+1 となる。また、k番目(l <= k < r)のブロックで区切り、dp[l][k] + dp[k+1][r] の最大がdp[l][r]となる。
全ての取りうる区間の幅のブロックを小さい方から試すのがO(n^2)、その区間の中の区切るブロックを全て試すのがO(n)でO(n^3)で計算できる。

2017-05-10

AGC014 A,B,C,D

AGC 競技プログラミング

agc014.contest.atcoder.jp

公式解説(pdf)
Editorial - AtCoder Grand Contest 014 | AtCoder

公式動画解説
www.youtube.com

A問題

問題の得点からそんな難しい問題ではないだろうと決め打ちしてlog_2(max(a, b, c))回でシミュレーションが実行できそうだと考えた。10^7回シミュレートして終わらなかったら-1を出力した。ちょっと勘違いして実装に時間をかけてしまった。

B問題

いくら手元で実験を繰り返しても思い浮かばず50分経過くらいで順位表を見たらすぐにWAも出さず解いてる人がいたので実は簡単なのではと思い考え直す。1と全ての他の頂点がつながっている木を試すとこのグラフのみでYes、Noが判定できるのではと思い提出したら通った。コンテスト後のtwitterを見ていた限り証明しないで（順位表を見て）出したらACだった人が多かった。

C問題

コンテスト中は問題文読んだ時点で難しそうだったのでスルーした。割と発想ゲーだったように思えたのでもうちょっと考えればよかった。最初にK回移動し、残りの魔法は壁をK回壊し、K回進むと考えると一番近い辺に直進するのがいいことがわかる。K回の移動でたどり着ける範囲をBFSで列挙し、辺にたどり着くまでの魔法の使用回数が最も少ない点を選ぶ。

D問題

次数1の頂点に2つ以上隣接している頂点があればFirstを返すコードをとりあえずで出したら予想外にACのテストケースが多くこの方針にコーナーケース対策を追加する方針で考え始めたのが終わりの始まりだった…隣接している頂点が全て次数1の頂点に隣接している頂点があるときFirstを返す（次数1の頂点からの距離が3以上でも白く塗れるケースはあるのでWA）、ある頂点が最終的に白く塗れるかどうかを葉の方に向かってDFSをすべての頂点に行う（O(n^2)で当然TLE）と考えたところでコンテスト終了。
中心の点から考えるのではなく葉から貪欲に考えることでO(n)で解ける。葉を黒く塗り隣接している頂点を白く塗る。そして塗った頂点をグラフから切り離す。このとき次数0の頂点が存在すればFirst、存在せず最後まで塗ることができればSecondを出力する。
グラフに完全マッチングが存在すれば白く塗った頂点とマッチングで繋がれた頂点を黒く塗ることで、すべての白く塗った頂点に隣接する頂点を黒く塗ることができる。よって完全マッチングが存在することと後手必勝は同値。
葉から探索を始める、完全マッチングといった発想は覚えておきたい。

2017-04-10

AOJ2254 Fastest Route

AOJ 競技プログラミング

Fastest Route | Aizu Online Judge

まずN<=8ならばnext_permutationi()でO(N!)全列挙すれば通りそう。クリアした順序は最短時間に関わらないので、どのステージをクリアしたかの情報のみを保持しておけば計算する量を減らせそう。クリアした・してないの2つの状態がNステージについてあるので全体で2^Nの状態について計算すればよさそう。

dp[S] = （集合Sをクリアするのにかかる最短時間）とする。
dp[S]は集合Sから要素を一つ取り除いた集合をクリアするのにかかる最短時間 + 集合から取り除いたステージをクリアするのにかかる最短時間と考えられるので漸化式で表すと
dp[S] = min{dp[S/{j}] + min{t[j][k] | k∈S/{j}} | j∈S}
となる。集合について扱うDPなのでbitDPで書くとO(n^2・2^n)で解けて間に合う。