AGC030 B - Tree Burning

今回は私自身がAB2完で実質的にこの1問しか解説を書けないのと、この1問だけでかなり説明が長くなりそうなので、単独記事にします。

Twitter見ていると微妙に色々違う解法があるようで…？私が本番で考察した内容をベースに書きます。他の人が書いていることとズレがあるかもしれないので、そこはご注意ください。

はじめに

以降の説明で使う方向を定義しておきます。高橋くんの家を円の上側に置き、問題文の座標と同じ反時計回りの向きを「左」、その逆向きを「右」とします。

また説明を簡単にするため、与えられる木の座標値 $X_{i}$ とは別に、座標の測り方を逆にして、逆向きに回った時に $j$ 番目にある木の座標値 $Y_{j}$ を定義しておきます。これらは同じ木をどちら側から訪れるかによって2通りの座標値を付けているだけであることに注意してください。

具体的には $Y_{N+1-i} = L - X_{i}$ で計算できます。 $X_{i}$ も $Y_{j}$ も木の位置を1-indexedで扱い、 $X_{0} = Y_{0} = 0$ としておきます。

f:id:betrue12:20181230210016p:plain

部分点解法

まず部分点ですが、DPをします。「家から左に $i$ 本、右に $j$ 本の木を訪問済みで、最後に訪れたのが左側の木なら $k=0$ 、右側の木なら $k=1$ であるときの最大移動距離」を $dp \lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ とします。

このようにDPの状態を定義すると、左右合計で $N$ 本の木を訪れた時点で終わりなので、 $dp\lbrack i \rbrack\lbrack N-i \rbrack\lbrack k \rbrack$ を $i=0, ..., N$ および $k = 0, 1$ の範囲で全て求めたもののの最大値が答えになります。家の座標を $X_{0} = Y_{0} = 0$ としているので、初期条件は $dp\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack k \rbrack = 0$ です。

遷移を考えます。 $dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 0 \rbrack$ は左に $i$ 本、右に $j$ 本の木を訪問済みで、最後に左側 $X_{i}$ の木を訪れている状態です。ここからは2通りの移動ができて、

さらに左に進み、 $X_{i+1}$ の木を訪れる。加算される移動距離は $X_{i+1} - X_{i}$ で、 $dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack 0 \rbrack$ に遷移する。
向きを変えて右に進み、 $Y_{j+1}$ の木を訪れる。加算される移動距離は $X_{i} + Y_{j+1}$ で、 $dp\lbrack i \rbrack\lbrack j+1 \rbrack\lbrack 1 \rbrack$ に遷移する。

という遷移になります。

f:id:betrue12:20181230211600p:plain

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 1 \rbrack$ からの遷移も同様に考えることができます。このDPを回すと $O(N^{2})$ で計算が終わり、部分点を取ることができます。

部分点獲得コード

（配るDP）Submission #3900997 - AtCoder Grand Contest 030
（貰うDP）Submission #3893900 - AtCoder Grand Contest 030

DPの実装における違いとして、いわゆる「貰うDP/配るDP」というものがあります。本番中の実装は「貰うDP」でしたが、「配るDP」のほうが文章化しやすかったので今回の説明は「配るDP」で書いています。この問題はどちらで解いても大差ないです。

あと、 $dp\lbrack N \rbrack\lbrack N \rbrack\lbrack k \rbrack$ とか実際に要らないところまで回してしまっているのですが、まあ計算時間が約2倍になるだけで十分間に合うので…添字の演算を増やしてつまらないバグを混入させたくないので、私はコンテスト本番だとこういう実装をたまにやります。