■ 2023 年 7 月 30 日

やつたこと

• 精進
• ABC296E
• 写像 f を f: {1, ..., N} -> {1, ..., N}; f(n) = A_n で定義する．
• i 回目のゲームでは，与へられた正整数 K_i に対して f^{K_i}(S_i) = i となる S_i が存在すれば，高橋君の勝ちである．
• さて，いま K_i はいくらでも大きく取れるが， K_i が充分大きいとき， f^{K_i} の終集合はかなり小さくなつてゐる．具体的には f から自然に定義される functional graph G を考へたとき， n \in {1, ..., N} に対して次の 2 つが同値になる．
• n が f^{K_i} の終集合に含まれる．
• G 上のある閉路 C が存在し， n \in C である．
• よつて，あとは G のすべての閉路を検出すれば，その閉路上にある数字のみ高橋君は勝つことができる．
• ABC298E
• 動的計画法．
• dp[i][j][k] = 高橋くんが地点 i，青木くんが地点 j，にゐて， k==0 なら次に高橋くんがサイコロを振る， k==1 なら次に青木くんがサイコロを振るときの高橋くんの勝率と定義．
• dp[N][x][*] = 1, dp[x][N][*] = 0 (x = 1, ..., N-1) であり，
• dp[i][j][0] = (1/P) \sum_{k=1}^P dp[min(i+k, N)][j][1],
• dp[i][j][1] = (1/Q) \sum_{k=1}^Q dp[i][min(j+k, N)][0].
• dp[A][B][0] が答へ．
• ABC299E
• 各頂点から Dijkstra 法を行ふことにより，次のやうに色分けをする．
• p_i から距離が d_i の頂点はすべて白頂点でなくてはならないから，白で塗る．
• 逆に，すべての p_i から距離が d_i 以上離れてゐる頂点の色は，白でも黒でも構はない．そこで，このやうな頂点はすべて黒で塗る．
• あとは，各 p_i から距離 d_i の点に黒頂点であるやうなものがあるか確認すれば良い．