目次
大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）A,B,D問題メモ
大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）
なんでダイワ証券なんだ……？
A - Gold and Silver
問題
- 金1g、銀0gを持っている
- これから $N$ 日間の金銀交換レート $A_1,A_2,...,A_N$ がわかっている
- 各日につき「交換する」か「何もしない」か選べる
- 交換する場合、その日の交換レートが $A_i$ とすると、以下の行動を取る
- 金を $x$ g持っていたら全てを銀 $x \times A_i$ gに交換する
- 銀を $x$ g持っていたら全てを金 $x / A_i$ gに交換する
- 最終的に持っている金の重量を最大化できるような各日の行動の一例を求めよ
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
解法
具体的な金と銀の重量を持ってDP、でも理論上できるのだが、 重量の桁数がとんでもないことになるので計算誤差がつきまとう。
よく考えると、未来がわかっている投資なので具体的な重量を持たなくても最適な行動は決まっている。
直感的にわかりやすくするため銀を日本円と考えると、$A_i$ は金の価格となる。
- 金を持った状態で、翌日に金の価格が上がるなら何もしない
- 金を持った状態で、翌日に金の価格が下がるなら売る（交換する）
- 円を持った状態で、翌日に金の価格が上がるなら買う（交換する）
- 円を持った状態で、翌日に金の価格が下がるなら何もしない
この通りにするといい。（さすが証券会社スポンサード）
最終的に円をいくら持っていても意味が無いので、そのような事態になる場合だけ少し気になる。
最終日の行動決定前に円を持っている状態になるのは、$N-1$ 日目→$N$ 日目で金の価格が下がる時。
その場合、$N-1$ 日目（以前）で買うより $N$ 日目で買った方がいいので、単純に「最終日に円を持っていたら全部金に交換する」でよいことが確認できる。
B - Balls of Three Colors
問題
- 赤、緑、青のボールが $R,G,B$ 個ある
- 以下の操作を何回でも繰り返せる
- 色が異なる2つのボールを選び、両方ともそのどちらでもないもう1色に塗り替える
- 最終的に全てを同じ色にできるか判定し、可能なら最小回数を求めよ
- 1つの入力に $T$ ケースあるので、全てについて答えよ
- $1 \le T \le 100$
- $1 \le R,G,B \le 10^8$
解法
とれる操作は3種類で、それぞれの回数が同じならどの順でやっても結果は変わらない。
仮に最終的に全てのボールが赤(R)になるとする。
「緑(G)と青(B)を選んで2個の赤(R)に変える」という操作を最後に持ってくると、 それを行う前は $G$ と $B$ は同じ個数でないといけない。
するとそれ以外の「$R,G→2B$」「$R,B→2G$」という操作で $G$ と $B$ をそろえられるか、という話になる。
これは、$G,B$ の個数だけに着目すると1回の操作で差が3ずつ縮まる。（広げることもできるが意味は無い）
よって、初期状態で $G$ と $B$ の差が $3$ の倍数であるかどうかが必要十分条件となる。
その場合、たとえば大きい方が $G$ だったとすると、
- 「$R,G→2B$」の操作を何回か行って $G,B$ をそろえる
- そこから「$G,B→2R$」を $G,B$ が0になるまでおこなう
どちらの操作でも $G$ は1ずつ減ることになるので、最低回数は $G$ 回である。
まとめると、
- 最終的に揃えたい色以外の2色の個数を $X,Y$ とする
- $X,Y$ の差が3の倍数であれば可能で、$\max(X,Y)$ 回かかる
これを、3色それぞれについて調べればよい。
D - Neq Neq
問題
- $N$ 個のボールが横一列に並び、$i$ 番目のボールには整数 $A_i$ が書かれている
- 以下の操作を何回でも行える
- $A_x \neq A_y$ かつ $A_y \neq A_z$ である隣り合ったボール $x,y,z$ を選び、$y$ を取り除く
- 次回の操作以降、$x$ と $z$ は隣り合っていると見なす
- 最終的に残るボールの並びとしてあり得るものの個数を、$\mod{998244353}$ で求めよ
- 書かれている整数が同じでもボールが異なる並びは区別する
- $2 \le N \le 2 \times 10^5$
解法
なんとなくDPで解けそうだが、どこから遷移できるか（できなくなるか）がややトリッキー。
DPの定義として以下のようなものを考えてみる。
- $DP[i]=1～i$ 番目のボールだけで同じ問題を考えたときの答え
$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] を意味する。
ほとんどの場合で遷移可能だが、どうも以下の性質があるっぽい。
- ①$A_{i-1}$ と $A_i$ が同じ数字だと、
- $DP[i]$ は $DP[i-1]$ からしか遷移できない
- $DP[i+1]$ 以降の全ては、$DP[i-1]$ 以前の全てから遷移不可能
- ②
2 5 2 5 …のように2つの数字が交互に繰り返されている場所では、- 繰り返し部分について、直前の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]$ は、
- 基本は (直前に同じ数字が2つ連続した箇所) ～ $i-1$ の $DP$ の和
- 2つの数字の交互繰り返しが3つ以上連続する箇所は、(繰り返しの開始) ～ $i-3$ の値は除く
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)$ で求められる。
