ABC244 参加記録

コンテスト中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]

答えはです。
提出コード