コンテスト中AC:A〜E
C - Yamanote Line Game
D - Swap Hats
自信ないまま通してしまいました。
操作を偶数回行った後に生成される状態には回行った後もその状態にできます。
10回操作すると状態数はになるものの、RGBの順番の入れ替えの通り数は6通りしかありません。
そのため、を10回操作して
にできれば達成できると考えました。
実際に実装してデバッグしてみると、状態数は偶数回、奇数回共に早々に3個に限定され、解を得られそうだとわかりました。
そして、提出した結果ACできました。
公式解説によれば、6種類の状態の関係性をグラフにすると、二部グラフになり、が同一のグループになれば達成できるということでした。
E - King Bombee
パスに関する以下のDPを考えます。
回移動した後に頂点
にいるようなパスの総数
初期値は
これは、のうち、
であるものの総数に一致します。
このDPテーブルの更新は、以下のような3重ループになります。
for k = 1からKまで for u in 全ての頂点 for v in uと接続する全ての頂点 dp[v][k] = dp[u][k-1] //uからvに移動する
for v in uと接続する全ての頂点
の部分は、のループの1回につき、合計で
回しか実行されないので、
になります。
また、回目で
にいるパスの総数は
となります。
ここまでは、同様の考え方が過去に出題されました。
あとはに訪れた回数(
に含まれる
の個数)の偶奇の情報が欲しいので、DPテーブルに加えます。
回移動した後に頂点
にいて、かつ
に訪れた回数の偶奇が
であるようなパスの総数
但し、であり、
の時は
に訪れた回数が偶数、
の時は奇数
DPテーブルの更新は、以下のようにの時だけ、偶奇を入れ替えればよいです。
for k = 1からKまで for u in 全ての頂点 for v in uと接続する全ての頂点 if vがX dp[v][k][0] = dp[u][k-1][1] dp[v][k][1] = dp[u][k-1][0] else dp[v][k][0] = dp[u][k-1][0] dp[v][k][1] = dp[u][k-1][1]
答えはです。
提出コード