開始前の5分でウンコしてきた（速い！）。Visual Studio 2019は微妙だった。変数の「名前の変更」にすごく時間がかかることがあった。puと打ってpush_backを出すような補完も遅いことがあった。終了後36.8。調子はよかったが、問題が難しくて緊張した。いいセットだった。
A - Five Antennas
問題が30秒くらい読み込まれず。一番離れた電柱と電柱はどれでしょうというやつだ。入力が長い。自分の入力スニペットは4つまでだ。Yay!とか出力させるのが面倒だが、公平感はあるか。いや、双子回とわかっていたのだから、準備はできた。
B - Five Dishes
趣旨がつかみづらい。10の倍数の時刻にしか頼めないってところだ。これは順列を全部試せばいいから思考停止next_permutationだ。想定解だろうし、いちいち思考停止する必要ある？とは思うがまあ。ABCDEはA[5]として処理する。
C - Five Transportations
これも簡単そうすぎて問題が読めない。しばらくして問題の意味はわかったが、解けない。やはり簡単そうすぎてふわふわしてしまう。明らかに簡単なのに「知らない」というのは焦る。どこかがっちりつかみたいが。そのうちに、（これもA[5]で読み込んで）Aは広義単調減少としてよいことに気づく。増えてても供給されないんだから意味ない。すると、ネックになる場所で必要な時間がわかる。ネックになる場所も最後とわかっているから、そこに最初の集団が到着するまでの時間もわかる。いやいかにもABCのCという感じの、簡単さと天才性を兼ね備えたいい問題だ。
D - Cake 123
パッと見は安心する見た目だったが、色々つついてみても一向に解けない。3000個、けっこう小さいけどなあ。全列挙しても10^9なので、ちょっと高速化するだけなのだが、どうにも。そもそも探索が書けない。グニャグニャ動く。上から順に取っていくことができない。いやーできるのかなあ。
二分探索を思いつく。この前のAGCもそうだけど、こういう向きから見るのは思いつきづらい。ただ、もう一つの方向から見れば解きやすいという典型ではある。できそうではあるが、全部同じ数とかのケースを上手く処理しないとTLEの危険もありそうだ（ここでかなりの時間を食う）。とりあえず問題を単純にしていく。XYZをX[3]に、ABCをA[3]にする。大きい順にソートしたら、先頭の要素をtとして各要素をt-a[i]に置き換える。つまり0から始まって小さい順になる。そして、「合計がl以下になる選び方がk通り以上あるか」でlower_bound。実際はこんなスムーズに進まないけどね。解けそうになってからの実装時間がマジでやばい。めちゃくちゃかかる。もっと簡単な想定解があるのかなあと思いつつ、見つからなかったら大変だしこれを実装する。
大きい順というのが嫌らしいのは感じていた。大きい順だと、k個あるかを判定するのに三重ループで将来的に足りるかがわかりにくくなる。小さい順で最初が0ならわかりやすい。a[0][i0]がlより大きければそこでループを抜けていい。イメージとしては、和の最大値からどれだけ減ってるか。一定以上削られたらそこで終わり。ループの最内ではkまでカウントしてkになったらtrueを返す。1回の判定がO(k)で終わることが保証されれば実行時間は問題ない。懸念はカウントがインクリメントされない空ループの存在だった。しかし、どのa[h]も0から始まっているので1回はループする。これで多分大丈夫だろうと思った。
さてこれで、小さい順のk個は全部l以下で、l-1以下では足りない、つまり小さい順だと最後lで終わることがわかった。あとは判定と同じようなコードで答えを列挙する。判定時は漏れがあってもk個見つければよかったが、今回はl未満の全てを見つける必要がある。よってl以上でループを抜けてしまうことにする。これはk個未満なのでO(k)で全部見つかる。あとはソートして、足りない分はlを出力すればいい。もちろん最初に変換した分を戻して出力する。いやあ、時間かかった。でもCとDは面白かったね。難しくないのにすんなり解けないのはよい。いや解けないこと自体はよくないけど、そういう弱点は誰にでもあるものなので。
