週記（2024/02/19-2024/02/25）

02/19(月)

午後2時半起床。購買に行ってパン類とラノベを買ってきた。

午後3時半からインターン先定例会に出席。用事で欠席・寝坊・休日とここ3週間進捗報告を行っていないようだ。まあ先々週までは報告するような進捗もなかった。先週は少し稼働したので、今日はそれについてと、博士課程合格を報告した。今週から頑張れるかというとそうでもなく、木曜日に修論修正・再提出の締め切りがある。

勉強会は母関数を使った数え上げの話で、特に指数型母関数を使ったり、簡単な関数との間の等式から式変形したりするテクニックを扱っていた。前者はcombinationから自然に見出せると思っていて、それで解けたこともあるが、後者は残念ながら成功体験がない。dpで扱おうとすると複雑でよくわからない遷移になって手に負えなくなるだろうし、難しい話だ。

解散後は週記を書いていた。今日はyukicoderがあるのでそれまでに先週の週記を投稿しよう、と思っていたのだが全く捗らない。そうこうしているうちに午後9時20分になったので、問題だけ読んでおくかとページを開き、流れでうっかり2時間近く参加してしまった。

traP 作問ハッカソンコンテスト 002(day2) - yukicoder

まともな取り組み方はしていない。Hを解いた後Iの非想定解と格闘し、最後にGを考えていた。

Hは3次元ということで一瞬嫌な気持ちになったが、操作後も必ず[0,100]に収まるというかなり優しい制約に気づいた。これなら細かいことを気にせず101\times 101\times 101の1次元に潰してもよい。ならば、と犯罪のつもりで畳み込みを書いたらFAだった。しかもこれが想定解だったらしい。

Iはd(k)/kが乗法的関数であることを利用するものと考え、以下のライブラリを自力で再現しようと試みた。素数の逆数和が必要だが、それは途中で打ち切っても何とかなるだろうと思った。しかしそもそも、まともな速度が出ない。諦めてライブラリを拝借した。

乗法的関数のprefix sum | Nyaan’s Library

設計が特殊なので使い方のメモをしておきたい。コンストラクタには和を取る範囲、今回ならNを渡す。答えを求める関数はrunだが、これの引数fprimeは1\le k\le\sqrt{N}に対するS_p(k),S_p(N/k)の列を期待しているらしい。ここでS_pはドキュメントの上のほうで定義されている。

そんなのどうやって求めるんだと思ったら、f(p)=1,pの場合のコードがpi_tableやprime_sum_tableとして用意されていた。今回は逆数和だが後者を弄れば作れそう。問題となるのはその関数の初期化部分で、1+1/2+\dots+1/xが必要。小さいxについては前計算し、大きなxはググって出てきた\log(x)+\gamma+\frac{1}{2x}で近似した。

調和数 (発散列) - Wikipedia

TLEしたので、long doubleをdoubleに変えたり、dfsの引数を増やしてf(p^c)を徐々に計算するようにしたりと高速化を試みたところ、1982msで通った。想定解を見て横転。

Gはうっかり牛ゲーに帰着して何もできなくなった。

いつの間にか午後11時を回っていた。週記の体裁だけ慌てて整えて投稿。半からCF #928 div.4に出た。

Dashboard - Codeforces Round 928 (Div. 4) - Codeforces

Aはよい。Bはややこしそうだが、行ごとの1の個数を見ると特定できる。Cは前計算。TLが謎。Dはmultisetを使いaと(2^{31}-1)\oplus aを貪欲にペアにしていった。Eは2^0\times\text{奇数},2^1\times\text{奇数},2^2\times\text{奇数},\dotsと並ぶ。

Fは簡単な方法がわからなかったので、Xの出現パターン225通りすべてに対して答えを前計算した。正確にはもう少し減るだろうが気にしない。下位集合へのゼータ変換が必要になって3000msを超えた。日記のこの部分を書いているとき、それがいらない遷移を思いついて、試したところ826msで通った。Gは木dp。

全完7位。Fは市松に塗り分けてみると完全に独立になるため、操作の候補も半分になって全探索できるらしい。

www.youtube.com

先週の週記にコンテストを三つばかり書き足したら朝になった。午前6時半就寝。

02/20(火)

正午くらいに腹を壊して目を覚ました。

槻影さんのなろう発ラノベ「嘆きの亡霊は引退したい」のアニメ化情報が流れてきた。好きな作家さんだ。めでたい。

1時間くらい二度寝するか迷っていたが、ここで寝てしまうと今日はずっと布団で過ごすことになりそうということで、気合いを入れて起床。学食で食事し、ラノベを受け取ってきた。

先週の週記にARCとその後取り組んだDMOJのことを書いていたら夜になった。DMOJと言えば先週一つコンテストに参加したのだった。そのコンテストは今日の午後2時終了で、TLでも言及が流れてきていた。自分もここで書いておこう。

The Contest Contest 1 - DMOJ: Modern Online Judge

P1はまあ、できる。P2は消える区間を管理してみた。各iに対しd=a_iについてだけ更新すれば十分であるようなデータの持ち方をすればよい。

P3は天啓一発。情報に間違いがないならa+bやc+dの頻度配列を見ることで要素の大小関係がわかる。それを満たすように小さい値から埋めていけばよい。ところで今間違いは高々一つだから、a+bとc+dのどちらかは正しい。よって両方試してチェックすることで候補が求まる。気づくまでは不可能に見えており、閃いたときはかなり気持ちよかった。

P4はかなり大変。操作が耳dpの元となった問題に似ていたので、まずその解説を読みに行ったが、今回は頂点を訪れた回数だし、始点に戻ってくるし、結局あまり関係なかった。1点、辺を通った回数のほうが扱いやすいというのはポイントかもしれない。

D - Ears

始点を決め打ち、そこだけfをデクリメントすることで、経路一周分が表現された状態になる。この状態で左から考えると、辺i\leftrightarrow i+1を通った回数が2(f_i-f_{i-1}+\dots+(-1)^{i-1}f_1)として表せる。これが0以下だったり、辺N\leftrightarrow N+1を通った回数が0でなかったりすると実現不可能。そうでない場合はKを無視すると可能。部分点1は愚直、部分点2はfのデクリメント分を差分更新すると通る。

問題はKについて。経路を辿る際、一瞬だけ往復することで制限を回避することを考えると、基本的には辺K-2本置きに往復する必要がある。ただし辺1\leftrightarrow 2,N-1\leftrightarrow Nでは往復したと見なしてもよい。そこで、経路一周を2回の1\rightarrow Nだと見なせば、辺を通った回数を見ながら貪欲に往復することで判定ができそう。

できそうなだけで残念ながら微妙に違う。今決め打っている始点がsだとすると、「片方の1\rightarrow Nにおいて」辺s-1\leftrightarrow s,s\leftrightarrow s+1で往復したと見なせる、という条件が付いてくる。そこで2回の1\rightarrow Nを2回ずつの1\rightarrow s,N\rightarrow sとさらに分割すると、往復しなかった辺の連続回数を記録しておけばマージができて、先ほどの貪欲が効く形になる。

これを毎回愚直にやると部分点3、左右で分けて前計算すると満点。先ほどの辺を通った回数の計算によれば、fのデクリメントはより右に、かつ決まった形でしか影響しないから、左からは元のfで、右からはデクリメント後のfで前計算しておける。

P5は1列持つdp。といっても状態は...、.##、##.、###の4種類しか考えなくてよい。bとして出現する列だけ遷移を全探索で行い、その間はいったん...に揃えてから一気に遷移した。この遷移の際、途中に1\times 1の家3軒からなる列がある場合や、遷移先が###になるなら1\times 1を取り除いて.##や##.にしなければならない点は注意。また2\times 2を縦に並べる際は2列分の条件を判定する必要があることにも注意。時間は結構かかったが、ほぼ一発で合ってそのまま通ったので助かった。

P6は部分点1のみ。頂点1の次数が1で、そこから頂点Nに至るまでのパスが1本道だと答えがYESになる。この場合Aliceは辿る辺を選べないので、辺の重みは何を出力してもよい。逆にそれ以外のケースではAliceが辺を選べるタイミングが存在して、頂点Nに向かわない辺を選ばれると戻って来ない。

以上510点。P4に1時間半くらいかけたので解いている途中はヤバいかもという気持ちになっていたが、満点をちゃんと出せたしP5も間に合ったので結果オーライ。P6の部分点でまくられることもなくずっと順位表のトップにいた。しかし最終日に自分より6分早く同じ510点に到達した人が出て、2位。レートは3091→3209(+118)と、前回優勝した3000以下Ratedより上がり幅が大きかった。

夜は修論の修正作業として先生から頂いたコメントを反映していた。眠気が来たのですぐ布団に入り、午後11時就寝。

02/21(水)

午前9時に一度目を覚ました。この時点で久しぶりに長時間連続して眠ることができていたが、そこからさらに二度寝まで成功。午後1時に起床した。

外を見たら雪が積もっていて学食に行く気がかなり失せたが、理由があって頑張って登校した。食事し今日もラノベを受け取って帰宅。

理由というのは、ミールの適用範囲拡大措置についてのもの。コロナ禍が始まってから何度かの期間延長を経て続いてきたこの措置だが、今のところ今日までということになっている。これまでの延長は数か月前の時点で告知されていたから、春休み突入に合わせて終わるのだと思う。いつもこの制度を利用してお菓子だったりパンだったりを買っていたので、残念。

帰宅して久しぶりにラノベを開いた。2冊読了。特に1冊目だが読むのに非常に時間がかかって、なろうばかり、しかも同じ作品をずっと読んでいた影響を感じた。

1冊目、「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」5巻。4巻に引き続きこの巻でも厄介事が持ち上がり、シュッと解決して終わった。話が長引かないのは読みやすくて良いこと。合間合間でヒロインたちとのイベントもこなし、どんどん距離が近づいている。そのゴールはどうやら作中で3か月後の武道館ライブになるようだ。と、順調な展開を見せるストーリーだが、あとがきを読むと6巻の刊行が確定していないような書き方で、4巻と5巻の間もちょっと長かったし心配。5巻まで出ていてそんなことあるか？続きが読めることを願う。

2冊目、「双子まとめて『カノジョ』にしない？」2巻。1巻の最後のほうでも垣間見えていたが、主人公の才覚・手腕によって校内のトラブルを解決へと導いていくのがラブコメと並ぶもう一つの軸という感じがする。確かに一歩引いたところからあれこれ糸を引いていた様子はあった。ただラブコメに紛れたあっさりした描写からは有能さがあまり実感できなかったというのが正直な感想。

日付も変わり、そろそろ修論の修正作業と向き合わなければならない。シャワーを浴びて気合いを入れ朝まで取り組んだ。いろいろ加筆していた部分が何とか形になったので、先生にメールを送信。今から寝て、起きたら見直しをし、午後5時までに教務課に行って提出を行う。

外を見たら雪がかなり積もっていた。明日は時間に余裕を持って登校しなければならない。午前9時就寝。

02/22(木)

午後1時起床。もう少し眠れるかなと思いつつ1時間ほどなろうを読んで、起き上がった。

昨日送ったメールへの返信では指摘は特になかった。では後は見直しということでしばらく修論を読み直して文章を弄っていたが、かなり時間がかかりそうだったので先に大学に登校することにした。到着した大学構内には入試に向け掲示物がいろいろ張り出されていて新鮮。まず教務課で締め切りと提出方法を確認し、院生室に移動して修正を続行した。

TeX打ちをする際、自分はかなり空行を入れるのだが、別行立て数式の前後に空行があると微妙にスペースが開いてしまうことに気づいた。どうせ別行になるならそのあたり無視されるだろうと勝手に思っていた。これを慌てて削除する作業に追われ、後半の文章をしっかり読み直す時間は残らなかった。

午後5時直前に慌てて印刷し、提出。その後院生室にいた同期・後輩とひとしきり喋り、一緒に学食で食事して解散した。自分の研究テーマの周辺に相手がやっていることと近い話題があったので、それについていろいろ話したのだが、知らないことが多くて雰囲気だけのコミュニケーションになってしまった気がする。

あとは、この先必要になりそうな分野について院生室に置いてある教科書をいくつか紹介してもらった。そういう教科書は皆自分で読み進めているらしい。偉すぎる……。正確にはそれが普通で、自分が怠惰すぎるという話なのだろう。セミナー発表に合わせてDiestelを読んでいるだけではお話にならなかった。

午後7時帰宅。夜中のSRMにレジってからYouTubeを見たりなろうを読んだりして、午後10時半から2時間ほど仮眠を取った。午前1時からSRM853。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19722

Easyは二分探索。入力の生成が面倒。

Medは最初a文字ずらしとb文字ずらしが可能なら|a-b|文字ずらしも可能だと思ってしまったが、サンプルのabracadabraで落ちる。ありがたい。ずらせる文字数の候補がd_1,\dots,d_kだったとすると、十分遠くでは\gcd(d_1,\dots,d_k)倍が全部作れる。しかしそれがどのくらい遠くになるのかわからない。ここでかなり長い間詰まってしまった。

最終的には考え方を変え、作れる文字列の長さをq\times|\mathrm{needle}|+rと書いたときにrに対しqの最小値を求めることにした。dを全部求めておけば01BFSになるが、気づかなくて各d_iごとに|\mathrm{needle}|頂点の遷移を行った。多始点dijkstraだとTLEするので、頑張って始点のソートと01BFSで処理した。ここにも結構時間をかけてしまった。

残り時間がもう少ないのにまだ提出がないHardは、よくわからない構築。サンプルと同じ方法ではカバーできないパターンを一つだけ考えて実装を開始したが間に合わなかった。チャレンジフェーズは何もせず。結果は8位で2967→2910(-57)となった。思ったより下がらなくて助かった。

Hardの解説を読むと、サンプルにあるパターンと四畳半みたいなパターンの二つで全部作れると書いてある。四畳半については自分も思いついていたが、ちょっと一般化が足りていなかったようだ。

しばらくなろうを読んで午前4時半就寝。

02/23(金)

夢を見た。一瞬起きたタイミングでツイート。また正午から3時間ほどなろうを読んでいた記録がある。

午後6時起床。2時間ほどなろうを読んで布団から脱出し、シャワーを浴びて午後9時20分からyukicoder 418に出た。今日のコンテストは2時間半で直後のECRと少し被っているため、そちらが始まる前に全完するのが目標。

yukicoder contest 418 (Re: start!) - yukicoder

Aはよい。BはX_i\lt X_{i+1}となる条件が笛を鳴らす回数の下限として書けるので、それらの最大値が答え。CはN(N+1)\bmod{2M}を計算する。Dはいろいろな方法がありそうだが、自分は人の座標をsetに入れ、音を逆順に見ながらどんどん取り出して確定させていった。Eはよくわからないので必死に手計算してx_i,y_i,x_j,y_jによる表示を具体的に求めた。

Fは一般的なパターンを構築しようとして失敗。Mo's Algorithmのことを考えたらうまくいった。手計算によると、ブロックサイズはL/\sqrt Nくらいがよいらしい。怖かったので、k=500からデクリメントしながら答えが見つかるまでL/kを試した。

Gは解が基本N-1で、そこからprefixがMの倍数になるたびに1減っていく。そこで各prefixについてそこがMの倍数になれる回数を数え上げればよく、左右から前計算すれば求まる。右からも計算する必要があるのは、prefixがMの倍数になるなら同時にsuffixもMの倍数になるというのがAに関する三つ目の条件だから。

Hは大変。操作回数はCの最大値または最小値を取り除いてから\sum|C-x|の最小値を求めることで計算できる。ただしxが取り除いた最大値あるいは最小値に一致する場合は少しずらす必要があるのと、そもそもCの値が一種類しかないケースがコーナーとなる。Cを値の大小で半々に分け管理することで、追加クエリ・削除クエリを処理しながら\sum|C-x|の最小値を求めることができるが、これを頑張って拡張すると今回の問題も解ける。

1時間半で全完し目標達成、3位。たまたまノーペナだったがこれはかなり偉いようだ。まあyukicoderではペナルティは関係ない。少しの間日記を書いて過ごし、午後11時半からECR162に参加した。

Dashboard - Educational Codeforces Round 162 (Rated for Div. 2) - Codeforces

Aは右端のチップを操作し続けるのがよい。1回操作する度左端のチップと右端のチップが近づくので、初期状態でその間にあったフリーのセルの数が答え。Bは適当にシミュレーションしていればn秒以内に決着がつく。Cは1でない値をできるだけ減らし、1をインクリメントしたい。よって1の個数をk個とすると\sum(a_i-1)\ge kが必要条件。m\ge 2なら十分でもある。m=1の場合は不可能。

Dはi番目に隣接する適当な区間をマージしてa_iより大きくするのが目標。区間の条件としては、まずマージのために長さが1であるか2種類以上の値が登場していて、さらに総和がa_iを超えている必要がある。これを満たす端点を二分探索で求めた。Eはマージテクで木dp。

Fは最初二つ目の操作を誤読していた。shrinkで左の0が消え、reverseで右の0が消える。その後に行うswap操作はその前に持ってくることができるので、結局swapを繰り返した後二つ目の操作を高々1回行うとしてよい。0回行う場合は簡単なので1回行う場合を考える。

swapは難しいので1をk-1個選んで一斉に動かすと考える。全部の1を選べるならよい。そうでないときは両端から合わせてk-1個を選んで、その間にある0を埋めることになる。その結果として得られる文字列に二つ目の操作を行うと、\mathrm{rev}(s)の連続部分文字列の後ろに1がいくらか連続した形となる。SA+LCPによって\mathrm{rev}(s)の連続部分文字列の大小比較を行うと数値としての最小も求められる。

全完6位。自分と全く同じ解法だったtouristのCがHackされて戦々恐々としていたが、何かミスがあったようでいつの間にか復活していた。

www.youtube.com

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

02/24(土)

午後2時半起床。Universal Cupは今日の夜中に走る予定。ゆっくり二度寝……するわけでもなくずっと布団でなろうを読んでいた。

午後8時起床。食事して午後9時からABC342に出た。

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342） - AtCoder

Aはちょっと手間がかかる。150点がつけられただけはあった。Bは逆順列。愚直でもよい。Cはaからzに対しそれぞれどの文字に置き換えられたか持った。Dはsquare-freeにしたとき同じ値となるペアを数える。ここまでなら見たことがあるが、今回はA=0に注意しなければならない。サンプルにあって助かった。Eは駅Nからdijkstra。

Fはまずディーラーの戦略をシミュレートして最終的なyの確率分布を求める。それによってx=x'で操作を終えたときの勝率が計算できるため、xの降順に勝率が高くなるよう操作するかしないか決めていくことができる。これで解けることはすぐわかったが、yの確率分布を求める際imos法の遷移と累積和を同時に行おうとしてバグらせ、かなり手間取ってしまった。素直に遅延セグ木でぶん殴ればよかった。

Gはクエリ番号をセグ木のインデックスと見て数列のインデックスを舐めながら操作を乗せたり下ろしたりし、取得の度に一時的にキャンセルすればよいと考えた。しかし冷静になるとキャンセル回数が毎回Q回くらいになる可能性があって間に合わない。そこでクエリ平方分割を行い、毎回\sqrt Q個に抑えることにした。あとは実装を頑張る。

ランダムケースで試すと思ったより遅かったが、バケットサイズを調整して一度に処理するクエリを多くすると速くなった。どういうケースに弱いかわからないのでそこまで多くはせず、最終的には1500クエリごとで提出。ところが同時に行っていた定数倍高速化にミスがあって、サンプルすら通らないコードを投げてしまったらしい。修正してAC。3secだったのでまあまあ余裕があった。

56分1ペナで全完。Fに手間取ったと思っていたが、それよりGを瞬殺できなかったのがダメだったらしい。37位だった。Gはクエリを点(l,r)に乗せて[1,i]\times[i,N]を取得するという典型的な言い換えをすれば終わりだったらしい。そういうテクニックがあることを見知ってはいても、実は使えたことがない気がする。

コードゴルフはAのみ。ソートしたSの2文字目「でない」文字を探す。Nibblesにはfind indexとfind indicesがあって、今回は一か所見つけるだけなのでどちらでも同じに見えるが、後者でだけ使えるnotによってわざわざ2文字目「でない」文字を探す必要がなくなり縮んだ。

www.youtube.com

動画の投稿まで済ませ、午前0時からUniversal Cup 24回目、Chongqingセットに出た。

https://qoj.ac/contest/1530

チームでCFILAGKの7完、12位。自分はLとGを解いた。

最初にLを読み、解けそうだと感じて手で実験を始めた。risujirohさんのC、NyaanさんのFが通ったところで考察がまとまったので実装へ。しかし念のため愚直コードも書いて比較したところ落ちてしまった。一旦PCを空けて考察をチェックし、間違いを発見。NyaanさんのIが通ったところで再度実装に入り通した。

左端がR、右端がLの場合が非自明で、この場合文字列は/(R+L+)+/と分解できる。ランレングス圧縮した状態でRL、RLRL、RLRLRLのケースを手計算し条件を眺めたところ、一般の形がエスパーできたのでそれを実装したという感じ。詳しい条件は省略するが交代和が出てきた。実は文字列が開き括弧Rと閉じ括弧Lによって正しい括弧列になる場合後手勝ちらしい。

その後risujirohさんがAを通した。ここまでが簡単枠のようだ。

Gは、Lが固定されているなら、|L-h_i|が狭義単調減少したのち狭義単調増加するという条件になる。減少と増加が切り替わるインデックスをbと書くと、i\lt bか否かで|L-h_i|と|L-h_{i+1}|の大小関係が決まる。そしてこれは\frac{h_i+h_{i+1}}2とLの大小関係で表現できる。

ここでLを昇順に試すことにする。すると、しきい値\frac{h_i+h_{i+1}}2より大きくなるタイミングでiとbの大小関係が切り替わる。これを差分更新すればよさそう。i\lt bなるiが続く区間とi\ge bなるiが続く区間をそれぞれ管理しておくと、更新された点が関わるペア(u,v)を「l\le u\lt b\le rなる(u,v)」という形で記録できる。

ところで今触れなかったコーナーケースがある。それがh_i=h_{i+1}。実は|L-h_i|の最小値だけ同じ値が2回連続することが可能なのだ。逆に言えばそこでしか出現できないので、先ほどのlとrを求める際に注意深く扱えば対処は可能。

自分がGを実装する前からNyaanさんはKに取り組んでおり、MLEに苦しまされていたようだが無事通っていた。その間自分とrisujirohさんはDを考えていて、自分が解けたと主張。実装に移るも微妙な考察ミスがあったりして、30ケースから先に進めなかった。risujirohさんはNyaanさんと共にJを考えていたらしい。そちらは進捗なしとのこと。

感想戦。CFIは自明らしい。この3問は公式Discordによれば昔の中国ICPC地区大会から持ってきた問題とのことで、セットの中でもとりわけ簡単に見える。Aは概要を聞いてすぐ寄与を考える解法が思いついた。まあコンテスト中はノータッチだったのだし、感想戦で冴えを発揮してもしょうがない。

Kは永続平衡二分木と双対セグ木を使って通したそうだ。永続だからO(1)でコピーできて、平衡二分木だからO(\log)でマージができるのだろう。それならできそうな雰囲気はある。詳しい話は一切わからず。またクエリ3に対応できるよう平衡二分木を書き換えるのも大変そう。永続重み平衡木に書き換えたらMLEを回避できたと聞いた。

Persistent-Weight-Balanced-Tree(永続重み平衡木) | Luzhiled’s Library

感想戦後に追加で1時間ちょっと格闘し、Dが通った。基本的なアイディアはコンテスト中に出せていて、細かいところが詰め切れていなかった。

区間の端点0\dots Nを頂点だと思うことで、ノード[l,r)と辺l\leftrightarrow rを対応させ、L_iとR_iを連結にする問題と読み替える。まず最初に0\dots Nをすべて連結にしなければならないケースを考える。葉のほうから辺を使うか使わないか決めていったとき、ノード[l,m)と[m,r)を見た後はもうmと繋がる辺は存在しない。

この性質を用いて、ノード[l,r)以下の辺を見たときl\dots rが連結になる場合の数a、あるl\le i\lt rについてl\dots iとi+1\dots rが連結かつiとi+1が非連結になる場合の数bを持ち、下から決めていく。[l,m)に対し(a_x,b_x)、[m,r)に対し(a_y,b_y)があるとき、[l,r)に対しては辺l\leftrightarrow rも考慮して(a_z,b_z):=(2a_xa_y+a_xb_y+b_x a_y,a_xb_y+b_x a_y)となる。

さて、一般のケースではl\le i\lt mとm\le j\lt rについてi+1\dots jが孤立してもよいことがある。具体的にはその内と外にまたがる連結成分がない場合。これに対応するため、先ほどbを「あるl\le i\lt rについて」と定義したが、各l\le i\lt rについて個別に持っておくことにする。そして、今のようにb_{x,i}とb_{y,j}をマージできる場合、その積をb_{z,i}とb_{z,j}のどちらか一方に足す。

i+1\dots jが孤立してもよいことさえ分かっていれば、i\leftrightarrow i+1とj\leftrightarrow j+1のどちらかは繋がっていたと見なしても問題ないのだ。これで切れ目が増えていく問題は解消できる。愚直を書いたらWAは出なかった。コンテスト中は高速化も一緒にやろうとして、マージ可能条件を正しく扱えていなかった。

高速化については詳しく説明するのが困難。まずマージテクでiまたはjを全探索する。例えばiを全探索したとき、iやrをまたぐ連結成分が存在しないjの最大値はセグ木上の二分探索で求めることができる。またiを降順に見ると、実は使用不可能なjがどんどん増えていくので、それを適宜キャンセルしていける。

以上、O(N(\log N)^2)で解けた。問題文にはTL 1secと書いてあるが1759msで通っている。最初のACは1467msで、それからちょっと整理してみたら伸びてしまった。

Submission #339235 - QOJ.ac

朝になった。大学入試2次試験初日の朝。TLに京大のタテカンの写真が流れてきた。以下のツイートの写真2枚目にある「タテカンの元ネタ全部分かるやつガチで危機感持ったほうがいい」が大好き。確かに、ちゃんとネット断ちできていれば流行りのネタはわからないのか。

午前9時就寝。

02/25(日)

午後6時前には目を覚ましていた。今日は珍しくコンテストのない週末。腹も減ったし外食しに行こうかなと考えていたのだが、昨日シャワーを浴びずに寝てしまったので、外出するならその分をこなす必要がある。これが面倒で面倒で仕方なく、空きっ腹を抱えて寝転がりながらずっとなろうを読んだりKoP 5thの生配信を見たりしていた。

www.youtube.com

日付が変わる前にようやく布団を脱出。外出は諦めたからシャワーも寝る前でいいだろう。パスタを食べて日記を書き始めた。しばしばなろうに吸い寄せられつつもそこそこ書き進めて、午前10時前就寝。

今週は2555話まで進んだ。以前読んだことのあるのは2600話弱までだから、あと少しで知らない話が始まると思うと非常に楽しみ。と同時に、これだけ長大な話でしかも読んでから3年近く経ったにも拘わらず、要所要所で話を覚えているという点に、自分のことながら驚いていた。それだけ好みだということ。