10/16(月)

午後2時くらいに起床。1時間ほどゴロゴロしてから起き上がり、購買に行ってお菓子・パン・本を買った。そのまま帰宅して食事はパンで済ませるつもりだったが、せっかくキャンパスに来たのだからと考え直して学食で食べて行った。

午後4時半からインターン先定例会。先週も相変わらずずっと学習を回していた。改善されている様子がなく、しかも回すだけ回して結果についての考察を全然やっていないため、話すことが本当にない。

勉強会はyukicoderで開催されたマラソンについてだった。3時間でテスターもビジュアライザもなしに取り組むには難しい問題に見える。実際解法もあまり理解できなかった。

しかしこういう状況を進行させながらパラメータを推定する問題は、推定フェーズと出力フェーズを分けられないという点に苦手意識があったので、一つ話を聞けて良かった。パラメータを最初適当に初期化しておいて、それを使ってクエリを投げ、返答を見て更新していけばよいらしい。言われてみればそれはそうか。更新は数式を弄るほか「粒子フィルタ」なるものを使う方法もあるようだ。

No.5018 Let's Make a Best-seller Book - yukicoder

かなり早めに解散となって、それから日付が変わるまでずっと週記を書いていた。TTPCとARCを残して投稿。

「赤点魔女に異世界最強の個別指導を！」を読んだ。鎌池和馬さんの新作。「未踏召喚://ブラッドサイン」が面白かったことを思い出して購入した。魔法の設定が非常に良かった。台詞に特徴的な語尾をつけて発話者を区別するのは、別に主人公でやる必要はないだろうと思ったが、そういえばブラッドサインでも「訳だが」という語尾が使われていたのだった。ただこの作品で使われたものはもうちょっと違和感が強い。

週記のARCの部分を埋めた後、読者になっているはてなブログの更新を久しぶりに読み漁った。シャワーを浴びて布団に入り、少しラノベを読んで午前7時就寝。

10/17(火)

午後3時起床。JOI一次予選の第2回過去問が公開されていた。昼前にはすでに提出があったようだが、遅ればせながらコードゴルフをした。

Aはdc。こういう問題はNibblesで書くと逆にとんでもないことになる。Bは $0^{(X+5)\bmod 7}$ 相当をdcとNibblesで書いたら後者が1B短くなった……と思っていたところ、後から見たら==でさらに1B縮んでいた。完全に頭から抜けていた。

CとDはどちらもNibbles。Cは $N$ にo以外の文字数を足した。Dはiterate while uniqなるものを使って操作の無限列を得て、先頭から $N$ 未満のものだけtakeした。

JOI 2023/2024 一次予選 (第2回) 過去問 - AtCoder

布団に戻ってR-18のハーメルンを2作読んだ。「とても都合のいいオナホ先輩」と「『最低』な彼は何でもお見通し」。後者はヒロアカの二次創作である。原作を読んでいないのでオリ主中心のハーレムに忌避感がないし、頭の中のイメージが原作の絵柄に引きずられることもない。ことR-18を読むにあたってはお得だった。

ハーメルン - SS･小説投稿サイト-

読んでいる間、午後8時から2時間くらい寝ていたようだ。次に布団から脱出したのは午前2時。ABC324のアマギフがもう届いていた。

食事してから先週のUC-Jを解説を見てupsolveした。「 $n$ （ $n\le 1000$ ）頂点のグラフに対し、頂点集合であって誘導される部分グラフの辺の本数が偶数であるものを数えよ」という非常にシンプルな問題。解法もシンプルで汎用的に見えるのにあまり解かれなかったという点で、かなり良い問題だと感じた。

まず問題を多項式に言い換える。頂点 $u$ に対し01の変数 $x_u$ を定めると、辺 $uv$ について $x_ux_v$ という項がその辺が誘導されるか否かを表す。つまり2次の多項式 $P:=\sum_{uv\in E}x_ux_v$ について $P\equiv 0\pmod 2$ となる変数の割り当てを数え上げる問題になった。あとはグラフを忘れて解ける。

以降法を2とする。 $P$ が $x_1,\dots,x_n$ を変数とする（高々）2次式であるとき、変数 $x_1$ に着目すると $P=x_1 L(x_2,\dots,x_n)+Q(x_2,\dots,x_n)$ と分解する。ここで $x_1^2=x_1$ なので、 $L$ には変数 $x_1$ は現れない。また $P$ は2次式だったから $L$ は1次式である。 $L$ の値で場合分けする。

$L=1$ のとき、 $x_1=Q$ とすることで、またそのときのみ $P=0$ となる。よって $L=1$ であるような $x_2,\dots,x_n$ の割り当ての個数だけ解が存在する。 $L$ は線形なので、この数え上げは容易。

$L=0$ のとき $P=Q$ であるから基本的には $Q=0$ を解けばよい。 $L=0$ の制約は、例えば $L$ に変数 $x_2$ が現れるならその変数を $x_3,\dots,x_n$ で表すことで保証できるから、それを $Q$ に代入して新たな式 $Q'(x_3,\dots,x_n)$ を作ればよい。この操作で変数が1個あるいは2個減るため、繰り返せば解ける。

計算量は繰り返しが $O(n)$ 回、さらに内側で多項式の書き換えに $O(n^2)$ かかるため $O(n^3)$ 。ただし変数がどんどん減っていくので定数倍はかなり良く、実際200ms弱で通った。

Submission #218334 - Universal Cup Judging System

2023/10/23追記：ABC220とほぼ同じ問題らしい。話題になったのも言われてみれば何となく覚えている。しかし当時はもっと違う言い方をされていた。

出てない回の UC に知ってる問題が出ていたらしい。https://t.co/K6hKLJ185s この問題と本質的に同じで、これを EntropyIncreaser が謎のアルゴリズムで解いているらしいということで一時期話題になっていた。
— 熨斗袋 (@noshi91) 2023年10月23日

sugarknri.hatenablog.com

朝までかけてラノベを2冊読了。

1冊目、「悪役御曹司の勘違い聖者生活」2巻。日記を読み返すと1巻の印象が悪かったらしいが、2巻はそうでもないどころかむしろ面白かったと思う。勘違いポイントはヒロインたる生徒会長の境遇に関するものだけだったので、どうすれ違っているのか分かりやすかった。また主人公が積極的に状況をコントロールしているようで満足。読んだ際の気分の問題だったのだろうか。

2冊目、「人数合わせで合コンに参加した俺は、なぜか余り物になってた元人気アイドルで国宝級の美少女をお持ち帰りしました。」。主人公の部活でありヒロインとの縁にもなっているサッカーの話が多かった。悪役ポジのキャラが不真面目なのにサッカーは上手いという奴で、一方主人公は目一杯練習していてもスタメン落ちというなかなか辛い設定になっていて目新しい。

午前8時半就寝。

10/18(水)

午後7時起床。

AtCoderの提出一覧の仕様が変わって1ページずつしか移動できないようになっていた。必要な提出だけロードすることによる高速化が目的だろうか。URLを弄ると遠くのページにも一度で飛べるが、読み込みに相応の時間がかかる。また全ての提出をロードする必要があるコード長や実行時間でのソートについては、当然ながら特に速くはなっていなかった。

提出一覧、AtCoder Jumper がなくなってこれになってた pic.twitter.com/LCIsOKOuMn
— ゴジラ＠競プロ (@gojira_kyopro) 2023年10月18日

日付が変わったくらいに「間の悪いスフレ」を読了。「タルト・タタンの夢」「ヴァン・ショーをあなたに」「マカロンはマカロン」に続くシリーズ4作目の、日常の謎短編集……のはずが今回は社会問題やコロナ禍、ロシア・ウクライナ戦争の話が目につき、また謎らしい謎もないように見えてあまりミステリとしては読めなかった。

その後別の本を開いて朝方まで読んでいた。シャワーと食事を済ませてからセミナー準備として論文を読んだり先週に引き続いて少しサーベイしたりして、午前10時就寝。

10/19(木)

午後5時起床。生協に行ってラノベを買い、夕食を摂って帰ってきた。

それからずっと本を読んでいた。午前3時過ぎに「ロジカ・ドラマチカ」を読了。あらすじに「偶然耳にしたわずか１文・数十字をめぐる知の殴りあい」とあって、これは「九マイルは遠すぎる」のオマージュ作品だろうと買ったがその通りだった。短編四つで、特に最後のものは「ましてや～ならなおさらだ」という形のセリフが何度も何度も登場していた。

本家の流れを汲んでか、自分が覚えているオマージュ作品はどれも、なんでもない日常のセリフから犯罪の真相を暴いていたように思う。これは瓢箪から駒という感じで驚きではあるのだが、しかし論理の飛躍も大きいように見えてしまう。その点本作で考察の対象になった文はどれも明らかな不穏さがあったので、犯罪に結びつくことにはそれほど不自然さがなかった。

300ページの本に昨日と今日で14時間かけたらしい。それくらい文章を読むのに苦労した。まず作者の特徴として言い回しが仰々しく難しいというのがあり、加えて本作では精密な論理展開のために持って回ったような言い回しが多用されていた。自明とか同値とか敏感になるべき言い方もあって、その度に本当にそうか考え込んでしまった。

それから急いでセミナーの準備をした。何とか終わらせて午前9時半就寝。

10/20(金)

午後3時起床。予報によれば天気が崩れるタイミングがありそうなので徒歩・地下鉄で登校した。川内キャンパスの生協でラノベを買い、昼食を摂り、山へ。図書室に寄って教科書を借りたり雑誌のコピーを取ったりしていたらちょうどセミナー開始の時間になった。

午後5時から2時間は留学生の発表。論文の文章がなかなか意味不明だったが、具体例を見ようにも簡単なものしか手計算できなくて大変だった。ちゃんと理解するには参照元の論文まで読みに行く必要がある。

その後自分の発表の予定だったが、既に予定していた終了時刻になってしまったし、今週用意してきた内容で特に話したいこともなかったためスキップとなった。学食で夕食を摂り、閉店まで先生と1対1で話して午後8時半帰宅。

しばらくダラダラして、午後9時20分からyukicoder 409に出た。

yukicoder contest 409 - yukicoder

Aは頭が回っていなかったので真面目に計算した。最終的に $a^2(p-q)^2\gt 0$ が得られて題意を理解。Bはビームが $O(H+W)$ 通りしかないので頑張って列挙して全探索した。答えを求める部分にも $O(H+W)$ かけてよいので、愚直。

Cは $(d,e,f)$ をメモした後 $(a,b,c)$ を全探索した。最初 $0\le d\le e\le f\le 300$ で計算しておいて、 $c$ をインクリメントするごとに条件に違反する $(d,e,f)$ をキャンセルしていけばよい。

Dはとりあえず立式してWolfram|Alphaに投げようとした。 $A$ の最大値とその位置を固定すれば後は単純な二項係数になる。ところがここから最大値を動かしても位置を動かしても閉じた形になってくれない。仕方なく自分で解釈しなおすと、最大値 $a$ を固定したときに左右それぞれ $1\dots a-1$ のうちどれがあるか考えれば位置も定まることに気づいた。よって答えは $\sum_{a=1}^M\binom{2(a-1)}{N-1}$ 。

EはまずDで出た式を閉じた形にしようとしたが、やっぱりWolfram|Alphaでもダメだったのでまた自分で。Dの解法は最大値の左右で分けたが、ここで最大値それ自身も左に入れてみる。すると求める値は左 $M$ 個右 $M$ 個から合わせて $N$ 個選ぶ方法のうち、最大値が左にしかないものとなる。

最大値の出現パターンは左、右、左右の3種類あって、左と右は対称だから等しい。左右のケースは片方削除すると $N$ が一つ小さい問題の解となっている。よって $(N,M)$ に対する答えを $f(N,M)$ と置いたとき、 $2f(N,M)=\binom{2M}{N}-f(N-1,M)$ が成り立つようだ。

実はここから平方分割っぽく解ける。つまり、だいたい1000個おきに $f(1,M)$ を計算した後上の式で $f(2\times 10^5,M)$ まで列挙しつつ、 $M$ が足りない分はその場で補ってクエリに答えればよい。

solved数を見てGに進んだ。 $f=\sum_{n=0}^{\infty}\frac{x^{3n+1}}{(3n+1)!}$ が欲しい。ここで1の3乗根で1でないもの $\omega$ 、つまり $\omega^2+\omega+1=0$ を満たすような数を考えると、 $f=\frac{1}{3}\left(\exp(x)+\omega^2\exp(\omega x)+\omega\exp(\omega^2 x)\right)$ であると分かる。よって $N!\times[x^N]f^M$ が答え。

$f^M=\frac{1}{3^M}\sum_{a+b+c=M}\frac{M!}{a!b!c!}\times\exp(x)^a\times(\omega^2\exp(\omega x))^b\times(\omega\exp(\omega^2x))^c$ である。係数を取り外せば、 $(a,b,c)$ に対し $[x^N]\exp((a+b\omega+c\omega^2)x)=(a+b\omega+c\omega^2)^N/N!$ が求まればよい。ここで外の $N!$ とキャンセルが起こり、 $\bmod$ を超える数の階乗が回避できる。

ここまで来て初めて $\bmod{998244353}$ には $\omega$ が存在しないことに気づいてしまった。しかしなければ仮想的に作ればよい。結局 $\omega^3=1$ と次数が大きくならないのが利点なので、FPSのべき乗とは違い $(a+b\omega+c\omega^2)^N$ は二分累乗法で高速に求まる。ここに気づくのにも時間がかかったが、何とか間に合った。

残り8分でF問題。かなり冴えていて、ちょっと考えたらすぐヴァンデルモンドの行列式だということに気づいたが、差の積を高速に計算するための手持ちがない。とりあえずTLE解を出しておいた。6完4位。

直後にFのupsolveをした。選んだインデックスの（順）列を $\sigma$ とすると、 $X=\mathrm{sgn}(\sigma)\prod_{i=1}^N A_{\sigma_i}^{N-i}$ となる。この $\sigma$ に関する和は $V_{i,j}:=A_j^{N-i}$ で定まる行列 $V$ の行列式であり、 $V$ はヴァンデルモンド行列を反転した形になるので、公式から $(-1)^{N(N-1)/2}\prod_{i\lt j}(A_j-A_i)$ が答えとなる。

ヴァンデルモンドの行列式 - Wikipedia

この差積の計算を高速化する。といっても分割統治すれば $\prod_i\prod_j(R_j-L_i)$ みたいな式が求まればよくて、 $\prod_i(x-L_i)$ を $x=R_j$ で多点評価すれば原理的には解ける。TLが6secなのでまあ通るだろう、ということでNyaanさんのライブラリをペタペタ貼った。

Multipoint Evaluation(高速化版) | Nyaan’s Library

符号についてはややこしいし、サンプルには $N(N-1)/2$ が偶数となるものしかない。一発で合わせることができてよかった。おそらく $\log$ 三つだがNyaanさんのライブラリが爆速でevilケースまでしっかり通っていた。

シャワーを浴びてから日記を書き始めたが、YouTubeを見てしまったりラノベに手を出したりと全然進まなかった。

www.youtube.com

午前9時就寝。

10/21(土)

午後7時半起床。食事して午後9時からABC325に出た。

KEYENCE Programming Contest 2023 Autumn（AtCoder Beginner Contest 325） - AtCoder

AはAWK。Bは世界標準時で何時に会議を開くか全探索する。CはBFS。

Dは見た瞬間に $[T,T+D]$ で区間スケジューリングをしたが落ちて頭が真っ白になってしまった。何か関連する話題があったはずと思って「区間スケジューリング」で調べたところ以下のツイートを発見。問題がほとんど一緒なので今回も想定嘘解法なのだろう。リプライツリーにあった解法をそのまま実装して何とかACした。

フェネック「区間スケジューリング問題を知ってるとRの昇順にソートして解こうとしてハマっちゃうかもねー。そういうアルゴリズムのhackケースは
3
2 2
1 3
3 3
だよー」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2021年8月14日

Eは頂点 $1$ と $N$ からそれぞれコストを変えてdijkstra。密グラフなので $O(N^2)$ の実装を用いた。

Fは「何番目の区間までを」「センサー1を何個」「センサー2を何個」使って覆えるかというbool値のdpを考えた。遷移はセンサー1を使う個数だけ全探索して $O(K_1)$ 。これだと計算量が大きすぎるが、値としてboolではなく必要なセンサー2の個数を持つと状態を $O(NK_1)$ に減らせて間に合う。

Gは区間dpで完全に削除できる区間を求めた。ある区間を削除できるか調べるためには、各文字を最後の操作で削除するか他の文字と一緒に以前の操作で削除していたことにするか決める必要がある。

最後の操作で何文字削除したか持って左から耳dpをすると状態数 $O(|S|K)$ 、遷移 $O(|S|)$ となる。まず遷移にはbitset高速化が効く。さらに区間dpの計算を $l$ 降順・ $r$ 昇順で行うと $l$ を決めた瞬間に内側の耳dpを開始できる。以上で $O(|S|^3K/\mathrm{wordsize})$ となり十分高速。

1ペナ全完で9位。賞品の対象にはならなかった。Dのペナがなくても順位は一つしか変わらないようだ。その後Aだけコードゴルフをしたが、簡単なVimの8Bがあって開始1分半で提出されていた。

www.youtube.com

午後11時からTROC #35。

https://tlx.toki.id/contests/troc-35

Aは2023年に $A$ 月 $B$ 日が存在するか判定。 $B$ 月 $A$ 日が存在するとかいう謎の制約のせいでどちらがどちらか分からなくなったため慎重に実装した。Bはインドネシア流の固有名詞がひたすら読みにくい。二人の人物と対応するパラメータに気を付けて読解したら後は算数。Cは $A$ の昇順に倒していくのが最適。

Dはかなり面倒そうに見えたがそこそこシンプルに解けた。水が張られている区間とその高さを持って更新していくことにすると、水が左右に溢れ出してから水位が元の区間と一致するまでの時間が知りたくなる。実はこのとき水が一方向にしか溢れていかないので、ある高さで壁がない区間は一気に水が張られる。よって単純な $H$ の和で書けてしまう。

Eはかなり難しかった。 $A$ を決めたとき、 $R$ の条件は $\max(A-1/2,0)\le R\lt A+1/2$ と書ける。ここで $A\ne 0$ となる項の数 $c$ を固定すると不等式の辺々の和が $\sum A-c/2\le \sum R=M\lt\sum A+N/2$ となるが、 $R$ を非負実数の範囲で自由に調節できるため、実はこれを満たす列 $A$ には対応する $R$ が存在する。

$S:=\sum A$ を固定すると場合の数は2項係数で書けるから、その値を範囲内かつ $S\ne M$ のもとで足し上げればよい。ここで $S=M$ を許すと2項係数の区間和となり、Wolfram|Alphaに投げると閉じた式になってくれるので、そこから $S=M$ の寄与を引くことで必要な値が求まる。

Fは整理が大変。まずcharmを使わなかった場合の移動方法は、経路を折り返すカタラン数の計算と同様のテクで $O(1)$ で求められる。これで立ち入れない領域を避ける移動方法については求まるので、今度は立ち入れない領域に入る移動方法を考える。 $(N,0)$ や $(0,M)$ が立ち入れない領域に含まれるケースは簡単なので先に処理。

それ以外の場合、初めて入る点 $(x_s,y_s)$ と最後に出ていく点 $(x_g,y_g)$ がある。この2点を固定するとその前後は同じ形の問題でcharmを使わなかった場合になっているので、先ほどの計算を流用できる。またcharmのパワーについては $x_s\le A$ と $y_s\le B$ が条件。よって2点間を移動する方法以外の係数は独立に求めることができる。

あとはその、2点間の移動方法。まずcharmのパワーの条件から2点間に立ち入れない領域は存在しない。そして立ち入れない領域の形から $x_s-x_g=y_g-y_s$ が分かるので、これを $d$ と置くと $\binom{2d}{d}$ が求める場合の数だと分かる。つまり $x$ 座標の差にしか興味がないから、畳み込みで $x_s-x_g=d$ となる2点について、先ほど述べた係数の積の和を求めておけばまとめて計算できる。

Gには手も足も出ず6完5位。それでもレートは2875→2906(+31)とかなり上がって、ランキング3位に浮上した。

TROC #35 oooooo- 5th
2875 -> 2906 (+31)

インドネシアで3位 pic.twitter.com/5V83NeMAlU
— こたつがめ (@kotatsugame_t) 2023年10月21日

午前2時からはMHC Round 2に出た。

Meta Hacker Cup - 2023 - Round 2

Aはよい。A1だけ実装するのは面倒だったのでA2も読んだら急に制約が大きくなってびっくりしたが、特に問題はない。Bは $A+B$ を左にrotateしていくので、大小関係の制約はあらかじめ $N$ 個離れたところと比較した結果を持っておけば判定できる。回文の判定はManacher。

Cが一番難しかった。トピックを一つ固定すると木dpで解けるが、部分木の状態を「完全に分解できた→0」「そのトピックを持たない根からのパスが1本残っている→1」「アウト→2以上」と定めると、だいたい和によって遷移していける。状態をオフセットとそこからの差分として持つと、部分木に存在しないトピックは差分0で表現できる。よって出現したトピックの差分のみマージテクで管理すればまとめて計算できる。

Dは二人が選んだ $H$ のGCDが $D$ の約数であることが必要で、十分でもある。一人1種類ならこの十分性は有名事実。2種類以上の $H$ を持っているときは十分高いタワーをGCD刻みで作れることから従う。そして $K$ 個の選び方をGCDごとに数え上げるのは約数除原理の典型。 $K$ が小さいことは使わなくてよい。

全部通って9位。かなり簡単なセットだった。今回はR1のようなシステムトラブルがなくて良かった。

日記を書いて午前10時就寝。

10/22(日)

午後3時半起床。午後4時からCF #904 div.2に出た。

Dashboard - Codeforces Round 904 (Div. 2) - Codeforces

Aは $10t\dots 10t+9$ の間には必ず存在するため見つかるまで探索してよい。この簡単な事実が思いつかないまま雰囲気で通して、証明はコンテスト後につけた。Bは右にある0から順に自分より右にある1の個数を数え、足し上げればよい。

Cは $\min$ を取るインデックスを固定したときそこを覆う区間はすべて使わないとしてよい。するとそこから左右に分けることができて、それぞれ区間ADD・区間MAXの遅延セグ木でシミュレートできる。Dは昨日のMCH R2-Dと同様に解ける。

Eは大変だった。最適な操作は、最小値が連続する極大区間を埋めていくことで達成できる。これを逆から考えると操作する区間がその中の最大値でどんどん分割されていくように見える。最初に $a_0=\max a$ を満たすようrotateしてから解くと、このときの操作がデフォルトの状態だと思えて、数列をrotateするごとに端に来た区間だけ二つに分裂しその分操作回数やコストが変化する。

例えば区間 $[L,R)$ があったとしよう。先頭要素が $a_i$ （ただし $L\lt i\lt R$ ）のとき、この区間は $[L,i)$ と $[i,R)$ の二つに分裂する。つまりコストの変化は $(i-L)^2+(R-i)^2-(R-L)^2=2i^2-2(L+R)i+2LR$ であり、インデックス $i$ に関する2次関数で書けるので区間加算が可能。

あとは区間を（重複をまとめて）列挙しセグ木で処理。遅延セグ木ではなく双対セグ木を使ったり、更新が可換なので遅延したものを下に流さないようにしたり、最後の1点取得 $n$ 回の前に遅延した更新を一気に反映したりと高速化を入れて2700msだった。

全完4位。

www.youtube.com

AHC025が終了した。結局初日の最初の1時間しか参加しなかった。アイテムを適当に振り分けた後、重い集合から軽い集合へ一つ移して重さの大小関係が変化しないケースのみ採用という山登り。1点swapで改善したかどうかすら分からないと思い込んでいたが、さすがにこれはまともに考察していなかっただけだと信じたい。

AtCoder Heuristic Contest 025 - AtCoder

AtCoderの提出ボタンが変なところに判定を持っているらしい。自分でも試してみたら本当に押せてしまった。これまで暴発した経験がなかったのが奇跡に思えてならない。

AtCoderの提出ボタン、紫の四角の範囲にも当たり判定あって（空のlabel要素がある）、思いがけないタイミングで提出されてしまった… pic.twitter.com/9ojStLWJLK
— tomerun (@tomerun) 2023年10月22日

食事して午後8時からCF #905 div.1。div.1からdiv.3まで三つ同時開催という見たことのない形式だった。

Dashboard - Codeforces Round 905 (Div. 1) - Codeforces

A1から大変。 $a:=c[1]$ 、 $b$ はソート済みであるとする。最終的な項数を $k$ と置くと、 $1\le i\le k$ に対し $a_i\lt b_{n-k+i}$ が条件。ここで $a_i\lt b_j$ なる最小の $j$ を $L_i$ と置くと、 $L_i\le n-k+i\Leftrightarrow k\le n-L_i+i$ となる。 $k$ をインクリメントしつつ判定すればよい。念のため、答えは $k$ ではなく $n-k$ である。

A2はこの方針だと難しい。まず $a$ を長さ $n-1$ の列のままにしてA1と同様に $k$ を求める。そこに $x$ を追加しても $k$ は高々1しか増えないので、1増やせる最大の $x$ を求めた。 $x$ を追加するとそれより小さい $a$ についてペアを組む $b$ がずれ、小さくなる。これが許されない最小の $a$ を探すと $x$ が入る位置が決まり、ペアとなれる最大の $b$ もわかって最大値が求まる。

完全に出遅れ、焦りながらBへ。こちらは簡単。すべての辺を集めてグラフを作り、たどり着くタイミングを距離としてdijkstraを行う。辺を通る際はそれが使える直近のタイミングを調べる必要があるが、まあ何でもできる。尺取りみたいな感じで $\log$ は落としておいた。

Cは実装に苦労した。数列の先頭の項から最小値を求めていくことにする。各項についてどのクエリで最小値を取るかだけなら、クエリ番号を遅延セグ木のインデックスにしてクエリを載せたり降ろしたりしながら数列を舐めればよい。しかし本当に欲しいのはこれまで最小値を取り続けたクエリのみ考えた時の最小値である。

そこで、最小値を0に揃えて $\infty$ を掛ける更新を間に挟むことにした。こうすれば最小値を取り続けない限り一瞬で $\infty$ に飛んでしまって、以降最小値の計算から弾かれる。実際には $\infty$ ではなく十分大きな値を使い、オーバーフローしないよう注意して区間ADDと区間 $\infty$ 倍の更新を表現した。

更新のためlong long二つとboolを持った最初の提出は3secギリギリだったので、リサブ。boolを持つのをやめ、片方のlong longを特殊な値にすることで表現したら1sec以上高速化した。

それから残り50分あったのにDを通せなかった。Cまでの4完142位でレートは3095→2969(-126)。LGMを保つことができない！Aは $k$ や $x$ を二分探索すればよかったらしい。真面目に頭を使っていたのがバカらしくなってしまった。

Dは4ケース目でずっと落ちていたのだが、コンテストが終わって一息つきランダムケースを試したらすぐ間違いが見つかった。ただ修正レベルではなく解法の根本的な見直しが要求され、相応に時間もかかったのでどうしようもない。

$l$ が固定されているとして、各 $i\ge l$ について「区間 $[l,i]$ と $(i,r)$ に分けることが可能な最大の $r$ 」を管理した。これを $l$ をデクリメントするごとに差分更新していく方針。コンテスト中は $l+1$ から右に見た時の累積MAXや累積MINを見て適切に区間chminをしていけばできると考えていたが、できなかった。

$i$ を中心に変化を考えるのが正解。 $i+1$ から右に見た時の累積MINの更新点を列挙すると、 $r$ はそのどれかにしかならない。 $l$ をデクリメントしていく際どのタイミングで $r$ が変化するかが求まるので、これを記録して適切に1点更新すればよい。記録すると同時に累積MINの更新点が消えるので、更新は $O(n)$ 回になる。