12/23(月)

午後4時前起床。今日のインターン先定例会は年末だからか知らないが縮小版で、30分遅く始まり、しかもほぼ勉強会のみだった。

内容はAHC040の話。箱を詰めるとき斜めのラインで置いていくと良いという話で、ゲーム「2048」を思い出した。あれも、例えば左と上でばっかり操作して大きな数を斜めに作っていくのが良い。

そのあとは日付が変わるまで先週の週記を書いていた。ICPC部分は真っ先に、結構気合いを入れて書き上げた。作業量の観点から、後日そこだけ切り出して独立した参加記にする、ということはしないだろう。常体を敬体にするのが結構な手間。

ほんの少しの穴あきを残して投稿。それからはうっかりなろうを読んでしまった。午前8時くらいに就寝。

12/24(火)

午後4時前起床。1on1があったが、まだ稼働できておらず何も進んでいませんと白状して、1時間予定されていたところを30分で終わった。昨日もうちょっと早く寝て、今日起きてから稼働するつもりでいたのに、なぜかなろうを読んでしまったのが痛い。

そのあと午後6時までコーディングして一応の成果物を作り上げた。この短時間で完成するのは手抜きの結果ではなく、それくらい軽いタスクを頂いていたという話。自分の腰が重すぎて反省。

急いで大学生協に行き、ラノベを受け取って食事して帰宅。午後7時からクリスマスコンテストに出た。

Xmas Contest 2024 - AtCoder

一通り眺めて、D問題が目についた。11月末のStanley先生の講演で $f(m)$ が $m$ の素因数と一致する数、すなわちpowerful numberに関する話を聞き、またそれについてYandex Cupからの帰り道でhosさんと話したから。

Combinatorics@Sendai2024

そこでD問題に取り組んだのだが、やっていたことはpowerful numberと全く関係なく、ずっと素数カウント $O\left(\frac{N^{3/4}}{\log N}\right)$ を弄っていた。

素数カウント( $\mathrm{O}(\frac{N^{\frac{3}{4}}}{\log N})$ ) | Nyaan’s Library

問題の性質から $f$ を $g$ に書き換える部分は飛ばせる。変な重みに対応して $\log$ が一つ付き、 $O(N^{3/4})$ は完成したはず。しかしそもそもこの計算量では間に合わない！TL 4secだと $N\le 10^{12}$ が精一杯で、 $N=10^{14}$ だと60secほどかかってしまった。

結局、順位表を見て解いたAとBのみの2完。Aは実験して全部1だろうとエスパー。Bは真面目に考察し、両隣の深さを見ることで復元できることに気づいた。

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

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

午後11時半からはECR173。これが今年最後の動画になるはず。

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

Aは4で割る度枚数が2倍になる。Bはそれぞれの倍数判定法を個別に実装。Cは $x$ を含む区間、 $x$ より左・右の区間について、それぞれあり得る和が区間になっている。

Dはまず全体を $G$ で割って $G=1$ の問題に帰着すると、あとは愚直に探索できる……はず。この部分はARC137-Aと同じ問題だったらしく、正当性もそちらを見るとわかる。

A - Coprime Pair

Eはbitごとに考えてよく、行を0埋めする、あるいは列を1埋めするという操作になる。操作同士の順序と必ず行わなければならない操作が決まるので、到達可能な閉路がないかをチェック。

Fは一つのクエリに対するdpを考えると、2⁶状態に対してXORをその値にするための最小の個数と場合の数を持つものが思い浮かぶ。すると要素の追加が状態数に対する線形時間で行えるので、Mo's Algorithmができそうな気がしてくる。要素の削除は行えないのでrollbackで対応。定数倍がとんでもないことになっているが、しばらく高速化していると3.5sec弱のものが完成した。

Gを解いている時間はなく、6完で終了。しかしopen hacking phaseでFが落とされてしまって42位となった。

www.youtube.com

日付が変わり、12/25はyukicoderのアドベントカレンダーコンテスト最終日。今日の問題はNyaanさん作問だった。Nyaanさんには普段UCでお世話になっているし、問題IDがキリ番の3000だし、なにより文字列の問題で星4.5ということはやたら高度なことはしないだろうからワンチャンあるのではと思い、取り組んでみたら解けた。

No.3000 Optimal Run Length Encoding - yukicoder

明らかにrun列挙が使えそうな形をしているので、Nyaanさんのライブラリを見に行く。冒頭のコメントにいくつかrun列挙に関する非自明な性質が書かれている。ところでdpを考えると、 $(l,r,p)$ というrunについて取得操作が必要になるのはインデックス $l+2p\dots r$ を見ているときのみである。実はこの回数の総和が $O(|S|\log|S|)$ になるらしい。その取得については、runとインデックス $\bmod p$ に対しデータ構造を持つと高速に行える。

string/run-enumerate.hpp | Nyaan’s Library

ついでに同じコンテストの他の問題も一通り眺めて、すぐ解けるものは解いてみた。

Advent Calendar Contest 2024 - yukicoder

Aは典型。Bは結局 $N$ 種類のsuffixから最大と最小を見つければよく、これが $3N/2$ 回の比較で行えるのはそこそこ有名な話だと思う。

D - ラーメンの食べ比べ

Cは原始ピタゴラス数に関するユークリッドの式によれば $m\gt n$ であって「偶奇が異なり」「互いに素」なものに対し $\left\lfloor\frac{N}{2m(m+n)}\right\rfloor$ の和を取ればよい。 $m$ を固定すると、 $\ell:=m+n$ は $m\lt\ell\lt 2m$ であって奇数かつ $m$ と互いに素となる。つまり、 $\ell$ は $2m$ に含まれる素因数で割り切れてはならない。

これを $2m$ の素因数に関する包除原理で扱う。計算するのは $\left\lfloor\left\lfloor\frac{N}{2m}\right\rfloor/\ell\right\rfloor$ だから、区間に対してそれらである定数を割った商の和が欲しい。商列挙で計算してみると、計算量は不明だが案外高速で、手元では $N=10^{12}$ が3.3secになった。しかし提出するとTLE。定数倍高速化として、奇数に関する和だけ計算することにして素因数2を無視したら通った。

Dは頂点が並ぶ順番を数え上げ、 $N!$ で割ればよい。EはYandex Cupの最終日に公開され、数人で考えたことを覚えている。まあ考えたというか問題文を読解するのが大変だっただけで、解法自体は二つの木（制約よりグリッドのほうも木になっている！）の同型を見つけるだけとなる。ところがいざ実装するにあたり、かなり面倒なことに気づいた。少し方針を考え、逃亡……。

順に解いていく野望が絶たれたため、以降は星3以下の問題のみを解いていった。

Fは攻撃力が $N$ より大きくなったらその分を先に計算してしまうdp。Gは緑に塗られたマスの集合を $2^{HW}$ 通り全列挙し、その寄与を足し合わせた。ビットシフトなどを駆使することで連結成分の取得はかなり高速になる。どうしても1ケースTLEしてしまったのだが、盤面が点対称であることを利用していくつか計算をサボったら通った。

Hは面倒なやるだけだが、隣接swapしかできないと思い込んでサンプルがなかなか合わなかった。デバッグが不可能なので困る。Jも面倒。Mはフィボナッチ数列の $\bmod N$ での周期を求めて算数。

Oは長さ4のループを使うと $N$ を2減らしたグラフに帰着できるので、 $N=2,3$ だけ手で構成。ところで、問題文の序文にある「グラフ理論のゼミ」は、自分のセミナーが元となって2023年春学期に行われていたものである。確かにこの問題について話し合われた記憶がある。解法そのものは忘却していたが……。

今日のセミナーから人数が増えるらしい。先生がTAの方にセミナーの聴衆を募集している話をしたらしく、巡り巡って競プロサークルに案内が来て、そこから今日は4人参加した。
週記（2023/04/24-2023/04/30） - kotatsugameの日記

Pはよい文字列の切れ端としてありうるパターンをすべてセグ木に乗せる。Rは実験すると周期 $p$ で0項目以外がすべて $0$ になっていたので、0項目をべき乗で求めた後最後だけ真面目に計算。しかしこれは数列の長さが $p$ より長ければ成り立たないことがあるらしい。周期を $p^2$ に増やし、最後の計算を二分累乗法で実装したら通った。U、Wはやるだけ。

以上で星3以下の問題はすべてである。午後0時半就寝。

12/25(水)

午後4時過ぎに目を覚ました。昨日のECRの結果を確認したらFがTLEで落とされていた。Mo's Algorithmのブロックサイズを2種類提出しておいたのに、ご丁寧にも一つ一つHackしてきた人がいたようだ。落ち込んでふて寝。

午後7時半に起床し、シャワーを浴びて外出。午後9時閉店の本屋に滑り込んで「ありふれた職業で世界最強」の14巻を購入した。また「新謎解きはディナーのあとで」2巻の初版も発見したが、調べたら1巻を母から借りて読んでいたので、2巻もそうすることにして買わなかった。

それから閉店までゲーセン。14クレプレイして14+のAJが二つ、またチュウニズムクエストを一つ終わらせた。今月始めのバージョンアップから始まったイベントは01/22までだが、キャラ数が多く走り切るのに時間がかかるものが二つあって、今からすでに焦っている。

今日は14クレ pic.twitter.com/7HGvst0PSN
— こたつがめ (@kotatsugame_t) 2024年12月25日

油そばを食べ、ドンキに寄って帰宅。それから朝までかけて「ありふれた職業で世界最強」14巻を読んだ。

期待通り非常に面白かった。WEB版の「ありふれたアフターストーリー」章から帰還の少しあと、かつ主人公メインの話のみ抜き出し、時系列順に並べなおしたものらしい。加筆もかなり多かった。ぜひこの調子で後日談を続けてほしいところだが、あとがきによればどうやら15巻は出すことが確定していない様子。単にアニメ三期に合わせて新刊を出したかっただけなのか？これだけの人気シリーズなのだから続きを出そうと思えばいくらでも出せると思っていたので、ショックである。

シャワーを浴びて日記を書き、少しインターンで稼働して、午前11時半就寝。

12/26(木)

午後4時半に目覚ましで起床。明日から大学生協は年末年始の休業に入る。帰省するための新幹線切符を購入するには、今日、窓口が閉まる30分後までに店舗に行かなければならない。ギリギリ間に合うタイミングということで、この時間に目覚ましを設定していた。

しかしよく考えると、切符を買うためのお金を下ろす必要もある。ATMに寄っていると間に合わない気がしてきた。どうせ今日もゲーセンに行くつもりだったので、ついでにみどりの窓口に並ぶことを覚悟し、生協は諦めて二度寝した。

午後6時に再度起床し、1時間ほどなろうを読んでから外出。仙台駅に向かった。みどりの窓口はそれほど混んでいなかった。

帰省するのは明日。新幹線はもうほぼ満席だろうと思っていたが、窓口で調べてもらったら、仙台を夕方出て富山に夜到着するという絶好の列車が空いていた。ギリギリ帰省ラッシュを外したのが効いたか。

無事切符を購入し、駅からゲーセンに向かう途中のガストで食事した。自分の注文した料理を積んだ配膳ロボットが、椅子に掛けられた上着に邪魔されて少し先の通路でずっと立ち往生しており、どうしたらいいのかかなり迷った。チラチラ見ていたら店員が来て解決。

午後9時から閉店までゲーセン。今日は13クレプレイして理論値が四つ増えた。日付が変わる前に帰宅。

今日は13クレ pic.twitter.com/Zw0Dzt3FZ0
— こたつがめ (@kotatsugame_t) 2024年12月26日

ICPC プレーオフの招待メールが届いた。コーチ一人ひとりに送っているようで、同じ日本チームでも1時間くらいタイムラグがあった。念の為suzukaze_Aobayamaのメンバーに確認を取って、参加と返事した。

朝まで日記を書いていた。

ふと昔のツイートを検索していたら、ノクターンノベルズのリンクがいくつか切れていることに気づいた。ググってみると「無地の水玉」というユーザが退会してしまったことが発覚。お気に入りだっただけに非常に悲しい。R18の確認ページが挟まるので、魚拓もうまく取られていなかった。

シャワーを浴び、ゴミをまとめて午前9時半就寝。

12/27(金)

午後1時半起床。寝る前にまとめたゴミを出して、帰省のため出発した。少し早めの時間に仙台駅まで出て、丸亀製麺で食事をしたあとゲーセンで7クレ遊んだ。

成果は理論値一つ、「Halcyon」黒のSSS。後者は初見の日ボーナスで終盤を通し、2プレイ目にしてこのスコア。同じくらい終盤が上手い日にもうちょっと頑張ればSSS+に乗るかもしれない。また、せっかくなので未プレイを埋めてプラチナポゼッションを復活させた。

今日は7クレ　年末なのでポゼッションもつけた pic.twitter.com/BSFiMvVFbB
— こたつがめ (@kotatsugame_t) 2024年12月27日

午後4時半の新幹線で大宮駅経由富山駅へ。車内では寝たりなろうを読んだりしていた。横の通路で子供が延々飛び跳ねており、もう大変だった。

父の迎えで実家に到着し、夕食。「新謎解きはディナーのあとで」2巻を貸してくれと母に頼んだら、すでに読み終えて売り払われたあとだった。そういえば10月に帰省したとき、読むか聞かれた気もする。1巻のことだと思い、もう読んだと答えてしまった。

午後9時半くらいにこたつで寝落ち。起きたら午前2時半だった。少しなろうを読んで、また就寝。

12/28(土)

午前8時半起床。外を見たら雪が少し積もっていた。溶けかけではあったが、今シーズン初めてまともな積雪を目にしたため興奮した。

朝食を摂りシャワーを浴びて、午前11時からUniversal Cup 23回目のHong Kongセット。夕方から高校の同窓会があるため、普段より早めのwindowで走らせてもらった。もともとこの週のUCはお休みの予定だったはずが、運営にやる気がありすぎてつい先日生えてきた。当然新年一発目は01/04に予定されている。

https://qoj.ac/contest/1885

書く

感想戦を早々に切り上げて、富山駅前まで両親に送ってもらった。午後5時半から同窓会開始。今年は担任の先生を呼んだこと、また隣のクラスと合同で行われることが通達されていたが、具体的に誰が来るのかは幹事しか知らない状態だった。

蓋を開けてみると、二クラス合わせたのに昨年とほぼ同じ20人ちょっと。主に浪人で＋1年している人が多く、医学部なら国試、理系なら修論で忙しかったのだろうと予測している。ということで就職した人ばかりだった。

実は幹事も今年修士課程を修了するのだが、話を聞いてみると学会発表の経験もあるとのことでかなり順調そうだった。しかし博士課程には進まないことにしたらしい。残念。

あとは、ついに結婚した人がちらほら。参加者の中には婚約したペアもおり、男性の方はよく知った友人だったので仰天した。また中学生の頃から付き合っているカップルがまだ続いているというのも良い知らせだった。もう10年以上になるということで、すごい話だ。

料理は写真のものに加えて、富山の郷土料理「あんばやし」と小さなピザ、飲み放題付き。このあとのコンテストを考えてお酒は控えめにしたが、そもそも大きな声で話さなかったので全然酔いが回らなかった。

食事 pic.twitter.com/g3fLjtMqc7
— こたつがめ (@kotatsugame_t) 2024年12月28日

2時間ちょっとで店を出て、午後8時から二次会のカラオケへ。偶然去年と同じ店舗だった。この二次会から合流した人もいる。

マイクが4本あるのに電源の入った先着2本しか認識しなかったり、そもそも電波が遮られて機械まで届かない位置があったりして、カラオケとしては微妙。自分から曲を入れることはしなかった。「ライラック」が流れているのに誰も歌っていなかったのでマイクを持ったが、機械に繋がらなかった。失敗！

今年持ち込まれたアルコールは缶チューハイ。ホスフィンとの家飲みでは絶対に登場しないので、かなり久しぶりな気がする。度数4%だったため、このくらい薄いお酒なら飲んでも問題ないだろうと思って、1缶手を付けた。

そうしているうち午後9時になったので、いそいそとノーパソを開いてABC386に出た。

ぞいぞいしてきた pic.twitter.com/AajgUeAhBa
— こたつがめ (@kotatsugame_t) 2024年12月28日

AtCoder Beginner Contest 386 - AtCoder

Aは出現したもののみに限った頻度列をソートして $(2,2)$ または $(1,3)$ になっているかチェックした。Rubyだと書きやすいが、あとから知った種類数が2であることをチェックする方針だと当然もっと書きやすい。Bは00を0に一斉に置換してから文字列長を見ればよいな、と思いつつC++で普通に実装。

Cを開いたらFの部分問題と言われたので、Fに飛んだ。編集距離の説明が書いてあってビビるが、よく考えると見ているインデックスの差が $K$ を超えることはないとしてよい。これで $O(|S||T|)$ から $O(|S|K)$ になる。FのACを確認してからCに投げた。

Dに戻る。結構面倒だが、黒と白の境界としてあり得るインデックスを区間で持ちつつ上の行から見ていくと判定できる。

Eは基底状態で必ず選び方が一通り求まる再帰関数を書けば $\binom{N}{K}$ 回の再帰になって間に合うと考えたが、3ケースTLE。よく考えると各基底状態に到達するまでに $O(K)$ 回再帰しており、しかも今回 $K$ が $N-1$ くらいのケースも許されている。そこで $K$ が大きいとき代わりに選ばない $N-K$ 個を見るようにしたら通った。

Gは解けず。唸っていたら午後10時になり、延長できない設定だったので店を出た。やはり年末価格でありえないくらい高い。店の前で解散し、三次会には行かず富山駅まで歩いた。父に連絡し、迎えを待つ間駅のベンチでGの考察を続けた。

重み $k$ の辺が何回寄与するかを考えていたが、これは全然ダメ。重み $k$ 以上の辺が何回寄与するかを求めるのが良い方針で、これだと「重み $k$ 未満の辺による連結成分」がうまく数えられれば計算できる。ただそこから整理できず、適当にdpを書いているうちに時間切れ。

結果は6完20位。600点にしては全然解かれなかったので助かった。帰宅して急いで入浴し、午後11時半からCF Good Bye 2024。

Dashboard - Good Bye 2024: 2025 is NEAR - Codeforces

書く

ABC-Gをupsolveした。ちょっとだけ解説を見て、ABC213-Gの解説で説明されている除原理を思い出したら、「重み $k$ 未満の辺だけ見たとき連結になるグラフ」が数えられるようになった。あとはすべての頂点集合について「その集合が重み $k$ 未満の辺でちょうど一つの連結成分になる場合の数」を求め、足し合わせることで「重み $k$ 未満の辺による連結成分」が数えられる。

G - Connectivity 2

日記を書いて午前6時過ぎ就寝。

12/29(日)

午後6時くらいに目を覚まし、1時間ほど布団でゴロゴロしてから起き上がった。夕食を摂り、食休みしてから入浴を済ませると、もう午後8時半。大事なコンテストがあると言って部屋に引きこもった。

午後9時からAGC070。

AtCoder Grand Contest 070 - AtCoder

Aは解けなかった。 $100\dots 200\dots$ というのを考えたが、 $iX$ と $2iX$ を重ねられるだけなので500個くらいはdisjointに出現しなければならず、全然足りない。一応 $142857$ もアイディアとして出たものの、大きめの $i$ で端が壊れてしまうのだけ見て捨ててしまった。 $i=1,\dots,6$ での結果を見ていれば、もしかしたら思いつけたのかもしれない。

1時間弱してBに移った。明らかにドツボにハマっており、一旦気分を切り替えなければならなかったこと、また今さらAが解けてもレートが大暴落するのは避けられないことが理由。また、この時点ではBのほうが少し多く解かれていた。

Bはまず、2べきという変な重みが気になる。どうせ $1+1$ に分解して展開するのだろうと考えると、偶数長の閉路を持たないという制約も $1-1$ のべき乗として同時に扱えそうに見えてくる。少し計算すると、グラフの重みが閉路の集合 $C$ に対して $\sum_{C'\subseteq C}\prod_{c\in C'}(-1)^{|c|+1}$ と書けることがわかった。

あとは辺 $i\rightarrow p_i$ を含まないという条件について。わざわざ木として与えられているのだからその構造を利用するのだろうと考え、木dpしてみることにした。閉路の切れ端がいくつあるかを状態に持ち、遷移していく。

しかし少し書くと畳み込みの計算が見えてきたし、 $i\rightarrow p_i$ を回避しようとすると状態が倍になって、どうにも高速化できなそう。まずこのdpが書けないとお話にならないのでは、と思ってかなり粘ったのだが、そもそも遷移がまとまらなかった。

残り1時間を切ったあたりで、 $i\rightarrow p_i$ の回避は無理筋だと判断し、この条件を包除原理で扱うことにした。さらに、木dpも全然わからないので、もっと愚直な計算をまず合わせてみることにした。

つまり、ループに属することを確定させる頂点集合 $L\subseteq\{1,\dots,N\}$ と、辺 $i\rightarrow p_i$ の採用を確定させる頂点集合 $P\subseteq\{2,\dots,N\}$ をそれぞれ全探索した。頂点 $i\in L\cap P$ については少し条件があることに注意。具体的には、 $p_i\in L$ かつ $i\ne j\in L\cap P$ について $p_i\ne p_j$ である。

また $P$ により、すでに $L$ 内部でいくつかの有向パスが完成している。入力は木なので閉路が完成していることはない。1点もパスだと思うことにして、パスの数を $k$ とおく。

重み $\sum_{C'\subseteq C}\prod_{c\in C'}(-1)^{|c|+1}$ を $\sum_{C'\subseteq C}(-1)^{|C'|}\prod_{c\in C'}(-1)^{|c|}$ と書けば、包除原理やグラフの重みに関する符号として、 $(-1)^{|L|+|P|}$ に加え閉路の数も関係することがわかる。それはまだ決まっていない。

$k$ 個の有向パスを適当につないでいくつかの閉路を作ることになるが、係数を込めた場合の数は $k$ に対して前計算できる。有名な数列になることを期待してdpしてみると、なんと $k=0$ に対して $1$ 、 $k=1$ に対して $-1$ 、あとは全部 $0$ だと判明した。ついに解けそうな雰囲気が漂ってきた。

しかし結局、愚直が合ったのは残り20分を切ってからだった。 $i\notin L\cup P$ について、辺の行き先を決めるとき $p_i$ を回避しないといけないと勘違いしていたが、それは包除原理で考慮済みなので問答無用で $N$ 通りを計上してよい。

間に合わないかもしれないと思いつつ、高速化を始める。 $k=0$ のケースは $L=\emptyset$ なので、 $P$ だけ考えればよい。どの頂点を選ぶかは係数に関係ないので、 $|P|=0,\dots,N-1$ を全探索できる。

$k=1$ のケースは $L\setminus P$ が1点集合 $\{u\}$ で、特に $L=\{u\}\cup(L\cap P)$ は木 $T$ 上で $u$ を終点とする有向パスの形に並んでいなければならない。まず、このパスの長さに関する数え上げは各頂点の深さを見れば簡単に求まる。

次に $P\setminus L$ を考えるのだが、 $u=1$ となれるのに対し $1\notin P$ でなければならないため、 $u=1$ か否かでパスを分類してカウントしておく。そこから先程と同様に $|P|$ を全探索すると、とりあえず $O(N^2)$ が手に入る。

あとは算数。 $|P|$ を全探索している部分は見るからに二項定理の形をしているので、閉じた式になるはず。残り時間が5分を切る中、慌てつつも計算を整理していくと、無事シンプルな $N-1$ のべき乗にまとまった。サンプルも合う！

愚直の部分が実行されないように書き換え、混乱のためACLを展開して、残り1分8秒で提出。ページをリロードするとすぐジャッジが進み始め、そのまま通った。深夜だが思わず手を叩いて喜んだ。スマートウォッチによればこのときの心拍数は125BPM。

結果はB1完の66位でパフォーマンス2860、レート2887→2885(-2)。0完太陽に終わらなくて本当によかった。最終的にはCのsolvedがBより結構多かったのだが、こちらはランダムウォークに関する知識・検索ゲーの側面があるようで、そちらに進んだとして自力で解けたかは怪しい。

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