ARC120

3完。(挑戦したけど解けなかった問題で)何もできなかったの久しぶりだな。調子は悪くなかったけどなあ。残念。

A - Max Add

何言ってるかわかんないけど、よく考えると最大値を足したらそれが最大値になるので、累積和に最初の最大値を足したような数列になる。やや複雑なので時間をかけて書く。最初オーバーフローの心配をしていたが、時間が経ったので忘れてしまった((10^7)^3になることを心配していたが、今考えると10^7*(2*10^5)^2なんだよなあ)。400点で身構えたけど複雑なだけで難しくはないなあ。

B - Uniformly Distributed

なんかDPっぽいけどね、落ち着いて考えよう。2*2のブロックを考えて、左下と右上のマスが違う色だったら、赤の数が異なる経路が構成できちゃうよね。つまりそのナナメの並びは全部同じ色確定。そしてそこが同じであればどの経路も各ナナメのライン(将棋的な言い方だ)を1回ずつ通るので、赤の数は同じになる。これは典型90の047での経験が生きる。マス(i, j)の状態をi+j毎にカウント。赤青両方あったら0通り、片方しかなかったらその色に合わせる、どちらもなかったら好きな色を選ぶ。0か1か2を掛けていく処理になる。

C - Swaps 2

操作を手でやってみて、なんかポテンシャルみたいのが見える。改めて、落ち着いて自然な解釈を求める。入力で与えられる数列は、実は右へいくほど小さく表示されている。だからスワップすると1増えたり減ったりして見えるのだ。a[i]にiを足すと真の姿になる。これで、スワップ何回で一致させられますかという問題になる。ここからが苦労した。

転倒数だと思うけど、同じ数が入っているかもしれない。どちらもソートなんかされてないので、思考のステップ数も増えて負荷がかかる。そもそも、意味が変わらない範囲で違う数を割り当ててAをソート済みにすることさえできない(0, 1, 2, 1 みたいになる)。例によってchokudai speedrunでググるんだけど、まあコード流用はしない。BITを貼って、あとは自分で考えるしかない。まず入力を別の場所にコピーしてソートして比較して、一致しないケースを先に処理しておく。次に座標圧縮。ここは時間をとって悩んでみたけど処理時間で悩むくらいならできることはさっさとやってしまったほうがいい。そしたらvectorvectorで「数列Bに3が現れるのはどこ」というのを構築。後ろからやると、前のものから取り出してpopできるので使いやすい。BITは全部の場所に1をセットしておく。方針としては、左から貪欲にAに合わせていく(Aの最初の要素が3なら、Bで一番左にある3を持ってくる)。すなわち、そこより左でまだAに合わせていないBの要素数をBITで得て足していく。

D - Bracket Score 2

括弧の深さの山を横に切る、区間DPの高速化、絶対値を外してなんかDP、楽観的にペアを作ってそれを実現する、Aを添え字の偶奇で分けてみる、近くの括弧で組み換え。色々考えたけど全然ダメだった。残り時間が少なくなると、「答えがこんなんだったらやってられん」というのを潰していく感じになる。残り10分を切って解ける見込みがほぼ消えると、EやFを考えて時間を過ごした。

(解説を読んで)楽観的なやつだった。白と黒に塗るのはやってたんだけど、白と黒のペアでありさえすればどう組み合わせてもいいしどっちの括弧に対応させてもいいというのがかなり難しかった(「言われればわかる」程度の理解では、無数に考察する中でつかみ取れない)。