AtCoder Beginner Contest 176 D,E,F問題メモ

AtCoder Beginner Contest 176

仮眠TLEしました。 バチャやったら40分くらいで5完できたので出たかったなあ。

F問題は知りません。

D - Wizard in Maze

• $H \times W$ のグリッド
• '.' が通過可能で '#' が壁
• $(C_h,C_w)$ から $(D_h,D_w)$ まで、徒歩とワープを駆使して移動する
  • 徒歩は上下左右4方向に1マス移動できる
  • ワープは、現在地を中心とした $5 \times 5$ マスの好きな位置に移動できる
  • どちらの移動でもグリッドの外には出られない
• たどり着けるか判定し、たどり着けるならワープの最小回数を求めよ
• $1 \le H,W \le 1000$
• $(C_h,C_w)$ と $(D_h,D_w)$ は '.'

徒歩をコスト0、ワープをコスト1として、経路探索すればよい。

俗に言う01-BFS。
両端キュー（Doubly-Ended Queue, Deque）を使って、コスト0なら先頭に、コスト1なら末尾に追加していくと、 次に調べるノード（キューに入っている中で最も累計コストの小さいノード）は常に先頭から取り出してよくなる。

ただし今回は1箇所から遷移できるマスが25マスあり、ちょっとTLEが厳しそうなのでNumbaでの実装を選択。

Numbaにはcollection.dequeがまだ機能として無い。heapq ならあるので、代わりにそれを使ってDijkstraで実装した。
多少は遅くなるがNumbaによる恩恵と差し引きすると致命的なものでは無い。

NumbaでDequeを使うなら、メモリ効率は本家Dequeと比較して多少悪いが「十分な長さの配列 $q$」「左index $l$」「右index $r$」を管理すれば比較的楽に実装できる。
$[l,r)$ の範囲に意味のある値が入っているとする。

ただし、確保すべきサイズは「ある一時点でのDequeの最大サイズ」ではなく「全行程を通してDequeに挿入されうる要素数」なので、 結構大きめのものを作っておかないと配列外参照を引き起こす。

Dijkstraでは 838[ms] だったのが、この実装では 374[ms] にまで高速化された。
（ただ、適切なサイズの見積もりを誤るとREになるリスクがあるので、まぁDijkstraでいい気がする）

コード

E - Bomber

• $H \times W$ のグリッドに、爆破対象が $M$ 個配置されている
• $i$ 番目の爆破対象は $(h_i,w_i)$。同じマスに2個以上は無い
• 爆弾を1個置くと、ボンバーマンよろしく、その行と列のみに1直線に爆風が届く
• 爆弾は爆破対象のあるマスに置いてもよい
• 爆弾1個で、最大いくつの爆破対象に爆風を届かせられるか求めよ
• $1 \le H,W \le 3 \times 10^5$
• $1 \le M \le 3 \times 10^5$

一番爆破対象の多い行と、一番爆破対象の多い列から、それぞれ1つずつ選んでその交点に置くのがよい。

(1行の個数の最大値 + 1列の個数の最大値) が答えとなる、、、のだが、交点に爆破対象があった場合、行でも列でも数えられているので1減らす必要がある。

つまり、爆破対象の最大値を達成する行・列の組み合わせで、交点に爆破対象が無いものが1つでもあるならそこを選び、無ければ仕方ないので1減らしたものが答えとなる。

    v  v    v      v,>: 最大値を達成する行・列
  +-----------      o : 爆破対象
> | o  o    o
  |    o
> | o  o    o
> | o    o  o
       ^ ここに置けばよい

しかし、たとえば対角線上に一列に爆破対象が置かれている場合、全ての行・列が「爆破対象の最大値(=1)を達成する行・列」となってしまう。

この組み合わせ数は $(3 \times 10^5)^2$ にも上り、全てチェックするのはとうてい無理。 別の判定方法が必要となる。

爆破対象の上限が $3 \times 10^5$ で抑えられているので、そちらの方からチェックする。
最大値を達成する行数を $M_H$、列数を $M_W$ とすると、両者の交点が全て爆破対象で埋まっていたなら、その個数は $M_h M_w$ である。

なので、そのような爆破対象の個数を数え、$M_h M_w$ より少ないなら爆破対象の無い交点が存在することになる。

もしくは、単純に全ての組み合わせを調べてもよかった。
$3 \times 10^5 + 1$ 個調べるまでには必ず交点に爆破対象がないマスが現れる。

「探索候補は多いけど、1つでも条件に当てはまるものが見つかったらよくて、条件に当てはまらないものは限られている」場合に愚直に探索すればよいのを忘れるの、結構繰り返してる。

F - Brave CHAIN

• $1～N$ の整数が3つずつある長さ $3N$ の数列 $A_1,A_2,...,A_{3N}$ が与えられる
• 以下のゲームを行う
  • $N-1$ 回、以下の操作を行う
    • $A$ の先頭5要素を好きな順に並べる
    • $A$ の先頭3文字を取り除く。この時、その3文字が全て同じなら1点を得る
  • 最後に3文字残るが、これも全て同じなら1点を得る
• 得られる最高得点を求めよ
• $1 \le N \le 2000$

3番目が早く出てくる数字から貪欲に確定したらいいのかなーと思ったけど、そうでもない。

解説を見ると、想定解としては5文字中の残す2文字の組で動的計画法を行うというもの。ただし遷移が結構ややこしい。

• $DP[i][b_0][b_1]=i$ 回目の操作後、残している2文字の組が $(b_0,b_1)$ の時の最高得点

• 補筆
  • 参照や遷移の2度手間を防ぐため $b_0 \le b_1$ とする
    • ただし、以下の説明では冗長になるため特に順序は気にしないで書いている
  • 実現可能不可能を区別するため、初期値は不可能を示す -1 等で埋めておく

操作対象には、1回目の5文字以降は3文字ずつ加えられる形となる。
便宜的に「0回目の操作」を先頭2文字を特に何もせず残す操作とすると、1回目の操作も同様に考えられる。

0回目  [1 1] 2 2 3  3 4 4  4 3 2  1
1回目  [1 1  2 2 3] 3 4 4  4 3 2  1
2回目         [? ?  3 4 4] 4 3 2  1
3回目                [? ?  4 3 2] 1

上記のDPをそのままやろうとすると、$i=0～N-1$、$b_0,b_1=1～N$ なので $O(N^3)$ となり、間に合わない。

しかし、よく考えると、新規に加えられる3文字（$a_0,a_1,a_2$ とする）に関わらない $(b_0,b_1)$ は、$i→i+1$ へ値がそのまま継承される。 （要は、新しい3文字をそのまま捨てることを意味するので）

よって、1回の更新で $b_0,b_1$ の組を全更新する必要は無く、以下の2パターンの箇所だけ更新すればよい。

• 引き継いできて残す文字1文字と $a_0,a_1,a_2$ から1文字
• $a_0,a_1,a_2$ から2文字

前者は $O(N)$、後者は $O(1)$ で更新でき、これを $i=0～N-1$ に対して行っても全体で $O(N^2)$ に抑えられる。

$DP[i]$ の更新には $DP[i-1]$ の情報があれば十分で、値がそのまま引き継がれる箇所も多い。
従って、実装上は2次元の $DP[b_0][b_1]$ を順次更新していくものとする。
（説明上は混乱を防ぐため $i$ の次元を残す）

また、遷移で必要になるため、以下も管理しておく。

• $DP_{max}[i][b]=DP[i][b_0][b_1]$ のうち、$b_0,b_1$ のいずれかが $b$ であるものの最大値

これは、$DP$ で $b_0,b_1$ のいずれかが $b$ である箇所を更新したときに、同時に更新しておけばよい。
これも、実際は $i$ の次元を省略して1次元配列で順次更新する。

$a_0,a_1,a_2$ の構成によって、3通りに分かれる。

「$←$」は、chmax（大きければ更新）を意味する。

全て同じ場合、その3文字を捨てて $b_0,b_1$ をそのまま引き継ぐのがよい。

この場合のみ、全ての（その時にあり得る）$b_0,b_1$ について値が1ずつ加算され、更新に $O(N^2)$ かかってしまう。

ただ、このパターンは今までにどういう操作をしていようと状態が変化せず一律に1点を得られるので、 このパターンで加算される得点は別の変数で持っておき、最後に合計すればよい。

DP配列は触らなくてよい。

$a_0 = a_1 \neq a_2$ とする。他の場合も適当に読み替える。

大まかに以下の2つの遷移がある。

• 引き継いできた文字から1文字、$a_0～a_2$ から1文字を残す
  • 残す文字が $a_2$ の場合、引き継いできた1文字と $a_0,a_1$ で1点が得られる可能性がある
• $a_0～a_2$ から2文字残す
  • 残す文字が $a_0,a_1$ の場合、引き継いできた2文字と $a_2$ で1点が得られる可能性がある

前者の遷移は、引き継いできて残す1文字 $b=1～N$ につき、

• $DP[i][a_0][b]←DP_{max}[i-1][b]$
• $DP[i][a_2][b]←DP_{max}[i-1][b]$

また、1点が得られるときの遷移は以下のようになる。

• 各 $b$ につき、$DP[i-1][a_0][b] \neq -1$（ここまでに $(a_0,b)$ を残すことが可能）な場合のみ
  • $DP[i][a_2][b]←DP[a_0][b]+1$

後者の遷移は、全ての $DP[i-1]$ の最大値を $M$ として、

• $DP[i][a_0][a_0]←M$
• $DP[i][a_0][a_2]←M$

また、1点が得られるときの遷移は以下のようになる。

• $DP[i-1][a_2][a_2] \neq -1$ の場合のみ
  • $DP[i][a_0][a_0]←DP[i-1][a_2][a_2]+1$

大まかに以下の2つの遷移がある。

• 引き継いできた文字から1文字、$a_0～a_2$ から1文字を残す
  • 得点を得られる可能性は無い
• $a_0～a_2$ から2文字残す
  • $a_0～a_2$ で捨てる1文字と、引き継いできた2文字で1点が得られる可能性がある

前者の遷移は、引き継いできて残す1文字 $b=1～N$ につき、

• $DP[i][a_0][b]←DP_{max}[i-1][b]$
• $DP[i][a_1][b]←DP_{max}[i-1][b]$
• $DP[i][a_2][b]←DP_{max}[i-1][b]$

後者の遷移は、全ての $DP[i-1]$ の最大値を $M$ として、

• $DP[i][a_0][a_1]←M$
• $DP[i][a_0][a_2]←M$
• $DP[i][a_1][a_2]←M$

また、1点が得られるときの遷移は、$a_0～a_2$ で捨てる1文字を $p$、他を $q,r$ として以下のようになる。（3通り）

• $DP[i-1][p][p] \neq -1$ の場合のみ
  • $DP[i][q][r]←DP[i-1][p][p]+1$

今回、何が難しかったかというと（もちろんDPで一部のみ更新という発想もそうだが）、更新の順序。

DP配列を破壊的に更新していくことが強く想定される解法なのに、 更新の順序によっては「$DP[i-1]$ の値を参照しなくてはいけないのに、$i$ 回目の他の遷移で既に $DP[i]$ に更新されてしまっている」可能性がある。

これは、その場で更新するのでは無く、リストに「今回で更新するべき $b_0,b_1$ とその値」を溜めていき、最後にまとめて更新を行う、という方法が楽だった。

更新順を気にしなくていいし、あり得る遷移をただ列挙して放り込んでいけばよいので、複雑な破壊的更新DPには使えそう。
また、今回、$DP$ の更新と同時に $DP_{max}$ も更新する必要があったので、その記述も1箇所にまとめられてスッキリした。

ただ、もし適切な順序で更新すれば誤った値の参照を避けられるならば、タプル生成などがない分その方が当然高速。 ¹⁾

また、もしほとんど全ての箇所が更新されうる（そのような遷移でも間に合う制約である）場合は、 DP配列を各段階の最初にまるっとコピーして新旧分けちゃう方法がある。（旧を参照し、新を更新する）

リストに溜めるのは、今回のように毎回コピーしてたらTLEになるDPに対して特に有効かな。