AtCoder Beginner Contest 278 備忘録
コンテストページ:AtCoder Beginner Contest 278 - AtCoder
コンテスト中AC:A〜D
E,Fはコンテスト後に自力AC
E - Grid Filling
このユーザ解説と同じ方法で解きました。
想定解法は二次元累積和だったようです。
実装:Editorial - AtCoder Beginner Contest 278
二次元累積和の構造体を作って解いてみました。
実装:Submission #36758941 - AtCoder Beginner Contest 278
F - Shiritori
後退解析+bitDP(巡回セールスマン問題)の考え方で解けます。
問題を有向グラフに言い換えておきます。
を頂点
とする。
を言える場合、頂点
へ向かう有向辺があるとする。
- 有向グラフ上を交互に移動することを繰り返し、移動できなくなった方が負け
制約上、bitDPが疑われるので、その要領で考えてみます。
これまでに訪問した頂点集合が
で頂点
で自分のターンを終えたとき、勝てるなら1、負けるなら0
まず、"次のターンでこれ以上移動できる頂点がない"となった時点で勝ちが確定します。そこで、訪問した頂点数が多い順から勝敗を確定していけそうです。
これが後退解析にあたります(おそらく)。
では、勝敗の確定条件を考えます。
自分が頂点で移動を終え、
から移動可能であって、かつ未訪問の頂点が
であるとします。
このうち、いずれか1つでも勝ちとなる頂点が存在する場合、相手はその頂点に移動すれば勝てるので、自分は負けとなります。逆に負けの頂点しかなければ、勝てます。
また、訪問可能な頂点がない場合も自分が勝ちとなる条件となります。
後はこれに従って、bitDPを逆に回していきます。
最終的に"頂点が1つだけ訪問済みである"という状態のDP値(例えば、N=3ならdp[001][0], dp[010][1], dp[100][2]。なお、1つ目のインデックスはbit列)について、頂点のうち、ただ1つでも勝ちがあれば太郎くんが勝ちます。
実装: Submission #36721268 - AtCoder Beginner Contest 278
余談で、DPの別の言い方を示しておきます。
これまでに訪問した頂点集合が
で頂点
で自分のターンが回ってきた時、勝てるなら0、負けるなら1
この場合、移動できなくなったら負けるので、訪問可能な頂点がなければ負けです。また、相手のターンになったときに負けとなる頂点が1つでもあれば自分は勝てます。
最終的に"頂点が1つだけ訪問済みである"という状態のDP値について、頂点のうち、ただ1つでも負けがあれば、太郎くんが勝ちます(1つだけ訪問済みの状態で順番がくるのは次郎くんであるため)。
実装:Submission #36708784 - AtCoder Beginner Contest 278
