読書記録（2025）

kotatsugame.hatenablog.com

1月

  • 16æ—¥
    配信に致命的に向いていない女の子が迷宮で黙々と人助けする配信

週記（2025/01/06-2025/01/12）

01/06(月)

午後3時過ぎ起床。半から今年最初のインターン先定例会に出た。昨年末に少し稼働したので話すべき進捗がある。勉強会は、実際に現場で行われた機械学習の精度改善手法について。数パーセントの改善をいくつも積み重ねている様子に圧倒された。

あとは先週の週記を書いて、日付が変わる直前に投稿。その後すぐにKUPCの分を追記した。

午前0時半就寝。

01/07(火)

夜明け前から寝たり起きたりを繰り返していた。起きている間はなろうを読んでいた。

エカスドクィナさんの昨年読んだネット小説まとめが投稿されていた。守備範囲が自分とほとんど重なっておらず、ハリー・ポッター原作の二次創作のみなのだが、その分野では以前投稿された同様のまとめ記事にかなりお世話になったことがある。4年以上前の話で、残念ながらもう削除されている。

sizu.me

毎月5日までに提出すべき書類（Googleフォーム）があって、指導教員の確認が必要なのだが、1日に送ったメールにまだ返信がなく困っている。

週記（2024/12/30-2025/01/05） - kotatsugameの日記

上の件について、ついに先生からメールが届いた。6日まで休暇だったそうだ。休暇でもメールチェックくらいしてほしいと思ったが、これはブラック企業的な思考だった。書類については提出先に状況を報告していたこともあってギリギリセーフという感じ。

午後9時前、ついに起床。合計の睡眠時間は12時間弱だった。

ICPCプレーオフの旅程についてsuzukaze_AobayamaのメンバーとZoomで相談した。ホテルについては三が日のうちにチャットで相談したので、フライトを決める。開催地・シンガポールは日本から南のほうにあり、時差は1時間だけだがフライト時間が7時間以上と長め。仙台空港からだとそもそも乗り継ぎでかなり待たされる便しかない。

羽田・成田からだと直行便がいくつかあるが、午前中に出るものは空港近くでの前泊が必要だし、仙台を朝出て間に合うようなものは今度はシンガポール着が夜遅くになって嬉しくない。どうしようもないので、前泊して午前中の飛行機に乗ることを選んだ。他大学のチームも同じ便に乗るらしいので安心、という側面もある。

LCCなので預け入れ手荷物についても確認しておく必要がある。大きなスーツケースだとそもそも現地タクシーに二つしか乗らないという噂もあったため、事前に荷物をマージしておいて二人分だけ払おうという話になりかけたが、HISというサイト経由で航空券を取ると一人あたり20kgぶん付いてくることが判明した。

【HIS】海外旅行・国内旅行の予約サイト

ところがこのサイトだと予約時に全員分のパスポート情報が必要らしい。実はチームメイトの一人がまだパスポートを手に入れていないため、受け取ってから再度予約手続きを進めることにして、今日は解散とした。

そのあと航空会社の公式サイトで調べていたら狙っていた飛行機の席が残り少ないことが発覚。明日またZoomで集まり、HISで3人、別のサイトで1人ぶん予約することになった。

しばらくなろうを読んで午前1時就寝。

01/08(æ°´)

午前3時半起床。朝までなろうを読んでいた。

シャワーを浴びて学食で食事し、ラノベを購入。その足で仙台駅前まで出て、航空券を買うための資金30万円をゆうちょ銀行から三菱UFJ銀行の口座へ移動させた。ATMの機能で送金するより自分で持ち運んだほうが反映が早いし、しかも手数料より地下鉄の運賃のほうが安い。

せっかく早い時間帯に駅前に来たので、mont-bellに入ってみた。このビル街にあって前庭を備えているのは驚き。原付に乗るときの防寒手袋でも買おうかと思ったら案外高かったので、尻込みして何も買わず店を出た。

イオンに寄りつつ正午に帰宅。すぐZoomを繋いで航空券を予約した。まずパスポートを持っていない一人の分を航空会社の公式サイトで取り、そちらが成功してから残り3人分をHISで取った。どちらも先ほど口座に入れた資金を使ってデビットカードで一括払い。公式サイトのほうはGoogle Payを経由して支払うと手数料がかからなかった。またHISのほうは謎のクーポンで5000円引きになった。

ついでに前泊用ホテルも予約した。成田空港近くに素泊まり4人部屋で16000円のところを見つけ、あまりの安さに仰天した。ド平日だとそんなものだろうか。さらにプレーオフの参加登録料も支払って解散。

眠かったので仮眠のつもりで横になったら、4時間も寝てしまった。午後6時に起きて明日のためのセミナー準備を開始。進めていくうち話そうと思っていた内容が全然足りないことに気付いたが、とりあえず午後11時過ぎの段階での資料をメールで送信した。

気分転換としてCodechef Starters 168に参加した。30分こどふぉったので別にタイミングが良かったわけではない。

https://www.codechef.com/START168A

書く

セミナー準備を再開し、午前8時に完了。すぐ寝た。

01/09(木)

午前11時半起床。昨夜作った資料をメールで送り、登校した。予報で天気が悪いことがわかっていたため、地下鉄で登校することは覚悟していたが、なんと雨ではなく雪が降っていた。ただこの時間は降り始めらしくまだ全く積もっていなかった。

学食で食事して午後1時半からセミナー。追加で準備した内容を合わせ、何とかいつも通りの分量のセミナーとなった。次に何をするか未定であること、また別件でテクニカルレポートを作成しないといけないことから、次回のセミナー日程を未定とさせてもらった。そのまま5限。今日は4年生が代数学の基本定理をいくつかの方法で証明してくれたようだが、眠気に負けてしまいあまり聞けなかった。

セミナー中からずっと雪が降り続けており、窓からも結構積もっている様子が伺えた。学食に向かうために建物を出たとき、写真を一枚。

夜は院生室でダラダラ。今年の箱根駅伝に出場した東大大学院生と、その給水係を務めた教授の記事を読んだ。D4と聞いていたのでやはり研究とスポーツの両立は難しいのかと思ったが、なんとこの箱根駅伝に出場するために卒業を一年遅らせたらしい。話題の給水シーンはテレビで見逃してしまったので残念。

news.yahoo.co.jp

また、久しぶりに立体四目並べの実装をした。アルファ・ベータ法にmove orderingを追加すると、まだほとんど練っていない順序でも驚くほど高速になってびっくり。これによって序盤の読み手数が他のAIに追いついた。ただし読み手の再利用をしていないため、中盤以降はまだ大きく離されている。

午後11時半に帰宅。なろうを読んで午前1時半に寝た。

01/10(金)

中途覚醒して2時間ほどなろうを読んでいた。午前11時過ぎに起床。シャワーを浴び、今日も地下鉄で登校した。雪はまだ降り続いている。

学食で食事して午後1時半から後輩のセミナー。論文の修正をしながら聞いていた。終盤詰まっていたので一緒に考えたものの、分野が違うため議論に慣れておらず、あまりまともなことは言えなかった。

3時間弱で終了。院生室に移動し、先ほどセミナー終わりに先生から解くよう言われていた教科書の演習問題について二人で考えた。午後6時半ごろ学食に行き、食事。

dcコマンドのバージョン1.5.1がリリースされたというメールが送られてきた。昔、コードゴルフ中に見つけたバグを報告した関係らしい。AtCoderの言語アップデート鯖に報告しようかと思ったら、そもそも誰もdc/bcを追加していなかった。自分ももうコードゴルフ熱が薄れてしまったし、なくなるならなくなるでいいか……という気持ちに。

院生室に戻って三人麻雀を打った。面子は自分、後輩、それにM2から一人。修士論文が大詰めの時期であるが、なんともう完成してしまったらしい。無理に誘ったわけではないことを強調しておきたい。

今日は劇的な局があった。先行リーチされて降りるつもりで手牌の対子を崩していたら、ドラを三連続で引いてきて四暗刻を聴牌。残念ながら上家にツモられて上がれなかったのだが、そのあとこんなの聴牌してたんだぜと手牌を見せ、戯れに次のツモ牌をめくってみたら、なんと当たり牌だった。みんなびっくりしていた。しかしこれでツキを全部使い切ったのか、最後は飛ばされて負けた。

午後10時半帰宅。2時間ほどなろうを読んで寝た。

01/11(土)

午前7時起床。

Rubikunさんが3か月ごとに集計しているCF div.2とECRでGP30を計算するランキングにおいて、昨年10月～12月の第12期で1位になった。3期から参加していて初めて。期間中、コンテストでの優勝こそなかったものの一桁順位を何度か取れたのと、他の参加者の調子が悪かったのが効いている。

R-18ハーメルン「ちょっと風紀のゆるいアナグラ」を読んだ。ゴッドイーターの二次創作は一時期読んでいた記憶があるが、ハーメルンのお気に入りを検索しても出てこない。どうやらどれも途中で読むのをやめてしまっていたようだ。

この作品と関係ない話をすれば、モンスターハンターだと古龍を主人公とする作品が大好きなのだが、ゴッドイーターのアラガミ主人公にはあまりそそられない。設定上、人類を攻撃せずにはいられないからだと思う。

syosetu.org

3時間ほど二度寝して午後2時からUniversal Cup。今日は25回目のHangzhouセット。

https://qoj.ac/contest/1893

書く

午後9時からはABC388に出た。

HHKB Programming Contest 2025(AtCoder Beginner Contest 388) - AtCoder

AはTUPCがサンプルにあってうれしい。Bは全探索。Cは尺取り。Dはimos法を更新しながら取得して線形時間で解いた。Eは小さいほうからK個と大きいほうからK個を組み合わせることになる。2A_i\le A_jとなる最小のjを各iについて求めておけば、あとは算数で線形時間。jを求めるのには二分探索を使ったが、Cと同様尺取りでよい。

Fはかなり面倒。どこに移動できるかを幅Bだけ管理し、悪いマスがない区間だけ適当に飛ばしていけばよいというのはすぐ分かるが、悪いマスが幅Bの間に点在していたりするとかなり面倒。一度のジャンプで移動する必要があるかどうかを丁寧に考えながら実装したら何とか1発でACできた。

GはEとほぼ同様で、j-iの列に対し区間MAXを取ることで判定が行える。遅延セグ木を使うなりSparse Tableを使うなりすれば実装も簡単。しかし自分は累積MAXの列を無理やり管理してその上で二分探索したりしていたため、算数パートでやられてかなり時間をかけてしまった。大きめのサンプルがあって助かった。

62分で全完して21位。AのNibbles 8Bは1分差で負けた。

www.youtube.com

直前でマイク音量がやたら大きくなっていることに気づいたものの、調整している暇がなかったので、動画でも音が大きいままになっている。

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

01/12(æ—¥)

1時間の中途覚醒を挟みつつ午後8時起床。寝すぎ。シャワーを浴びて食事し、午後9時からARC190 div.1に出た。マイク音量は調整済み。

AtCoder Regular Contest 190 (Div. 1) - AtCoder

Aは簡単で、コスト2以下で達成できるケースを除いたら区間の状態が1パターンしかなく、区間が三つ以上あれば必ずコスト3で可能ということがわかる。コスト2のパターンは3通りあるため合計5通りとなり、それぞれ丁寧に実装したら問題なく通った。

Bはやたら時間がかかってしまった。マス(a,b)を含むL型を固定すると、レベルk-1までは単に4のべき乗、レベルk+1以降は上下と左右それぞれ二項係数を求めて掛け合わせれば場合の数がわかる。回転・転置を組み合わせることで、向きを固定したL型を左右にずらすケースのみ考えればよいことになった。

立式してみると二項係数の区間和が出てきて、これを計算する方法がわからず30分以上溶かした。しかし実は典型で、f(n,k):=\sum_{i=0}^k\binom{n}{i}からf(n\pm 1,k\pm 1)を求めるのが定数時間で可能というもの。ずっと畳み込みのことを考えていた。

solved数を見てDに移った。整数ならa^p+b^p\equiv(a+b)^pだが、行列だと非可換なので成立しない。非可換でもp乗する理論はあるだろうと思ってしばらく検索したものの、役に立つものは見つからなかった。

諦めて真面目に考えたら解けた。A_{u,v}=0なる(u,v)に対し変数aと行列P=(\delta_{(i,j),(u,v)})_{i,j}を考え、(A+aP+\dots)^pを展開してa=1\dots p-1などで和を取ったが、やっていることは解説と同じ。

p=3がコーナーケースになることも気づいていたものの、実装が5分ちょっと間に合わなかった。AB2完の106位。Dで調べ学習しようとしていた時間が無駄。あるいは、読んでいたPDFに一度不定元を導入して特殊化することで等式を導く方法が書いてあったので、それを試してみてもよかった。

www.youtube.com

振り返りをギリギリで終え、午後11時半からはCF #996 div.2。

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

Aはお互い相手のほうにジャンプしてみて、それができなくなったほうが負け。まあこんな方法で判定するよりa-bのパリティを見たほうが早いだろう。Bは2種類以上のインデックスに対して操作するのが損。Cはx=0とできるか考えてみる。n-1行・n-1列までは1マスずつ使って達成できて、このとき残りの1行・1列の和が等しくなっているため最後の1マスで両方揃えられる。

Dは大変。「カカシiが座標yにいて、カラスが座標y+kまたはそれより右にいる」という条件のもとyがとりうる最大値を時刻tに対して考えた。この関数は常にある1点(t,y)から傾き1で伸びる半直線の形をしており、カカシiの結果からカカシi+1についてが計算できる。また遷移をよく見ると2t,2y,t+yが常に整数になっている。

Eは空にする順番を考えた。1,\dots,nの順とすると、まず\sum a\le \sum b-b_nが必要。このときn番目に全部押し付けることで必ず作業を完遂できることがわかる。

あとはコストの最小化だが、\sum_{i=1}^{k-1}b_iの容量に\sum_{i=1}^k a_iだけ入れて、はみ出した分をn番目に押し付けるというのをk=1,\dots,nで行うと考えると、\sum a+\max_{k=1,\dots,n}\left(\sum_{i=1}^{k-1}(a_i-b_i)+a_k\right)になる。2項目を最小化したい。

(+1,+a)と(+1,-b)を繋いだ折れ線の最大値だと思うと、この問題は見たことがあって、a-bの正負によって分けたあと適当な比較関数でソートするのが最適だったはず。すると最後の要素を全探索することもできる。ところがその比較関数を導き出すことができず、最終的にググってABC167-Fを見つけた。ちなみに、自分が見覚えあると言っていた問題はARC053-Cだったらしい。

a-b\le 0のときaの昇順でよいことはほとんど明らかだったのだが、後から考えてみるとこれを用いてa-b\gt 0のソート順も直ちにわかる。折れ線の終点も固定されているので反転して考えればよく、bの降順になる。

F - Bracket Sequencing

C - 魔法使い高橋君

Eに1時間以上かけたためFをやっている時間は残されていなかった。5完13位。

www.youtube.com

ARC-Cのupsolveをした。左上と右下からそれぞれdpしたテーブルを管理し、適当なところでマージする方針。更新クエリが変な形をしているので、dpテーブルの更新によって値が変わる範囲のうち、実際に再計算する必要のあるところは少ないだろうと考えた。

具体的には、マス(x,y)を更新したとき、左上からのdpテーブルは[1,x]\times[1,y]、右下からのdpテーブルは[x,H]\times[y,W]の範囲が正しい値になっているようにし、再計算が必要なマスを長方形領域の和として管理した。

遠くのマスの再計算が必要ならそのマスから今いるマスまで移動してくる必要があるから、ならしでクエリO(1)を達成できたかと思ったが、マス全体をぐるっと一周するように更新クエリが来ると全体を再計算する必要があるため、実際はO(HW/(H+W))=O(\min(H,W))になって公式解説と同じ計算量のはず。しかし今のところFastestではある。

atcoder.jp

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

週記（2024/12/30-2025/01/05）

12/30(月)

午後1時半起床。昼食を摂ってから先週の週記を書き始めたが、夕方用事で携帯ショップに行ってきたあとはこたつで寝ていた。午後7時に夕食。

食後はまた週記の執筆に戻ったが全然はかどらなかった。入浴を挟んだりしつつ、日付が変わる直前にUniversal CupとCF Good Byeを残して投稿。AGCは真っ先に書いたのでちゃんと埋まっている。かなり劇的なコンテストだったから、実況動画にできればよかったなと思う。

ハーメルンを読んでいるうち椅子の上で1時間ほど寝てしまったので、布団へ移動。しかしそこからまた3時間以上スマホを弄ってしまった。午前7時半就寝。

12/31(火)

午後3時半に目を覚ました記録があるが、布団でスマホを眺めているうちにまた寝てしまった。

午後8時起床、夕食は年越しそば。このとき紅白ではtuki.さんが「晩餐歌」を歌っていた。歌い始めのほうは声が少し細いように思えて、緊張だろうかと心配したのだが、曲が進むにつれて声量がしっかりしてきて安心。良いパフォーマンスだった。

近年、紅白にはGReeeeN（現GRe4N BOYS）、Adoさんと顔出ししていない歌手が出場している。tuki.さんもその一人ではあるが、彼女は実際にスタジオに来ていたし、歌い終わりのコメントのときはスクリーンを通さない後ろ姿が映ってかなりびっくりした。

食後すぐ部屋に引っ込んで、年末恒例の各種ツイートを行った。レート変動、AC数、読書記録。

CHUNITHMは高難度の譜面を詰めているときにもっと上まで到達した記憶があるのだが、レートシステムが変わってCHUNITHM-NETから確認できず、また写真にも残っていなかった。競プロのほうは上振れしたときの記録を抜かせていないという感じか。AtCoderでは赤から陥落せず、また最近CFでLGMを維持できているのは、highestには現れずとも成長した点だ、ということにしておきたい。

昨年はTopCoderが取得できずに11015問、今年はCodeChefが取得できずに12450問。その二つは大体同じだろうから1年で+1500問くらいと言えて、昨年・一昨年とほぼ同じ。精進もupsolveもろくにせずコンテストにだけ出続けているとこのくらいになるようだ。週29問弱、4コンテスト強で、まあそんなものかという感じ。

12月は、新刊をチェックした時点で分かっていたが、購入した本がそもそも少なかった。年間でみると昨年よりちょっと多く買って、ちょっと多く読んだらしい。購入した本の過半数を積んでいる状況は変わらず。

論文に関する作業をしているうち、年越し。この作業は年内に完了させるつもりだったのだが、着手するのが遅すぎて全然間に合わなかった。年が変わった後もずっと続けていた。

午前5時に切り上げて布団へ。ハーメルンで「無声慟哭」を読んだ。

syosetu.org

この作品はふるつきさんが大絶賛していたもの。10万文字ある短編だし、バンドリというほぼ知らない原作の二次創作だし、さらに「チラシの裏」区分になっていて、自分で見つけられることは絶対になかっただろう。

メンバー一人ひとりの抱える問題がそれぞれ導入され、絡み合い、それぞれ一定の解決を見て綺麗にまとまったので満足感があった。調べてみるとこの「問題」自体が二次創作で付け加えられたものだったらしい。かなりえぐい設定もあったので仰天した。自分が普段読む作品と比べると、必須タグ「アンチ・ヘイト」の重みが段違いだ。

ふるつきさんは毎年、その年に読んだネット小説をまとめている。自分も昔似たことをしたのだが残念ながら継続できなかった。リストを見ると、自分が読んだものとあまり被っていなくて面白い。共通しているのは「『星天』」「強めのモブウマ娘になったのに、相手は全世代だった。」「高1を12回ループしたクラスメート達が賢者モードになっている件」の3作。これらは確かに面白かった。

furutsuki.hatenablog.com

午前8時前に就寝。

01/01(æ°´)

午前10時過ぎ起床。食事はお雑煮とおせち。母は毎年おせちの何品かを手作りしてくれていたのだが、今年はついに丸ごと購入したらしい。ということで写真をパシャリ。またお雑煮に入れる餅を3個にしてほしいと頼んだら丼で出てきて、正月からフードファイトじみた食事になった。

ちなみに昨日の年越しそばも今日の正月料理も、起きるのが遅くて家族とタイミングが合わず一人で食べることになった。この性分は治らないな……。

食後は初詣。今年、平野部にはちっとも雪がないが、山あいに行くとさすがにいくらか積もっている。ただ昔に比べるとかなり少ない。

例年帰りに道の駅で昼食を摂っているところ今年はスルーして、午後2時半に帰宅。部屋に戻って論文作業を続けたが、眠くてどうしようもなかったので3時間ほど仮眠をとった。午後6時半に夕食、しゃぶしゃぶ。昨年もしゃぶしゃぶだった。

今年分の読書記録と買った本の記録を投稿し、論文作業に戻った。日付が変わるくらいでひとまず完了。風呂に入ったあと、紅白の録画を見た。特に良かったのはこっちのけんとさん「はいよろこんで」と米津玄師さん「さよーならまたいつか！」。

「はいよろこんで」はモールス信号の最後の一音とサビの入りが重なっており、THE FIRST TAKEだとモールス信号のほうを発音していなかった。当然の扱いではあるが、ちょっとスッキリしない。一方紅白だとライブ仕様ということか、サビを音響に任せモールス信号のほうを最後まで発音してくれた。

「さよーならまたいつか！」はドラマパートから歌唱パートへの繋ぎが好き。作中世界に米津玄師さんが溶け込んでいるというわけではないのだが、その微妙な異物感に引き込まれた。最後、決めポーズする米津玄師さんの横に飛び出してきた主人公っぽい女性は司会の方だったらしい。

午前3時半就寝。

01/02(木)

午前11時起床。今日の昼食は幼馴染二人と食べに行くことになっている。秋にも会った彼に車を出してもらった。

午後6時から幼馴染と飲み。

週記（2024/10/21-2024/10/27） - kotatsugameの日記

もう一人は成人式以来。そのときの話では一浪しており、さらに噂では大学院に進んだらしいので、ちょうど今が修論シーズンのはずなのに、試しに呼んだら来てくれてびっくりした。事情を聞くと、別にどこかでもう+1年したわけではなく、すでに学会発表をこなし書く内容も固まっているので切羽詰まってはないとのことである。

店ははま寿司。中学の同級生がその後どうなったかをひたすら聞いた。地元にいると駅で会ったり職場関係で噂が流れてきたりして、同窓生のつながりというのは緩やかに保たれ続けるようだ。自分の話もどこかでされていたら嬉しいな。今日聞いた中では、博士課程に進んだ人は他にいなかった。

食後すぐ解散では寂しいと主張してドライブに繰り出し、マンガ倉庫まで行ってデュエマ・フィギュア・ガンプラ・漫画の棚を眺め歩いた。

「聖霊王アルファディオス GS」は「G・ストライク」のぶん我々が知る「聖霊王アルファディオス」の完全上位互換になっていると話し、キーワード能力「G・ストライク」の説明をしたのだが、「相手クリーチャーを1体選んでタップし、次のターンアンタップしない」という誤ったことを伝えてしまった。これだと強すぎる。

dm.takaratomy.co.jp

午後3時半帰宅。寝っ転がってなろうを読んだ。午後6時に夕食、鍋。食後はまたなろうを読んだ。

夜になってワインが登場。ホスフィンとの家飲みなら大丈夫だったからと思い、勢いで一瓶開けたが、今日はペースが速く、また間にチェイサーもつまみもほぼ挟まなかったため、てきめんに酔っ払ってしまった。

日付が変わって家族が寝静まったあと、気分が悪くなってこっそり吐いた。お酒でこういう事態になるのは初めて。部屋に戻る元気もなくこたつに潜ろうとしたが、それすら力及ばなかったようで、気づいたら突っ伏した状態で頭だけこたつに突っ込んでいた。

01/03(金)

午前8時起床。二日酔い。塩気が欲しくなって、朝食のお雑煮を汁だけおかわりした。気分がまだ悪いので一日寝ていたいが、今日は仙台に帰る予定であった。

乗車券は往復切符を学割で買ってあったが、帰りの日を特に決めずに来たため、新幹線特急券を買う必要がある。シャワーを浴びて、近くの駅員がいる駅に出向いた。当然帰省ラッシュで満席であり、富山駅から大宮駅までは立席になった。

昼まで横たわったままなろうを読みつつ過ごし、昼食にそばを食べて親の車で富山駅へ。午後2時過ぎのかがやきに乗車した。

立席は思ったより辛かった。まず足腰が弱っている。さらにデッキにはキャリーバッグが置いてあったり、子供を抱いた人が景色を見に来たりして、なかなか角に身を落ち着けていられなかった。必死に耐え大宮にたどり着くと、そこからのはやぶさはスカスカ。3人掛け席に自分ひとりだった。しかし疲れ果てており、席も倒さずに寝入った。

午後5時過ぎに仙台到着。本屋で「新 謎解きはディナーのあとで」2巻を手に入れた。ちゃんと初版本。

そのまままっすぐ帰らず、ゲーセンで20クレ遊んだ。理論値と14+のAJが一つずつ、さらにチュウニズムクエスト完走。「ウニの歌」はラストがフリックを無視しても押せないので、それっぽく手を動かすだけで完全にお祈りだった。

ラーメンを食べて午後11時帰宅。シャワーを浴び、なろうを読んで午前4時半就寝。

01/04(土)

午前9時半から1時間ほどなろうを読んでいた記録がある。

午後2時前起床。新年一発目のコンテスト、Universal Cup 24回目・Polandセットに出た。

https://qoj.ac/contest/1890

書く

急いで食事して、午後9時からABC387。

AtCoder Beginner Contest 387 - AtCoder

A、Bはよい。Cは桁数と最上位桁を決めれば算数できるだろうと思ったら、そこから桁ごとに見ていく必要があって大変だった。Dは直前の移動も状態に入れてBFS。Eは桁和が小さいと嬉しそうなので、適当に上位桁と下位桁を探索すれば見つかるだろうと考えた。最終的には上位4桁と下位1桁を全探索した。Fはまあ、やるだけ。

Gはまず、許されるグラフの形を考える。閉路がパスを共有しているとダメで、さらに頂点を共有していてもダメらしい。つまり、2辺連結成分が1頂点あるいはサイズ素数のサイクルになっているグラフだと言うことができる。ここでサイズ2のサイクルが不可能であることに注意。

2辺連結成分がk個あり、それぞれの頂点集合がU_1,\dots,U_kであるときに、グラフが何通りあるか数える。まず連結成分内での辺の張り方は、|U_i|=1なら1、|U_i|\ge 2なら数珠順列で(|U_i|-1)!/2になる。連結成分の外については実は既出で、N^{k-2}\prod_i|U_i|となる。この式はk=1でも成立するのだが、コンテスト中は気付かず場合分けしてしまった。

与えられた森を含むラベル付き木の数え上げ公式

週記（2024/09/30-2024/10/06） - kotatsugameの日記

今度は頂点集合のサイズに対して\{1,\dots,N\}の分割を考えてみる。ありうるサイズの集合をP:=\{1\}\cup\{\text{奇素数}\}とし、サイズp\in Pの集合がc_p個あるとすれば、\sum_p c_p p=Nに対して\frac{N!}{\prod_p(p!)^{c_p}c_p!}になる。多項係数から同じサイズの集合の区別を取り除いたものである。

まとめると、a_1=1,a_p=1/2\;(p\ne 1)として\sum_{\vec c}\frac{N!}{\prod_p(p!)^{c_p}c_p!}\times N^{\sum_p c_p-2}\left(\prod_p p^{c_p}\right)\prod_p (a_p(p-1)!)^{c_p}=\frac{N!}{N^2}\sum_{\vec c}\prod_p(a_pN)^{c_p}/c_p!。多項式で書き直すと\frac{N!}{N^2}[x^N]\prod_p\sum_{i\ge 0}(a_p N)^i x^{pi}/i!=\frac{N!}{N^2}[x^N]\exp\left(\sum_p a_p N x^p\right)が得られる。

ここまでたどり着いたが残り2分しかなく、そこからFPSを窃盗してくるのはさすがに間に合わなかった。ライブラリの整備の大切さを実感。6完12位。今日はA・B・C・Eが2025の性質を題材としていて面白かった。Fの制約の2025は、無理しなくても……という感じ。

午後11時半からはCF Hello 2025に出た。

Dashboard - Hello 2025 - Codeforces

AはMEXが2以上になれる行・列が高々一つ。Bは最初問題文が壊れていてかなり詰まった。修正されると単に要素の種類数だとわかり、あっけない。Cはa,b,cですべて一致しているbitのみ答えに寄与できない。lとrが食い違う最上位bitを2^kの位としたとき、下位k+1桁で2^k-1と2^kを使うと上界が達成でき、残り一つは何でもよい。

Dでかなり詰まってしまった。MAX・MINが変わらない間区間を縮めてもよいので、a_lとa_rがMAXとMIN・MINとMAXになると思って計算でき、それぞれ(-a_r-r)-(-a_l-l)、(a_r-r)-(a_l-l)になる。rをfixしたときの最大値をセグ木に乗せようとして1時間ほど苦しみ、最終的に平方分割したが、この平方分割自体がよく見るとセグ木に乗る。前半を典型で処理したのに後半がそうできないのは意味不明。反省。

Eは二分探索を考えると、重み0または1の辺からなるグラフ上での最短距離を求める問題になる。並列二分探索しながら全点対間最短距離を管理すると、O(n^2)で一つの辺を重み1から重み0に更新できるので、まずO((q+mn^2)\log m)が手に入る。そして、もともと重み0の辺で連結になっていたら更新しなくてよいため、m=n-1とできる。これでE2まで通ったが、実は並列二分探索はいらない。

solved数を見てGに進んだが間に合わず、E2まで遅解きの317位。しかもDで一度Judgement Failedが出ており、仕様を知らずリサブしたら普通に点数を減らされて踏んだり蹴ったり。レートは3063→2919(-144)。残念。

www.youtube.com

CF-Gのupsolveをした。基本的には十字の中心に置きたいため、まずi+2j\bmod 5に応じて敷き詰め、それで置けずにカバーできなかった部分は貪欲で処理してみた。敷き詰め方は5通りあるので、連結成分ごとに最適なものを選ぶ。コードはコンテスト中にほぼ書けていて、最後vector<vector<int> >がMLEするのを1次元に潰して回避したら通った。実は連結成分ごとに見なくてもよいらしい。

ABC-Gの\expを用いた解法は準備時に見落とされていたようで、TLが12secもあるため2辺連結成分を遷移のたび一つずつ追加していくO(N^2/\log N)のdpが通る。コンテスト中は素数だけ集めたリストを作っていなかったので遅く、気づけなかった。その方針でコードゴルフをした。最初のコードはGCCで5secだったのに、そこから定数倍を悪化させすぎて、最終的にClangですら11secかかっている。

atcoder.jp

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

01/05(æ—¥)

午後1時直前に起床。Universal CupチームでKUPC 2024に出た。UCに収録される予定はないとのことだが、念のためPC 1台ルール。今回チーム戦順位表しかなくなっていてびっくりした。

KUPC 2024 - AtCoder

せっかくだからFAが欲しいなと思ってOに特攻したら、最大化はよく知っている典型だったのに最小化が01 on Treeという未履修の高度典型で手も足も出ず、最初の1時間チームに全く貢献できなかった。その間EADJBがそれぞれNyaanさん、risujirohさん、risujirohさん、risujirohさん、Nyaanさんによって通された。Bは昨日のCF-Gが大ヒントだったらしい。

我に返って仕事を探し、NyaanさんがWAを出していたHを引き取った。誕生日攻撃をするという方針らしい。チェッカーを書いて確かに落ちるなあと言っていたが、このときクエリはA側を固定し、B側を全部聞くというものだった。risujirohさんにA側も動かせばよいと言われてやってみると、たしかに40回くらい間違えるようになった。

しかし出したら落ちた。手元で試すと確かに数回に1回落ちる。パラメータ調整をもうちょっと頑張って、もう一度出したら通った。実はA=Bとしてしまっており、使えないクエリがいくつかあったのが痛いようだ。

01/07追記：よく考えると、A=Bのときは意味のないクエリが大量に発生している。これが痛すぎるだけで、クエリ数が少し減ったのは全く問題ではなかった。

NyaanさんがPを通す間にほかの問題を眺めて、KとMを解いた。Kは2種類の包除原理を同時に行うと、KYOTOとTOKYOを適切に含むような文字列を数え上げる問題になる。重なるところが難しいのでKYOとTOに分け、それぞれいくつ置いたか、また「連結成分」がいくつあるかを持つと3乗のdpができて、連結成分の隙間に任意の文字をねじ込めば文字列が数えられる。Mは左右からシミュレートした結果を適切にマージ。

KとMの間にNyaanさんがOを通してくれた。ここから少し停滞。自分はIを考えており、risujirohさんはずっとLと格闘、NyaanさんはNに取り組んでいたはず。まずNの構築ができて、通った。

Iも解けた。まず01の問題にして、X_{i,j}=1となる場合の数を総和に対して数えてみる。するとiに依らないことはすぐわかる。ここでいったん実装して正しいことを確認した。書いたコードを眺めると、j-1のpopcountが共通していればまとめて計算できて、N-j+1の総和さえ分かっていればよいようだ。これは桁dpで可能。あとはちょっと畳み込みを使うとO(M\log M\log N)くらいになった。

残りの時間はrisujirohさんのLとNyaanさんのGを往復していたが特に貢献はない。答えの候補を半分にするクエリを乱択で探したLが最後の最後で通り2位に躍り出たものの、その1分後に3位だったチームがCを通し、部分点1点の差で負けて最終順位は3位だった。1時間半ほど感想戦をして解散。

note.com

謎のnoteが出ていた。現在の環境におけるデータ取得はかなり大変そう。「返信先」は取得ミスだと思う。また「講義室の机」と「机」は自分の中では別物で、後者は自室の机にしか使っていない。もっと細かい話をすると、自室の机に向かっているときでも椅子の背もたれに寄りかかって寝ていたなら椅子に、机に突っ伏して寝ていたなら机に突き刺さっているという判定である。

なろうを読んで、眠気に負けて4時間寝て、またなろうを読んだら午前7時になっていた。

2時間ほど論文作業をしてから先生にメール。毎月5日までに提出すべき書類（Googleフォーム）があって、指導教員の確認が必要なのだが、1日に送ったメールにまだ返信がなく困っている。

シャワーを浴び日記を書いて正午就寝。

買った本の記録（2025）

kotatsugame.hatenablog.com

1月

新 謎解きはディナーのあとで2
迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について7

週記（2024/12/23-2024/12/29）

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は真面目に考察し、両隣の深さを見ることで復元できることに気づいた。

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

午後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を考えると、26状態に対して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巻を読んだ。

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

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

12/26(木)

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

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

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

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

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

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

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

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

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

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

12/27(金)

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

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

午後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年以上になるということで、すごい話だ。

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

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

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

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

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

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時半就寝。

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

12/16(月)

午後3時過ぎ起床。半からインターン先定例会に出た。

先週は1on1でタスクをいただいたのみで、まだ稼働できていない。勉強会は遅延セグ木＋AVL木で要素の挿入・削除操作を可能にするという話だった。すごい木を使う問題はUniversal Cupでたまに見かけるが、いつもNyaanさんにぶん投げて終わってしまう。

解散後に追加で1時間ほど1on1。別のタスクが降ってきた。数学的なことをやってほしいという感じだったが、専門が違いすぎてもう何にもわからない……。やるだけやってみようとは思う。

あとは週記を書いて、午後11時半くらいに投稿。全部書ききることができた。それから朝まで、本を2冊読んだ。

一冊目、「視線から始まる」。女性視点の学園恋愛小説。普通の女子高生と謳っておきながら実は校内で親衛隊ができるほど人気を集めており、びっくりした。また彼氏のほうの恋愛感情は一目惚れであることが明かされたが、彼女側がなぜそれに応えたのかよくわからなかった。さらにエピローグで急にオカルトな設定が追加され、これも謎。

二冊目、「才女のお世話」9巻。面白かった。選挙戦における主人公の振る舞いは、読者の自分からすると勝ち馬に乗ろうとしているようにも見えてしまうが、作中の学院生からはその仕事ぶりやこれまでの実績から好意的に受け取られているらしい。ずいぶんと立派になったものだ。

午前8時就寝。

12/17(火)

午後7時前に目を覚ましたが、セミナーのために論文を読んでいたら2時間ほどでまた寝てしまい、次に起きたら午後11時だった。セミナー資料を作ろうと机に向かったはいいものの、うっかりラノベに手を出してしまい、一冊読了。

「異世界転生したのでマゾ奴隷になる」。ハーメルンからの書籍化。面白かった。タイトルも表紙もいかがわしいし、内容もまあいかがわしい部分は多いが、それを補って設定と描き方がよい。主人公自身が自分の特別性についてかなり自覚しているのに、それでもなおめちゃくちゃな行動基準で動くところが好み。それにしても、イラストや本文の一部に白黒以外の色がついているという、この装丁への気合いの入りようは何だろう。

次のラノベに手を出し、結局セミナー準備が一切進まないまま午前7時半就寝。

12/18(æ°´)

午後5時過ぎ起床。シャワーを浴びて大学生協に行き、ラノベを受け取って食事してきた。帰宅してから午後11時までかけて、セミナー準備を何とか完了。

ラノベ「屍王の帰還」2巻を読了。非常に面白かった。主人公陣営の強さを引き立てる設定・キャラ・描き方がどれも大好物。また、主人公が異世界人だというのを側近にもひた隠しにする理由として、1巻時点では「話すと仲間を失うから」としか言っていなかったが、その正確な事情が明らかにされた。主人公の不誠実さに少し引っ掛かりがあったので、解消されて良かった。

しばらくなろうを読み、シャワーを浴びて午前7時就寝。

12/19(木)

午前11時直前に起床。それから1時間ほど1on1をした。この1on1はタスクに関してではなく、最近どうですかというもの。和気あいあいと話して終了した。

この時期になっても仙台は雪が積もっておらず、それどころか今日は非常に良い天気であった。寒さは強いが原付で登校。

学食で食事して、午後1時半からセミナー。準備してきた内容を過不足なく話し、今日も2時間弱でまとまった。これが年内最後のセミナーとなり、新年は論文で参照されている別の文献の議論を追うところから始まるだろう。今日の論文については一段落したため、キリがよいと言ってよいのではないかと考えている。

談話室で小一時間過ごし、5限。今日は指導教員が同じ後輩がセミナーをした。二人のセミナーの日時がずれてから数か月経ち、ずいぶん久しぶりに聞くが、正直文脈がよくわからずあまり身が入らなかった。そもそも講義の一環とするのには無理があったのではないだろうか。

午後7時過ぎに終了して学食で食事。それから立体四目並べの実装をした。アルファ・ベータ法を実装したら探索が爆速になって、さすがにさぼりすぎだったと反省した。また、久しぶりに麻雀を1半荘打った。東1局でメンタンピンツモドラ赤の跳満を上がり、守り切って1着。

午後11時過ぎに帰宅。半からCGR28に出た。

Dashboard - Codeforces Global Round 28 - Codeforces

Aは操作1を操作2で再現できる。Bはkの倍数のindexに小さい値を置き、残りは適当に。Cは片方をs全体と固定してよく、もう片方のrを全探索できる。DはKevinが解けない問題だけ考える。より簡単なものはより多くの参加者に解かれてしまうため、それらはできるだけ使わないようにし、さらにどうしても使わなければならない場合は最小限のコンテストにまとめるとよい。

Eはなかなか思いつけなかった。2m本の辺を持つ色があるため、m\ge 2nの場合は不可能。そうでないときはできればパスを作りたい。ジグザグに張るのを適宜ずらしていくと上手くいくようだが理由は不明。

Fは最小値で分割していくと区間がO(n)個になり、それぞれ操作する回数に応じた達成可能な最小の最大値を持つと解ける。状態数がk:=1+\log\max aで、マージはmax-min convolution。O(k^2)かけたが、列が単調減少なのでマージソートっぽくO(k)になる。

Gは簡単。左辺をwと置くと、条件は\exists i.\;\forall j.\;a_{i,j}\le wかつ\exists j.\;\forall i.\;a_{i,j}\ge wになる。2重に包除原理を行うとO(vnm)が得られ、一番内側の計算を二項定理でまとめるとO(vn)になる。

Hには50分残せたが、まとめきれず。結果は7完55位でレート3081→3044(-37)。EとFでかなり詰まったのが苦しい。

www.youtube.com

その後Hをupsolveした。操作をする度に0の連結成分それぞれが一つ短くなるようなので、後ろから操作回数を持ちつつ、0が残る連結成分だけ伝って遷移するようなdpを行う。とりあえず計算量を無視して書いてみるとサンプルが合い、そこから遷移をまとめてO(|s|\log|s|)にしてAC。実はすぐO(|s|)にもなる。

なろうを読んだり日記を書いたりして、午前9時半就寝。

12/20(金)

午後2時半起床。登校し、午後3時から留学生のセミナーに出た。留学プログラムも折り返しを過ぎたが、自分と彼はセミナーが一緒でなかったため、何をしているのかいまいちよく知らなかった。

去年と同じ半年だけの留学プログラムで、今年は後輩が留学生のチューターを担当している。

週記（2024/10/14-2024/10/20） - kotatsugameの日記

今日は四色定理の証明において計算機を使う前のパートで用いる定義・定理とその証明をいくつか話してくれた。Kempe鎖を縦横無尽に用いる議論で、非常に面白かった。おそらくこれらをポスターにまとめるのだろう。余裕があれば実際に彩色を求めるプログラムも書きたいと言っており、かなり熱意があったが、ポスターセッションで見せられるような出力をさせるのはかなり大変そう。

午後5時半ごろ学食で食事し、院生室に戻って麻雀を打った。最初の半荘は親満を2回ツモられる立ち上がりだったが、そこから自分にもツキが向いてきて、最終的には何とかまくることができ1着。次の半荘は特に良いところがないまま、後ろの予定が近づいてきたため東場だけで交代し帰宅した。

午後11時直前に家に着き、Universal Cup 22回目、Zhengzhouセット。明日からICPCで家を空けるのでこの時間にずらしてもらった。CF div.2はお休み。順位表情報がないかと思いきやすでにHoMaMaOvOと03 Slimesが走っており、また現地チームも十分強かったので、問題選定に関してはそこまで大変ではなかった。

https://qoj.ac/contest/1873

書く

感想戦を終えて午前5時。それからシャワーを浴び、少し日記を書いて、午前6時に寝た。

12/21(土)

今日から二日間はICPC横浜地区大会。自分がsuzukaze_Aobayamaの、milkcoffeeさんがAobayama_Marinesのコーチを担当しており、共に現地にいた。

午前7時半起床。鬼のように眠いが何とか布団から這い出し、1泊分の荷造りをして出発した。先週の反省から今日はちゃんと「そばの神田」に行った。麺は同じくらい柔らかくても、より細いこちらはそれほどブニブニした感じがなく、食べやすい。

もうちょっと早めに駅まで来て、少し歩いて「そばの神田」に行くようにしたい。

週記（2024/12/09-2024/12/15） - kotatsugameの日記

思ったより早く着きすぎて、仙台駅で30分ほど暇になった。本屋を覗くと知らない新刊がいくつか。「新 謎解きはディナーのあとで」の2巻を見つけておったまげ、奥付を確認して9月に出ていたことを知りひっくり返った。もう初版は手に入らなそう。

www.shogakukan.co.jp

「ありふれた職業で世界最強」14巻も今月発売だったらしい。ついにアフターストーリーが書籍化される。こんなに良いものはほかにないから、すぐにでも手に入れて読みたい。なろうのほうは、実は途中で読むのが止まってしまっているが、最高だった。

over-lap.co.jp

元の世界に帰ってからの話も欲しかったなと思っていたら、アフターストーリーという形でなろうで連載が続いていると後書きにあった。それも刊行されるかも、とも書いてあったが13巻発売から1年経過して音沙汰がない

週記（2023/09/11-2023/09/17） - kotatsugameの日記

また「引きこもり姉ちゃんのアルゴリズム推理」が気になった。児童書らしいが、著者が井上真偽さんなので内容に期待が持てる。

publications.asahi.com

そうこうしているうちに新幹線の時間になった。午前9時半仙台発、午前11時東京駅着。車内では寝ていた。東北大勢はチーム6人＋コーチ2人全員この列車に乗っており、改札のあたりで合流して、それからはずっと固まって移動していた。

横浜駅で乗り換える際、駅ビルのレストラン街でいったん昼食とした。二グループに分かれて別々の店に入った。自分はそば屋。つい数時間前に食べたなあと思いつつ、軽めのメニューを注文した。それからみなとみらい線に乗り、日本大通り駅で偶然shinchanさんと合流しつつ、午後1時過ぎに会場に到着。

入り口前で案内していたnoimiさんを始めJAGスタッフには結構知り合いがいるが、明日のコンテストが終わるまで話しかけることはできない。参加者はもうわからない人ばかりだったため、このタイミングでの交流は全くせず、Tシャツを着てチームの写真を撮った後は配布物を読んでいた。

今年はチーム紹介ドキュメントでアスキーアートQuineをしているところがあり、大変感心した。ちゃんと変数名やコメントにメッセージが仕込んである。おそらく運営のミスでダブルクオーテーションが2倍になるなど表示が少し崩れてしまったが、チーム紹介スライドのほうではideoneのリンクも用意されていた。しかし残念ながらREになっている。

vYsfTL - Online JavaScript Interpreter & Debugging Tool - Ideone.com

このコードの作成者とコンテスト後の懇親会で話す機会があった。どうやら手元では動くらしく、ideoneの環境が問題のようだ。別のコード共有サービスを聞かれたので「Attempt This Online」をお伝えしたら、そちらでは無事動いたとのことである。ただリンクは信じられないくらい長くなっていた。

Attempt This Online

開会のあいさつといくつかの説明を聞いた後、リハーサル。当然やることはないので椅子で寝ていた。突っ伏す机がない状態で寝るのはかなり無理があり、体がぐらぐらしたりしてまともに休めなかった。昨年は寝ていたらうしさんに起こされたものだが、今年はスタッフとして来ていないようだ。

印刷物配布に来たうしさんに起こされてかなりびっくりした

週記（2023/11/20-2023/11/26） - kotatsugameの日記

チーム紹介では「HokkaidoDekkaido」の文字をはみ出させる演出、「TORA NI TSUBASA」のゴールドタイガー（英訳付き）、「SPJ」のキラキラ陽キャな雰囲気、前述のアスキーアートQuineを載せた「OSMA」、チーム名だけで面白い「I_do_understand_the_danger_of_overflow_and_really_want_to_use_32bit_integer」、丁寧に「にょ」の説明をしていた「tcknyo」が印象に残っている。

suzukaze_Aobayamaは、スライドに思いきり日本語が書いてあってあれあれと思っていたら、とりゐさんが日本語を話しだしてビビった。TUPCオンサイトの紹介を英語でしてもしょうがないというのは理解するが、スライドにくらい英訳を載せておいてもよかったのではないか。

午後5時半には解散。夕食は東北大勢揃って中華街に行った。今年はホスフィンがおらず、適切な店を選ぶ方法がよくわからない。適当に練り歩いて、店舗が大きそうな「福臨閣」という店に入った。時間が少し早いので8人でもすぐ入ることができた。

ターンテーブルがあって興奮したが、全員定食を注文してしまいシェアを行わなかったのでほぼ邪魔なだけだった。支払いもかなり安く済んだのでコーチ二人で出した。店を出るとき別の競プロerの集団を発見。kotamanegiさんを筆頭とした阪大勢に加え、別大学の方も少し混じっていた。

解散してホテルに移動。suzukaze_Aobayamaと自分は二俣川駅の東横インに泊まることになっている。毎年会場近くのスーパーホテルを使っていたが、今年は高すぎた。全員バラバラのホテルを取ったAobayama_Marinesにはスーパーホテルに泊まる人もおり、聞いてみたら2万円くらいしたらしい。

二俣川駅への移動は1時間ほどかかった。特に横浜駅でみなとみらい線のホームから相鉄線のホームに移動する際、非常に長い距離を歩かされた。明日はかなり早くホテルを出る必要がありそう。

午後8時くらいにチェックイン。二人部屋を二つ取っており、自分は仮の人さんと同室になった。ノーパソをセットし、順にシャワーを浴びて、午後9時からABC385に参加した。

UNIQUE VISION Programming Contest 2024 Christmas (AtCoder Beginner Contest 385) - AtCoder

Aは二グループに分けることだけ考えていたらサンプル2を見てびっくり。Bは面倒。Cは間隔を1\dots N-1で全探索したらN=1のときにループが回らず1WA。Dは(x,y)と(y,x)をsetで管理するとよい。Eは中心の頂点を全探索する。y=0を許さないように注意。

Fはまず何も考えずに二分探索を書いた。視点位置からビルの天辺までのベクトルを考えると、その向きたちが適切な順序で並んでいるのが条件。よって隣り合うベクトルの外積を計算すればよい。答えがピッタリ0になるケースと-1を出力すべきケースの区別が難しいと思い、そこだけは先に整数で処理した。ところがWA。

答えが大きくなるケースを用意して二分探索の範囲を変え何度か実行すると、誤差が結構大きいことが分かった。精度が足りないらしい。判定の式をよく見ると直接求まることが分かったので、それに書き直した。しょうもないオーバーフローで追加1WAしつつ何とかAC。

GはまずP_i=Nとなる位置を境に左右に分割してそれぞれ考えた。挿入dpが簡単に多項式になったが、よく見ると左右でマージすることができない。ここで両側一気に挿入dpで扱えることに気づき、\prod_i(1+ix+x^2)を求める解法を得た。

41分で全完し、3ペナで4位。Aのコードゴルフをしていたら、a\le b\le cとしてa+b=c,2cで判定できることに気づき、これを発展させて((a+b+c)\bmod{\max(a,b,c)})=0にたどり着いた。対称な式を得られたので、ソートする必要がない。

日記を書いてコンテスト終了を待ち、仮の人さんと問題について少し話して、午後11時就寝。

12/22(æ—¥)

今日はICPCのコンテスト当日。自分はコーチのゲストとして公式実況放送に出演することになっている。

午前6時半起床。ホテルで朝食を摂った。スープ・味噌汁の器が紙コップだったり、納豆が袋に入っていたりして、コスト削減にかける熱意を感じた。

午前7時半出発。今日の横浜駅での乗り換えは距離が非常に短かった。どうやら昨日は相鉄線から遠い改札から出てみなとみらい線から遠い改札に入ってしまったらしい。会場へは午後8時半過ぎに到着して、コンテストエリアに向かう人々を見送った。

今年のコーチ控室は同じ建物の302号室。参加者が全員揃うのが早く、コンテスト開始が15分前倒しされたようで、荷物を置いて一息ついたらもうコンテストが始まっていた。問題文もすぐ届いた。

30分くらいして配信部屋まで案内された。特に段取りなどは決まっておらず、時間があるときここに来て出演すれば良いらしい。自分は気合い十分だったのでそれからずっと配信部屋にいたが、最初の紹介のときド緊張してしまい、またICPCに関してあんまり話せることがないことに気づいたので、ほとんどの時間はカメラの裏で問題を解いていた。

www.youtube.com

以下、各問題について。

A、Bはよい。Cは実は10分くらい考えても解けず、先にnoimiさんが解説しているのを聞いてしまった。まあ入力がしっかり大きめで変なことはできないから、そもそも全域木を作れる方針というのに限りがある。Dは結構しっかり考えたのに最初の一歩すら踏み出せず、これも解説を聞いた。Eはやればできそう。

Fはかなり嫌。chokudaiさんが山登りで解けるということを主張しており、自分はそれに対して誤差がまずいのではと言ったが、そもそもコスト関数が変な形をしており運がよくないと通らないらしい。結局配信中は誰も考えなかった様子。しかし表彰式のときにtatyamさんがササッと通しており感動した。

Gはtatyamさんがかなり早期に解決した。自分は解法を聞いてフンフン言うだけで、実装が死ぬほど面倒であることに気づいていなかった。Hは概要だけ。Iは典型的だが、ライブラリがない状況だと少し面倒。自分だったらセグ木を写経するのを嫌がり、mapで単調増加列を管理するかなと思う。

Jも概要だけ。謎のYokohama Yellowが出てくるしY.Y.さん作問かな？と話していたが、懇親会で「自分が作った問題でそういうことはしない」と仰っておられ、確かにとなった。Kは概要を理解したあたりで配信席から「Kってなんだっけ」「あのゼータ変換みたいなやつ」という会話が聞こえてきて終了。しかしすべてYのケースがまずいことには気づけなかった。

Lはnoimiさん、potatoさんと考えた。まず解法は区間dp一択。区間をdisjointに取って残った部分をまとめることを考えると、lごとにrをインクリメントしながらもう一つdpを行うタイプの遷移かなと思ったが、計算量が全然ダメ。最終的にはnoimiさんが、操作できる回数の最大値を持てば分割位置を全探索する簡単な遷移でよいと気づいた。potatoさんが実装して無事AC。

Lがあまり解かれていないのは順位表マジックだ、と話していた。実際オープンのほうではDとどっこいどっこいの解かれ具合であった。

https://onlinejudge.u-aizu.ac.jp/services/room.html#ICPCOOC2024/ranking

凍結後の配信はすることがないから問題解説になるだろう、と聞いていたのに、順位表と選手の画面を見つつ話しているだけで終わってしまった。午後2時くらいにコンテスト終了より少し早く配信を締め、表彰式の会場に向かった。例年はそのままコンテストエリアで行われるが、今年は建物9階にある「横浜シンポジア」というホールで行われた。

今年もYes/Noは盛り上がった。「tcknyo」のNoがNyoになっており、丁寧。Objective-KUB1の凍結後3完の大躍進とScreenwalkersのJ単独ACは会場がざわついていた。suzukaze_AobayamaはちゃんとLが可能であることに気づいて通し、8完最速の7位となった。Aobayama_Marinesも前半6問をちゃんと揃えて24位。

午後5時前に1階に降りてきて懇親会開始。HUAWEIがかなりしっかりしたトートバッグとデカいぬいぐるみのついたキーホルダーを配っていた。

食事は今年も油っこいものだらけだった。夕食を別のところで取る予定はなく、またうっかり昼食を食べ損ねていたので自分も手を付けたが、一部のポテトが暖められておらず度肝を抜かれた。

あとはひたすら懇親。個人識別のためアイコンの描かれた名札としてTUPC2023のものを持ってきていた。それが功を奏したのかこちらに気づいて声をかけてくださる参加者の方がたくさんおり、動画や週記を読んでいると言ってもらえて非常に嬉しかった。また2ショットを依頼されることも多く、たぶん10回くらいは撮ったはず。有名人になった気分だった。

夏の学生最強コンでお会いしたテナガザルさんとも話せた。あの日のサイン色紙は、1枚を飾り、もう1枚を持ち歩いているらしく、今日もお守りとして持ってきたと聞いて感動した。

テナガザルさんに依頼され、色紙にサインを書かせてもらった。

週記（2024/08/19-2024/08/25） - kotatsugameの日記

午後8時前に会場を離脱し、ひとまず全員で横浜駅まで移動。そこからもう1泊する3人が別れ、5人で東京駅へ向かった。全員午後9時半のはやぶさに乗る。東京駅では30分くらい暇になって、改札を出て駅前広場に行ったり、駅構内の本屋に行ったりした。「ありふれた職業で世界最強」14巻を入手しようとしたが、そもそもラノベがほとんど置いてなかった。

新幹線車内では爆睡だった。仙台に到着するとわき目もふらずに地下鉄に乗り換え、午後11時半に帰宅。先週と同じ移動だが思ったより余裕がない。ともかくCF #995 div.3にはなんとか間に合った。

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

A、B、Cはよい。Dはaをソートしてiごとに二分探索。Eは値段としてaやbのみ考えればよい。全部まとめてソートし、適当に更新しながら計算。Fはジョーカーの位置がprefix、真ん中、suffixと高々三つの区間になるようだ。それらを愚直に更新。Gはヘビiの後ろにヘビjをどれだけ詰めて置けるかO(n^2 q)かけて計算し、その後O(n^2 2^n)のbitDPをする。

全完8位。

www.youtube.com

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

週記（2024/12/09-2024/12/15）

12/09(月)

午後1時半起床。定例会が始まる前に学食に行って食事し、購買でラノベを買って帰ってきた。

午後3時半からインターン先定例会に出席。ウズベキスタンから無事帰ってきたと報告した。今週からまた1on1を入れてもらい、少しでも稼働していく所存。勉強会はジップの法則の一般化であるべき乗則について。Barabási–Albert modelという、次数分布がべき乗則に従うランダムグラフ生成モデルを知った。

解散後は週記を書いていたが、実質二日ちょっとしかないのでUniversal Cup以外を早々に書き終え、それからはYandex Cupの参加記のほうを書き進めていた。そちらは完成までまだまだ遠い。日付が変わる直前に週記のほうだけ投稿。

ラノベ「路地裏で拾った女の子がバッドエンド後の乙女ゲームのヒロインだった件」を読んだ。手ひどい裏切りを受けたばかりのはずのヒロインだが、主人公と出会って間もないうちから信用してしまっているように見えて、危機感のなさにちょっと冷や冷やした。

午前5時就寝。

12/10(火)

正午覚醒から二度寝を挟んで午後5時起床。セミナー準備をしなければならないが、とにかくやる気が出ない。布団でスマホを弄り、午後6時を過ぎて閉店直前の購買に駆け込みラノベを受け取った。学食で夕食を摂り帰宅。

ラノベを2冊読んだ。1冊目、「最強の悪役が往く」。ヒロインが複数人登場したが、ほとんどがやたら主人公に執着してベタベタしてくるのであまり好きになれなかった。その点では主人公と契約を結んだメインヒロインは好み。

2冊目、「地味なおじさん、実は英雄でした。」2巻。面白かった。主人公の強さもそうだが、女性関係の枯れっぷりにも安心感がある。

それにしても、このほとんど盗撮みたいな配信スタイルはかなり扱いが難しそう。主人公が配信のことを知らない状態が続くのにも違和感があるし、配信者としての話の展開もかなり制限される。ただ作家がベテランなので、うまく話を転がしてくれるのだろうと期待できる。とりあえず3巻への引きはかなり面白そうだった。

シャワーを浴びて午前6時就寝。

12/11(æ°´)

午前10時起床。もともと今日この時間から留学生のセミナーに参加するという話だったのだが、先生から届いたメールでは木曜日の自分のセミナー後になっており、どちらが正しいかわからない。ということで、十中八九木曜日のほうだろうなとは思いつつ、念のため登校することにしていた。とはいえそういうあいまいな動機ではちゃんと起きられず、セミナー開始時刻の起床と相成ってしまった。

登校してみたら案の定セミナーはなかったので、院生室に移動。ウズベキスタン土産を設置した。これは空港で買ったもので、日本円にして1箱4000円弱する。ビターチョコレート32枚入り。16枚入りだと思って2箱買ってしまったので、1箱は実家に持ち帰ろうと思う。

人と話したり昼前に学食に行ったりしていたが、どうにも眠い。家に帰ると夜まで寝てしまうだろうなと思ったので、院生室で少し寝ることにした。

思ったよりしっかり寝てしまい、気づいたら午後3時だった。眠気覚ましで外に出たら路面が濡れていた。少し雨が降ったらしい。原付で登校したので、夜また降られると困る。雪になったらもっと困る。

とは言いつつも、特に帰宅せずそのまま院生室でセミナー準備を行った。午後11時半になってようやく完了。本当は、今日準備した内容は今後使う予定が一切ないので、セミナーで話す必要もない。しかし準備を終えてから気付いてしまったのでどうしようもない。

それから立体四目並べの実装をした。今日は高速化のため、これまでのコードをビットボードによる表現に書き換えた。判定の並列化などにはまだ手を付けていないが、これだけでも少し速くなって面白い。午前2時前に帰宅。路面は乾いていた。

帰宅後にビットボードを用いた処理の並列化をいくつか実装した。またコードをメールで共有するのはさすがに卒業するべきと思い、GitHubに公開した。

GitHub - kotatsugame/yonmoku

午前6時就寝。

12/12(木)

午後0時半起床。さすがにセミナーで話す内容は変えるべきな気がしてきた。読んでいる論文にある別の命題と証明を頭に入れ、考えながら登校。学食で食事しているうちに考えがまとまり、何とか話せるようになった。

午後1時半からセミナー。慌てて準備した内容だが幸い特に勘違いなどはなく、無事話し終えることができた。その後先生とこれから申し込む発表の題目・abstractについて相談していると、5限の時間になった。見覚えのない学生が来たので何かと思ったら、先生が担当している別の講義で追試が発生したらしい。同じ教室で試験を受け始めてびっくりした。まともに集中できたものではないと思う。

それはそれとして5限開始。今日は本題に戻り、学部2年生が課題本「天書の証明」から一つ発表していた。3章の「4\le k\le n-4のとき\binom{n}{k}は整数の（非自明な）べき乗にならない」である。本で証明の核とされている部分は面白かったが、それ以外は延々不等式評価をしていて、かなり長く非常に疲れた。

学食で食事して院生室へ。今日も立体四目並べの実装をした。リーチがかかったときに勝てる手を列挙するのは、ビットボードとビット演算を駆使するとなかなか高速になった。あとは言われるがままに盤面の評価関数を実装。実際に試し強さをチェックするのは皆に任せっぱなしだった。日付が変わって帰宅しても、もうしばらく実装を続けた。

Yandex Cupの参加記を書き進めた。進捗は全然良くない。今日はブログ更新ページに直接書いていた内容がいつの間にか消えており、ショックを受けた。投稿済みのブログだと当然下書き保存はできないので、今後は別のところに保存するようにしたい。

午前7時半就寝。

12/13(金)

午後3時前に起床。1時間ほど1on1をし、タスクをいただいた。

シャワーを浴びて大学生協へ。今週末のTTPCと来週末のICPCで2回東京に行くため、その新幹線切符を買った。今週末の切符はさすがに直前すぎたらしく、帰りの席は3人掛けの真ん中になってしまった。それから学食で食事。

このときLINEが来て、立体四目並べの強いAIがつい最近公開されていることを教えてもらった。当然ビットボードを使っているし、ゲーム木で真面目に戦略を考えており、完敗という感じ。ただ判定の並列化まではしていないようだ。

note.com

帰宅せずそのまま地下鉄に乗って仙台駅まで出た。本屋とドラッグストアに寄りつつゲーセンへ。大型アップデート翌日だったが待ちは多くて三人というところで、閉店までの4時間ちょっとで22クレ遊べた。

新曲をいくらか埋めて、成果は理論値8個、14+のAJ二つ。「Igallta」は最後のトリルを全力で押すと微妙に追い越してしまうらしく、速さを理解するまで全部赤になってかなり大変だった。ちょっと前に14+のAJが99個になってウキウキしていたが、バージョンアップで譜面定数を全体的に高くされ、今日見たら101個になっていた。きれいにキリ番が消えてしまい残念。

ラーメンを食べ、ドンキとコンビニに寄って帰宅。

Universal Cup Finalsのフライトを他の日本人参加者とすり合わせた。羽田空港から香港国際空港と、その逆。実はなんとも都合の良いことに、ちょうど同じくらいの時間に仙台空港と香港国際空港を結ぶ便も存在し、それを使えば仙台と羽田を自腹で往復する必要がなくなる。ただ、他の参加者と合わせずとも香港くらい一人で行ける気がするが、安心を買うことにした。

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

12/14(土)

午後4時起床。夕方までゲーセンに行くつもりだったがもうそんな時間ではない。夜は院生室で環境構築の手伝いをする予定がある。昨日見つかったAIを動かしてみたいらしい。g++はあるので、makeコマンドをインストールさせて基本的な操作を教えれば終わりだろう。ABCの時間には十分間に合うはず。しばらく布団でなろうを読み、午後6時過ぎに登校した。

環境構築はすぐ終わったが、動かしたいプログラムが日本語を出力しており、文字化けで苦しんだ。コマンドプロンプトの文字コードをUTF-8に切り替えてもダメ。コンパイラのほうで弄る方法もあることに気づき、オプション-fexec-charset=cp932を指定することでなんとか解決した。

帰宅して午後9時からABC384。

Toyota Programming Contest 2024#12（AtCoder Beginner Contest 384） - AtCoder

A、B、Cはよい。Dは長さNのブロックからはみ出したprefixとsuffixをそれぞれ考えたが、ブロックは適当にずらせるのだから、どちらか片方を空としてよかった。Eは優先度付きキューでBFS。

Fはk\ge 0について2^kで割り切れるA_i+A_jの和を求め、足し引きして解いた。しかしあまりにも適当に実装した結果、mapを使っていて遅いのと不要なkまで調べているのとでTLE。kの範囲を絞り、存在しない要素でmapにアクセスするのを止めたら通った。

GはMo's Algorithm。最近次のようなツイートを見たので、ドンピシャだなと思いながら解いた。

全完11位。AをNibblesで縮めた。Sの各文字について1行目におけるインデックスを求めると、出現しない文字には0が返ってくるが、これはPythonにおける-1のようなものでc_2のインデックスにもなる。よってそのまま添え字として使えばよい。

www.youtube.com

部屋が寒くてなかなかシャワーを浴びる気になれず、ダラダラなろうを読んでいたら午前4時を回ってしまった。明日はTTPCに現地参加するため早起きしなければならない。慌ててシャワーを浴び、午前5時就寝。

12/15(æ—¥)

今日はTTPC2024。

TTPC2024 - connpass

午前8時起床。荷物を準備して家を出た。会場の教室の椅子が固いとのことで、運営がクッション持参を推奨していたが、荷物になるので自分の臀部を信じ持っていかなかった。

仙台駅構内で立ち食いそばを食べた。朝から新幹線に乗るときはたいてい食べているが、いい加減このそばが口に合わないことに気づいてきた。少し太めの麺はブニブニした食感で、汁の中で絡み合いうまくすすれない。もうちょっと早めに駅まで来て、少し歩いて「そばの神田」に行くようにしたい。

午前9時半発のはやぶさで東京へ。車内では寝ていた。午前11時過ぎに東京駅に着き、そこから大井町駅での乗り換えを挟み大岡山駅まで移動。記憶が正しければ、ここに来たのは2017年のSuperCon以来である。東京科学大学のプレートの写真を撮り、connpassページの案内をガン見しながら会場へ移動した。

正午少し前に到着したらもう開場していた。教室入り口で名札を貰ったが、アイコンがデフォルトのものになっていた。名札のアイコンについてはconnpassでの参加登録時に選択肢がいくつかあったはずで、そこで自分はデフォルトのまま変えていないことを忘れてAtCoderのアイコンを選んだらしい。もう何も覚えていない。

立ち歩く時の利便性を考えて最後尾の長机を確保し、持参した延長ケーブルを這わせるなど用意を整えていたら、noya2さんに話しかけられてサインをお願いされた。あとはmtsdさんと話していた。

ぼちぼちチームメイトも集まり午後1時にコンテスト開始。我々japan406364961はUniversal Cupのほうで参加した。こちらは日本語問題文が提供されなかった。また一度はAtCoderの順位表を見てはいけないと通達されたのだが、教室前方スクリーンに順位表の1ページ目が表示されており、それなら見てもよいという話になった。

https://qoj.ac/contest/1872

今回のセットは簡単枠が存在せず、序盤の順位表に動きがほとんどなくてかなり苦しい立ち上がりだった。F問題が8分で解かれたのでrisujirohさんが読みに行ったが、まったく解けるようには見えないらしい。実際、この速度で解かれたのは既出だったからのようだ。

Symmetry: Closure - Problem - Universal Cup Judging System

しかし我々はギャグであることを疑いしばらく粘着していた。というのもスクリーンの順位表では、すなわちAtCoder上では続々とF問題が解かれていたのである。しかししばらくしてその順位表がdiv.2のものであることに気づき、ようやく諦めがついた。

ぼちぼちACが出始めてもまだ各問題一桁ACで、どれに取り組むべきか区別がつかない。自分はB、risujirohさんはE、NyaanさんはLを考えていたはず。結局最初の1時間はPCを使わなかった。

Bは後ろから考えるとよい。まず1が末尾にしかないことに気づき、とりあえず末尾が1のケースを解いた。こちらはそこそこ簡単で、3の連結成分に対しカタラン数を掛け合わせればよい。ところが末尾が1でないケースはもうちょっと面倒らしい。正確には、最後にC=3となった直後のAが2,2,\dotsであるようなケースが問題。

ウンウンうなっていたらCも同じくらい解かれ始めた。確認すると見覚えのある問題設定。たしかUCのどこかでやったことがあるはずで、セグ木のノードについてその両端に移動するまでの距離をそれぞれ管理し、適当にマージなり親への移動なりをしていくとよい。雰囲気で書いてサンプルを合わせたら通った。

NyaanさんがLを通し、risujirohさんのEが落ちたのを尻目にBの解法を詰めた。冷静になるとカタラン数が出てくるのは当たり前で、グリッド上の移動を考えると問題だったケースも数えられる。丁寧に実装した後、さすがに自信がないので愚直を書いたら、見事一発で合っていた。提出してAC。

次はEのhelpに回った。解法を聞くとそれっぽい貪欲ではあったが、計算量がO(N)で何かおかしい。落ちるケースを見つけたので、それに対応できるO(N^3)の解法という線で考えを進めた。履歴を管理する貪欲に考えを引っ張られつつも何とか区間dpにたどり着き、そんな面倒な遷移はしなくてよいだろうという読みで思いついたそれっぽいものをrisujirohさんに伝えた。トイレに行って帰ってきたら通っていた。

次に通ったのはNyaanさんのM。これは論文ゲーだったらしく、Cartesian Treeが一致する条件が以下の定理3に書かれている。あとはあんまり工夫せずO(N\log N)になるらしい。

[1905.08974] Cartesian Tree Matching and Indexing

その間自分はrisujirohさんとAを考えていた。言われた通り構築することも少し考えたが、こちらは何をすればいいのか全く分からない。辺を1本ずつ消す方針で解けた。まず橋は無視できるので、グラフを2辺連結としてよい。このとき、消す辺の端点に次数3以上のものがあると、その頂点は2辺連結であることから存在を保証される閉路に含まれており、条件を満たさない。よって次数2の点同士を結ぶもののみが消せる。これをO(m)回繰り返す。

最後に取り組んだのはFで、これもrisujirohさんと。1次元の場合は簡単で2\gcd(x)周期の話になる。これでX軸・Y軸に平行な直線しかない場合は解ける。そうでない場合が問題。

点を移すだけでなく、軸となる直線そのものを別の直線を軸として移して考えてみる。サンプルの二つ目は、斜めの直線がX軸と有理数でない角度で交わっている。このとき、直線を移すのを何回も繰り返すと、交点を通る任意の直線を軸として使用できるようになると気づいた。そのような交点はY軸との交わりも合わせて二つあるので、任意の点を任意の点に移せる。

今直線の傾きの\tanが有理数なので、0度・45度・90度という自明な角度以外はこれが適用できるらしい。そのような斜めの直線が存在する場合をまず考える。その直線が原点を通っていなければ、サンプル2と同様なんでもできる。原点を通っていても、ほかにX軸・Y軸に平行な直線があれば同じこと。そうでないとき、つまりすべての直線が原点を通るとき、原点からの距離が一致していることが必要十分条件になる。

傾き45度の直線がある場合が最後に残った。適当に反転して、直線x+y=aがあるものとすると簡単。このときX軸平行の直線とY軸平行の直線を同一視でき、さらに直線x=a、y=aがあると思える。よって正方形領域の周期が続く形になり、傾き45度の直線は重複を除いて高々2本、x+y=0,\gcdしかありえない。

risujirohさんによれば斜めの直線を使う回数は高々1回らしいので、22通り全探索できる。あとはX軸・Y軸に平行な直線しかない場合と同様。これらの場合分けを紙で丁寧に詰めて実装し、サンプルを合わせて投げると……WA！

残り20分ちょっとしかない。NyaanさんがJを解けていたのでPCを交代し、コードをにらんだ。すると実装ミスが二つ見つかった。少しPCを空けてもらって書き直し、再度投げると見事AC。小躍りした。

残りの時間はNyaanさんを応援していたが、残念ながら実装ミスが取り切れなかったらしく、ACならず。その後9分ちょっと遅れて通っていた。そのくらいの時間であれば、例えばF問題の実装をもう少し早く始めるなどでいくらでも捻出できたはず。非常に残念。

結果はCLBEMAFの7完で11位。7完のチーム中でペナが最大なので、もう一問通せていれば大きく違っただろう。

AtCoder側の順位表はUCのものとかなり雰囲気が異なる。Mが解かれておらず、JのACが結構多い。Nyaanさんが最後Jに取り組んでいたのもこの順位表を見てのものであり、情報が真に多いことは明確に有利だった。

7完までの速度差でsemiexpさんに、部分点でチーム🇧🇴liviaに負けた。しかし結果発表では我々のチームが1位だとされていて謎。聞くところによると、AtCoderのdiv.1とUCの結果を混ぜる際、部分点を無視し、最後にACした時刻のみ・ペナなしで順位を付けたらしい。

懇親会ではlumaさんに話しかけてもらったほか、もっぱらUniversal Cup勢と話していた。会場が午後8時に閉まり、夕食でもどうですかという感じになって駅前のサイゼに移動。メンバーはチームjapan406364961、チームtritr、Rubikunさんの7名。昨日のAJO決勝の余興について、Twitterで内容が一切流れてこないので一体何だったのか聞いてみたが、口止めされていそうな雰囲気だった。

新幹線の終電があるため自分だけ午後8時40分に離脱。ちょっと余裕を持って出たら1分での乗り換えに成功したりして、思ったより早く東京駅までたどり着けた。午後9時36分、満員のはやぶさで仙台へ。車内では寝ていた。

午後11時半帰宅。何とか間に合ったのでCF #993 div.4に参加した。

Dashboard - Codeforces Round 993 (Div. 4) - Codeforces

Aはよい。Bは正確な定義がないが雰囲気で。Cもよい。Dは順列にするギャグであると気付くまで時間がかかった。Eは算数。Fはすべてのxに対して予め判定する。同じa_rを何度も調べないようにすれば、調和級数で十分高速になる。

Gは二つに分かれている。G2から解いたが、G1とは異なる問題だった。どちらもサイクルの外が消えるまでの時間を求めればよく、G1は深さ、G2は木の頂点数になる。G2でサイクルの同じ頂点から生えている複数の木をまとめてしまい1WA。Hは二次元累積和。

全完10位。

www.youtube.com

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