12/22(月)

午後3時起床。半からインターン先定例会に出席した。今年最後となるが、報告できることは何もない。勉強会はStable Diffusionの紹介だった。

夜まで週記を書いていた。Yandex Cupの期間中の分もとりあえず完成させることはできたが、参加記として満足の行くものに仕上げるため、日記パートとは別にもうちょっと文章を書いておきたい。そこまでは流石に間に合わないため、諦めて出発前日の火曜日まで二日分だけの週記を投稿した。

そのあと参加記を書き進めて、午前7時就寝。

12/23(火)

正午起床。

川内キャンパスでnononさんと待ち合わせ、Yandex Cupと被って欠席してしまったICPC横浜大会のスポンサーグッズを受け取った。コーチ用Tシャツは用意されていなかったようで残念。

欠席したICPCのスポンサーグッズを貰った。コーチ用Tシャツはなかったらしい😢 pic.twitter.com/8uMmjObST9
— こたつがめ (@kotatsugame_t) 2025年12月24日

購買で帰省用の新幹線切符を取った。来週月曜日に帰る予定だが、北陸新幹線はすでにかなり混雑しており、終電かその一本前しか残っていなかった。ギリギリセーフだったとも言える。朝早いほうが空いていると思っていたので、逆と知りびっくりした。

食事してラノベを受け取り帰宅。しばらく参加記を書いたらゲーセンに行こうと思っていたが、眠くてどちらもできず布団に突っ伏してしまった。

寝て起きたら午後10時前。もう外に出る時間ではない。しばらくハーメルンを読み、午後11時半からCF #1071 div.3に出た。久しぶりに10分こどふぉった。

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

Aは $kx+1$ 。Bはprefixとsuffixをそれぞれ前計算したが、差分更新でよかった。Cは $a$ がソート済みだとして、 $x=a_1$ で操作できればOK、そうでないなら $x=a_2-a_1$ で操作して $a_2$ を $a_1$ にする必要がある。結局 $\max(a_1,a_2-a_1)$ が答え。Dは $2^k-1$ を含む数を $k$ の降順に並べていく。

Eは難しい。どちらかの党は、その支持者しかいない地区でしか勝たないとして良い。二通り決め打ち、残りは党Aの支持者と党Bの支持者をペアにして割り当てる要領で地区の人数制限を満たす。

Fは頂点1からの距離 $\bmod 3$ で色を決めるくらいしかできそうになく、実際それでよい。二部グラフなので隣接する色は高々二色であり、そこから自分の色もわかるのでどちらが近いか確定する。

Gは盤面の隣り合う角を二マス特定する。最初に適当な点から最遠点を調べることで一マス確定。そのマスからの距離を調べると二マス目の候補は $n$ 個になり、角に隣接するマスからの距離も調べることで区別できる。そうして得られたマスからの距離もすべて調べると、 $3n^2+n$ クエリで答えられる。

Hは加算する値の列を適当に分解すると、間隔が2べきの等差数列 $\log$ 本になる。それぞれimos法で処理すれば $O(q\log n)$ 。

1時間半ほどで全完して12位。

www.youtube.com

Puzzle Square JPで巨大な「へやわけ」を解き始めた。どうせすぐに手詰まりになるだろうなと思いつつチマチマやっていたら、案外先へ進めたので途中で投げ出すのが惜しくなった。そのままうっかり徹夜。

12/24(水)

9時間かけてついに全マス埋めると、なんと破綻していた。赤色のひと繋がりのマスは解き始めの段階で盤面の上辺に接地しており、そこからジグザグに伸ばしていくのが解き筋になっているが、最後の最後に左辺にも接地してしまった。数十手巻き戻して確認してもミスは見当たらない。それ以上遡る気力はなく、諦めてしまった。

9時間かけて解き進めたへやわけが破綻して本当に泣いているhttps://t.co/64MQ2Ukcfz pic.twitter.com/tKiORw0aNG
— こたつがめ (@kotatsugame_t) 2025年12月24日

しばらく参加記を書いて、午後7時からクリスマスコンテストに出た。

Xmas Contest 2025 - AtCoder

Aは黒マスごとに畳み込みを行うと、黒マスの数を $B$ として $BK\log K$ が達成できる。こんなのが通るわけはないから、黒マスをうまく長方形に分割して畳み込みの回数を減らすのだろうと思った。そういう面倒な手作業を要求してくるのは毎年恒例のこと。

ただそれはやりたくなかったので、周波数領域で値を管理し離散フーリエ変換の回数を減らす高速化を試してみた。すると、 $i+j$ ごとに周波数を重ね合わせてから戻してもうまく行くことに気づいた。これによりオーダーレベルでの改善がなされ、画像の幅を $W:=200$ として $O(WK\log K+BK)$ が得られた。

Bは実験すると $m$ がフィボナッチ数列になっていた。1が隣接しない文字列の数と等しいが、それには気づかず、ただ $N-1$ と $N-2$ のパターンから再帰的に作る方法だけ考えていた。結構自由度があって、実験結果からは見えづらかったものの、たくさん解かれているので流石に解けるはずと信じて考えたら見つかった。

solved数を見てD……には手も足も出なかったのでEに取り組んだ。法が3¹⁹なのが気になる。別に離散フーリエ変換しやすいというわけでもなさそう。法が3だったらどうなるか、その結果を法が3²の場合に持ち上げられるか、など考えていたら、 $q\bmod 3$ を固定したうえで $\lfloor q/3\rfloor$ の多項式として展開する方法を思いついた。

3完14位。3問も解くことができて嬉しい。また解いた範囲だけなら手作業をほぼ要求されなかったため楽しかった。

大家さんからケーキの配布があった。

食事 pic.twitter.com/7qLMn8mgPW
— こたつがめ (@kotatsugame_t) 2025年12月24日

Yandex Cupの参加記を仕上げ、ついに投稿した。もっとたくさん書きたかったことがあるような気もする。しかしここ数日考えていて思い出せなかったならもう仕方がないだろう。ここ数年海外オンサイトに何度か参加させてもらっているが、参加記を書き上げることができたのは初めて。

kotatsugame.hatenablog.com

明日はホスフィンとランチを食べ、家飲みする。部屋の掃除をして午前5時就寝。

12/25(木)

午前11時前起床、出発。

魚介とワインのお店「fill」で、「クリスマスランチコース」を楽しんだ。ランチタイムの客は、テイクアウトを除けば我々一組のみだった。

食事 pic.twitter.com/poDmlBeWrZ
— こたつがめ (@kotatsugame_t) 2025年12月25日

ドリンクはお互いノンアルコール。自分の選んだ白ブドウジュースは白ワインみたいなグラスで出てきた。量が少ないと思ったが、非常に濃厚な甘さだったためこれで十分。

海鮮パフェは下からひよこ豆のムース、人参のソース、蟹・海老・帆立。透明なジュレは酸味があり、蟹を三杯酢で食べるような感じだった。器にギリギリまで盛られていたので上の具材から順に食べ進める必要があり、全体としての味わいはよくわからない。

食事 pic.twitter.com/LFiy320Ghu
— こたつがめ (@kotatsugame_t) 2025年12月25日

魚料理は真鯛のポーピエット。エリンギ、チーズ、鯛が横に積み重なっており、鯛は柔らかく調理されていたため切るのが難しかった。添えられたビーツのアリゴの甘さがいい感じ。肉料理は蝦夷鹿のロースト。

デザートはごぼうのフォンダンショコラと、トンカの豆アイス。黄色いモジャモジャがごぼうだった。金箔もかかっていて豪華な飾り立てだが、味への寄与はないように思う。下には焼き固めたメレンゲが隠れていた。

アイスは非常に美味しかった。第一印象では控えめな味だが、あとに残らない甘さがしっかりある。さっぱりしているとも感じられた。

ドンキと大学生協に寄って帰宅。ホスフィンにイスタンブール土産のお守りを渡したあと、家飲み開始。

飲酒します pic.twitter.com/6489hQBaKN
— こたつがめ (@kotatsugame_t) 2025年12月25日

前回の続きで「逆転裁判2」の3話からスタートした。前回買ったゲームパッドがどうやって接続しても不安定で、ワイヤレスキーボードでのプレイとなった。

今日は「逆転裁判2」の最初からスタートした。
週記（2025/07/07-2025/07/13） - kotatsugameの日記

3話はコショウが引き起こした事件や殺害トリックにはすぐ気づけたものの、実際に法廷でその話が登場するまで結構かかり、焦れて眠くなってしまった。また理論立てて考えるというより、登場する物品から適当なストーリーをでっち上げているのに近く、人間関係や悪意の有無については大ハズレだった。

午後9時過ぎにラーメンを食べに出かけた。途中で光のページェントを通りかかり、写真を一枚。非常に明るくて、近隣に住んでいたらたまったものじゃないだろうと思ったが、ちゃんと午後10時に消灯するらしい。タイミングよくその瞬間も見ることができた。

光のページェント！この数分後に消灯でタイミング良かった pic.twitter.com/mNpKo1Vp3m
— こたつがめ (@kotatsugame_t) 2025年12月25日

店は「麺屋58」。中華そばを選んだ。ホスフィンがせっかく紹介してくれたお店だが、残念ながら刺さらず。

食事 pic.twitter.com/3Uvaj1iCEN
— こたつがめ (@kotatsugame_t) 2025年12月25日

帰ってきて4話をプレイした。「逆転裁判2」の最終話だけあって非常に重く、序盤は証言のどれが誰を指していて何がいつ効いてくるのかまったくわからない。そのうち寝てしまったようで、起きたらホスフィンがある程度進めてくれていた。それからは最後まで二人でプレイ。かなり難しくて、ところどころ攻略サイトを見た。

あとはYouTubeを見つつ残ったお酒を処理して、午前4時半解散。

焼酎と書いてあるものは度数が高くほとんど飲まなかったが、それ以外は瓶を空けることができた。度数控えめの果実酒ばかり飲んでいたので酔いはあまりなく、単に睡眠不足でしばしば寝てしまったようだ。毎回のことなので流石に学習すべき。

部屋の掃除をして午前6時就寝。

12/26(金)

3時間ほどの中途覚醒を挟みつつ午後5時起床。部屋の状態を元に戻し、空き瓶をゴミに出した。少しだけ雪が降っていた。

集中講義のレポートの締め切り当日になってしまったので、ササッと仕上げて提出した。

シャワーを浴びて午後8時からUniversal Cupを走った。Extra Stage 3のOsijekセットで、本来先週土曜日に走る予定だったものである。

https://qoj.ac/contest/2757

この時間からUniversal Cupを走る予定だったが、まだコンテストの準備ができていなかった。
週記（2025/12/15-2025/12/21） - kotatsugameの日記

書く

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

12/27(土)

午前11時半に目を覚ました。ハーメルンを開いてしまい二度寝失敗。

午後2時からUniversal Cup 10回目、Grand Prix of Wrocławに出た。ポーランドの都市「ウロツワフ」で、ポーランド語の「ł」は「w」と発音するらしい。

https://qoj.ac/contest/2814

書く

午後9時からはABC438。

https://atcoder.jp/contests/abc438

Aは苦手な算数を要求されて手間取った。Bはよい。Cは貪欲に操作してもよい。Dは耳dp。Eはfunctional graphを作り、木とサイクルでそれぞれ求めた。非常に面倒だった。Fは $f(i,j)\ge k$ となる $(i,j)$ を $k=1,\dots,N$ で数えればよい。 $k=1$ だけ特別扱いし、ほかは頂点0と頂点1を結ぶパスを軸にして求めた。

Gは575点なのになかなか解けず苦しんだ。 $\gcd(N,M)=1$ のケースに帰着し、値をdistinctだと思って $\min$ を固定したところで長時間詰まっていたが、残り20分で $B_{(a+kN)\bmod M}$ が区間をなすよう並べ替えておけることに気づいた。急いで実装したら幸いバグもほとんど生まず、なんとか間に合った。

95分で全完して52位。振り返りの際にEがダブリングで解けると気づいてひっくり返った。まったく同じ問題で同様に面倒な実装をしてしまった記憶がある。

Cの貪欲は典型だが、正当性の証明と言われるとどうしていいかわからないし、今回の公式解説にも書いていない。TLでAGC055Bの解説に書いてあると教えてもらった。

https://atcoder.jp/contests/agc055/tasks/agc055_b

www.youtube.com

午後11時半からはCF combined、Good Bye 2025。

Dashboard - Good Bye 2025 - Codeforces

AはYが一個以下。Bはuが隣接して現れず、先頭と末尾にもないことが条件。Cは最後に残る要素を決め打つと可能な符号の割り当てがわかる。Dは一回戦うと必ずどちらかが死ぬため、 $n\ge 2m$ が条件。構築は $n=2m$ となるまで $a$ が小さいものを倒したあと、上位 $m$ 人が下位 $m$ 人に攻撃すればよい。

Dにおいて攻撃可能なエルフは、「has not attacked」とある通りこれまで攻撃したことがないものであり、攻撃されたことがないものではない。ここを誤読してWAを出し、詰まっていたジャッジのせいで大きなペナルティを背負った人が多かったようだ。自分は高々 $n$ 回で操作が終了することを疑問に思い、読み返して気づいた。

Eは列の作り方がよくわからないが、雰囲気で言えば和が2べきとなる区間がたくさんあるらしい。短い方に降りていけばいいだろうと思って実装し、小さなランダムケースで正しく動くことを確認して出した。

Fはサイズが偶数の部分木を切り離すことができて、かなり大規模に組み替えられる。切ることのできる辺とできない辺があるようだ。すべてバラバラにしたあと、条件を満たすよう一列に並べ、繋げる方法を数えた。

Gは最後に使った弦を固定し、鎖の本数と奇数通りの鎖に出現する弦の集合を管理した。集合のXORでいろいろ計算することができるので、Zobrist hashと相性がよい。弦の端点にhashを置いて区間XORを取ると、交差する弦の値だけ取ってくることができる。怖かったのでhashを512bitにしたら、TL 3secのうち2sec弱使って少し怖かった。

Iのほうが解かれていたがわからなかったのでHも読んでみたら、こちらは解けた。一種類の場合はSmall Multipleでよい。束ねたとき問題となるのは操作2であるが、複数同時に行うだけなら問題ない。そこで操作2の操作回数が多い順に束ね、その度にSmall Multipleを解くとうまく行った。

残り30分でIのみが残った。制約が小さいので適当な全探索ができるのではないかと思い、いろいろ試しているうちコンテスト終了。8完11位で3138→3223(+85)。今年最後の二回は非常に調子がよく、断トツのhighestで年越しできることになった。

2026/01/07追記：レート再計算で3138→3220(+82)となっていた。

www.youtube.com

ハーメルンに熱中していたら動画公開し損ね、眠気に負けて午前7時就寝。

12/28(日)

午前10時半に目を覚まし、今日も睡眠調整失敗かと思っていたら、二時間ほどで二度寝に入ることができた。午後6時起床。

横になってハーメルンを読んでいたらコンテスト1時間前になっていたので、慌てて食事し、昨日の動画二本を公開した。

CFの通知で、LGMお祝いブログが投稿されたことを知った。ずっと日本人向けと思って日本語でやっているYouTubeだが、海外の視聴者もそこそこいることは認識している。ありがたい限りだ。年々上がっていく自動翻訳の精度に助けられている。

Congratulations to kotatsugame on Reaching LGM! - Codeforces

午後9時からAGC076に臨んだ。

https://atcoder.jp/contests/agc076

Aは各列から $N$ 項ずつ取ってくることで、すべての $i$ で $d(x_i,y)\le N^2-N$ となる $y$ が作れる。もう少し増やして $d(x_i,y)\le N^2-N-1$ とするには、 $y_j=x_{i,j}$ となるような $i$ を複数持つ $j$ が必要。 $x_{\ast,j}$ の最瀕値を $y_j$ としてみると、頻度の和は $N^2+N$ 以上になる。

実はこれで十分でもある。和の条件を満たすだけなら一つの列に一致する要素が集中してしまうと困るが、最瀕値の頻度が1より大きな $j$ は高々 $N$ 個で十分であり、ほかを適当に分散させればすべての列に一致する要素を $N+1$ 個ずつ作ることができる。

数え上げは何をしてもよい。適当にdpを書いたら $O(N^4)$ になっていて、そのまま通った。30分で解いて90位近い順位。思ったより悪くてびっくりしたが、先週の百倍マシ。

残りの問題を全部読んで、Bが一番取っつきやすそうだったので取り組んだ。一回操作する度に $N$ 文字出力することになるため、定数回で終わるはず。実験したら二回で十分なようだったので、まず一回でできるものについて考えた。

位置を大きく変えてしまう操作なので、もともと正しかった文字をそのままにするのが難しい。動くべきでない文字を0と1に分け、それぞれreverseの中央になるように操作を構成してみた。これが可能なら一回の操作で揃えられることはわかるが、実験と照らし合わせるとなんと必要条件でもあることが判明した。

あとは残りを一回のケースに帰着できればよい。条件がそこそこ緩いため、どのくらいきれいな文字列を目指すとやりやすいのかわからず、試行錯誤した。0が $A$ 文字、1が $B=N-A$ 文字あるとして、 $A\le B$ を仮定する。例えば先頭 $A$ 文字をすべて1にすれば条件を満たすが、少し長い文字列では不可能なものが見つかった。