トップ > プロコン > ABC261

ABC261

プロコン

6完。ここ数日体調が悪く、昨日のゆきこでは問題が異常に難しく見えて1完撤退してた。今日はなんとか戻ってよかった。

A - Intersection

離散的なボールとかに色を塗るのかと思って全探索を書きかけたが、よく見ると数直線だった。区間の共通部分。解説が丁寧でよい。

B - Tournament Result

矛盾を定義されても怖いが。Wを1、Lを-1、他を0に変換して受け取る。反対側と足して0でない場所があったらダメ。

C - NewFolder(1)

サンプルを見ると要するにどういうことかわかりやすい。問題名もそうだったのか。unordered_mapで文字列をカウントしていく。

D - Flipping and Bonus

どうすんだって感じだが、i回目でカウンタが0になったときそれまでの過程は関係なくなりまとめて考えられると思いDPだと気づく。最初はカウンタが0になったときでまとめることを考えていたが、どうも考えがまとまらず、普通にDPする方法も思いついたので、普通にやることにした。i回コイントスしてj回連続表が出ているときの最大でDP。表が出た場合と裏が出た場合で配った（chmaxする）。実装上、連続ボーナスは（ボーナスがないところは0で埋めて）N通り持つ。

i回コイントスして最後裏が出たときの最大でDPするには、遷移が、最後に裏が出た場所の全探索になって、後ろから累積和を更新していく感じになるのかな。裏が1回も出てないときは「最後に裏が出たのが-1回目」みたいな扱いをするのでDPの配列のサイズがN+1ではなくN+2になり実装も混乱する。累積和の時点で難しいし、コンテスト中に選ぶ方針ではなかった。ただ、最初に思いついた方針で実際に解けたのでよかった。

E - Many Operations

xorが入っているのがかなり厄介そう。冷静になれば、ビット毎に考えればよかった。操作としてあるのは、0にする・1にする・01反転する・何もしない。これを累積和みたいに更新して保存していくだけだが。さすがにビット演算でやりたくて、0にするビットマップ、1にするビットマップ、他のビットマップが0のときに元のビットを反転するビットマップ、みたいにやろうとしたがかなり複雑。考え直すと、初期値が0のときと1のときにどうなるかという2通りを持てばいいだけだった。c = (~c & t0) | (c & t1); のようにしてCを更新しながら出力すればいい。

F - Sorting Color Balls

平衡二分探索木の何番目かわかるやつが欲しいと最初のころから思っていたが、実際欲しかった。各球について、左にある球で書かれている整数が自分より大きく自分と違う色であるものの個数がわかればいい（どういう順番で操作してもそのような球と入れ替えることは必要になるし、左から順に入れ替えていけばその回数で達成できる）。色関係なく大きいのを数えるのはBITで簡単なので、あとは同じ色で大きいのを数えることができればいい。multi_setで書き始めたけどだめなんだよなあ。なんとかできそうだと思ったので頑張って考えてついに見つけた。色毎にBITで同じことをやる。座標圧縮が必要だった（解説を見ると、BITを毎回逆操作すればN回ではなくその色の球の個数ぶんの回数でクリアできるので、そうすれば不要だった）。

G - Replace

読んだだけ。

Ex - Game on Graph

Gがわからず順位表を見てこちらに専念した。ゲーム木探索に見える。普通にミニマックスを書く。手番によって状況が異なるので、同じ手番で同じ場所に来たらINFを返す。再帰して得たスコアに辺の重みを足してそれらの最大値（後手番のときは最小値）をとる。合法手がないときは0を返す。サンプルが全く合わず時間を消費したが、木用のテンプレを貼って入力のループ回数（辺数）をN-1からMに書き換えるのを忘れていた（ひどすぎる）。直してコンテスト終了1分後に提出するがTLE。同じ場所を2回訪れるといっても、探索木の祖先と探索済みの場所とあるのを混同していた。なんか祖先しか見ないコードになっていたので、スコアをメモして探索済みならそれを返すようにしてAC。これはコンテスト中に取りたかったよ。後退解析思いつかないのもあれだし、ミニマックスの千日手の扱いに自信がない状態だったのも時間をかけることにつながった。30分あったから本当に通したかった。

（追記）嘘解法だった。


とりあえず下のケースで落ちる。自分の実装だと後からadd_edgeされたものから先に探索するので、「1 2 0」が「1 3 0」より後となるようにしてある。

5 7 1
1 3 0
1 2 0
2 1 0
2 4 0
3 4 0
4 3 0
4 5 0

経路依存のスコアは置換表に入れないとかの話はコンピュータ将棋で聞いたことあり考えたこともあったが全く思い出さなかった。何か工夫すればDFSでも解けるんか？経路依存のスコアをメモしないようにしたときの計算量もわからんし、ループしたときのスコアが1万とか中途半端だったときの計算量もわからない。

（追記2）解説を見てAC。とてつもなく大変だったしまだよくわかってない。まず、普通に後退解析しようとすると何も確定しない（高橋君にとってスコア1が最適なのにスコア0があるかもしれないから確定せずループ）。じゃあ、解説にあるように千日手でない局面だけ後退解析で確定させて、そしたら残りがDAGになってるかなと期待したらそうでもなかった。DAGでないならメモ化再帰でいいじゃんと思ったけど、経路依存のスコアを保存したら間違うし保存しなかったら時間がかかる。これでようやく解説の方法の必要性と具体的にどんな方法かがわかった。まさにダイクストラ法で、局面の最小スコアが更新されたら優先度付きキューに入れて小さい順に取り出せば、取り出した時点でそれより小さいスコアの局面は全て遷移済みかつこれから確定する局面のスコアは全てそれ以上なので、局面のスコアが確定する（詰みまでの手数などスコアが1ずつしか変わらないときはBFSが使えそう）。これでACはできたものの、ABC209Eもなんであれで引き分けがわかるのか、よくわかってない。まあ、今回の解説の後退解析でいうと、もしfiniteならあの手順で確定されないことはないってのは正しそうに思えるけど。