10/20(月)

午前10時起床。先週の週記を書こうとしたが全く気が乗らず、ずっとなろうを読んでいた。

午後3時半からインターン先定例会に出席。進捗はなし。勉強会はKFoldとその亜種の実装についてだった。GroupKFoldは厳密に解くのが困難なため適当な貪欲を行うことになる。さらに正解ラベルの比率を揃えるStratifiedGroupKFoldは、ラベルの分散を見るなどかなり大変そうなことをしていた。

眠くなってきたので午後6時過ぎに布団に入ったら、仮眠だけのつもりだったのにうっかり次の日まで寝てしまった。先週の週記も投稿できず。

10/21(火)

日付が変わったころに目を覚まし、なろうに熱中。午前5時から3時間ほど寝て、また読み続けていた。

午前11時過ぎに「ラケッティア！　～異世界ゴッドファーザー繁盛記～」を読了。信じられないくらい面白かった。マフィアマニアの主人公が、転移先の異世界でファミリーのボスとなる話。会話がほぼギャグとマフィアに関する蘊蓄で構成されているため、普段はなんだかのんびりした雰囲気になっている。しかしその分、ボスとして振る舞う際のギャップがたまらなかった。

また、現実のエピソードを参考に異世界で様々なマフィア的行為を行うというストーリーも非常に面白い。お金や権力でなく、あくまでマフィアっぽいことを行うのが目標であり、その一貫性がこれまた魅力的だった。マフィアとして相応しいかどうかで様々な行為の可否を定めており、法とは独立した善性が感じられて、それに基づく勧善懲悪はとても爽快。

https://ncode.syosetu.com/n9866fb/

現在1400話近くあるうち残り300話で読むのが止まっていたのを、先週火曜日からまた読み始めて今日最新話までたどり着いたのだった。あまりに面白かったので、以前読んだ部分も再読したい。特にファミリーの拠点・カラヴァルヴァでの話は、主人公の影響力が強く発揮されていて好みのシーンが多い。そういうところだけ拾い読みすることにした。

午後5時前に就寝。

10/22(水)

午前2時起床、午後6時就寝。その間はずっと、昨日同様になろうを読んでいた。

10/23(木)

午前4時起床。なろうの再読は一段落した。

そろそろラノベも消化しなければ、と思って「煽り系ゲーム配信者（20歳）、配信の切り忘れによりいい人バレする。」4巻を読んだ。会話パートは相変わらず苦手だけど配信パートは面白い。

しばらく日記を書き、昼前にゲーセンに行った。数時間ほどプレイして昼飯時を避けてから昼食を食べに行こうと思っていたら、タイミングよくホスフィンに誘われて、「肉そばてノ字」に行った。

そばと中華麺のあいもりを注文。「田舎そば」と呼ばれる力強い麺が特徴で、やわめで注文したにもかかわらず非常に食べ応えがあった。普通サイズの麺量300gはラーメン屋なら満腹になる量だが、今日は若干物足りなかった。茹でる前後で重さがあまり変わらないのか、あるいはそもそも茹でた後の重さを言っていたのか。

食事 pic.twitter.com/XDQsz1Rxnl
— こたつがめ (@kotatsugame_t) 2025年10月23日

ゲーセンに戻ってまたプレイを続け、腕に限界が来た午後7時過ぎに、ホスフィンに教えてもらった近くのラーメン屋「中華そばHIKAEME」に行った。昼は物足りないと言っていたが空腹というわけでもなく、普通サイズを完食するのに少し苦労した。

食事 pic.twitter.com/V5WFtO7JPG
— こたつがめ (@kotatsugame_t) 2025年10月23日

今ゲーセンに戻っても腕が使い物にならないため、カフェに入って、閉店の午後9時まで本を読んで過ごした。

pic.twitter.com/rMQbokZWMz
— こたつがめ (@kotatsugame_t) 2025年10月23日

それから本日三回目のゲーセン。腕の疲れに加え眠さもあったのですぐ帰ろうかと思っていたが、プレイしていた筐体に撮影用の道具が備わっていることに気づいたため、久しぶりに手元を撮っていた。結局閉店までいて、今日一日で合計45クレプレイ。内訳は10＋20＋15。

「LibrariA」のSSS+が出た。手元動画もある。先々週に初めてプレイしたときから苦手だった107小節から109小節は、右の黄タップとそれ以外で分業して取った。ミスが出るのは右手のリズムがずれたものと考えていたが、撮影した手元動画を見るとなんとエアーが抜けていた。

「Last Celebration」は最後のタップスライドが下手くそすぎてまだAJを出せていなかったが、片手ずつでべちゃっと押したら通って拍子抜け。「Galaxy Collapse」はラストの速すぎるフリックが追い付かないものの、それ以外を噛み合わせてなんとかSSSを出した。この譜面が新曲枠に入って、今バージョンでもレート17を達成。

今日は45クレ pic.twitter.com/5tFTV5lyRZ
— こたつがめ (@kotatsugame_t) 2025年10月23日

撮った手元動画は以下のツリーにまとめてある。「ライアーダンサー」は曲も譜面も好きなので閉店前のラスクレで頻繁に選曲しているが、今日動画を撮ったら一発で理論値が出た。通算四回目で、宮城県ランキングのトップに立った。

LibrariA 1-1 SSS+ 手元 pic.twitter.com/Lsg9CbruKA
— こたつがめ (@kotatsugame_t) 2025年10月23日

ドンキに寄って日付が変わってから帰宅。つい最近、仙台市中心部でも熊が目撃された。繁華街や大通りはこの時間でも多少の交通量があるため安心できるものの、家の近くまで来ると人通りがなくなる。非常に怖い思いをしながらの帰り道となった。

シャワーを浴びてから撮った動画をツイートした。課金で長尺の動画をツイートできるようになったせいか編集画面では2分20秒以上の区間を選択できてしまい、制限に収めるため手で調整する必要が生じて面倒になっていた。

午前5時就寝。

10/24(金)

午前10時半起床。

ハーメルンの日間ランキングから「一般男性、TS令嬢転生(嫌々)からの圧倒的ダラダラ異世界無双」を読んだ。序盤から他者視点で主人公の特異性を語るパートが挟まれているが、今のところは頭でっかちで無双に繋がりそうには見えない。

syosetu.org

次に、昨日読んでいた「かくりよの宿飯」13巻を読み切った。天神屋の社員旅行でメインキャラクターが揃って現世にやってくる。外伝だから楽しい話ばかりかと思いきや、主人公の母・祖父・新キャラのいとこに関わる少し重いストーリーがメインで、本編の補足になっていた。同作者の別シリーズ「浅草鬼嫁日記」の主人公カップルと遭遇するシーンは、どちらも読んでいる身としてかなり興奮した。

しばらくラノベを読んで、午後8時から3時間半ほど仮眠し、CF #1061 div.2に参加。

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

Aは $(1,1,m-2)$ と分割していくべき。BはタイプBが存在する場合、 $O(n\log a)$ でシミュレートが終了する。Cは全要素を $g$ の倍数にしようとしたとき、 $4g$ 以上の値ならSplit操作で二つの $g$ の倍数にすることができる。そこで $[1,4g)\setminus\{g,2g,3g\}$ をカウント。

Dは $x$ を2べきにして各bitをそれぞれ特定する。 $p$ におけるインデックスと対応する値の集合が分かっていれば、 $n$ 以外をすべて聞くことで残りが判明する。さらにこのとき、聞いたbitが立っているかどうかで集合を二分割することができて、片方は捨ててよい。

下のbitから特定していくと、集合のサイズがそれぞれ $n,\lceil n/2\rceil,\lceil n/4\rceil,\dots$ となり、毎回それより1だけ少ない回数のクエリを投げるので制限に収まる。うっかり上のbitから特定してしまうと $3n$ 回くらいかかる。1WA。

Eは初手を全探索。以降は後手がlockした数に対し、先手は値が最大となる相方を削除するため、二番目に大きくなる相方が採用される。一つ削除した状態で「二番目に大きくなる相方」とは元の列においては二番目または三番目なので、それらをあらかじめ求めて置き、三番目が採用されるタイミングだけセグ木の1点更新で書き換えた。合計 $2n$ 回なので十分高速。

Fは最小値をできるだけ先頭に近い位置に置く貪欲が正当らしい。実験で確かめた。F1は毎回どのインデックスに最小値を置けるかチェックすることができる。チェックすべきは自身がprefix minであることと、値の偶奇。

F2はこの判定を遅延セグ木で行った。偶奇は分けてデータを持ち、操作対象になった要素だけflipする。インデックスに対して値を持つとflipすべき要素がバラバラに並んでしまうが、値に対してインデックスを持てば区間クエリになる。prefix minの判定はこの持ち方でも行える。

残り3分で全完して8位。

www.youtube.com

本日、大西拓磨さんらが運営するYouTubeチャンネルに競技プログラミングの動画が上がったが、コードゴルフの文脈で自分の提出が一瞬写っていたらしい。

突然の @kotatsugame_t すき pic.twitter.com/3FWX30S26h
— 小川(ちいかわ) (@_LiSa0) 2025年10月24日

www.youtube.com

ラノベ「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」7巻を読了。この巻はずっとオカルトの話をしていた。神様を手厚く祭るだけならともかく、大真面目に超常現象を描かれるとどう受け取っていいのかわからなくなる。自分の知覚する現代社会ではない。

午前8時就寝。

10/25(土)

午後1時半起床。午後2時からUniversal Cup 3回目、Polar Grand Prixに出た。3回連続どころか来週行われる4回目もRatedとアナウンスされている。一応Unrated回も枠だけ用意されているものの、日時は未定のようだ。

https://qoj.ac/contest/2559

書く

シャワーを浴びて午後9時からABC429に参加。

Polaris.AI Programming Contest 2025（AtCoder Beginner Contest 429） - AtCoder

A、Bはよい。Cは二種類以下のものからちょうど一種類のものを引くというかなり面倒なことをしてしまった。Dは尺取り。列を二倍にした後も端のカウントのタイミングでそこそこ頭を壊していた。Eは多始点かつ上位二件を持つBFS。dijkstraとは違い1st maxが2nd maxにずれる遷移はない。Fは列が常に単調増加なためdpで解ける。トロピカル半環上の行列積をセグ木に乗せて1点更新に対応。

Gは任意mod BSGSの前処理と同じ気持ちで、 $G:=\gcd(R,X^L)=\gcd(R,X^{L+1})$ となるような $L=O(\log R)$ を取る。すると $d\ge L$ に対しては $(X^d\bmod R)=G\times\left(\frac{X^L}{G}\cdot X^{d-L}\bmod{\frac{R}{G}}\right)$ が成立し、 $\gcd(X,R/G)=1$ より $X^{-1}\bmod{\frac{R}{G}}$ が存在するため計算できそう。

$d=(Ak+B)\bmod M$ として、 $d=0,\dots,L-1$ についてはそれぞれfloor_sumで $k$ をカウントできる。 $d\ge L$ は平方分割を用いて $X^{(d_1+d_2)\bmod M}\bmod R$ の計算に帰着し、 $X^{-M}\bmod{\frac{R}{G}}$ を掛けるものと掛けないものに分けて和を取った。計算量は $O(\log R\log M+\sqrt N(\log N+\log M))$ 。

80分で全完して2位。自分のGの解法は途中までMMNMMさんのユーザ解説と同じ。平方分割パートはfloor_sumのモノイド積版なるものに置き換えられるらしい。その存在を知らなかった。

www.youtube.com

午前1時半就寝。

10/26(日)

午前6時起床。

AtCoder Japan Openのホテルを取って参加登録フォームを記入した。ホテルが高い後泊を友人宅にお願いし、前泊は会場と非常に近い「アパホテル〈渋谷道玄坂上〉」に決めた。高いほうの朝食付きプランにすると黒毛和牛すき焼きを食べられるようだが、このために＋2200円のプランにするのは申し訳ないし、そもそも朝から重過ぎるだろうということで止しておいた。

ラノベの新刊チェックを行い、21冊注文した。本当はもう3冊ピックアップしてあるが、それらは大学生協で買うには少し勇気が必要なもの、つまり表紙イラストが扇情的なラノベなので、後日書店に出向いて買うことにしたい。

ハーメルンの「『星天』」が書籍化すると知ってひっくり返った。発売日を十日後に控えた今日朝の時点で、まだ作者Twitterでもハーメルンでも告知されておらず、感想欄にも気付いている人がいない。更新も一年以上空いているが、一応今日から再開されるというアナウンスだけがあった。好きな作品なので、初動で失敗しないことを願う。

www.kadokawa.co.jp

syosetu.org

昼まで日記を書いたあと、午後はラノベを読んでいた。「クラスで2番目に可愛い女の子と友だちになった」7巻を読了。かなり前から「クラスで1番目に可愛い女の子」が主人公に横恋慕していた様子だったが、ついに決着。主人公が今の彼女を深く愛しており、愛が行き過ぎて話がこじれつつも最終的には希望を残さないようきっぱりと振った。一途で好印象。ハーレム展開とか考えてニヤニヤしていたことを反省した。

どこかで仮眠しようと思っていたのにいつの間にか午後6時になってしまい、しかも今更眠気がやってきた。逆らわず入眠して、午後8時45分起床。起きてから3時間くらい経たないと脳が活性化しないという話は聞いたことがあるため、AGCの日は午後6時に起きることを目指しているのだが、成功した試しがない。

午後9時からAGC074。ついにAI使用が禁止されたためか配点は控えめで、ARC div.1と同じくらいに見える。

AtCoder Grand Contest 074 - AtCoder

Aは $P$ をトポロジカルソートの結果だと思って頂点を並べ、その間に辺を張ってサンプルを観察した。どうも互いに交換可能な区間、つまり辺を含まない極大な区間が重要そう。なぜならそのうち二点の $P$ が不明ならswapできてしまうから。逆にこれさえ回避すればOKだとするなら、伝えない $P$ を先頭から貪欲に選ぶことで最適解が出る。

証明していない部分があるものの自信はあるし、ペナルティ率もそれほど高くは見えない。提出したら通った。考察を終えた30分時点ではsolved数が40人ちょっとだったのに、それから10分後にACしたときには倍増していてひっくり返った。出だしはあまり良くない。

Bは途中まで操作回数の制限を忘れていたのがうまく作用した。操作回数を無視するなら、実は $(0,1)$ と $(1,0)$ のswapだけで任意の操作を再現できる。特に、操作によって転倒数は不変。この条件自体は操作を直接観察することでも示すことができるが、そもそも転倒数に注目できるか、という点で差があるものと思う。ちなみにこの事実は、紙の上で示したあと実験でも確認している。

それから、またしても実験によって、和と転倒数が一致していれば必ず変換可能だということをエスパー。ここで操作回数に制限があることをようやく思い出した。 $\lfloor N/2\rfloor$ は非常に少なく、一手で二文字ずつ揃える必要がある。

しかし転倒数の条件がある今、もっと良い見方が考えられる。01列の転倒数が1のインデックスの集合と密接に関わっていることを思い出すと、一手で1を一つ揃えるという解釈のほうが有望そう。もし1の個数が多いなら、全体をflipすればよい。

転倒数が等しいなら、ある1が右に移動するとき別の1が同じだけ左に移動している。左右への移動をペアにすると、 $(1,0,\dots,0)$ と $(0,\dots,0,1)$ のswapで1の移動が再現できる。特に、右に移動する1のうち最右のものと左に移動する1のうち最左のものをペアにすれば、swap一回で短いほうの移動を必ず完了できる。これで解けた。

実装にはしこたまassertを入れ、小さいケースを全部入力することも行ったが、得られた解のチェックは行わずサンプルを手で確認するのみに留めておいた。それだけ考察と実装に自信があったということ。出したら無事通った。実験をやりすぎて手間取ってしまったという印象だったため、21位まで浮上したことにはびっくりした。

Cは制約の $2^{30}$ と $N\le 1024=2^{10}$ から、3bit追加して $N$ を二倍にする方針を考えた。正確には $N\rightarrow 2N$ に2bit、 $N\rightarrow N+1$ に1bit使った。

$N$ における解 $(P,A)$ があったとき、 $A'=(2A_1,2A_1+1,2A_2,\dots)$ とすれば $P=2P_i+1$ でLISの長さ $i$ が、 $P=2P_i$ で $2i$ が達成できる。よって問題は $N$ より大の奇数長。奇数を $2i-1$ で作る方針を長い間考えていたが、 $2i+1$ に着目するのが正解である。つまり、長さ $2i$ のLISに一つ要素を追加することができればよい。

$N$ における解について、「長さ $\ell\lt N$ のLISが $A_N$ を使わないように取れる」場合、 $A'$ の末尾の要素に十分大きなbitを追加することで一つ延長できる。そこで、この条件も満たすように列を構成することにした。帰納法の仮定を増やすのと同じで、これで問題なく議論が回った。ただし、上にbitを追加するのは $A'$ の末尾から二番目の要素になる。

これで $A$ の上下に1bitずつ追加して $N\rightarrow 2N$ ができるようになった。あとは $N\rightarrow N+1$ だが、 $A'=(0,2A_1+1,2A_2+1,\dots)$ とすればよい。これでもともとのLISの長さはすべて1増える。 $P$ として全bitが立っているものを取れば、長さをちょうど1とすることは簡単。

実装して、すべての $N$ でチェックして、提出。無事通ったが順位は先ほどと同じ21位だった。これでもノーペナのおかげで数人抜かしている。

残りの時間で一つ順位を落とし、3完22位で終了。パフォーマンス3216、レートは2843→2886(+43)と久しぶりにしっかり伸びてくれた。

www.youtube.com

午前3時就寝。