ABC149

いつもと違うPCで参加したけど問題なく終わってよかった。unratedは常に残念ですねー。unratedなことに気づかず戦っていつも通りくらいの結果。いいセットだった。

A - Strings

T+S

B - Greedy Takahashi

Bなのに32bit整数に収まらない。残り行動回数を持ってシミュレーション。

C - Next Prime

どう直したら使いやすいかわからないまま放置してる素数列挙ライブラリを貼った。サンプルが上限を示してくれてるのは気づいたが、まあ最初に見えた方針で。20万までの素数を列挙しておいて初めてX以上になったところで出力する。

D - Prediction and Restriction

DP臭がするうえにわからないので5分くらいでEに行った。

FがわからなくてDがかなり解かれてるので戻ってきた。いやなぜ気づかない。K個の列に分割できるじゃん。あとはDPで解けるが、よく考えると、筐体の出す手（手を筐体が決定するだけで筐体が出すってのは変か）の（分割後の列で）連続する部分列が同じ手で成っていたとして、最初に勝って次妥協してを繰り返すのが最善だ。つまり貪欲でいい。ええと、筐体の連続する2つの手が異なるなら、1個目が勝ちなら2個目も勝てるし1個目が勝ちでないなら2個目の邪魔にならない手を選べる（新ABC、こういう「思ったより簡単にできている」問題が多い気がする）。ということでDPを使わず書いた。

終了後に知ったが、分割せずに（勝敗だけ記録しておいて）貪欲で解けるんだね。

E - Handshake

問題文を頑張って読むと、N*Nのマスになる。Aはソートしていいので降順ソートして、そうするとマスは上に行くほど左に行くほど大きい数が書かれている。これを大きい数から貪欲にM個取ればいい。制約にでかい数が出てこないのでうっかりするが、Mは32bit整数に収まらない可能性がある。

N*Nのマスを1行ずつ見ていく。例えば「10以上の数を全部取ったら何個になるか」はO(NlogN)でわかる。各行で二分探索すればいい。さらにそれを使って二分探索すれば、いくつまで取ったらM個をオーバーするかがO(NlogNlog(max(A)))でわかる。もう少し考えると、最初のO(NlogN)はしゃくとりでO(N)になる。Nがそんなに大きくないのでlogが2つ付いても間に合うけど、最近はしゃくとりにも慣れてきた（それに二重二分探索も決して簡単ではない）。

降順はループ方向が慣れないので、N*N-M個を小さいほうから貪欲に取る問題を解くことにする。全体の和は2*N*ΣAで、ここから引いたものを出力する。これを考えるのも時間かかるけど、これすらわからないようではこの問題は解けないと思ってこの方針にした（実際、これを考えた経験値はこの問題を解く中で役に立った）。入力を昇順ソートし、累積和も持つ（しゃくとりの中で計算できそうだがこのほうが簡単そうだ）。さて、二分探索では「どの数までならM個以下に収まるか」「どの数で初めてM個を超えるか」しかわからない。求めたいのはM個の和だ。とりあえず、コードの全体像が見えるまでテキトーに書き進め、それを見て考える。誤りを含むコードをコントロールして利用できるのは調子がいい。

和で二分探索できないかとか色々考えたが、DDCC2020予選E問題の経験を生かし境界の前後は必ず探索されるという性質を使い二分探索内でM個の和を計算した。具体的には、二分探索内ではt以下の数を全部取ってその総和sumと個数kを求める。個数は二分探索に使い、総和はM個の和の推定に使う。k>Mのときのsum - t * (k - M)の最大値が求めたいM個の和。tが初めてM個を超えた数のとき正しい値になり、それより大きいときは小さく推定するので、最大値。探索範囲は、多少広げても悪いことが起こらない問題設定だったので安全側に振った。最後、サンプルが合わずに苦しんだが、ソートする前に累積和を構築してしまっていた。

F - Surrounded Nodes

Eに時間をかけたあとで意外と時間が残っていたので挑戦したがわからなかった（あと、コンテスト中に挑戦する問題は多いほどいい、復習時のモチベが違う）。内側の白を決めてそれに接する黒を固定し外側を自由に決めるみたいなイメージで考えていったが、穴となる白は連続しているとは限らないし外も自由に決められるわけじゃないし連続している白が内側と外側に分かれることすらあって最初のイメージがボロボロだった。