09/02(月)
午後3時過ぎ起床。半からインターン先定例会に出席した。
先週は以前から関わっているツールについての調査を依頼された。念願のタスクだが、まだ稼働できていない。進捗報告はこれで終わりで、今週はちょっとした事情で勉強会がなくなったため、普段よりかなり早く解散となった。
まだ購買が開いている時間だったので、向かってお菓子とラノベを買い、開店直後の学食で夕食を摂って帰宅。それからはずっと先週の週記を書いていた。
午後7時にAHC036が終了した。自分は結局、初日に1回提出したきりとなってしまった。解法は適当な頂点を根としてdfs木を取りその上だけ移動するというもの。全域木としてdfs木を選んだのは、より長いパスがあると嬉しいと思ったからだった。配列は頂点をdfs順に並べて作成し、配列
は毎回すべて書き換えることにして最も遠くまで進めるものを貪欲に選んだ。
シード0で試したらサンプルよりスコアが悪かったのだが、試しに提出してみたところ、順位表のサンプルそのままと思しき団体より上に位置していてびっくりした。シード0はという点で少し特殊なケースだったらしい。感想戦をチラ見すると、初手で木を作る部分だけは当たっていたようだ。
RECRUIT Nihonbashi Half Marathon 2024 Summer（AtCoder Heuristic Contest 036） - AtCoder
午後11時半に先週の週記を投稿。Univarsal Cupを除いてすべて書き切ることができた。先週はハーメルンに捧げた週だった。今日も投稿後は朝方までずっとハーメルンを読んでいた。
「Game of Vampire」の「アンネリーゼ・バートリと幻想の守護者」章を読了。この章の敵は不死身のため勝った気がしない。彼女の思想に主人公が惹かれているのも、先週読んだ章と同じく好ましくない。しかしどちらの敵も動機は十分説明されており、それは理屈の上では理解できるものだった。自分が拒否反応を起こしているのは前半が重厚すぎて舌が肥えてしまったからかも。ともかくこれにて「Game of Vampire」のすべてのイベントは終了し、あとは少しのエピローグを残すのみである。
シャワーを浴びてゴミをまとめ、布団に入った。しばらくハーメルンを読んで午前6時半就寝。
09/03(火)
午前10時起床。今日はホスフィンの研究室にお邪魔して研究合宿を行う。昨日約束した時間は……午前10時。遅刻である。
今日は天気が悪いらしいが、雨合羽を持って原付で出発。太陽が出ておらず信じられないくらい寒い。購買でパンを買いつつ研究室に向かった。
合宿では春に公開したpreprintを加筆修正していた。昼食は午後1時に学食で摂り、その後大学図書館の工学分館で参考文献を借り出した。夕食は午後6時半ごろ、地下鉄で街に出て「隠れ家洋食の店 ぴかぴかぶー」に入り、サラダと大盛りのペペロンチーノを食べた。スーパーで買い物をして戻った。
— こたつがめ (@kotatsugame_t) 2024年9月3日
午後10時半に解散。今日は加筆修正のうち加筆部分をひとまず終わらせることができた。明日も午前9時から集まる約束なので、そこで修正部分を進めていきたい。早い時間から合宿を始めるのは、午前の時間を長く取るのが良いだろうという考えからである。
帰宅してシャワーを浴び、午後11時半からCF #971 div.4に出た。
Dashboard - Codeforces Round 971 (Div. 4) - Codeforces
A、Bはよい。Cはと
を見て算数。Dは特殊な直角三角形がちゃんとサンプルに用意されていて優しい。Eは絶対値を外した値の符号が切り替わるところを二分探索で求めた。Fは
にして計算。
Gは、まずすべての幅の区間について
を求める。
とすれば最頻値の出現回数が分かればよく、区間をずらしながら求めていける。これでG1は解けた。幅
より広い区間に対する
は求めた値の区間MINだから、
を降順に見ながら右向きの累積MINをstackで管理するテクと区間更新区間和取得の遅延セグ木でG2も求まる。
G3は大変だが、これもまあ見たことがないではない。G2の区間更新の代わりにを掛けて区間ADDを行い、また更新される区間については
を掛けて再度区間ADDを行うことにすると、その値が出現してから消えるまでの寄与の和が得られる。こうして更新した遅延セグ木の区間和はだいたい答えになっている。
ところがG2のコードを流用してG3を書いたら作用素でオーバーフローしてしまった。区間更新ならint型でよかったが、区間ADDだとlong long型にする必要がある。ジャッジが詰まりまくっており、結果が返ってくるまで10分ほど待たされるこの状況で1ペナは非常に大きい。次の提出でちゃんと合わせたものの、残念ながら2位となった。
午前4時過ぎ、ついにハーメルン「Game of Vampire」を読了した。およそ2週間弱で駆け抜けたことになる。後半の章についてはどれも嫌いな点をあげつらってしまったが、それでもぐいぐい読み進めていけたのは確か。またちょくちょく挟まれるホグワーツのシーンだったりゲラート・グリンデルバルドとのシーンだったりは常に良いものだった。前半については言うまでもない。やはり最高だった。
これを読んでいる間に「とある黒猫になった男の後悔日誌」が読みたくなってきていたので、次にそれを開いた。昨年3月に最新話まで追いついて以来読んでおらず、一年半分の更新が溜まっている。量も少ないので最初から読み返すことにした。
主人公の慇懃な口調とはっちゃけた内心に面食らったが、そういえばそういう文章だった。展開は文句なく面白い。読み進める手が止まらず、午前6時になってようやく寝た。
09/04(水)
午前9時起床。今日も遅刻。スーパーで買ってきたパンを食べて出発した。昨日とは異なり少し天気が良く、暖かい。暑くはない。
今日はpreprintの英語の修正をしていたが、全然進まなかった。昨日の時点でかなり眠気に負けていたのにうっかりさらに睡眠時間を削ってしまって、輪をかけて使い物にならなかった。昼食は午後1時ごろに農学部のほうの学食で摂った。
午後6時解散。合宿はこの二日で終わりである。数学棟近くの学食で夕食を済ませたあと院生室に顔を出したら友人が二人いて、かなり長い間雑談をした。午後10時帰宅。
眠気でぼんやりしつつTLを眺めていたら午後11時半になったので、久しぶりにCodechefに出た。今日はStarters 150。
https://www.codechef.com/START150A
書く
ハーメルンを読んで午前5時半就寝。
09/05(木)
正午起床。今日が締め切りの書類を提出するため、この日は日付が変わるまで指導教員とメールのラリーを続けていた。メールとメールの合間は、午後2時から午後5時までは寝ていて、それ以外はハーメルンを読んでいた。
日付が変わってからはハーメルンに没頭。午後0時半に寝落ちするまで読みふけっていた。
09/06(金)
午後6時半起床。
ハーメルン「とある黒猫になった男の後悔日誌」を読了した。非常に面白かった。前回自分が読んだところより先では話がどんどんどんどん大きくなっていき、海軍とも世界政府ともぶっといパイプを築き上げ、その上海軍大将を一騎打ちで撃破して懸賞金が跳ね上がった。この二つを両立させた展開というのもまた面白い。
午後9時20分からyukicoder 444に出た。
yukicoder contest 444 - yukicoder
書く
少しだけ日記を書いた後はまたずっとハーメルン。今度は「ヒエヒエの実を食べた少女の話」で、1年ちょっと溜めていた更新だけ読んでいた。午前7時くらいに読了。
この作品の主人公はかなり昔に王下七武海入りし、自身並びに配下の懸賞金が一切更新されないまま二十年ほど経過していた。ところがここ数話でついに脱退。現在の彼女たちの危険度がどう評価されるのか、かなり気になる。そのほかにも今ちょうどいくつかの大きなイベントが同時並行で起こっているようで、なんとももどかしいタイミングで読んでしまったなと思った。
また、いつの間にか番外編「ヒエヒエの実を食べた少女の話エクストラ」が生えていたため、こちらも読んでおいた。
ワンピース原作の二次創作がまだ読み足りない。ハーメルンを漁って「大文豪に私はなる！」を読み始めた。冒頭から主人公の故郷が滅ぼされたり奴隷として売られたりで大変な目に遭ってばかり。貞操の危機に陥ったときはかなり冷や冷やしたが、このときは何とかセーフだった。
午前10時前に寝落ちした。
09/07(土)
午後1時半起床。午後2時からUniversal Cupに出た。今日は9回目、Xi'anセット。
書く
今日のABCはG問題が650点となっている。コンテスト中に全完できるかかなり怪しく、録画時間は振り返りまで含めれば確実に2時間を超えるだろう。つまり午後11時からのTROCも一緒に録画することになる。
このコンテストサイトは、ページのボタンをクリックして開いたエクスプローラーから選択するという形式のファイル提出しかできない。しかし今、エクスプローラーを録画に映り込ませたくない事情がある。解決策は非常に簡単だった。エクスプローラーが開く位置は前回のものを記憶しているようだから、前もって録画しているモニターの外に追いやっておけばよいのだ。
そういう準備を整え、午後9時からABC370。
Toyota Programming Contest 2024#9（AtCoder Beginner Contest 370） - AtCoder
Aは面倒。Bはやるだけ。Cは1文字ずつ揃えていく必要がある。辞書順最小を達成するのは簡単。Dは縦と横それぞれsetで壁を持つ。Eはdp。
Fはかなり手間取った。円環をどこかで切り開き、質量が以上となる最低限の区間をどんどん切り出して一周するまでに
人分用意できるか確かめたい。二つ目の出力のことを考えると、
種類すべての位置で切り開いてそれぞれチェックしなければならないが、これにはダブリングが使える。判定問題が
で解けたので、OK。
手間取ったのは「一周」の判定だった。無理やり値域をにしたら、ピースを一つも切り出していない状態と一周丸々切り出した状態が区別できなくなってしまったのだ。気合いを入れて実装すれば回避できると思っていたのに失敗してタイムロス。結局値域を
にして解決した。
Gは惜しいところまで行ったと思ったが、有名手法が使える形にはできておらず、自分で実装したことのないライブラリを弄る必要が生じて手が出なかった。6完18位。
午後11時からはTROC #38に出た。
https://tlx.toki.id/contests/troc-38
書く
— こたつがめ (@kotatsugame_t) 2024年9月7日
ABC-Gのupsolveをした。基本方針はBlack Algorithmというやつで、頂点について最大素因数を
、その重複度を
とすると親が
となるような木を考えた。降りるときに
を見て、
が良い整数かどうかを判定。
乗法的関数のprefix sum | Nyaan’s Library
このとき、以下の「素数」の個数と「素数かつ3で割って2余るもの」の個数が必要になる。前者は普通の素数カウントで手に入るから、後者も同様の手法で計算できるだろうと思った。ここまでがコンテスト中に考えられたこと。素数カウントは自分で書いていないのみならず、以下のページにある丁寧な解説も読み解いたことがなかった。
素数カウント( $\mathrm{O}(\frac{N^{\frac{3}{4}}}{\log N})$ ) | Nyaan’s Library
今日改めて読むと、であるらしい。
は
から
を除いたものになり、
が素数かつ
ならばこれは
と一対一対応する。そのサイズは
であり、確かに解説の漸化式を満たす。
これを応用して、さらにという条件を加えたい。漸化式がどういう理屈になっているか考えると、
に応じて
という状態から遷移してくることもあると分かった。というわけで、両方管理すればよい。
で分けるのが面倒だったので
より少し大きな定数を使ったら、結構実装が楽になった。
二つのコンテストの振り返りまで終え、6時間に渡る録画が完了した。普段ならすぐアップロードするが、今日は途中で誤クリックによりTwitterのタイムラインを映してしまったので、確認の必要がある。該当箇所を探し出すと、なんとも間の悪いことに鍵アカウントのツイートが見えてしまっていた。AviUtlで編集してモザイクをかけねばならない。
何しろ動画が6時間もあるから、ソフトへの読み込みだけで長大な時間がかかってしまった。しかも動画のフレーム数上限を突破していたため、設定を更新して再度読み込む羽目になった。編集で数秒だけモザイクをかけ、今度はエンコードに2時間半。動画が公開できたのは午前8時のことだった。
その作業の待ち時間ではずっとハーメルンを読んでいた。午前9時半就寝。
09/08(日)
午後5時半くらいに目を覚ました。今日はコンテストがない……と思っていたら昼過ぎにyukicoderがあったらしい。がっくり。逃したものは仕方ないとして、夜何もないのは確かだからゲーセンに行こうと考えていた。
しかしハーメルンを読むのが止められない。しかも、寝転がったままスマホを凝視していたら午後7時半くらいにうっかり寝落ちして、気づいたら3時間が経過していた。もう外出するような時間ではなくなってしまった。仕方がないのでそのまま延々とハーメルンを読んでいた。
日付が変わり、午前10時くらいになってようやく布団を脱出。まともな食事をせず、水分もあまり摂らずにずっと横たわっていたせいか、頭はぼんやりするし体は重いしかなり辛かった。もしかしたら眠気もあったのかもしれない。何とかシャワーを浴びて洗濯しつつ日記を書き、午後1時過ぎに就寝。
