脳log[20230709]

2023年07月09日 (日) [AtCoder] 今日は ARC164 があった。くやちい。C 問題が AC だったのがくやしい。コンテスト成績表。自分のすべての提出。以下 ABC のふりかえり。■A 問題「Ternary Decomposition」。とりあえず３進数を考えます。純粋な３進数と違うところは、各桁の上限が２に限られないということ。どういうことか。n=9 のとき、3^0 ×９個が k の上限で、3^2 ×１個が k の下限。もうちょっと書くと下限は３進数で表したときの各桁の和。その範囲外なら No。範囲内であれば、ある桁を崩して１つ下の桁を３個増やすことができる。つまり２個ずつなら調整が可能。奇数個の調整は不可能。■B 問題「Switching Travel」。白黒白黒……とパスを辿っていったとき、白白もしくは黒黒の辺によって閉路が生じるなら答えは Yes だと思った。それを BFS で実装したら WA だったので UnionFind で実装し直して AC になった。何が悪かったのかはわからない。嘘ですわかります。白黒の辺だけを考えるときグラフが連結だとは限らないので一応すべての頂点を始点にして BFS をしたのだけど、訪問済みフラグを流用していた。だから白白もしくは黒黒の辺で訪問済みの頂点にぶつかったとき、それが異なる連結成分を結んでいるのか閉路なのか区別できなかった。N 回 N 要素の配列を確保することが許されないので流用したのだけど、訪問済みフラグの値を工夫しないといけなかったらしい、BFS/DFS でやるならね。ほら WA→AC■C 問題「Reversible Card Game」。B 問題の AC から１時間弱の時間が残っていたのだけど、ほぼほぼ途方に暮れていた。何が最適な戦略なのかさっぱりだった。終了 10 分前くらいから書き始めたのはこういうの。まずカードを裏が大きい(A≦B)と表が大きい(A>B)で分ける。裏が大きい(A≦B)カードについては何もすることがない。だってね、全部のカードが A≦B だったとしよう。Bob は Alice が引っ繰り返したそばからカードを得点に変えていくのが最善。だから他にカードがあるときに Alice はひっくり返さないし、Bob もまだ取らない。では A>B のカードについてはどうか。これは A-B が大きい順に Alice が A を隠す(裏が大きいカードに混ぜる)、Bob がカードを得点にするということを繰り返す。表が大きいカードが１枚だけ余ったらうまいこと考える。それがサンプルの１。なんで終了６分半後に AC だったんだよー。■C 問題はもっと単純だったらしい。「B の大きいペア数が奇数のときは、1 枚だけ低い値をとらされるようだ。低い値は何を取らされる？ Alice がどうがんばっても、Bob は最もリスクの低いカードを選ぶことができるようだ。abs(B-A) が最も小さいカードを選べばいい。」 言われればそう。Alice が裏返して隠した表が大きいカードも、後半戦で裏返すそばから Bob に得点に変えられてしまうのだから。