まず、$i=1$ の時は $A_1 \times B_1$ しかない。
次に $C_{i-1}$ までが求まっているとして、$C_i$ を考える。
$B_i$ を使うか使わないかで分けて考えると、
この2つを比較して、大きい方を $C_i$ とすればよい。
例えば $0,1,2$ が入って $3$ が入っていない箱があったら、後はどれだけ大きい数字を入れようとその箱のMEXは $3$ である。
次のようにイメージするとよい。
ボールを値別にカウントした状態 ai 5: oooooooo 4: 3: ooo 2: ooooooooooo 1: ooooo 0: oooooooo
ここで、同じ値のボールを1つの箱に入れたり、たとえば3を0,1,2の入っていない箱に入れるのは無駄。
よって、値ごとに左詰にして、縦の1列が1つの箱に入れるボールと考えて問題ない。
すると、MEXを大きくするのに意味のあるボールは結局、小さい方から最小値をとっていった以下のようになる。
5: 4: 3: ooo 2: ooooo 1: ooooo 0: oooooooo
以下の手順を実装するとよい。
'R','D','X
' を書き込むDPだけど、通らない空白マスは何でもよい、というのをどう扱うか。
まず、'R','D' などの変な制約のない経路数を求める時の定石として、上と左を足していく以下のDPはよく使われる。
これを踏まえて今回の制約を含めて経路数を考える。例えば右移動を考える(下移動も同様に考えられる)。
なんとなくのイメージとして、以下のようなことを行えばうまくいきそう。
■遷移元の文字が明らかなとき: 移動できるならそのまま, 移動できないなら0。
遷移元のマス 文字/経路数 R/20 → 20 D/20 → 0 X/20 → 20
■遷移元が空白の時、右に移動できるのは'R','X'の2文字なので、2倍して遷移。(下移動も同様)
_/20 → 40
しかし、このままでは「ある経路において通過しなかった空白マスは、何の文字でもよい」ことが考慮されていない。
答えに反映する際には経路数を $3^{通らなかった空白マス数}$ 倍する必要がある。
だが通過しなかった空白マス数は経路によって異なる一方、上記のDPではいろんな経路が混ざってしまっているので、うまく求められない。
逆に、答えとなる値を直接求めるようなDPを組むとよい。つまり、以下のDPを定義する。
$DP[1][1]=3^{HW-K}$ としておく。
遷移元の文字が明らかなときはさっきと一緒。
遷移元が空白の時、その遷移ができる文字の種類数は $3→2$ になるので、$2/3$ 倍して遷移する。
_/60 → 40
こうすると、うまく求められる。
$\mod{}$ が素数なので、$3^{-1} \times 2$ はあらかじめ求めておくとよい。
ひらめき系? 構築方法自体は何かの過去問にあったような気もする。
条件は2つあるが、「全操作回数 ー 同じグループに入った回数 = 違うグループに入った回数」なので、 一方が満たされればもう一方も満たされるので、実質1個と考えてよい。
操作回数の下限を考える。
以下のような表で同じグループに入った回数を数えることを考えると
i\j 1 2 3 4 1 - 2 - - 3 - - - 4 - - - -
これは、$C(2^{N-1}-1) = D(2^N-1)$ で一致することとなる。
逆に、$2^N-1$ と $2^{N-1}-1$ の最大公約数は必ず1なので(ユークリッド互除法の最初の1手を考えるなど)、これ以上は小さくならない。
よって、少なくとも操作は $2^N-1$ 回は行われないと全てのペアを同数にできない。
これはあくまで下限なので、うまい振り分け方が無くて実際はもっとかかるかもしれないが、 もし $2^N-1$ 回でできるとしたら、同じグループに入る回数は $2^{N-1}-1$ 回、違うグループは $2^{N-1}$ 回ということになる。
どうせできるやろと当たりをつけて考えを進める。
$N$ の答えを求めるにあたり、$N-1$ の答えは、半数の人のグループ関係については条件を満たしているので、これをうまく使いたい。
$N=2$ の答えがある。(見やすさのため、$A=0,B=1$ とおく)
1 2 3 4 ------- 0 0 1 1 0 1 0 1 0 1 1 0
$N=3$ の答えを7回の操作で実現したい。とりあえず最初の3回について横に並べてみる。
1 2 3 4 5 6 7 8 ---------------- 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0
こうすると、
2,3,4についても同じことがいえ、残る問題は、1と5、2と6、などのペアについての回数が多くなっていることとなる。
7回中、同じグループに入るのは3回。つまり1と5などは、これ以上同じグループに入らない。
ここで、1と5、2と6などがこれ以上同グループにならないようにすることを考えると、 「$5~8$ については0,1をまるっと反転させた結果を横に並べた」のを追加するとよさそう。
1 2 3 4 5 6 7 8 ---------------- 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 NEW 0 1 0 1 1 0 1 0 NEW 0 1 1 0 1 0 0 1 NEW
ひとまず1を中心に考える。
$N=2$ の時に、1と、2,3,4の関係は、同グループが1回、違うグループが2回だった。
つまり、$N=3$ の時に上の図で1と6,7,8との関係は、反転してないのとしたのを合わせるとちょうど目標の3回となる。
また、1と5についても前述のように同グループとなる規定回数を満たしている。
残るは、1,2,3,4について同グループとなった回数が1回ずつ少ないことなので、それを追加すると、どのペアとも3回ずつとなる。
1 2 3 4 5 6 7 8 ---------------- 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 NEW
今、1と同グループになる回数をもとに説明したが、対称性があり、2,3,4についても同じことがいえる。
(問題文の条件違反ではあるが)全ての人が同グループになる仮想的な操作を追加すると、
1 2 3 4 ------- 0 0 0 0 ← 0 0 1 1 0 1 0 1 0 1 1 0
これを田の字に並べ、右下だけ反転したもの(の最初の1行を無視したもの)が、次の答えとなる。
1 2 3 4 5 6 7 8 ---------------- 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1
仮想的な操作の追加により、全てのペアについて同グループになった回数も、違うグループになった回数も $2^{N-1}$ 回で揃うので、 反転させたもの、反転させないものを繋げた時、各ペアにつき同じグループに属した回数がそれぞれ2倍になることが少しだけイメージしやすくなる、かも。
このように生成される行列は、アダマール行列と名前が付いていて、任意の2行が互いに垂直になるなどの性質があるらしい。
解説AC。区間DPで解ける。
大まかには美味しいキャンディから取っていくのがよさそうだが、それでは上手くいかない例が入力例1で(優しいことに)紹介されている。
4 3 1 🐜 2 1000 2000 3000
この例では、初手で1を取るのが最適となる。
うかうか3000などを取っていると蟻は2→1000→2000とどんどん美味しいキャンディの方に浸食してきてしまうが、
1を取ることで蟻は3→4の方向に誘導され、2の壁によって美味しいキャンディが後回しになる。
このような現象は初手にのみ起こるわけでも無く、途中で何度でも起こりうる。
また、蟻に隣接するもののみ考えていればいいわけでも無く、「あらかじめある範囲をまとめてごそっと取り除いておく」必要があるケースも考え得る。
N=20 11 10 9 8 7 3 6 2 1 5 🐜 4 1000 2000 3000 4000 5000 6000 7000 8000 9000
この例とか、何も対策しないと蟻は2ターン目に4の壁を突破して、以降は大きい数の取り合いとなり1000~3000は蟻に取られてしまうが、 まず1,2,3を取り除いてやることで、蟻は7→8→…の方に誘導され、人は大きい方から7つを悠々と取ることができる。
この「蟻がまだ4,5あたりにいる段階から、1,2,3を選んで取り除き始める」ことを予見するのはなかなか難しそうに思える。
また、蟻を誘導するためには何個か小さい数字を取ることになるので、その差し引きが、最大から貪欲した場合より得なのか損なのか変わってくる。
さらに、右側を堰き止めて、ある程度右側で大きい数字を取り尽くしたら、堰き止めてたやつを取って、今度は左で堰き止めて……という戦略もあり、
「どこで堰き止めるか」などを固定するような方法は、ちょっと切りが無さそう。
以下の事実を利用すると
なので、実際に蟻の行動範囲を管理などして、1,2あたりに到達したときに、「1,2を取った場合の最終値」と「無視して大きい方から取った最終値」の比較ができると、DPが組めそう。
ただ、十分準備ができないまま蟻が来てしまう場合もある。蟻がそこに到達するまでに、本当に取り除けるのか、位置関係によって変わってくる。
11 10 9 8 7 4 3 2 1 6 🐜 5 1000 2000 3000 4000 5000 6000 7000 8000 9000 5を取られる前に1,2,3,4を取り除くと蟻は7,8,...の方に誘導されるが、 実際には全部取り除くには間に合わず、どうしても5を先に取られてしまう。 (なのでこの場合は、大きい方から取っていくのがよい)
実際に取るのでは無く、「取る権利を1ターンごとにもらう」と考えると上手くいく。
両端に $a_0=0,a_{N+1}=0$ を番兵として追加しておくとよい。
たとえば、最初の例では、以下の3通りの選択肢がある。
l r i 0 1 2 3 4 5 6 7 8 (0) 4 3 1 🐜 2 1000 2000 3000 (0)
ただし、$←$ はMAXで更新する操作とする。
$k=0$ の時は取ることはできないので、何もしない操作のみとなる。
$DP[l][r]$ を求める際には、より外側に範囲を拡張させた $DP[l-1][r]$ や $DP[l][r+1]$ が埋まっている必要がある。
つまり、$r-l$ の大きい方から順に埋めていくとよい。
$r-l=1$ まで埋めたら、$i=0~N$ につき、$DP[i][i+1][1]$ が答えとなる。(人からターンが始まるので、最初に取る権利は1個存在している)
まるで別の解法というわけではないが、以下の入力で、
2 1 1000
以下の結果を返すコードが通ってしまった。(本当は最初も当然1000)
1 1000 1000
どうも、「最大まで取れる権利を貯めてから、一気に使う」ようなケースが見逃されているらしい。
DP配列で、取る権利の残数 $k$ は、取る権利をためて意味のある $\dfrac{N}{2}$(切り上げ)個まで考慮すればよいはずと考えた。
この値を $lim$ とすると、配列外参照をしないためには、$DP[l][r][lim]$ の更新をどうすればよいか。
「$lim$ まで貯まったんなら、必ず消費する必要があるだろう」と誤った考えを元に、必ず $l,r$ のいずれかを取る、というコードを書いてしまうと、上記の誤ったコードになる。
このDPの遷移は、1つ $r-l$ が大きい前計算結果の $k-1,k+1$ を参照する。
そのため、($r-l$ の偶奇)XOR($k$ の偶奇) によって、遷移元・遷移先のつながりが2つに分かれてしまっている。
この断絶により、$N$ の値によっては、正しい答えが求まらなくなってしまっていた。
ここでは、$DP[l][r][lim]$ を「$lim$ 以上」と見なして、取る権利をさらに蓄積することも可能にすると、問題なくなる。