週記（2024/08/19-2024/08/25）

土日の分は参加記として切り出される予定です。

08/19(月)

午前11時半起床。

今日から三日間、山形大学で開催されている「離散数学とその応用研究集会2024」にオンラインで参加する。事前にプログラムを読んでどの発表を聞くか目星を付けておいた。本当はそれ以外の発表も可能な限り聞くつもりでいたのだが、今日になってそれほどのモチベーションが存在しないことを自覚した。

JCCA-DMIA-2024

初日は組合せ最適化関連の発表が目当て。発表者にも聴衆にも先々週のCOSSで出会った人が数多くいて、自分も対面で参加すればよかったなと思った。参加に向けて動き始めたのが遅すぎて各種申請が間に合いそうになく断念したという経緯がある。また今日になってもまだお腹の調子が不安定なので、結果的にはオンライン参加で正解だった。

午前の部は午後0時半に終了。お盆休みが明けた学食に行って昼食を摂った。帰宅後、午後の部の発表は聞かず、インターン関連で少しコードを読んでいた。

午後3時半からインターン先定例会に出席。3週間ぶりだが何も稼働できていないので、進捗報告では感染性胃腸炎にやられた話をした。タスクについては、いつまでも「待ちのフェーズ」とかほざいてのんびりしているわけにもいかない。相談するつもりで今週木曜日に1on1をお願いしてある。

勉強会はヒューリスティックコンテストの高速化に高度なデータ構造を用いたという話だった。ヒューリスティックコンテストは制約が小さめなので、オーダーを落とすよりは定数倍を改善するほうが効くものと考えていたが、そこは問題によりけりということらしい。いくら入力が小さくても、計算する値にはいくらでも複雑化する余地がある。

解散後、また学食に行って夕食を摂り、先週の週記を書いていた。午後10時半くらいに先々週のものと合わせて投稿。この2週間分はUniversal Cupを除いてすべて埋めることができた。

しばらく数値計算と格闘した後、新刊のチェックを行った。前回からずいぶん間が空いてしまったので、8月と9月のほぼ2か月分をチェック。本の注文サイトにオーバーラップ文庫の新刊が登録されていなかったが、それ以外で33冊注文した。チェック中、3月に出た新刊を見落としていたことが発覚。どうやら新刊チェックに使っているサイトの時点で抜けていたらしい。

久しぶりに読書した。「ムーンシャイン」を読了。前半部分は7月末に読んだのだが、そこから後半を読み切るまでにいろいろな出来事があってかなり長くかかってしまった。

円城塔さんの作品をいくつも読んだことがあるわけではないが、普通の小説のように明確なストーリーがあるようなものではないと自分は認識している。もっと言うと、作品ごとに主題となるものが存在しており、それを理解・解釈できないと読んでも意味が分からないと考えている。以前「文字渦」を読んだときにそのような思いを抱き、今回それを強めることとなった。

どの短編も全くの無から生まれてきたわけではなくて、ちゃんとモチーフになる事物が存在したらしい。

週記（2021/03/29-2021/04/04） - kotatsugameの日記

ただ今回は分かりやすかったほうかもしれない。一つ目の短編はより短い短編の集まりとして構成されているから別として、それ以外の三つは日英のタイトルから主題がわかる。四つ目はタイムリーな話題でもあった。画像生成AIの黎明期からこの作品が著されるまで、だいたいどんな感じの画像が生成でき、また生成されたかというのはまだ何となく記憶に残っており、それを元に想像力を働かせることができた。

午前5時過ぎ就寝。

08/20(火)

午前9時半起床。今日の研究集会はグラフ理論の発表が目白押しだったのだが、午前中は眠気に負けてしまいあまり聞けなかった。

昼休みの時間帯に原付を点検に持っていこうと考えていたのに、バイク屋が定休日だった。間が悪いことに第三水曜日、すなわち明日も休みらしい。外出する特別な理由がなくなったので、学食にすら行かず布団に倒れこんで過ごした。午後の部を1時間ほど聞いて今日は終わり。

オーバーラップ文庫の新刊がサイトに登録されていたので、追加で6冊注文した。また今週末オンサイトのために東京に行くので、乗る新幹線を決めた。そうしているうちに午後4時を回ったので大学に向かい、閉店間際の生協で切符を購入したのち、学食の夜の部が始まるのを待って食事した。

その足で街に繰り出し、午後6時前から4時間ほどゲーセンで遊んだ。新曲を埋めた後は前回のプレイで残っていた14+の未鳥を触り、計21クレプレイ。日を置いたからというよりは単に前回真面目に詰めなかっただけという感じだが、14+のSSSを新しく三つ出すことができた。「ΩΩPARTS」は最後の超高速地帯がそこそこ安定していたのにその前の鍵盤にどんどん癖がついて、噛み合い待ちが大変だった。

ゲーセンから出たくらいの時間に、とうとう通信制限がかかった。かなり久しぶりだ。実家はネット回線が貧弱なので携帯回線を使って過ごしたのだが、以前より明らかに速いペースで通信量が増えていってびっくりしていた。最近現れたTwitterの動画広告が原因だと考えている。せっかく画像のサムネイル表示をオフにして節約しているのに、勝手に動画なんて流されてはたまったものではない。

腹の調子が結構良さそうなので久しぶりにラーメンを食べ、午後11時前に帰宅。シャワーを浴びて半からCF #967 div.2に出た。

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

書く

www.youtube.com

1時間半ほどインターンの稼働をし、ハーメルンを読んで午前7時就寝。

08/21(水)

午前11時起床。研究集会最終日だが寝坊してしまった。午前の部を少し聞いて、正午くらいに二度寝した。

午後4時半起床。しばらくラノベを読んで午後6時に学食に向かい、夕食後は今日もまた直接ゲーセンに向かった。地下鉄駅で後輩たちと遭遇し、しばらく話していたら、ホスフィンが通りかかってかなりびっくりした。

午後7時から閉店の午後11時過ぎまでで25クレプレイ。14+からSSS一つ、SSS+三つ、AJ一つを出した。「チューリングの跡」は昨日プレイしたら鍵盤がボロボロだったが、今日は上手い日だったらしい。これで14+の未鳥はいつもの「Reverberate」1譜面に戻った。これにも上手い日が来ることを期待して、今は特に座学などしていない。

油そばを食べ、ドンキに寄って帰宅。

うっかり「Game of Vampire」の読み返しを初めてしまい、翌朝まで時間が飛んだ。主人公アンネリーゼ・バートリがホグワーツに入学するまでたったの60話しかないが、その中でパチュリー世代・アリス世代・フラン世代という3世代100年にも渡るキャラたちの濃密な関わりを導入しきっているのは驚異的だと思う。また、そのような世代を分けた東方とハリポタとオリキャラの組み合わせ方も芸術的。相変わらず最高だった。

syosetu.org

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

08/22(木)

目覚ましで起きたら、1on1開始時刻の正午だった。布団から飛び出てPCを付け、一言断って顔を洗う時間をもらった。今日の1on1では月曜日にも言っていたとおり今後のタスクに関して相談し、新しいものを紹介してもらった。タスク内容や背景について説明を受け、ピッタリ1時間で終了。インターンの歴だけは長いので、プロジェクトの経緯については少し知っていることもあって話が早かった。

ようやくバイク屋の営業日になったので、電話で確認を取り点検に持っていった。実際に作業するのは明日になるらしいが、先に預けておく。もっと言うと明日と週末はそれぞれ用事があるので、引き取るのは週明けまでずれ込むことになる。

バイクを預けた後街で昼食を摂ろうとして、いい感じの店を探しながら歩いていたらいつの間にかミスドまで来てしまった。もういい時間だったので諦めて入店。腹具合とドーナツの体積を比較して7個注文したら思ったより高くついたし、量ではなく甘さにやられて完食するのにかなり苦労した。

食休みのため1時間くらい店内でハーメルン「Game of Vampire」を読んでいた。2年生編ラストは非常に好きな箇所で、その部分を読み返すだけで泣いてしまうのだが、今回久しぶりに最初から通して読んだらもっと心にくるものがあった。涙をこらえながら、これは家で一人で読むべき箇所だったなと後悔した。

Game of Vampire - 二人で - ハーメルン

ゲーセンに行って10クレだけプレイ。バイク屋に向かった時点では遊ぶ予定はなかったので手袋を持ってきておらず、素手でプレイした。手の滑りがあまりよくないのに無理して理論値を狙ったらかなり苦労したし、最終的に指を立ててプレイしたので爪が少し剥がれて痛い。散々だったが新曲埋めは結構スコアが出た。

ホスフィンに誘われて一緒に夕食を摂った。辛い物が食べたいと伝えて韓国料理屋に連れて行ってもらったが、しっかり辛くて腹の具合が悪くなった。まだ本調子には程遠いらしい。

午後8時前、この時間に街で暇しているというのは非常に珍しい。何をしようか迷って少しブックオフを冷かしたりもしたが、結局はゲーセンに戻ってきてしまった。追加で14クレプレイ。粘着して「FREEDOM DiVE」のAJを出した。いつの間にか冒頭の変なリズムも見切れるし、終盤も普通に追いつくようになっていて感動した。

日付が変わる前に帰宅。シャワーを浴びて日記を書き、午前4時過ぎに寝た。

08/23(金)

正午起床。週末のUniversal Cupはオンサイトの日と被っているため、運営に連絡を取って今日の午後1時から走ることにしていた。それまでに学食で昼食を摂り、購買で大量に届いたラノベを受け取ってきた。

午後1時からUniversal Cup 7回目、Warsawセット。

書く

AHC036が始まっていたので提出した。

RECRUIT Nihonbashi Half Marathon 2024 Summer（AtCoder Heuristic Contest 036） - AtCoder

午後9時からはyukicoder 441に参加した。

yukicoder contest 441 - yukicoder

書く

少しインターン関連の作業をした後、ハーメルンを読み始めた。すぐ切り上げて明日の準備をするつもりが全く止められず、そのうち布団に移動して午前4時前には寝落ちしていた。

08/24(土)

午前8時起床。今日はオンサイトコンテストのため東京に向かう。シャワーを浴びて洗濯し、荷造りや書類作成などの準備を行った。これらは本来昨日寝る前に済ませる予定だったが、うっかり寝落ちしてしまったので今慌ててやっている。それでも間に合う時間に目覚ましをかけておいたのだけはファインプレーだった。

午前9時半に出発。駅で立ち食いそばを食べ、午前10時半発の新幹線に乗った。移動中はハーメルンを読んだり寝たりしていた。東京駅には正午過ぎ着。すぐ東京メトロ丸ノ内線に乗り換えて西新宿まで移動し、そこから徒歩で会場に向かったら、ちょうど受付が始まる午後1時くらいに到着した。

机に書かれた番号と名札の番号が1だけずれていたので、どこからずれているのか探し歩いてみたら、単に一つ前のこたまねぎさんの名札と取り違えられていただけだったことが判明した。

実際に開会するまでは1時間ほどある。コンビニで買ったパンを食べたり、人と話したりしていた。計算用紙が配られないとぼやいたら近くにいた方に恵んでもらったのだが、その直後に後ろの方に置いてあるとアナウンスされて申し訳ない気持ちになった。

ちょっとした開会式の後、ネットワークトラブルもなく予定通り午後2時10分からコンテスト開始。

第五回日本最強プログラマー学生選手権 -決勝- - AtCoder

Aは順当に解けた。(x_i,x_{i+1})=(a,b)となる確率は、多項係数で計算してみると\frac{A_aA_b}{S(S-1)}となる。これをすべてのiとa\gt bで足し合わせればよい。Sで割るべきところをNで割っていて少し手間取った。

Bは典型。vで操作する確率を考えるというのがよくある手筋で、今回は約数の個数をd(v)として1/d(v)となるからその和を求めればよい。これは乗法的関数の和だから、今回の制約でも解けるようなライブラリが存在する。

乗法的関数のprefix sum | Nyaan’s Library

以前拝借した記憶があるが、使い方は覚えていない。親切にも当時の日記にメモが残してあったのに、今日もまたverifyコードを読解した。結局fprimeはpi_tableを2で割ったものになる。貼るだけ問題なのに窃盗に時間をかけてしまったな、と思いつつ順位表を見たらFAでびっくりした。

設計が特殊なので使い方のメモをしておきたい。

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

次にCを読んだ。なんとかして行列累乗にしたいが、どうにもうまくいかない。Dも同じ900点だったことを思い出し、順位表に一切情報がないことを確認しつつ試しに読みに行ってみたら、思いの外なんとかなりそうだったので取り組んだ。

1要素ずつ追加するdpを考える。状態は\min(X_1),\min(X_2)だが、片方はこれまで見た要素の最小値mになっているので、もう片方だけ持つ。それを状態vとして、新しく追加する要素をaとしよう。

ほとんどの遷移は状態vを同じく状態vに移す。a\lt mなら+a、そうでなくてv\gt aなら+m、v\lt aなら+v。状態aだけは新しく生じることがあって、状態v\ge aのMAXにaを足したものが値となる。

これを実家dpにしたいが、+vだけが問題。しばらく考えてどうしようもなかったので、平方分割を試みた。ブロックに対して+vの遷移が行われた回数を管理し、CHTを計算しておいて最大値を取得する。状態aへの更新だけが既存のCHTを破壊するので、再構築はブロック一つ分だけでよい。

これでブロック幅Wに対しO(NW+N^2/W)となっている。ただのCHTではなく、+vの遷移が何回以上ならどの値が最大値になるかという情報を持ってみたり、その回数がN回を超えるなら無視したりしてみると、かなり高速になった。

それでもCHTの再構築は定数倍が悪いので、ブロック幅は小さいほうが嬉しい。ランダムケースによって見出したW=400を使って提出した。じわじわとジャッジが進み、見事一発AC。TL 6secに対して4sec弱で通ったので思ったより余裕があった。

Bに引き続いてDもFA。その10分ちょっと後の順位表凍結時点では、なんとC以降のACは自分のみという圧倒的な状態だった。それ以降興奮してしまってあまり集中できていた気がしない。結局それから1問も解けなかった。

Eはチラ見したが、変な出力形式が逆行列の存在性に関する話だろうなと思っただけ。Cは行列累乗のため2N状態で表現してみるも遷移がうまくいかず、ラグランジュ補間もダメだった。

ABDの3完。CはBMBMというやつならうまくいくらしい。違いがよくわかっていなかったが、Nyaanさんに聞いたらBMBMで計算できる多項式のうち分母が1-xのべき乗であるもののみがラグランジュ補間できるとのことだった。

トイレ休憩後、表彰式。準優勝だった。優勝したyutaka1999さんは凍結後にDとEを解いており、大差で負け。しかし2位でも望外の結果だと感じる。maroonさんにメダルをかけてもらった。

懇親会ではAtCoderのノベルティ（黒いトートバッグ）を入手するためスポンサーブースをすべて回った。またUniversal Cupの話をしているところに近づいてみた結果、yutaka1999さんを筆頭とした錚々たるメンバーと会話することに成功した。そのうち行われるであろうUniversal Cup Finalsでまたご一緒することになる。

COSSでもお会いしたテナガザルさんに依頼され、色紙にサインを書かせてもらった。スマホのペイントアプリで書いたことはあるが、色紙というのは流石に初の経験。それにしては結構よく書けたのではないかと、自分では思っている。包丁だけでなくWindowsロゴマークも描けばもっとよかったかも。

懇親会は午後8時前に解散。その足でmaspyさん、Rubikunさん、rniyaさんと近くのファミレスに入った。懇親会で少し飲み食いしたので、夕食は控えめに。隣の席にはpotato167さんご一行がいた。

そのファミレスで他3人に見守られつつ、午後9時からABC368に参加した。今日はG問題が575点の簡単回なので、適当に出てもひどいことにはならないだろうと考えていた。

Hitachi Vantara Programming Contest 2024（AtCoder Beginner Contest 368） - AtCoder

Aはよい。Bは何も考えずシミュレート。Cも5で割った余りを見ながらシミュレート。Dは指定された頂点の一つからdfsした。

Eでかなり詰まった。見た目は牛ゲーだが制約が大きいし、そもそも疲れているのか問題設定がうまく頭に入ってこない。中空を睨みながらなんとか考えをまとめ、時系列順に処理するだけでよいことに気づいた。ところが実装中にX_1を書き換えてしまうバグを埋め込み、これの解消にも結構時間を取られた。

Fは何も考えず実験。Grundy数が16以下だったので、定義通りに求めるコードを書いた。Gは問題文に太字で書いてある制約からB\ge 2が少ないことにすぐ気づいた。\logが二つ付くのにTL 2secで不安になりつつも実装、全く問題なく通った。

全完2位。1位はペナルティを含めれば自分と48秒差だから、Eでもう少し頭が働いていれば優勝もあり得たかもしれないと思うと少しもったいない気持ちになった。一方それ以外の問題、特にG問題を一切バグらせず非常にスピーディーに通せたのは上振れた部分だったから、総合するとまあ、これがほぼほぼ最良の結果だろう。

そのままコードゴルフを始めた。AとBはNibbles、FはPerl。ちなみにFのGrundy数が素因数の重複を込めた個数であることは周りの人に教えてもらった。真に何も考えていなかったことを自覚し、反省。

午後10時解散。すぐ近くに取っておいたホテルにチェックインし、しばらくエゴサして楽しんだ後シャワーを浴びて日記を書き、午前2時半に寝た。

08/25(日)

午前9時起床。ホテル1階のサンマルクカフェで朝食を摂った。ここの支払いもホテル宿泊プランに含まれている。専用の朝食会場があるようなホテルは高すぎたのでやむなく、という気持ちが泊まる前にはあったが、実際経験してみるとこちらはこちらでかなり良かった。サンマルクカフェのホットサンドが好きなだけかも。

荷物をまとめて午前10時チェックアウト。帰りの新幹線は夕方なので、今日は1日東京で遊べる。昨夜の時点でナンさんに連絡を取っておいた。睡眠に失敗したようで多少手間取ったが、午前11時前に新宿駅で合流。待っている間ハーメルンを読んでいたため時間の経過は気にならなかったものの、うっかり作中世界に没入しすぎて、しばらくは夢から醒めたような心地だった。

午前中は新宿駅直結のビルに入っているゲーセンでmaimaiとCHUNITHMのマッチングをした。平気な振りをしていたが素手でmaimaiをプレイするのは難しい。まだとても脱力なんて意識できる腕前ではないから、かなり強くボタンを叩くことになって、指の関節部分を痛めてしまった。

午後1時を目掛けて秋葉原に移動。ナンさんが呼んでくれたplatypusさんとhogetさんと合流した。高校時代からJOI参加者として交流を持っていたが、ここ数年は全く会っていなかったお二人。自分の認識がまだ高校生のまま止まっており、もうM2であることを聞いてなんというか遠いところに来たなあという気持ちになった。

昼食は台湾まぜそば。

午後もゲーセンでマッチングを楽しんだ。自分がプレイした機種はmaimai、ポラリスコード、SDVX、CHUNITHM、オンゲキ。みんな多機種勢の中にCHUNITHM一辺倒の自分が紛れ込み、スコアでは結構差がついていた。SDVXは昔の感覚がまだなんとか残っていたようだ。

ここ数年音ゲーをするときはほとんど一人だったので、一つの機種「だけ」に専念するのを当然のことと考えていたが、こうやってワイワイ楽しむなら多機種に手を伸ばそうとするのも納得である。

CHUNITHMでは良いスコアが出たかというとそんなこともなく、「Aleph-0」ULTIMAを投げられて鍵盤力の差でボコボコにされてしまった。一人でプレイしていると嫌な譜面からずっと逃げ続けてしまうのも良くないポイントか。

午後6時に離脱。新幹線は東京駅を午後6時20分に出るが、秋葉原からなら余裕で間に合う。ホームに着いてみると、大雨の影響とやらで10分以上遅れていた。仙台までの車内ではハーメルンを読もうとしつつ眠気に負けそうになっていた。

午後8時に仙台駅到着。夕食をどこかで摂るつもりだったが、よく考えるとARCまでほとんど余裕がない。アンパンマン像だけ撮影し、コンビニでパンを買って帰宅した。

何とかシャワーを浴びる時間はあった。午後9時からARC183。

Marubeni Programming Contest 2024 (AtCoder Regular Contest 183) - AtCoder

書く

午後11時半からはCF #968 div.2に出た。

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

書く

www.youtube.com

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