大和証券プログラミングコンテスト2021(AtCoder Regular Contest 128)
なんでダイワ証券なんだ……?
具体的な金と銀の重量を持ってDP、でも理論上できるのだが、 重量の桁数がとんでもないことになるので計算誤差がつきまとう。
よく考えると、未来がわかっている投資なので具体的な重量を持たなくても最適な行動は決まっている。
直感的にわかりやすくするため銀を日本円と考えると、$A_i$ は金の価格となる。
この通りにするといい。(さすが証券会社スポンサード)
最終的に円をいくら持っていても意味が無いので、そのような事態になる場合だけ少し気になる。
最終日の行動決定前に円を持っている状態になるのは、$N-1$ 日目→$N$ 日目で金の価格が下がる時。
その場合、$N-1$ 日目(以前)で買うより $N$ 日目で買った方がいいので、単純に「最終日に円を持っていたら全部金に交換する」でよいことが確認できる。
とれる操作は3種類で、それぞれの回数が同じならどの順でやっても結果は変わらない。
仮に最終的に全てのボールが赤(R)になるとする。
「緑(G)と青(B)を選んで2個の赤(R)に変える」という操作を最後に持ってくると、 それを行う前は $G$ と $B$ は同じ個数でないといけない。
するとそれ以外の「$R,G→2B$」「$R,B→2G$」という操作で $G$ と $B$ をそろえられるか、という話になる。
これは、$G,B$ の個数だけに着目すると1回の操作で差が3ずつ縮まる。(広げることもできるが意味は無い)
よって、初期状態で $G$ と $B$ の差が $3$ の倍数であるかどうかが必要十分条件となる。
その場合、たとえば大きい方が $G$ だったとすると、
どちらの操作でも $G$ は1ずつ減ることになるので、最低回数は $G$ 回である。
まとめると、
これを、3色それぞれについて調べればよい。
なんとなくDPで解けそうだが、どこから遷移できるか(できなくなるか)がややトリッキー。
DPの定義として以下のようなものを考えてみる。
$DP[i]$ への遷移を考えるとき、「最終的な並びの中で $i$ の1つ前として可能なボール」から遷移できる。
遷移元を $j$ とすると、「$j~i$ 間(両端除く)のボールは上手くやれば全て消せる」ことが条件となる。
i 1 2 3 4 5 6 7 8 9 10 11 Ai 3 1 4 4 1 2 5 2 5 2 6 DP 1 1 初期値 DP[3] 2 i=1,2から遷移可能 DP[4] 2 i=3は消せないので、i=3のみから遷移可能 DP[5] 2 i=4は消せないので、i=4のみから遷移可能 DP[6] 4 i=4,5から遷移可能 DP[7] 8 i=4,5,6から遷移可能 DP[8] 16 i=4,5,6,7から遷移可能 DP[9] 28 i=4,5, 7,8から遷移可能 DP[10] 48 i=4,5, 8,9から遷移可能 DP[11] 108 i=4,5,6,7,8,9,10から遷移可能
たとえば $DP[3]$ だと、$i=1$ からの遷移が [3,4]
、$i=2$ からの遷移が [3,1,4]
を意味する。
ほとんどの場合で遷移可能だが、どうも以下の性質があるっぽい。
2 5 2 5 …
のように2つの数字が交互に繰り返されている場所では、2 5 2 5 2 6
のように繰り返しが終わったら 6
へは繰り返しを含めた全てから遷移可能になる①はまぁ、同じ数字の連続は消せない→消せないボールを挟んでは遷移できないと考えるとわかりやすい。
②は、例えば上記の例で $DP[10]$ を求めるときに、仮に $DP[6]$ から遷移したければ、
i 1 2 3 4 5 6 7 8 9 10 Ai 3 1 4 4 1 2 5 2 5 2 o o ←これとこれを残しつつ ~~~~~~~ ←こいつらを消さないといけない
が、この間のどの3つ並んだボール $x,y,z$ も $A_x=A_z$ なので、1回操作すると同じ数が新たに隣り合うことになってしまう。するともう $x,z$ は消せない。
つまり2つの数字が交互に繰り返される部分だけでは、初期状態で隣り合っていたボールをともに消すことは出来ない。
上の例では $i=8$ も $i=9$ も両方除くというのは不可能。
$i=9$ を除いた場合→$DP[8]$、除かない場合→$DP[9]$ から遷移できるので、直前2つからのみの遷移となることがわかる。
ただし、2つの数字が繰り返される箇所以外を含む、例えば $DP[5]$ からは可能である。
あくまで、「2つの数字が交互に繰り返される部分だけ」しかない場合に不可能となる。
i 1 2 3 4 5 6 7 8 9 10 Ai 3 1 4 4 1 2 5 2 5 2 o o ~~~~~~~~~~ 左から順に消していけばできる
従って、繰り返しが終わって $DP[11]$ のように別の数字になった際も、右から消していくことが可能となる。
i 1 2 3 4 5 6 7 8 9 10 11 Ai 3 1 4 4 1 2 5 2 5 2 6 o o ~~~~~~~~~~
まとめると、$DP[i]$ は、
i 1 2 3 4 5 6 7 8 9 [10] 11 Ai 3 1 4 4 1 2 5 2 5 2 6 DP[10]を求めるには |----------------| ここの和から |xxxx| ここの和を引く
これはどちらも連続している区間の和なので、累積和の形でDPを計算していくと、$O(N)$ で求められる。