週記（2024/07/15-2024/07/21）

07/15(月)

午後4時起床。今日は祝日である。

午後11時過ぎまで先週の週記を書いていた。うっかり週末をすべてなろうに捧げてしまったため全然出来上がっておらず、コンテスト部分が軒並み穴あきのまま投稿することになった。

午後11時半からはCF #958 div.2。

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

Aは1をk-1個作るように分割していくのがよいと考えてシミュレーションした。最後の状態からマージで元に戻すことを考えれば、最適な操作方法を考えずとも直ちに\lceil (N-1)/(K-1)\rceilが得られる。Bは連続する0それぞれに対して操作を行った後、全体を操作して1が残るか見る。0の個数と1の個数の差は[0,\dots,0]\rightarrow[0]でしか改善されない。

Cはnで立っているbitだけ取り出し、さらに0と1を反転して考えるとよい。条件は隣接2項のbitwise ANDが0かつ狭義単調減少ということになるから、MSBを少しずつ小さくしていくのが最適。末尾の0も含めて基本的にはk=\mathrm{popcnt}(n)+1が最長となり、nが2べきの場合だけa_1=0が許されないため1減る。

Dはモンスターごとに倒すラウンドを割り当てる問題として考える。頂点uにいるモンスターはラウンド\mathrm{deg}(u)+1までのどこかで確実に倒す機会が訪れるから、木dpの状態数はO(n)でよい。あとは計算量が壊れないように遷移する。区間更新を累積和にしたりと頑張ってみたが、取得がtop2だけでよいことを使えばもっと簡単だったようだ。

Eは要素の削除による差分を頑張って計算する。削除したとき区間の新たなMINとなる要素を一つ一つ見ていきたい。たくさんあるように思えたが、よく考えるとstackで累積MINを管理するテクで行うpopと対応がつくため、合計O(n)個しかなかった。あとは頑張って実装。削除する要素ではなく新たなMINとなる要素を起点に考えると、差分が発生する削除が高々2通りになってわかりやすかったようだ。

Fはnの位置を境に左右で分けるとまったく同じ構造をしている。空間計算量がO(n^2)でおさまるよう丁寧にdpしてマージするととりあえずO(n^5)が得られ、2次元畳み込みを行ったりして理論的にはO(n^3\log n)まで落ちたが、定数倍が重すぎてお話にならなかった。5完11位。

www.youtube.com

朝方、なろうの「臆病少女は世界を暗躍す。」を読了した。実力を完全に隠す主人公という触れ込みでハーメルンの捜索掲示板で紹介されていた作品。ネタバレになってしまうが、本当に隠しきったまま終わってびっくりした。完結を優先したのか回収されなかった要素が多く、キャラもイベントも何かありそうな気配がプンプンしていただけあって消化不良気味。

https://ncode.syosetu.com/n7693ci/

ハーメルンの「ローカル役でしかあがれない」を再読した。やはり面白い。稀に見るチートてんこ盛り主人公だが、すべての能力に「ローカル役」という一つの根っこがあるため、説得力があり、また能力を使いこなしているという印象を受ける。

syosetu.org

シャワーを浴びて布団に入り、ネット小説を漁ってまた1作読み始めた。午前11時半くらいに寝落ち。

07/16(火)

記録によれば午後7時から午後8時半、午後11時から午前3時にかけてなろうを読んでいたらしい。ほかの時間は寝ていた。

07/17(水)

この日は午前7時から午後3時、午後6時から午後7時、午後9時から午前3時にかけて読んでいたようだ。

07/18(木)

午前7時起床。なろうを読んでいたら正午になったので、シャワーを浴びてセミナーのため出発した。雨が降っていたので地下鉄で登校し、昼食は学食で摂った。

午後1時半からセミナー開始。今日は先週末行っていた数値計算の話だけで2時間使い切った。またここ最近はかなり前に用意した内容をじっくり進めていたが、さすがに時間をかけすぎているし、特に怪しかったり難しかったりする点はないため、スキップして来週から別の論文に基づいて話すことになった。つまり来週以降はちゃんと準備を行う必要があり、今週のようにずっとなろうを読んでいるような余裕はない。

その後後輩の発表。2次方程式を解いているが2次の係数が0だった場合はどうなるか、ゼロ除算が発生した場合はどのような解になるか、とか細かいところを聞いたら少しグダグダになってしまった。まあ壊れたりするようなことはなく、全部上手くいくことが確認できてよかった。午後6時過ぎに解散。

院生室に移動してしばらく喋っていたら学食が閉店しかけたので、慌てて駆け込み夕食を摂った。食後はまた院生室に戻り、午後9時半くらいになってようやく帰路に就いた。

帰宅してシャワーを浴び、tatyamさんのスライド「定数倍高速化の技術」を読んだ。低レイヤの話を丁寧に行うことで、いろんな定数倍高速化テクの原理を明らかにしており、大変参考になる。

定数倍高速化の技術 - Speaker Deck

午後11時半からCF #959 combinedに参加した。もともと3時間9問の予定だったはずがいつの間にか2時間8問になっていて不穏。

Dashboard - Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2) - Codeforces

Aはaの値を1ずつずらせばよい。nm=1の場合は不可能。Bは0のみからなるprefix以外を任意に書き換えられる。Cはlを固定して尺取りで次にg=0となるタイミングを求めると、ごく単純なdpができる。なんと尺取りに失敗して1WA。端を縮めるためのwhileをifにしていた。

Dは面白い。xの降順に張る辺を決めていくと、連結成分がちょうどx+1個あるため鳩ノ巣原理から辺の候補が必ず存在する。Eは葉を取り除いていくことで木のサイズを任意に調整できるため、nまたはnの適当なbitを下ろしてそれ未満をすべて立てた数のbitwise ORが得られる。

Fはc=0なる辺をいくつか削除し、残った辺が連結かつすべての頂点の次数が偶数になっていればよい。後者の条件については、次数が奇数の頂点をc=0の辺のみで繋ぎ、それぞれのパスのXORを取れば構築可能。しかし前者が問題。しばらく考えてふと問題文を読んだら「c=1の辺のみで」連結であることが保証されていた。制約に書いておいてほしい。オイラー閉路の復元はdfsして帰りがけ順に辺を並べると簡単。

Gはカス。下の桁からdpしたらO(nk)になっていた。Hは"aa"を聞くと(p+1)\bmod m=p+1が得られることに気づいたものの、mをどう求めるかわからず時間切れ。ハッシュ値がm-1またはそのくらい大きな値になるような文字列を作ろうとする乱択コードを書いていたが、後から提出したらWAだった。

7完67位で3010→2961(-49)。せっかく前回LGMになったのに、また落ちてしまった。1回も耐えられたことがない。今日のセットはcombinedにしてはかなり簡単だった。ボス問やそれに類する問題が爆破されたのだろうか。開催を強行せずに延期してほしかった。

www.youtube.com

なろうを読んで午前6時半ごろ寝落ち。

07/19(金)

午前9時過ぎ起床。今日は先生が招いたM2の学生のセミナーを聞きに行く。曇り空だが天気予報的にあまり雨が降りそうになかったので、念のためカッパを荷物に入れつつ原付で登校した。セミナーは10時開始で、購買も同じ時間に開くため、最初10分ほど抜けさせてもらい朝食を摂った。

午前の部はまず今日の目標について話し、前提となる知識や事前準備を済ませ、いよいよ目標の話が始まるというところで終了。内容はもちろん構成や時間配分も非常に良かった。発表者と先生とともに学食で昼食を摂り午後1時から再開。こちらは詳しい証明の内容がまだ理解しきれていなかったらしく、専ら主張の確認に留まった。あれこれ口出しするタイミングもあって、これはこれで楽しかった。

セミナー終了後は先生を交えて議論し、先生が帰宅されてからも二人で雑談を続けていた。数学科の学生ではなく情報科学研究科の数学教室の学生ということで、普段の活動をお互いに質問しあったり、博士課程進学について話したり。午後5時過ぎに解散し、少し院生室に顔を出して下山した。

川内キャンパスの購買でラノベを買い、夕食を摂って帰宅。疲れ果ていつの間にか床で寝落ちしていたが、午後9時に目覚ましで起きた。この目覚ましはyukicoderに向けてのもの。急いでシャワーを浴び、20分からyukicoder 437に出た。

yukicoder contest 437 ('09 Contest 002 day2) - yukicoder

Aは\gcdができるので、Sの要素が\gcd(T)で割り切れるか確認すればよい。Bは全然わからず、苦し紛れに絶対値が小さい2数を貪欲に足すシミュレーションを投げたら通った。解説を読んで考えてみたが、最小値と最大値をできるだけ使わないように操作すれば良いはず。

Cは実験してGrundy数を決定する。証明は知らない。Dは実験したが実験コードがバグっていて大変な目にあった。結論は簡単で、Nが2べきならXの偶奇が確定し、そうでないならSによらずNの偶奇で勝敗が決まる。1時間以上かけてACした。

残り時間が短いのでsolved数を見てEを飛ばした。FはO(N)の式を合わせたあとWolfram|Alphaに投げてO(\log\mathrm{mod})に。Gはさすがに親の顔より見たが、1次式の積を求めるパートも含め3分足らずで書けたのは偉い。入力受け取りでオーバーフローして1WAしつつ、ギリギリ修正が間に合って残り15秒で滑り込みAC。

6完13位。後からEとHをupsolveした。EはSに対する解の構造を丁寧に考えると非常にシンプルな結論となった。Hは\prod C=Nならよいらしい。そのようなCについての\sum Cの総和を求めることになり、Nの素因数ごとに数え上げや寄与の計算が行える。

なろうを読んで午前4時過ぎ寝落ち。

07/20(土)

正午から午後4時半までなろうを読んでいたらしい。二度寝して午後8時起床。食事を済ませ午後9時からABC363に参加した。

AtCoder Beginner Contest 363 - AtCoder

Aは100-(R\bmod 100)。BはP番目に髪の長い人が長さTになるまでの日数。Cは全探索。Dはまず桁数を求め、その後は算数で一発。EはBFS。Fはa\times\mathrm{rev}(a)の形をした数で何度か割ってみて、（十進表記で0を含まない）回文数が得られればよい。a\le\sqrt{N}を全部試して愚直にチェックするくらいしか思いつかなかったが、投げてみたら爆速だった。ただし復元でミスしてサンプルすら合っておらず、1WA。

Gはクエリがなければ優先度付きキューを使って日付の降順に見ることによってO(N\log N)で解ける。ここで何日目に何の仕事をして報酬を得たか管理しておくと、仕事の削除と仕事の追加に対応する差分更新が両方O(N)でできることに気づいた。仕事が削除されたら後ろから詰めていけばよく、仕事が追加されたら前のほうに押し出せばよい。このO(QN)を定数倍高速化することにした。

日付に対して仕事のIDだけでなくDとPも同時に持つと、ランダムアクセスが減るし、仕事をしない日も統一的に管理できて場合分けが減る。これは一つのポイントだと考えていたが、後から試してみたら1sec強の改善でしかなくTLE解消にはそれほど役立たなかったようだ。

一番大変なパートは、削除された仕事の代わりに行う仕事を探す部分らしい。報酬を得るタイミングがなくあぶれていて、Dがある程度大きいもののうち、Pが最大となる仕事を探したい。愚直にチェックしていては間に合わなかったのでsetを使ってみた。これであぶれている仕事をPの降順に取得できる。さらにDの判定を省略するため、適当な定数W:=1000を用意し、\lfloor D/W\rfloorで入れるsetを分けた。

これらの高速化により見事6sec弱で動作するコードが得られ、AC……したのは午後10時43分だった。3分ちょっと間に合わず6完、20位。コードゴルフではAのdcがNibblesに負けており愕然。2回出現する100をA0と書けるのは強いだろうと考えていたら、Nibblesではsaveとimplicit argにより1回しか出現していなかった。一方BはNibblesで勝ち。

C問題について、C++だとnext_permutationが重複を除いて列挙してくれることもあってかなり書きやすいが、一方スクリプト言語だとそもそもO(N!NK)をただ書くだけでは間に合わないらしい。コンテスト中もN\le 10はちょっと攻めているなと思っていた。

振り返りをしていたら午後11時半になったので、録画を止めずそのままCF #960 div.2に出た。

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

Aは奇数回出現する要素があれば先手勝ち、そうでなければ後手勝ち。Bはy番目からx番目までを+1で埋めるのが良さそう。その前後は和が0に近いほうが嬉しく、またa_{y-1}=a_{x+1}=-1なので、そのまま\pm 1を交互に並べる方法が思い浮かび、実際に条件を満たしている。

Cは1回操作すると列が単調増加になる。以降は後ろにどんどんずれていくだけかと思ったら、1回しか出現しない要素はずれずに消えてしまうようだ。しかしこれも2回目の操作でしか発生しないので、そこだけ愚直に計算すればよい。

Dは基本的に1行につき1回の操作が必要で、a=0の行や「2以下の数」「4以下の数偶数個」「2以下の数」という区間に対して1回ずつ得していく。これをもとにdpすればよい。遷移時の条件チェックをミスして1WA。

EはHLDをベースに解いた。heavy pathの上で二分探索を行いどんどん下に降りていく。判定に失敗した場合は二分探索の区間を親のほうに一つ伸ばす必要があるため、幅2から減らない可能性があり、そのときは手で場合分けをする必要があった。またheavy pathから降りるために子を一つ一つ聞くときは、部分木が小さく絶対にいないと判断できる子を飛ばした。

クエリ回数を一切見積もっていなかったので、E2に投げてチェックしていた。最初は二分探索の場合分けパートを真面目にやっておらず、同じheavy pathの上で何度も二分探索を繰り返していたようだ。E1の制約なら通るんじゃないかという誘惑を振り払ってコードを修正したら、これまで落ちていたケースを通過。pretestが全部終わるまで待つ時間は残っていなかったので、その時点でE1にも提出した。

何とかE1・E2共に通り、ギリギリ5完で36位。

www.youtube.com

午前9時くらいになって、最近読んでいたなろう「眠れる王」を読了した。主人公が追放されたり迫害されたりしないクラス転移ものということで、これもハーメルンの捜索掲示板で見つけた。この作品では主人公がクラスのまとめ役となり、そのまま早々に立国までしてしまう。自分にとってはこの展開や、その後立派に王として活躍する主人公が大好物だった。非常に面白かった。

https://ncode.syosetu.com/n7449em/

そのまま続編「傍らに異世界は転がっている」も読了した。単体でも読めるようにしようとしたらしく、前作のキャラがあまり大っぴらに登場せず残念。この先出る予定はあったようだが、そこまで話がたどり着く前にエタってしまっている。

https://ncode.syosetu.com/n8115hh/

「眠れる王」が非常に好みだったので似た作品を探そうと捜索掲示板で検索をかけたが、クラス転移の系列で紹介されているものばかりで、「王」という要素に注目したものは残念ながら見つからなかった。この状況では、以前からそういうキーワードでいろいろ検索していたのに「眠れる王」が見つからなかったのも納得。

午前0時半ごろ就寝。

07/21(日)

午後4時に目覚ましで起きた。AHC035が始まってしまっている。あまりに眠く布団から出られなかったため、スマホでコードゴルフだけして、30分ほどで二度寝した。

ALGO ARTIS Programming Contest 2024 Summer（AtCoder Heuristic Contest 035） - AtCoder

午後8時起床。シャワーを浴び、外出して油そばを食べ、ゲーセンで閉店まで遊んだ。今日は13クレプレイ。新曲の14+を端から触っていってAJ五つ、SSS+二つ、SSS一つを出した。どの譜面も数回程度しかプレイしていないのにポンポンとスコアが出て、自分が上手くなったかのような気分。

中でも初見プレイが上手かったものをツイートにまとめた。どれも譜面動画なら何度も見ていたが、まさか一発でこんなスコアが出るとは思わなかった。「《創造》 ～ Cries, beyond The End」はもう一度プレイしたらボロボロだったので、SSSは二度と出ないんじゃないだろうか。「オンソクデイズ!!」はこの次に2-1が出たので、まだ再現性がありそう。癖がついたら終わりではある。

ドンキに寄って帰宅。シャワーを浴びて朝方まで日記を書き、少しラノベを読んで午前9時半就寝。

今週はなろうに捧げた。来週からまた頑張ってラノベを読んでいきたい。