ABC283E- Don't Isolate Elementsをrubyで解く
レートも落ちるし宅建も落ちたし簿記も落ちそうだし落ちないのは体重だけよぉぉぉぉ！(ダメ人間)
今回の問題はこちらです
計算量を落とすための枝刈りの考え方
以下、行に対して「操作」をすることを「裏返す」と呼びます。
まず同じ行を二回裏返すと元に戻ってしまうため、どの行も「操作なしで表のままか」「一回だけ裏返すか」の二通りしかないことがわかります。つまりパターン数は2^H(最大1000)です。こ無ゾ。
ここで偉い人のツイートを見返してみましょう。
DP設計のコツ2つ
緑以下でDPが得意な人は多分いないと思います。
私としてもコツがあるならこっちが聞きてーよと言いたい所ですが、二年近く競プロやった現在は結局「同じ事」になるルートは合流させて考える事で計算量を落とすと考えています。部分和問題は「『ここまでの数字を足すか足さないかしてできる合計数』だけを覚えておき、『どの数字を足したか』は忘れる。1+2と1+1+1は合流」、期待値DP問題は「このマスに来るまでの期待値を覚えておき、どの経路を通ったかは忘れる。A→CとA→B→Cの期待値は合計して合流」です。経路復元問題とか知りません。
まあ「同じ事になるルートは合流させる」は何の解決にもなってません。難しい部分を「同じ事って何だよ(哲学)」「合流って何だよ(哲学)」に押し込んだだけだからです。そこで第2のコツですが合流では逆転不可のルートを見捨てる事が多いと考えるとひらめきやすいです。(部分和は普通にまとめる、期待値は合計するという風に例外も多いのですが)
最高得点(または最低コスト)が欲しい場合、途中経過時点で同じ状況なのにそこまでの最高得点(またはそこまでの最低コスト)が得られていないのならそこからはもう逆転不可能です。よって途中経過時点の最高得点(最低コスト)のみを考え、それ以外は「合流という名の計算打ち切り」です。ナップザック問題は「ここまでのアイテムを選ぶか捨てるかした時点で、ナップザックの埋まり方が同じ事になっていれば合流。埋まり方ごとに最高得点だけを残してそれ以外は打ち切り」、蛙飛び問題(atcoderのeducational DP contestのA問題)は「同じマスまで進んでいれば合流。最低コストだけ残してそれ以外は打ち切り」です。
2つのコツを今回の問題に当てはめると
今回の問題で行を上から一個ずつ見ていく時、表のままか裏返すかの決め方は「今の行の一行上で孤立マスが出ないように」だけだという事がわかります。厳密には「今の行、一行上の行、二行上の行を見比べて、今の行が表のままでも一行上で孤立マスが出ないか、今の行を裏返したらどうか」です。
つまり今回における「同じ事」とは「一行上と二行上のそれぞれのオモテウラが同じ」 であり、また最低コストだけを残してそれ以外の計算を打ち切る事で合流です。
回答
擬似コード
- dpのために記憶しておくのは「二行上が表、一行上が表」「二行上が表、一行上が裏」「二行上が裏、一行上が表」「二行上が裏、一行上が裏」の４パターンの最低コスト。回答コード20行目。
- 入力された盤面を三列ずつに区切り、「二行上のオモテウラ」「一行上のオモテウラ」「現在のオモテウラ」の合計8通りについて確認。回答コード23~27行目。
- 「二行上のオモテウラ」「一行上のオモテウラ」に持ち込むまでの最低コスト確認。回答コード28行目。
- 「二行上のオモテウラ」「一行上のオモテウラ」がそもそも不可能なパターンだったり、「現在のオモテウラ」と突き合わせて一行上に孤立マスが出来てしまうならば早期リターン。回答コード29行目。
- 3で計算したコストに「現在のオモテウラ」のコストを足し、「一行上のオモテウラ、現在のオモテウラ」が未記録または大きいコストの場合は合流して2に戻る。回答コード31~37行目。
- 8パターンとも計算し終わった後、どうあがいても不可能だった場合は早期リターン。まだ可能性が残っている場合は1に戻る。回答コード39~40行目。
回答コードは表がtrue、裏がfalseになっているので注意してください。ruby以外の言語だとtrueが1でfalseが0なので裏をtrueにした方が直感的に数えやすかったかもしれません。
また回答コード17~18行目で最上段と最下段に空配列を入れています。これを入れないと盤面として入力されたすべての行をeach_consの真ん中に持ってきて孤立を吟味する事ができません。dpの初期値を見てもらうとわかりやすいですが、空配列にまでオモテウラを検討してしまっていますね……。
今回学んだ事
- timesとall?は併用できる(内部的に早期リターンしてるのかは不明)。
- each_consで配列の要素を複数ずつ取れる。
- DPはライブラリを用意しておく事が難しい。実装量がデタラメに多い問題があるので、思いついたら最速で実装する。迷ってたら間に合わない。
Discussion