週記（2024/09/16-2024/09/22）

09/16(月)

午前5時起床。

布団で最近読み返していたハーメルン「じゃしんに愛され過ぎて夜しか眠れない」を読了した。やはり面白い。傲慢なくらい自信に満ち溢れていて実力と知名度が伴っている主人公の造形が好みだし、デスティニードローを駆使したカードバトルでの無双も見応えがある。

syosetu.org

起きて先週の週記を書いていたが、正午を回ったくらいでもう眠くなってきてしまった。諦めていったん寝ることにし、午後2時半くらいに仮眠に突入した。

数度の目覚ましを無視し、午後8時になってようやく起床。そこからまた週記を書き進めて日付が変わる前に投稿したが、コンテスト数個に加え日曜日の分が丸々穴あきになってしまった。

昨日チームメイトに発送した賞品のスマートウォッチがもう届いたらしい。こちらでも開封し、写真をTwitterに上げた。一足先に受け取ってはいたが、なんとなくタイミングを合わせてみた。続いてスマホに「Huaweiヘルスケア」アプリを入れて諸設定を済ませた。

何やら心拍数、血中酸素濃度、さらに謎のストレス値も計測できるらしい。自分が一番気になっているのは睡眠の記録である。いつも部屋が明るい中で寝ているし、時間もバラバラな現状、果たして睡眠の質はどのようになっているのだろうか。

また時計としての使い方も面白かった。どうやらディスプレイを上に向けて水平にすると勝手に画面が点灯するようだ。つまり腕に着けた状態で腕時計の文字盤を見るしぐさをすると、手を触れなくても時刻が確認できる。腕を下ろせば消灯するので内容が人目に触れることもあまりない。デフォルトの時計は見にくいが、着せ替え機能でシンプルなものにしておいた。

先週の週記に日曜日分とABCを追記した後、ラノベを読んだ。「悪役転生者は結婚したい」を読了。

面白かった。ヒロインの心を射止めようと努力しアタックする、恋愛に対し積極的な主人公に好感を抱いた。一方で悪役転生である必要性がよくわからなかった。原作主人公も原作ヒロインも人の話を聞かないどうしようもないキャラとして悪し様に描かれており、ゲームのメインキャラとして成立していたとは思えない。そこがかなり気になってしまった。

午前5時半就寝。

09/17(火)

午前8時少し前に起床。今日は東邦大学で行われるセミナーを聴講する予定である。寝不足で途轍もない不安があるが、こうなってしまったものはしょうがない。ただ残念なことに、せっかくスマートウォッチを着けて寝たのに睡眠時間が3時間未満だったため詳しい計測が行えなかった。

荷物を整え午前8時半出発。駅で立ち食いそばを食べて新幹線に乗り、東京駅で総武本線に乗り換え、正午前に津田沼駅に着いた。移動中はずっと本を読んでいた。時間に余裕があったので駅近くの本屋を少し長め、バスに乗車。午後0時半ごろセミナー会場の東邦大学習志野キャンパスに到着した。

まず学食で昼食を摂った。カレーを注文したが、東北大学からは消えて久しい福神漬けがまだ残っていて感動した。会計は東北大学生協の電子マネーが当然使えなかったので、現金。アプリが同じだけらしい。

午後1時にセミナー会場の教室に到着。30分ほどボーっとして、セミナーの開始時刻を迎えた。タイトルは「辺着色グラフと関連する代数構造」。

可換代数と組合せ論セミナー

内容になんだか既視感があったが、問題の定式化が昔Universal Cupで見た手法だった。もっと言うと、当時参考にしたこどふぉブログの「Colorful spanning tree」の話だった。ということでここまでの話が容易に理解できたため、最後まで話についていくことができた。講演者の方の共同研究者としてY.Y.さんが出てきてびっくり。

Login - QOJ.ac

[Tutorial] Matroid intersection in simple words - Codeforces

4時間弱で終了。懇親会は不参加の予定だったので、すぐさまバスに乗って津田沼駅前に戻ってきた。よこに連絡を取って東京で一緒に夜ご飯を食べることにしたが、その前に駅前でチュウニズムをプレイしておく。全国行脚である。

行きのバスの車内からAPINAが見えていたので、まずはそこに向かった。しかし残念ながらクレーンゲームと太鼓の達人しか置いていないタイプの店舗。仕方ないので少し歩いてシルクハットに入った。2台しかなく、しかも埋まっていたが、並んでみると一人帰ったので無事連コできた。3クレで称号「千葉勢」を獲得。

記録を確認すると、全国行脚で新しい県が埋まったのは実に6年ぶりらしい。ひとつ前に埋まったのは神奈川県で、大学一年生時のICPCで行ったときだった。そこから自分の行動範囲は一切広がっていないようだ。分かっていたこととはいえ、こうして突きつけられると思うところはある。

総武本線で東京に戻る道中、JOI一次予選の第1回が公開されていることに気づいたため、スマホで縮めた。Cのみsed、残りはNibbles。改行コードを1Bにするテクが必要なかったのはラッキーだった。またPascalでも実装し、すべて0msを出しておいた。

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

午後7時半過ぎ、予定より少し遅れて御茶ノ水駅に到着。よこと合流し、しばらく線路沿いを歩いて適当なラーメン屋に入った。

食後、帰りの新幹線までまだ時間があったので、秋葉原まで歩いてゲーセンに入った。こちらでも3クレプレイ。

秋葉原駅で解散し、東京駅に向かった。秋葉原駅を出たのは新幹線が発車する15分前だったが、二駅しか離れていないし乗り換えも慣れたものなので問題なく乗車に成功。車内では行きと同じく本を読んでいた。「池袋ウエストゲートパーク」17巻を読了。

コロナ禍初期、2020年夏から1年の間に発表された作品四つ。トラブルシューターの仕事は人と会わないとやっていけないから、あまり自粛しているような印象は受けなかったが、通行人・客が少ないとか店が夜遅くまで開いていないとか、随所にコロナ禍の描写が挟み込まれていた。まさにウィズ・コロナの小説。

次の巻はコロナ禍初期の、一番騒がれていた時期の話になるだろう。どのように描かれるのか気になる。

週記（2023/12/25-2023/12/31） - kotatsugameの日記

パターンとして、作品四つのうち最後のものは表題作であり、ページ数が少し多く内容も重厚である。この巻だとネット炎上の話。誹謗中傷した人を訴えたわけでもなければ改心させられたわけでもない、なんともスッキリしない結末だった。それ以外の三つはかなり軽快。特に二つ目の「グローバルリングのぶつかり男」は、多少ご都合主義的な側面もあったが主人公が大活躍していて好みである。

午後11時過ぎに仙台駅着。最近寒い気がしたので念のためパーカーを持って行ったのだが、東京で使わなかったのはもちろん仙台に帰ってきても半袖で過ごせる暖かさだったから、完全なお荷物だった。

帰宅してシャワーを浴び、しばらくラノベを読んで午前3時前に就寝。

09/18(水)

午前8時前起床。布団でラノベ「レベル0の無能探索者と蔑まれても実は世界最強です」2巻を読了した。

主人公は自分が強いことを自覚していないため、パーティーにおける自分の役割について悩んでみたり、メンバーのサポートこそが本懐だと結論付けてみたりしているが、何もかも縛りプレイとしか思えない。世界最強であるという設定がどこにも表れていなかった。残念。

正午から午後4時くらいまでは二度寝。起きてから、ついに計測に成功した睡眠を確認した。よくわからないが質はそう悪くないようでびっくり。まあ若さにものを言わせているだけな気もする。

しばらくスマホで動画を見て、午後5時過ぎに外出した。今日は数学科の友人と焼肉を食べる。店は2か月ほど前に新しくオープンした「焼肉きんぐ」。

「炙りすき焼カルビ」を食べたくて食べ放題コースのランクを上げたのだが、薄切りの肉は焼くのが難しく、かなり焦がしてしまった。また「きんぐカルビ」や「壺漬けドラゴンハラミ」など大きめの肉を網の上で切ろうとして、熱気でやけどしそうになった。普通のコースで十分。

午後8時解散。それからゲーセンに行き、閉店まで20クレ遊んだ。久しぶりに「Blue Noise」をプレイしたらいつの間にかラストを押せるようになっていたので、ちょっと頑張ってAJを出した。なんと99AJが出て精度も大満足。もともとSSS+8点という14+で下から2番目のスコアだったことを思うとすごい伸び幅だ。

ドンキに寄って帰宅。シャワーを浴びてラノベを2冊読んだ。

1冊目、「怠惰な悪辱貴族に転生した俺、シナリオをぶっ壊したら規格外の魔力で最凶になった」2巻。書籍版で追加されたエピソードだと思うが、舞踏会部分が好きではなかった。学校行事の運営に精を出したり上級生にからかわれたりする主人公は、ちょっと丸くなりすぎている。凶悪さがどこにも出ていなかった。その観点で言えば、本編もあまり尖ってはいなかったかもしれない。そちらはまだ許容範囲内だった。

2冊目、「悪の令嬢と十二の瞳」。信じられないくらい面白かった。次の段落はネタバレ注意。

終盤まではあらすじ通り普通の逆行転生モノで、それも十分面白かったのだが、オチが素晴らしかった。このようなストーリーを根底から覆す仕掛けは大好物であり、その存在を知らないまま読めたことはかなりの幸運だったと思う。帯の文言がいちおう匂わせっぽくなっているものの、結末を知らないとそうとはわからないだろう。読む前の自分は気にも留めていなかった。

こういう作品を書く著者なら、他の作品もストーリー・設定に依らず面白いことが期待できる。調べると、デビューがたった1年前なのにも関わらずすでに他に4シリーズも手掛けられていた。どれも新刊チェック時にあらすじを読んで買わないことに決めてしまったのを覚えている。今また出会えてよかった。

ということで既刊7冊の購入を決定。ついでに9月・10月の新刊チェックを行い、計27冊注文した。「誰が勇者を殺したか」シリーズ2冊は品切れ中だったので、いずれ本屋で手に入れてくる予定。

今年のYandex Cupの日程が出て、参加登録が始まっている。自分も登録した。職業を学生にしたら学年の選択肢にD1がなかったので「Postgraduate Program」を選択しておいたが、調べた感じ何か違うような気がする。まあ間違っていても大した問題にはならないだろう。

Yandex Cup — championship for developers

しばらくハーメルンを読んで午後1時就寝。

09/19(木)

午後7時半起床。布団でラノベを読んでいたが、3時間ほどでまた寝てしまった。ここで日記の日付を変えておく。

09/20(金)

午前2時半起床。ラノベを2冊読んだ。

1冊目、「こましゃくれり！！」。設定がびっくりするくらい「依存したがる彼女は僕の部屋に入り浸る」と似ている。以前ハーメルンで見かけたときは二つ目はいらないかなと思ってスルーしたが、なんとこちらも書籍化とのことで買ってみた。比較すると、こちらはかなり理性が失われているという印象を受けた。正直ライン越えだと思うクズ描写もあって、ちょっと肌に合わなかった。

2冊目、「家事代行のアルバイトを始めたら学園一の美少女の家族に気に入られちゃいました。」2巻。主人公の主婦力は1巻で十分描写したということなのか、2巻は主人公とヒロインの両片思いがメインだったように思う。ヒロイン宅でヒロインの家族を巻き込んで進行する点は特徴的かもしれないが、前提として雇用関係があるせいかまだ距離感が遠く、偽の恋人関係を始めたりもして、すれ違っていきそうな印象を受けた。

午後1時頃シャワーを浴び、生協へ。学食で食事して購買で本を買い帰ってきた。火曜日のセミナーに関する出張報告書を作成し、午後5時半に寝た。

5時間くらいで目を覚ましTLを見て、今日CFがあることに気づいた。しばらくラノベを読んで待ち、午後11時半からCF #973 div.2。

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

Aは毎秒\min(x,y)個の果物を処理できる。Bは符号を考えるとa_{n-1}のみ必ず負になる必要があり、それ以外は正にできるからこれが最適。

Cは細かいところがかなり面倒だった。最初に空文字列を用意し、sの部分文字列という状態を保ちながらクエリ2回で1文字ずつ伸ばしていく。ただし伸ばす方向を切り替えるタイミングで2回のロスが発生するため、これをカバーする必要がある。切り替えた後はクエリ1回で1文字伸ばせるので、少なくとも1回は減らせる。もう1回は初手の分で、最初に"0"を聞いて0が帰ってきたらsは全部1だと確定する。

Dは先頭から舐めることにより\min(a)の最大値が求まり、それを固定した状態で今度は後ろから舐めると\max(a)の最小値が求まる。これが最適。Eはprefixの長さと\gcdを持ってdpしたいが、状態数が多すぎる。そこでprefixの長さを持たず、代わりにdpの値を少し調整するとうまくいく。遷移は約数包除でちょっと大変。

F1は先手後手ともに勝敗が確定しない手が高々一通りしかないので、勝つチャンスが巡ってくるまではそれを採用して1手ずつ進めていけばよい。根とuを結ぶパスの上をお互いに1歩ずつ近づくような形になる。勝敗の判定は、各部分木について根からできるだけ長く続くパスの長さを前計算しておくと、セグ木と適当な区間取得で行える。

F2はパスuvをLCAで分割してそれぞれ解くと、根と始点を結ぶパスたちが重なる。あとはその上で頑張って並列に解く。先手後手ともに初めて勝てるのが何ターン目かを求めればよい。勝てるならば相手の頂点が根と始点を結ぶパス上でどの区間にいるか、というのが計算できるから、並列で行うのが効く。

ところがF2が合わない。そのままコンテストが終了し、6完10位となった。その後30分くらいかけてようやくどこが違うのか判明。前計算では根とuまたはvを結ぶパスの外しか考えておらず、例えばuの親を始点としたときに、後手が初手でuに降りるようなケースをカバーできていなかった。初手だけF1の方法で計算することにして対処した。

www.youtube.com

MHC2024のシーズン到来。Practice Roundが始まったので念のため参加しておいた。終了は来週火曜日なので、感想は来週の週記に。

Meta Hacker Cup - 2024 - Practice Round

朝方から日記を書いていたが、昼前にはハーメルンに移っていた。「幸運薬オーバードーズ少女、ホグワーツに行く」を読了。興味深い設定であり、どのように話を転がしていくのか気になった。

syosetu.org

次にラノベ「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」6巻を読了。面白かった。たしか5巻の時点でもあった描写だと思うが、外野が主人公と総理の対立を予想して動くのに対し、主人公は未来知識から総理には勝てないと判断して敵に回さないよう立ち回り、結果はしごを外された外野の人々が大損して痛快。この総理は元ネタが元ネタだし、描かれ方的にも主人公の頭を押さえつけるような政治が許容できるくらいの大物である。

午後3時就寝。

09/21(土)

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

UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372) - AtCoder

Aは問題名が問題になっている。sedで書いたらピリオドのエスケープを忘れて1WA。Bは3進法での展開を使う。これが最適なので、N\le 20であることはチェックしていない。Cは周り5文字だけ見る差分更新。Dは累積MAXをstackで管理するテク。Eはマージテクとsetで連結成分の頂点集合を管理した。

Fは辺N+1\dots N+Mのどれを直前に使ったか持ってdp。計算量はO(KM^2)であり、配列アクセスも飛び飛びのため1900msかかってびっくりした。dpの次元を入れ替えると1400msにはなった。GはCHTで凸包を作成し、floor_sumで内部の格子点を数えた。面倒だが書いてみると案外できる、といいつつ傾きが同じ直線の処理をミスって1WAした。

45分で全完、3位。コードゴルフはAとBをNibblesで書いたがどちらも負けた。

www.youtube.com

午後11時半からはCF #974 div.3。10分こどふぉった。

Dashboard - Codeforces Round 974 (Div. 3) - Codeforces

Aは言われたことを書く。Bはi^i\equiv i\pmod 2。Cはソートして\lfloor n/2\rfloor+1番目の値が\frac{x+\sum a}{2n}未満であればよい。この不等式を解く。ただしn\le 2のときは過半数と全体が一致するため不可能。Dは適当な尺取りですべての日程について計算する。

Eは頂点1とnからそれぞれ拡張dijkstraを行い、合流する頂点を全探索する。同じ馬を使ってしまう可能性があるが、このときはそもそも馬がいる頂点で合流するほうが得なので問題ない。Fは木dp。Gはシミュレーションで、同じ日に手に入れた牛乳を飲み続ける期間を算数によってO(1)で処理すれば十分高速。Hは各要素が偶数個ずつあればよく、これはZobrist hashで判定できる。

全完3位。

www.youtube.com

ラノベ「凶乱令嬢ニア・リストン」6巻を読了。面白かった。弟子の一人アンゼルに「外氣」を教えるシーンの主人公があまりにも格好良くて、ほんの数ページながら強烈な印象を残した。いまだ主人公は表に出ないし、暗闘でも強さの底は見えないが、さすがに慣れてきた。それでもなお面白いということで。

しばらく論文を読んでいたら猛烈な眠気がやってきたので布団に入った。しかしスマホを弄っているとなんだか目が冴えてきてしまい、起き上がってまたラノベを読んだ。「ネットの『推し』とリアルの『推し』が隣に引っ越してきた」3巻を読了。主人公とヒロイン3人で旅行に行く展開。アイドル声優もVTuberもその設定が活かせる出番はなく、有名人としての特別性が失われてしまっていた。

午後1時半就寝。

09/22(日)

午後6時半に目を覚まし、1時間ほどなろうを読んでからなぜか二度寝に入ってしまった。午後8時以降15分おきにセットしてあった目覚ましだが、止めてまた寝てを繰り返した結果、最終的な起床は午後8時45分までもつれ込んだ。危ないところだった。

午後9時からARC184。

AtCoder Regular Contest 184 - AtCoder

Aから難しかった。N-1回聞けば2種類に分割でき、サイズを見ることで特定できる。そこでもっと小さなブロック50個以上に区切り、同じことをしてみた。ブロックサイズを20にするとちょうど50個に分けられるからクエリは950回。しかしこれだと、ある一つのブロックに偽物10個が全部集まったとき区別できなかった。

サイズを少し変え、サイズ19のブロック51個とサイズ31のブロックを作るとうまくいった。偽物が二つ以上のブロックに集まれば、1ブロックには9個以下しかないため特定可能。一つのブロックに固まった場合も、10個と9個もしくは21個に分かれるから、これまた特定可能。ただしここの実装でミスして1WA。assertで落ちるはずなのにWAが返ってきたので戸惑った。

Bは面白かった。2でも3でも割れない数mに対し、2^a3^bmという形をした数のみを考え、これをすべてのmで行えばよい。また特に(m,N)=(1,\lfloor N/m\rfloor)として計算しても同じなので、O(\sqrt N)通りのn:=\lfloor N/m\rfloorで解いて、適切に係数を掛けて足し合わせれば答えが求まる。

nを固定したときにどう解くか考える。格子の座標(a,b)に2^a3^bを並べると、操作はちょうどL字型に並んだ3点をカバーすることとなる。これでn以下の点を埋め尽くせればよい。端から貪欲に置いていくのが良いと考えたが、出してみるとWAだった。

となるとルールベースで考えるのは筋がよくないだろう。幅が1+\lfloor\log_3 n\rfloor\le 19しかないため、bitDPできるのではないかと考えた。下位集合へのゼータ変換を使いつつ書いてみたらN=10^9でも1secしかかからなかったので提出、見事AC。計算量はわからない。

順位表を見るとDがたくさん解かれていたので、Cを飛ばしてそちらに進んだ。最初は選んだボールkも取り除かれるものだと勘違いしていたが、もしそうだったとしてもこのとき考えていた区間dpは役に立たない。しばらく考えて、残るボールの集合が一致するときにボールの選び方の重複を除くのが難しいことに気づいた。

操作するボールは左上から右下に並ぶので、その順にdpしていく。直前に操作したボールを状態として持ち、次に操作するボールへと遷移する。この遷移が可能かどうかというのを決めたい。選ぶボールを極小にする目的で「その操作で新しく取り除かれることになるボールがあるか」という条件を考えたが、これだとまだ重複してしまうようだ。サンプル2が強い。

面白いことに、極小ではなく極大だとうまくいった。つまり、遷移元のボールと遷移先のボールの間にあるボールで「それを選ぶ操作を加えても取り除かれるボールの集合が変化しない」ものがない場合のみ遷移を採用する。

普通に書くとO(N^4)で、取り除かれるボールの集合をbitsetで管理し定数倍高速化すれば十分間に合う。左上と右下に番兵を置くと実装がやりやすい。コンテスト中は左上にだけ置いていたので、最後の答えの集計に少し手こずってしまった。出したら一発AC。

残り12分でCの問題概要を読み、終了。ABDの3完で21位だった。BはO(\sqrt N)通りのnで解いたが、実際のところ2^a3^bという数にしか興味がないのでO((\log N)^2)通りでよいらしい。

www.youtube.com

その後CとEのupsolveをした。

Cは山折りと谷折りの0-indexedの列がOEIS A014707にある。コメントに「The regular paper-folding sequence」ともあるし間違いなさそう。このシンプルな定義を見れば、インデックスのbit列を見ることで山折りか谷折りか判定できることがわかる。あるいは、ほぼ同じ列であるA038189の説明を見てもよい。ここまではコンテスト中に考えていた。

A014707 - OEIS

A038189 - OEIS

実はもう考察の必要はない。i+A_kのbit列の下位桁が特定の形になっていてほしいという状況で、上位bitを弄る必要性は薄いのだから、「特定の形」を達成する最小のiを候補として計算すればよい。これは全体でO(N\log A)個存在し、それぞれfの計算にO(N)かかるため、間に合う。

Eは大変だった。一つのf(i,j)を求める方法を考えるのは役に立たない。とにかく実験。列の先頭要素を1とすると、すべての列はちょうど長さに対して定まる回数だけ操作することで元に戻ることが分かった。つまり同じ長さのサイクルがdisjointに存在し、同じサイクルに属する列たちが互いに移り合う。サイクルの中で一つ特徴的な列を決め、そこからの距離を求めたい。

辞書順最小の列を選んでみる。M=6の例を以下に書いたが、0-indexedで0,2^0,2^1,2^2番目が固定され、それ以外は任意となっている。ここからサイクルの個数が2べきだとわかる。M=6ではサイクル四つ、またサイクルの長さは8で、列の種類数は2^{M-1}=32=4\times 8とうまく成立している。

100000
100001
100100
100101

では任意の列からこの形にするにはどうすればよいか？これも実験によって見出した。i=0,1,\dotsの順に、列の2^i番目が1だった場合、操作を2^i回巻き戻せばよいのだ。これで同時にインデックスも計算できる。2^i回の操作がまとめてO(M)で行えるので、巻き戻しもやはりO(M)で可能。あとは適当にグループ分けして計算。

その後は日記を書いていた。この日は徹夜したので、日付はここで区切っておく。