週記（2025/01/13-2025/01/19）

01/13(月)

午後4時に目を覚ましたもののまだ眠い。二度寝して起きたら午後7時だった。この間30分おきに目覚ましをかけていたが、午後7時より後はかけていなかったので、ここで起きなかったらそのまま火曜日に突入していたかもしれない。

今日は成人の日でインターン先定例会がない。先週の週記を書き続け、日付が変わる前に投稿した。微妙に穴あき。

ハーメルンを読んで午前3時半くらいに寝落ち。

01/14(火)

午前8時に目を覚まして昨晩読んでいたハーメルン「大文豪に私はなる！」を読み続け、昼過ぎに読了した。

この作品は夏に一度最新話まで追いついたもので、ちょっと更新を溜めてしまっていたのだが、最近完結したため読み切った。相変わらず面白かった。特に最終章の決戦は非常に映える展開だったと思う。ただし主人公たちが使っていたクロスオーバー技は大半がわからなかった。

最後に主人公陣営の懸賞金が更新されたのも嬉しい。この懸賞金というシステムは非常にわかりやすい指標で、ついつい額がポンポン跳ね上がっていく様子を想像してしまうが、自分が読んだ限りのワンピース二次創作はどれも自制が効いているのか、現状の最高額であるロジャーを超えた人はいない。原作へのリスペクトか、あるいは「ひとつなぎの大秘宝」が明かされないと他の何を描いても海賊王には勝てないという話か。

「大文豪に私はなる！」と「大文豪に私はなる！ R18版」を読了。

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

syosetu.org

夕方まで論文の修正をした。先生にメールで送ろうと思っていたが、ついでに始めた数値計算が終了しない。眠気に負けて4時間ほど仮眠を取った。起きてもまだ終わっていなかったものの、最後まで待てそうな進み具合ではある。

時間ができたのでTechFULの新春TCB2025を走ろうと思ったら、イベントページが見当たらない。日程としては今週末までだったはず。しばらく探していたが、どうやら昨年末発生したセキュリティインシデントで延期になったようだった。

布団に戻ってハーメルン。R-18の「【完結済】眠れる師匠のわて様を好きに使っていい日」を読んだ。出会いから今の関係性に至るまでが描かれていたはずだが、話の順番が時系列通りではなかったので分かりづらかった。

syosetu.org

なろうの更新チェックでふと「影の勇者の再冒険」を確認したところ、つい先日「はるかな過去編」が終了していたことを知った。2947話から3620話まで実に674話、毎日投稿で2年弱かけたらしい。自分はこれが主人公不在の章であると判明した少し後に読むのをやめてしまったのだが、終わりがわかる今なら乗り越えられるかもしれない。

https://ncode.syosetu.com/n5534co/

2947話から始まる「はるかな過去編」が主人公不在のストーリーであることが発覚した。主人公の無双が好きで読んでいる部分が大きいためこれは結構辛い。どこまで続くのか知りたくて先のほうを確認したところ、なんと開始から丸一年、366話経過した最新話でも未だにこの章が進行中であることに気づいた。

週記（2024/03/04-2024/03/10） - kotatsugameの日記

久しぶりに新刊チェックをした。前回が11月末だったのでひと月半空いたことになる。その間にもう出てしまったラノベを含め50冊注文・予約した。切りよくするために財布のひもを緩めまくったことは否定しない。タイミングが悪く、数日後に出版される富士見ファンタジア文庫で買おうと思った本3冊は予約できなかった。

シャワーを浴び、朝になってiTEPという英語能力の試験を受けた。準備も含めて2時間弱かかった。リスニングはメモもパソコンで取らされるのだが、そこで日本語が使えるのかよくわからず、英語でメモしようとしたらかなり大変だった。このメモもそうだし、ライティングでもそこそこのタイピングスピードが要求されていたように思う。

先生にメールを送り、午前11時過ぎに学食。そのあと床屋に寄って帰ってきた。散髪中はスマートウォッチに記録されるレベルでしっかり寝ていたらしい。

再度シャワーを浴びてから年度末の出張に関して数学専攻事務室にメールを送った。02/10-11は名古屋の研究集会、02/19-24はUniversal Cup Finals、02/26-03/03はICPCプレーオフ、03/04-07は北海道の研究集会と、半分は競プロ関連だが、特に2月下旬からはかなりのラッシュ。体調だけは崩さないようにしたい。

午後3時過ぎ就寝。

01/15(水)

夜中まで寝てしまうことを覚悟していたのに、起きたら午後5時半だった。それほど眠気もないので布団を出ることにした。

大学でタブレット端末が買えそう。買った人はほとんどみんなiPadを選んだらしいので自分もそうすることにして、貰ったカタログを見ながら考えていた。

2時間ほどして外出。まず腹ごしらえのため昨年末開店したばかりの油そばの店「元祖油堂」に行った。卓上調味料が大量にあったり、水以外の飲み物も飲み放題だったりして、なかなか面白い。油そば自体は「東京油組総本店」と似ていると思った。

その後ゲーセンに移動し、閉店まで18クレプレイした。大きな成果が二つ。

最近追加された「激烈!!!!ファミレスガールは帰しま1000!!!!」で理論値を出した。初見3-0-2がAJ時9-0-0になったのでさすがにもう少し詰めたいなと思ってプレイしていたら、7落ちからいきなり出た。Lv.14の理論値は初めてだし、3000ノーツを超える譜面としても初めて、タップスライドが含まれる譜面としても確か初めてだったはず。全国ランキングもまだ埋まっていなくて非常に嬉しい。

Lv.15「MeteorSnow」でSSSを出した。78-79小節がほとんど16分トリルで通ると気付いた瞬間に出た。終盤も難しくて正直認識すら怪しいが、なぜかたまにめちゃくちゃ噛み合い、低速を抜けてから1-0で通ったこともある。それがタイミングよく発動してくれた。癖が付く前に終わってよかった。

立ち食いそばを食べて帰宅。道が凍っていた。朝まで日記を書きながらハーメルンを読んでいた。

富士見ファンタジア文庫の注文ができるようになっていたので、3冊購入。

午前10時前就寝。

01/16(木)

午後4時過ぎ起床。

事務室にメールでいくつか確認しつつ、北海道行きの飛行機とホテルを取った。国内線に乗るのは家族旅行以来で、相場がわからないしかかる時間も読めない。飛行機とホテルをセットで予約したらどちらにどれだけかかったのかもわからなかった。

閉店直前の学食に駆け込んで食事し、そのまま街に出てゲーセンに向かった。閉店まで19クレプレイ。今日も大きめの成果が出た。

Lv.15「Stardust:RAY」SSS。案外押せた。最後は自分の手の大きさを信じ、片手6レーン＋端フリックでど突きまくった。アタミスはいくつか出ているはず。SSSが出た回は確か76小節までAJで通過したのだが、92小節のこれまで特に苦労しなかった擦りに失敗して2-2くらい出してしまい、悔しい。

Lv.15「Killing Rhythm」SSS。突然58-65小節の左手の速さを理解し、空打ちが通るようになった。また今日は95-96小節が信じられないくらい上手かった。あとは43、45、47、97小節を耐え、最後のタップスライドが抜けないことをお祈り。

Lv.15「Tempestissimo」99AJ。これだけ譜面定数が15.1で、旧基準だと14+になる。初AJは109小節で全押ししたためホールドが抜けまくって37落ちで、さすがにひどすぎると思ってやり直したら結構なスコアが出た。ラストに癖が付きかけていたのでギリギリセーフという感じか。

立ち食いそばを食べ、ドンキに寄って帰宅。雪が降っていた。

驚くべきことにSRMの過去問アーカイブが作られていた。ジャッジデータも置いてある。提出へのリンクも用意されているように見えるが、権限がなくアクセスできない。

TopCoder Statistics - Problem Archive

現在のArenaが閉鎖されるらしい。それに伴ってSRMもしばらく開催されなくなる。メールではあくまで一時的な休止だと言っているが、最近のTopCoderのグダグダっぷりを見るに復活する可能性は低そうだ。それどころか過去問アーカイブもComing Soonのままずっと放置されるのではと思っている。

週記（2024/07/08-2024/07/14） - kotatsugameの日記

朝までかけてラノベ「配信に致命的に向いていない女の子が迷宮で黙々と人助けする配信」を読了。面白かった。ダンジョンや魔法の設定がかなりふわっとしていて、主人公が強いことは配信コメントから伺えるものの具体的な尺度がない。より強くなろうとしているのは好み。

名古屋のホテルを取って午前8時半就寝。

01/17(金)

正午起床。iTEPの結果が返ってきた。詳細なスコアは隠すがCEFRでB2と判定されていた。個人的には予想していたより良い。

各セクションの結果を見ると、文法は全く分からなかった割に当たっていて、リスニングが一番良く、リーディングは手応えがあったのにかなり点を落としている。残りのライティングとスピーキングはみそっかす、という感じ。はるか昔センター試験国語・英語の長文読解でミスした際点数が10点単位で下がっていったことが思い出され、かなり嫌な気持ちになった。

地下鉄で登校して学食で食事し、午後1時半から留学生のセミナー。昨年末の続きである。2月の頭にポスター発表を控えた今内容はすでに完成しており、非常に面白かったし説明も上手だったと思う。四色定理を証明する際に行われるグラフの各種リダクションを、それぞれの意図から丁寧に解きほぐしていた。午後4時に終了。

注文したiPadと教科書1冊が事務室に届いたらしいが、受け取りに印鑑が必要とのことだったので今日受け取るのは諦めた。

今日午後5時が修論の提出締め切りだった。今年はオンラインでの提出になっていたため、院生室に人が全然いない。それでも麻雀を打つ面子は集まったので、1半荘打った。リーチ・ピンフ・ドラ3・裏ドラ1の跳満を上がって1着。

学食で夕食を摂ったあと、面子を少し入れ替えてもう1半荘打ったが、こちらは焼き鳥で4着。それからしばらく雑談して、午後11時過ぎに帰宅した。

半からCF #997 div.2。

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

書く

www.youtube.com

ハーメルンを読んで午前4時半就寝。

01/18(土)

午後2時前に起床。Universal Cup 26回目、Chinaセットに出た。

書く

午後9時からはABC389。今年最初のトヨタ自動車プログラミングコンテストだが、去年と異なり「#1」がついていない。

Toyota Programming Contest 2025（AtCoder Beginner Contest 389) - AtCoder

Aは見覚えがある。文字xはdcのコマンドで「stackのtopをdcコマンドとして実行」を意味し、特にtopが数値なら何もしないのと同じであるから、?*pでよい。Bはオーバーフローを過剰に怖がりRubyで書いた。解が必ず存在することを見落としていた。Cは頭の位置の差を見る。Dは右上だけ尺取りで計算。

Eは2乗の典型でP,3P,5P,\dots円の商品にバラし、もう一つ典型で買えなくなる最小の価格を二分探索する。それぞれのテクニックがすぐ出てきたので解法は一瞬だったのに、実装で手こずってしまった。二分探索の上限はかなり大きくなるはずなので、オーバーフローに注意。

FはあらかじめXをソートしておくと常に大小関係が保たれるため、Ratedなクエリが区間になって遅延セグ木で解ける。Gは必要な情報をありったけ持って頂点1からの距離が等しい頂点集合を追加していくdpをすると十分高速だった。見た目ではO(N^9)だが定数倍がかなり小さく、また場合の数が0の状態をスキップしているのでもしかしたらNが一つくらい落ちているのかもしれない。

53分でノーペナ全完して7位。AはABC232-Aとまったく同じ問題で、最短コードもやはり同じ。今回は提出時刻の差でちゃんとShortestが取れていた。BもNibbles 6Bで勝ち。

A - QQ solver

www.youtube.com

ハーメルンでワンピース二次創作「百獣と呼ばれぬ男」を読了。人情のあるカイドウが主人公で、その意味では同じく百獣海賊団がメインの話「正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる」とは真逆だった。後者の印象が強く、合わないかと思ってちょっと敬遠していたが、そんなことはない。よく考えるとむしろ主人公たちの悪逆非道なふるまいにもかかわらず面白く読める作品のほうが特殊だった。

syosetu.org

午前3時就寝。

01/19(日)

午前7時に起きて3時間ちょっと日記を書いていた。それから二度寝。

午後3時に目覚ましで起床。AHC041の問題を読んで自明な解を提出した後、眠気に負けて布団で横になりながらハーメルンを読んだり二度寝したりしているうち、コンテスト時間が終わってしまった。

ALGO ARTIS Programming Contest 2025 Winter（AtCoder Heuristic Contest 041） - AtCoder

午後10時に布団を脱出。食事してシャワーを浴び、午後11時半からCF #998 div.3に出た。

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

Aはa_3に関する等式が3本立ち、一つ成立するごとにFibonaccinessが1増える。Bはラウンドごとに場がリセットされると思い込み、1ペナに加えてめちゃくちゃタイムロスした。いまだに問題文のどこを読めばわかるのか不明であり、自分はサンプルの説明を見て感づいた。嫌になったので残りは後ろから解いた。

Gは操作を整理すると、aとbを入れ替えない状態での2点swapに加え、(a_i,b_i)\leftarrow(b_i,a_i)というflipが偶数回行える。最小値の昇順に並べなおすなどするとswap操作が確定し、flip操作についてはdpで求まる。

Fは素因数分解した後の指数の多重集合だけが問題で、種類数は非常に少ない。各項の値が2以上となる場合の数を列の長さに対して再帰で求め、間に1を挟むことにすると、閉じた式で長さまで同時に数え上げることができる。EはGで連結でない点を結ぶ辺をFから取り除き、連結成分数の差を足せばよい。

Dは大小関係が逆転している箇所が存在すればその左に対して操作する必要があり、このとき2項のうちどちらかが0になるので、それより左もすべて0にする必要がある。そのような場合は操作を左から順に行うとして問題ないようなので、実際にやってみてチェックした。証明はあまりしていない。Cは最大値が達成可能。

66分で全完したもののペナルティが重く、最終的に46位になった。

www.youtube.com

インターンで稼働したり論文の修正をしたりしていたら朝になった。少し日記を書いて午前10時半就寝。

週記（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
神薙虚無最後の事件
戦地から帰ってきたタカシ君。普通に高校生活を送りたい2
攻撃力ゼロから始める剣聖譚4
創成魔法の再現者8
最強の剣聖、美少女メイドに転生し箒で無双する3
モンスターの肉を食っていたら王位に就いた件4
世界で一番『可愛い』雨宮さん、二番目は俺。3
灰原くんの強くて青春ニューゲーム8
勇者殺しの花嫁III
家事代行のアルバイトを始めたら学園一の美少女の家族に気に入られちゃいました。3
りゅうおうのおしごと！盤外編3
凡人転生の努力無双3
レベル0の無能探索者と蔑まれても実は世界最強です3
なぜ逃げるんだい？僕の召喚獣は可愛いよ
貴族令嬢。俺にだけなつく5
公女殿下の家庭教師18
引きこもり姉ちゃんのアルゴリズム推理
元英雄は大都会最強の便利屋さん1
異世界転移で女神様から祝福を！1
俺は学園頭脳バトルの演出家！1
最強の吸血鬼は普通に生きたい1
悪役令嬢はしゃべりません3
クラスの大嫌いな女子と結婚することになった。10
前世不死身の魔王にとって、デスゲームはぬるすぎる
若返った俺が、二度目の高校生活でやりたいこと
原作最強のラスボスが主人公の仲間になったら？2
現代魔法をぶち壊す、あたしだけの魔法
闇堕ちラスボス令嬢の幼馴染に転生した。俺が死んだらバッドエンド確定なので最強になったけど、もう闇堕ち【ヤンデレ化】してませんか？1

2月

偶然助けた美少女がなぜか俺に懐いてしまった件について
陰キャだった俺の青春リベンジ7
少年名探偵 虹北恭助のハイスクール☆アドベンチャー 新装版 上
かませ犬から始める天下統一3
神の代行者（自称）
不死を求める者、これを道士と呼ぶ
黄金の経験値VI
『無刀』のおっさん、実はラスダン攻略済み
サイレント・ウィッチIX
R．G．O！2
魔法使いが多すぎる
十分魔導士ハヤブサ
スクール＝パラベラム3

3月

こそっと恥じらう姿を俺だけに見せてくる学園のお姫さま
義妹生活13
義妹生活 another days
男子禁制ゲーム世界で俺がやるべき唯一のこと7
転生したら奴隷使役と回復のスキルを持っていたので遊び半分で奴隷だけの秘密結社を作ってみた
VTuberなんだが配信切り忘れたら伝説になってた10
異世界でチート能力を手にした俺は、現実世界をも無双する 宝城佳織伝
魔術探偵・時崎狂三の回顧録
転生王女と天才令嬢の魔法革命10
商人令嬢はお金の力で無双する4
転生した空間魔法使いは正体隠して目立ちたい！1
バスタード・ソードマン5
竹取物語 森見登美彦訳
ホーンテッド・キャンパス22
わたしの幸せな結婚 九
妹の配信に入り込んだらVTuber扱いされた件2
【悲報】コミュ力0オタク少女、ドラゴンをワンパンで沈めて有名配信者を助けたら不本意バズが止まらない1
Tier1姉妹2
なぜかS級美女達の話題に俺があがる件4
男嫌いな美人姉妹を名前も告げずに助けたら一体どうなる？6
俺が告白されてから、お嬢の様子がおかしい。3
ダンジョンに閉じ込められて25年。救出されたときには立派な不審者になっていた1
キグナスの乙女たち7
ソードアート・オンライン プログレッシブ9
王国を裏から支配する悪役貴族の末っ子に転生しました
お隣の天使様にいつの間にか駄目人間にされていた件11
友達の妹が俺にだけウザい11
平民出身の帝国将官、無能な貴族上官を蹂躙して成り上がる3
ロクでなし魔術講師と福音後記
魔王は扇子で蕎麦を食う
仮面の黒騎士。正体バレたのでもう学園でも無双する
弱小国家の英雄王子3
孤高の華と呼ばれる英国美少女、義妹になったら不器用に甘えてきた3
無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし7
無気力ニートな元神童、冒険者になる2

4月

アラサーがVTuberになった話。6
サイバーパンク居酒屋『郷』
英雄と賢者の転生婚6
最強魔法師の隠遁計画19
我が焔炎にひれ伏せ世界4
一般人の俺を芸能科女子達が逃がしてくれない件。
シャーロック＋アカデミー4
高校時代に傲慢だった女王様との同棲生活は意外と居心地が悪くない3
あとはご自由にどうぞ！3
非科学的な犯罪事件を解決するために必要なものは何ですか？2
俺は星間国家の悪徳領主！10
あたしは星間国家の英雄騎士！4
灰の世界は神の眼で彩づく4
煽り系ゲーム配信者（20歳）、配信の切り忘れによりいい人バレする。3
人数合わせで合コンに参加した俺は、なぜか余り物になってた元人気アイドルで国宝級の美少女をお持ち帰りしました。3
嫁に浮気されたら、大学時代に戻ってきました！
エロ漫画の悪役に転生した俺が、寝取らなくても幸せになる方法
エロゲの伯爵令嬢を奉仕メイド堕ちさせる悪役御曹司に転生した俺はざまぁを回避する
エルフの渡辺2
誘拐されそうになっている子を助けたら、お忍びで遊びに来ていたお姫様だった件2
公女殿下の家庭教師19
変人のサラダボウル8
地味なおじさん、実は英雄でした。3
許嫁が出来たと思ったら、その許嫁が学校で有名な『悪役令嬢』だったんだけど、どうすればいい？5

5月

天網恢恢アルケミー
犯人IAのインテリジェンス・アンプリファー
学園の魔王様と村人Aの事件簿
路地裏で拾った女の子がバッドエンド後の乙女ゲームのヒロインだった件2
怠惰な悪辱貴族に転生した俺、シナリオをぶっ壊したら規格外の魔力で最凶になった3
クラスで2番目に可愛い女の子と友だちになった7.5
凶乱令嬢ニア・リストン8
ガリ勉くんと裏アカさん3
一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら7
反逆者として王国で処刑された隠れ最強騎士4
凡人探索者のたのしい現代ダンジョンライフ5
現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変7
転生したら皇帝でした9
推しにささげるダンジョングルメ03
図書館の魔女 高い塔の童心
古川くんと二ノ瀬さん
俺にだけ小悪魔な後輩は現実でも可愛いが、夢の中ではもっと可愛い2
妖精の物理学
悪役御曹司の勘違い聖者生活5
ざつ旅謎-That's "Mystery" Journey-
二度目の勇者に仲間はいらない
間取りと妄想
願わくば海の底で
記憶の対位法
やり直し悪徳領主は反省しない！3
これが魔法使いの切り札4
双子まとめて『カノジョ』にしない？5
異世界でチート能力を手にした俺は、現実世界をも無双する18
口もききたくないあいつと、自習室で甘い筆談
娼館の乙女1
岸辺露伴は動かない 懺悔室
俺は学園頭脳バトルの演出家！2
あの子は可愛い男の子。
無双ゲーに転生したと思ったら、どうやらここはハードな鬱ゲーだったらしい1
前世は冷酷皇帝、今世は幼女2
後方師匠面したい系転生者1
薬屋のひとりごと16
カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている2
才女のお世話10
女友達は頼めば意外とヤらせてくれる6
モブ司祭だけど、この世界が乙女ゲームだと気づいたのでヒロインを育成します
誰が勇者を殺したか 勇者の章

6月

あがり
世界最強の魔法使い。だけどぼっち先生は弟子に青春を教わります
二度目はタの付く自由業1
異世界転生勧誘詐欺
凡人転生の努力無双4
メイジアン・カンパニー10
天嬢天華生徒会プリフェイズ
家事代行のアルバイトを始めたら学園一の美少女の家族に気に入られちゃいました。4
サイレント・ウィッチIX -extra-
【悲報】お嬢様系底辺ダンジョン配信者、配信切り忘れに気づかず同業者をボコってしまう4
北欧美少女のクラスメイトが、婚約者になったらデレデレの甘々になってしまった件について3
なぜ逃げるんだい？僕の召喚獣は可愛いよ2
このコスプレお姉さんは、僕専用らしい
転生王女と天才令嬢の魔法革命11
引退した皇帝騎士、帝国三大組織の主となる
スパイ教室13
義妹生活14
男子禁制ゲーム世界で俺がやるべき唯一のこと8
攻撃力ゼロから始める剣聖譚5
無気力ニートな元神童、冒険者になる3
無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし8
悪役令嬢はしゃべりません4
転生した空間魔法使いは正体隠して目立ちたい！2

7月

時々ボソッとロシア語でデレる隣のアーリャさん10
やがて黒幕へと至る最適解3
灰原くんの強くて青春ニューゲーム9
元勇者はのんびり過ごしたい1
好きだった子をメイドにしたら、俺の部屋でこっそりナニかしている
最強の悪役が往く2
この青春に、別解はない。
社畜剣聖、配信者になる4
黄金の経験値VII
サイレント・ウィッチX
お嬢様頭脳戦
りゅうおうのおしごと！20
商人令嬢はお金の力で無双する5
イヴと偽りの天使たち
公女殿下の家庭教師20,0
エロゲの伯爵令嬢を奉仕メイド堕ちさせる悪役御曹司に転生した俺はざまぁを回避する2
異世界でチート能力を手にした俺は、現実世界をも無双する 宝城佳織伝2
探偵はもう、死んでいる。13
モンスターの肉を食っていたら王位に就いた件5
俺は星間国家の悪徳領主！11
創成魔法の再現者9
オーバーライド
【悲報】コミュ力0オタク少女、ドラゴンをワンパンで沈めて有名配信者を助けたら不本意バズが止まらない2
男嫌いな美人姉妹を名前も告げずに助けたら一体どうなる？7
ダンジョンに閉じ込められて25年。救出されたときには立派な不審者になっていた2
TS衛生兵さんの戦場日記V
カナンの城
恋愛魔法学院3

8月

数学ガール リーマン予想
不死を求める者、これを道士と呼ぶ2
美少女フィギュアのお医者さんは青春を治せるか2
悪役ムーブで青春リスタート！
汝、暗君を愛せよ
不死探偵・冷堂紅葉3
俺がシフトの時だけバイト先の喫茶店に来る、クラスの美少女モデル様
王様のプロポーズ8
仮面の黒騎士。正体バレたのでもう学園でも無双する2
灰の世界は神の眼で彩づく5
最強の剣聖、美少女メイドに転生し箒で無双する4
無双ゲーに転生したと思ったら、どうやらここはハードな鬱ゲーだったらしい2
バズれアリス4
魔法や異能が存在する世界のモブのはずが、裏では黒幕扱いされていた話1
神の試練で最強になった凡人当主、災厄前の世界に帰還して無双する1
稼ぎの少ないオカルト事務所所長、VTuberになる01
屍王の帰還3
妹の配信に入り込んだらVTuber扱いされた件3
こそっと恥じらう姿を俺だけに見せてくる学園のお姫さま2

9月

バスタード・ソードマン6
凶乱令嬢ニア・リストン9
池袋ウエストゲートパークXIX
孤高なカノジョと、彼女の部屋でシてること
転校先の清楚可憐な美少女が、昔男子と思って一緒に遊んだ幼馴染だった件9
戦地から帰ってきたタカシ君。普通に高校生活を送りたい3
悪役好きの俺、推しキャラに転生4
キノの旅XXIV
夜の帳に闇は閃く3
好きだった子をメイドにしたら、俺の部屋でこっそりナニかしている2
お隣の天使様にいつの間にか駄目人間にされていた件11.5
二度目の勇者に仲間はいらない2

読書記録（2025）

kotatsugame.hatenablog.com

1月

  • 16日
    配信に致命的に向いていない女の子が迷宮で黙々と人助けする配信
  • 22日
    なぜ逃げるんだい？僕の召喚獣は可愛いよ
    戦地から帰ってきたタカシ君。普通に高校生活を送りたい2
  • 23日
    モンスターの肉を食っていたら王位に就いた件4
    世界で一番『可愛い』雨宮さん、二番目は俺。3
  • 28日
    最強の吸血鬼は普通に生きたい1
    前世不死身の魔王にとって、デスゲームはぬるすぎる
  • 29日
    闇堕ちラスボス令嬢の幼馴染に転生した。俺が死んだらバッドエンド確定なので最強になったけど、もう闇堕ち【ヤンデレ化】してませんか？1
    悪役令嬢はしゃべりません1,2

2月

  • 1日
    悪役令嬢はしゃべりません3
  • 2日
    若返った俺が、二度目の高校生活でやりたいこと
  • 3日
    引きこもり姉ちゃんのアルゴリズム推理

3月

  • 13日
    こそっと恥じらう姿を俺だけに見せてくる学園のお姫さま
  • 15日
    『無刀』のおっさん、実はラスダン攻略済み
  • 16日
    不死を求める者、これを道士と呼ぶ
  • 18日
    魔術探偵・時崎狂三の回顧録
  • 19日
    スクール＝パラベラム3
    異世界転移で女神様から祝福を！1
    かませ犬から始める天下統一2
  • 25日
    魔王は扇子で蕎麦を食う
  • 27日
    王国を裏から支配する悪役貴族の末っ子に転生しました
    ダンジョンに閉じ込められて25年。救出されたときには立派な不審者になっていた1
    妹の配信に入り込んだらVTuber扱いされた件2
    【悲報】コミュ力0オタク少女、ドラゴンをワンパンで沈めて有名配信者を助けたら不本意バズが止まらない1

4月

  • 2日
    最強魔法師の隠遁計画19
    黄金の経験値VI
    煽り系ゲーム配信者（20歳）、配信の切り忘れによりいい人バレする。3
  • 4日
    一般人の俺を芸能科女子達が逃がしてくれない件。
    転生したら奴隷使役と回復のスキルを持っていたので遊び半分で奴隷だけの秘密結社を作ってみた
  • 8日
    エロゲの伯爵令嬢を奉仕メイド堕ちさせる悪役御曹司に転生した俺はざまぁを回避する
    エロ漫画の悪役に転生した俺が、寝取らなくても幸せになる方法
  • 9日
    嫁に浮気されたら、大学時代に戻ってきました！
  • 11日
    非科学的な犯罪事件を解決するために必要なものは何ですか？2
  • 12日
    サイバーパンク居酒屋『郷』
  • 13日
    冒険者酒場の料理人2
    アラサーがVTuberになった話。2
  • 15日
    アラサーがVTuberになった話。3
  • 20日
    アラサーがVTuberになった話。4
  • 22日
    アラサーがVTuberになった話。5
  • 23日
    アラサーがVTuberになった話。サブチャンネル
  • 24日
    アラサーがVTuberになった話。6
  • 26日
    攻撃力ゼロから始める剣聖譚2
  • 27日
    攻撃力ゼロから始める剣聖譚3
  • 28日
    攻撃力ゼロから始める剣聖譚4

5月

  • 2日
    地味なおじさん、実は英雄でした。3
  • 3日
    推しにささげるダンジョングルメ03
    古川くんと二ノ瀬さん
  • 4日
    一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら7
    凶乱令嬢ニア・リストン7
  • 5日
    凶乱令嬢ニア・リストン8
  • 9日
    サイレント・ウィッチII,III,IV
  • 11日
    サイレント・ウィッチIV -after-
    サイレント・ウィッチV
  • 12日
    サイレント・ウィッチVI
  • 14日
    サイレント・ウィッチVII
  • 15日
    サイレント・ウィッチVIII
  • 17日
    サイレント・ウィッチIX
  • 20日
    サイレント・ウィッチ-another-上
  • 23日
    サイレント・ウィッチ-another-下
  • 24日
    ルームメイトと謎解きを
    許嫁が出来たと思ったら、その許嫁が学校で有名な『悪役令嬢』だったんだけど、どうすればいい？5
  • 25日
    ガリ勉くんと裏アカさん3
  • 27日
    無双ゲーに転生したと思ったら、どうやらここはハードな鬱ゲーだったらしい1
    前世は冷酷皇帝、今世は幼女2
    娼館の乙女1
  • 28日
    間取りと妄想
  • 29日
    二度目の勇者に仲間はいらない
  • 30日
    後方師匠面したい系転生者1
  • 31日
    才女のお世話10

6月

  • 14日
    二度目はタの付く自由業1
  • 16日
    天嬢天華生徒会プリフェイズ
  • 25日
    カードゲームで世界が滅ぶ世界に転生してカードショップを開店したら、周囲から前作主人公だと思われている2
  • 27日
    怠惰な悪辱貴族に転生した俺、シナリオをぶっ壊したら規格外の魔力で最凶になった3
  • 29日
    悪役令嬢はしゃべりません4

7月

  • 1日
    なぜ逃げるんだい？僕の召喚獣は可愛いよ2
  • 4日
    元勇者はのんびり過ごしたい1
    このコスプレお姉さんは、僕専用らしい
  • 5日
    虚構推理短編集 岩永琴子の密室
  • 6日
    凡人転生の努力無双3
  • 10日
    凡人転生の努力無双4
    U-15サッカー日本代表だけど部活は幼馴染と一緒の文芸部です
    口もききたくないあいつと、自習室で甘い筆談
    神の代行者（自称）
  • 11日
    黄金の経験値VII
  • 13日
    社畜剣聖、配信者になる3
  • 14日
    社畜剣聖、配信者になる4
  • 15日
    好きだった子をメイドにしたら、俺の部屋でこっそりナニかしている
  • 16日
    お嬢様頭脳戦
  • 29日
    モンスターの肉を食っていたら王位に就いた件5
  • 31日
    よって、初恋は証明された。

8月

  • 2日
    恋愛魔法学院3
  • 5日
    この青春に、別解はない。
  • 6日
    ざつ旅謎-That's "Mystery" Journey-
    オーバーライド
  • 10日
    岸辺露伴は動かない 懺悔室
  • 13日
    美少女フィギュアのお医者さんは青春を治せるか2
    ケーキ王子の名推理7
  • 15日
    ダンジョンに閉じ込められて25年。救出されたときには立派な不審者になっていた2
  • 20日
    俺がシフトの時だけバイト先の喫茶店に来る、クラスの美少女モデル様
  • 21日
    俺は星間国家の悪徳領主！10,11
  • 26日
    稼ぎの少ないオカルト事務所所長、VTuberになる01
  • 27日
    無双ゲーに転生したと思ったら、どうやらここはハードな鬱ゲーだったらしい2
  • 28日
    屍王の帰還3
    妹の配信に入り込んだらVTuber扱いされた件3
    魔法や異能が存在する世界のモブのはずが、裏では黒幕扱いされていた話1
  • 29日
    神の試練で最強になった凡人当主、災厄前の世界に帰還して無双する1
  • 30日
    こそっと恥じらう姿を俺だけに見せてくる学園のお姫さま2
    仮面の黒騎士。正体バレたのでもう学園でも無双する
  • 31日
    仮面の黒騎士。正体バレたのでもう学園でも無双する2

9月

  • 2日
    凶乱令嬢ニア・リストン9
  • 4日
    バスタード・ソードマン5
  • 5日
    孤高なカノジョと、彼女の部屋でシてること
  • 9日
    戦地から帰ってきたタカシ君。普通に高校生活を送りたい3
  • 11日
    バスタード・ソードマン6
    悪役ムーブで青春リスタート！
  • 12日
    汝、暗君を愛せよ
  • 13日
    商人令嬢はお金の力で無双する2,3
  • 14日
    商人令嬢はお金の力で無双する4
  • 16日
    商人令嬢はお金の力で無双する5
  • 18日
    サイレント・ウィッチIX -extra-
    サイレント・ウィッチX

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