10/21(月)

午前6時起床。シャワーを浴びて洗濯を済ませ、朝からインターンで稼働した。ここ2か月くらい立ちはだかっていた問題に対し、ついに対症療法を確立。動けばよかろうという感じではあるが、これ以上だとちょっとわからないことが多すぎる。

ただその代償として、手元で試行錯誤しているとき急にUbuntuが落ちて、数値計算を走らせていたJupyter Notebookが消えてしまった。途中経過はある程度ファイルに保存してあったものの、何も考えず適当にダンプしただけなので再利用しにくい。今回は頑張って読み込むとして、次回以降で要改善。

……と考えていたのに、topコマンドで確認するとPythonだけまだ走り続けていた。謎。出力ファイルの更新も徐々に行われているので、このまま待ち続ければ所望の結果も得られるということになる。まあNotebookがないと進捗の確認ができないので、結局再起動した。ファイルの記録も利用できて、無事止めたところから再開できた。

しばらく週記を書いて、午後1時過ぎに大学生協へ。学食で食事した後、明日使う新幹線の切符を買った。ラノベも買って帰宅。

午後3時半からはインターン先定例会。進捗報告では今朝の話をした。対症療法を適用してから5時間ほど経つが、幸いにして変な挙動の報告はない。もう大丈夫だろう。

勉強会はAHC038について。自分はこのコンテスト、実装があまりに大変そうで何も実装せず挫折してしまったのだが、シミュレータのコードを流用すればよいと聞いて目から鱗だった。操作を出力できる形式でのみ取り扱い内部をブラックボックス化すれば簡単に流用でき、またマラソンではそれで十分なことも多い。

週記を書き進めて日付が変わる前に投稿した。コンテストの詳細が微妙に間に合っていない。

午前1時くらいに布団に倒れこんで寝た。

10/22(火)

午前10時半起床。昨日再起動した数値計算が終わりかけていたので、最後まで見守った。落ちる前も合わせて計34時間弱かかったらしい。前回のものと入力のサイズ的にはほとんど変わっていないのだが、ほんの少しの違いが計算量にはたぶん3乗くらいのオーダーで効いていて、ここまで違いが出たのだと思う。

PCを確認すると全体の計算に成功していた。7時間かかったようだ
週記（2024/08/26-2024/09/01） - kotatsugameの日記

さて、昨日買った新幹線の切符を使い、今日から帰省する。シャワーを浴びてゴミを出し、午後1時くらいに家を出た。

最近仙台では非常に寒い夜があったためもう冬だと認識しており、最初はパーカーの上に防寒着を羽織って行こうとした。直前で現在の気温を確認し、さすがにパーカーを取りやめたのだが、取りやめるのは逆であるべきだった。防寒着を着ている時点でめちゃくちゃ暑い。まだ全然冬ではなかった。

汗まみれになりつつ仙台駅前に到着。丸亀製麺で食事しようとしたがすごい行列だったため、諦めて新幹線の時間までゲーセンで過ごした。軍手を持ってきていないため素手で、5クレプレイ。手が滑らなくてスライドを押さえるのすらおぼつかなく、また速いタップスライドが抜けまくって辛かった。

今日は5クレ pic.twitter.com/9n2Xz3axGp
— こたつがめ (@kotatsugame_t) 2024年10月22日

駅のコンビニで弁当を買い、新幹線に乗り込んだ。今日は大宮以前・以後どちらもかなり混んでいた。隣席に人がいる中小さくなりながら弁当を手早く片付け、大宮まではハーメルンを読み、それ以降はずっと寝ていた。

父に迎えに来てもらって帰宅。午後7時過ぎに夕食を摂ったあと3時間ほど居間で爆睡していた。入浴して布団に移動。

Yandex Cup Semifinalの日程が出たらしい。情報が錯綜しているが、公式のTelegramを翻訳すると11/03の17時から19時（UTC+3）になっていた。つまり、AGC069と被っている。どうするのだろう。

しばらくハーメルンを読んで午前2時半ごろ寝落ち。

10/23(水)

午前6時過ぎに目を覚ました。耳元で虫の飛ぶ音がして二度寝できず、1時間ほど悶えたあと諦めて起きて、朝食を摂った。

今日は免許の更新をする。これが今回の帰省の目的だった。無事故無違反のまま2回目の更新なので講習は優良運転者向けとなり、たった30分で完了。最近の道路交通法の改正点としてあおり運転厳罰化はホットトピックであり、前回講習と同じ話を聞くことになったが、厳罰化のきっかけの話は何度聞いても辛い。

初回の更新ということで、2時間コースの講習を受ける。
週記（2021/10/18-2021/10/24） - kotatsugameの日記

タイミングよく選挙が行われていたので期日前投票もした。昼前に帰宅。富山県、信じられないくらい暑い。今日は30度を超える真夏日らしい。昨日パーカーやら防寒着やら寝ぼけたことを言っていたが、長袖Tシャツ1枚で全く問題なかった。

母が昼食を用意してくれている間にうっかり寝てしまい、起きたら午後3時だった。食事してまた2時間ほど睡眠。その後、少しだけ公文式の教室に顔を出した。春に話した高校生が今日もいて、自分のことを覚えておりびっくりした。

少しだけ公文式の教室に顔を出した。今日はこの時間になっても生徒が多く残っていて、まだ忙しかった先生とはあまり話ができなかった。すぐ帰るのも寂しかったのでその場にいた高校一年生と話をしたのだが、せっかく質問してもらっても高校時代の勉強の話を何一つ覚えておらず、まともな返答ができなかった。ただ邪魔しただけになってしまい申し訳なさを感じる。
週記（2024/04/22-2024/04/28） - kotatsugameの日記

帰宅して三度、睡眠。午後8時過ぎに起きて夕食を摂った。今日のメニューは自分が頼んだアジの塩焼き。そこに何品も副菜が追加されており、昼食から5時間しか経過していない身にはかなり苦しかったが、なんだかんだ食べきることができた。

自室の衣類の片付けをした。高校時代に来ていた服を残していたが、もうさすがに着ないだろうということで大胆に捨てた。一方競プロのコンテストTシャツもかなりの量が溜まってきている。こちらこそ絶対に着ないものの、とはいえ記念なので一切捨てはしなかった。数えたら、スポンサーセッションで貰ったものを含め42着あった。

午後11時ごろ入浴し、洗濯しながら日記を書いていた。昨日Yandex Cup SemifinalとAGCが被っていることが判明したが、いつの間にかAGCが11/10にずれていた。これは短期AHCと同日である。

午前1時就寝。

10/24(木)

午前6時半起床。朝食を摂ってから集中講義の課題レポートの清書をした。火曜日に課題の提出先が用意され、締め切りが11/15であると判明。まだ頭がぼんやりしているので、提出は再度見直しをしてからにしたい。

後から清書する予定。ちなみにClassroomにはまだ課題の提出先が用意されていない
週記（2024/10/14-2024/10/20） - kotatsugameの日記

布団に戻ってしばらくハーメルンを読み、正午から3時間ほど二度寝。昼食を摂ったのちさらに三度寝に入った。

午後5時半ごろ起床。AGCの日程がさらにずれて11/24となっていた。公式でアナウンスも出たため、これで確定と考えてよいだろう。

【コンテスト日程の変更について】
- 11/22（金）ABC381
- 11/23（土）ARC188
- 11/24（日）AGC069
海外コンテストの事情などを考慮し、コンテスト日程が再度変更されました。ABCが金曜になっていることにご注意ください
— AtCoder (@atcoder) 2024年10月24日

午後6時から幼馴染と飲み。夏の反省を活かし帰省の日程が固まった段階で連絡を取ったら、この日の夜なら空いているという返事があった。待ち合わせに仕事帰りすぐの格好で来てくれて、直前まで寝ていた身として少し申し訳なくなった。

仕事を終えた幼馴染が久しぶりに訪ねてきてくれた。なんと話すのは成人式の日以来らしい。なんとなく気が引けて連絡も取っていなかったが、そんなことで昔からの親友を失うのはもったいないし、向こうもまだ自分のことを友達だと思ってくれているし、これからは帰省するときにLINEで一報入れるくらいはしようと考えた。
週記（2024/08/05-2024/08/11） - kotatsugameの日記

店は中華料理屋。近況、ボドゲ・TCG、就職の話をした。自分は働くことについて何にも考えていないので、職業選択の心得を聞いてもピンとこなかったが、確か「やりがい」について話してくれたはず。転職の多いITエンジニアという特殊な職業でも、もしかしたら重要なポイントになるのかもしれない。

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

食後、近くを散歩しながらもう少し喋った。ここでは本の話をした。幼馴染は最近「三体」を読破したらしい。また、人生を変えた一冊を選ぶとしたら何かという話題も扱った。自分は森見登美彦「きつねのはなし」で、記憶している限り初めて読んだ小説だから。幼馴染ははやみねかおる「都会のトム＆ソーヤ」を挙げた。自分も小学生のころ彼から借りて読んだが、非常にワクワクしたことを覚えている。

午後9時過ぎ帰宅。またしばらく寝て、CFが始まる直前に起きた。午後11時半からCF #981 div.3。

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

Aは $n$ の偶奇が問題で、何も考えずサンプルに合わせればよい。Bは極大な対角線のみを使うべき。Cは両端を同時に見ていくdp。DはZero-Sum Rangesをちょっと弄ったdp。Eはサイクルの長さがすべて2以下になればよく、そうでないサイクルに対しては1回の操作で長さを2減らせる。

Fは $n\mid m\Leftrightarrow f(n)\mid f(m)$ という関係を思い出し、初めて $k$ で割り切れるインデックスを探してその $n$ 倍を出力してみたら通った。実験で $10k$ 以下の範囲ならこれで正しいことは確認できていたが、それ以降は知らない。

Gは頂点を $k$ 個まで遡り、部分木の最遠点を求めたい。ただし元の頂点が属する部分木は除かなければならない。これがHLDで解けるのは有名な話で、heavy edgeは「元の頂点が属する部分木」が判明しているため前計算した結果をセグ木に乗せておくことができ、light edgeだけ個別に確認すればよい。ただあんまりライブラリを窃盗できるような形ではないため、その場でフルスクラッチした。

1時間で全完して12位。

日記を書き、入浴して、午前3時就寝。

10/25(金)

午前6時ごろ目を覚ましたが、今日は仙台に帰ってそのまま夜のコンテストに出るため、朝食より二度寝を優先した。

午前11時起床。昼食後にケーキを食べた。

pic.twitter.com/GPAWfocRm7
— こたつがめ (@kotatsugame_t) 2024年10月25日

母の車で新幹線駅まで送ってもらった。車中で米津玄師の新アルバム「LOST CORNER」を聞いた。「KICK BACK」はMVの印象が先行していたが、トラックで跳ねられた箇所は音だけでも強烈。しかしこの音、例えば以下の動画では使われていないから、改めて聞くと新鮮な感じがした。

www.nicovideo.jp

新幹線は今日もほぼ満員。大宮まではpreprintの加筆、大宮からはハーメルンを読んでいた。午後5時前に仙台に到着した。

帰る前にゲーセンで7クレプレイ。今日はなんだか鍵盤が上手く、14+を伸ばすことができたが、それでもやはり素手でプレイしたことによる失点がいくらかあった。残念。

今日は7クレ　素手なのが辛いところ pic.twitter.com/2s1OzfFxqq
— こたつがめ (@kotatsugame_t) 2024年10月25日

ラーメンを食べて帰宅。シャワーを浴びて午後9時20分からyukicoder 451に出た。TROCと被っているので45分だけの参加となる。

yukicoder contest 451 (並木中等プログラミングコンテスト 2024) - yukicoder

A、Bはよい。Cは問題文がよく読めなかったのでサンプルからエスパーした。解が存在しない場合どうするのか迷ったが、問題文を振り返ってみると存在が保証されていて仰天。Dは適当にbitDP。EはLCAごとに足し上げる木dp。Fは $l$ を降順に見ながら累積MAX・累積MINをstackと区間代入区間和取得の遅延セグ木で管理し、積の和を差分更新していった。

Gは値 $v$ を降順に見て、列に含まれない $v$ 以上で最小の整数と列のうち $v$ 以上の要素が何個あるかを状態に持つdpをすれば解けると思った。しかし書いてみると状態が3乗なのに遷移に $O(N)$ かかり間に合わない。時間もないので適当に畳み込みにして $O(N\max(M,K)^2\log N)$ を投げたらギリギリ通った。

ここで午後10時5分となり時間切れ、かと思ったらTROCが15分こどふぉったので、ロスタイムでHに取り組んだ。シンプルな $O(NM)$ 解が得られたので通らないかと投げてみたものの、当然TLE。それ以上は特に何もできず、午後10時20分からTROC #39に移った。

https://tlx.toki.id/contests/troc-39

書く

11月の新刊チェックを行い、28冊注文した。1巻から長く空いて続刊を絶望視していた「非科学的な犯罪事件を解決するために必要なものは何ですか？」と「FPSゲームのコーチを引き受けたら依頼主が人気VTuberの美少女だった」の2巻が出るらしく、嬉しい。

www.kadokawa.co.jp

www.shufu.co.jp

午前5時就寝。

10/26(土)

午前10時半起床。ハーメルンを読んでいたら午後2時、Universal Cupの時間になってしまった。今日は14回目のHarbinセット。

https://qoj.ac/contest/1817

書く

食事して午後9時からABC377。

TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377) - AtCoder

Aはソートして判定。Bは愚直。Cは置けないマスをsetで管理。Dは $l$ を降順に見て $r$ の条件を徐々に追加していく。Eはサイクルグラフで $2^K$ 個先に進めばよい。

Fはひたすら面倒。置かれているコマが取れるすべての直線を列挙したのち、直線二つの組について高々一つの交点をすべて求めた。この重複度を見ることでそのマスが何本の直線に乗っているか区別できる。

GはTrie木を使うと終わり。木曜日のCF-Gとは異なり求めるのが最も近い点であるため、自分自身を含む部分木を無視する必要がない。

35分で全完して6位。AとBをNibblesで縮めておいた。Bは行とtransposeした行つまり列のペアを全列挙し、連結して"#"から引くと、集合の引き算により数えたいペアのみ空でない列が得られて、うまく真偽を分けられる。

www.youtube.com

素早く全完したので、振り返りして動画投稿するまでを次のCFが始まる前に完了できた。午後11時半からCF #982 div.2。

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

書く

www.youtube.com

あまりにお腹が空いたので、コンビニに走って菓子パンを大量に買ってきた。いくつか食べてTLを眺めていたところ、急激な眠気に襲われて布団に倒れこむ。午前6時就寝。

10/27(日)

午後1時半から2時間ほどは起きてハーメルンを読んでいた。二度寝して午後8時起床。シャワーと食事を済ませて午後9時からARC186に参加した。

AtCoder Regular Contest 186 - AtCoder

まず全問読んで、とっつきやすそうなBから取り組んだ。区間 $[A_i,i]$ が中途半端に交差することはないため、 $i$ の親を $A_i$ として木を作ると部分木ごとに独立に考えられる。その大小関係も根と直接の子によってのみ決定できるので数え上げは簡単。順調に通った。しかし順位表を見るとみんなもっと速くB問題を通しており、83位で絶望。

以降はsolved数順。2問目としてAに取り組んだ。例えば $[1,0;0,1]$ と $[0,1;1,0]$ は似ている。実は本質的にこれしかないんじゃないかと考えた。もう少し一般化すると、 $h,w\ge 2$ に対して $h\times w$ の長方形領域以外をすべて固定することができる。

さすがにそれだと自明すぎるので $N=5$ で全探索してみたところ、固定されている成分を12個にできることが発覚した。つまり長方形領域で13個の成分を覆わなければならず、一つの領域では不可能。実際に構成例を出力してみて、複数の長方形領域を対角線上に並べてもvalidであることに気づいた。これでAC。計算量はbitset dpによる $O(N^6/\mathrm{wordsize})$ だった。この時点では50位。

C問題に進んだ。箱が十分あれば、最終的な状態は $M-1$ 個の箱にボールが1個だけ入り、それ以外の箱は満タンか、そもそも買っていないか、という状態になるはず。満タンにした時は利益 $V-P$ 、ボールが1個だけだと利益 $1-P$ のため、球橋さんはこの差分 $V-1$ が大きいものを優先的に残したい。そして、これまで買われた箱のうちどの $M-1$ 個を残すかは常に球橋さんが決めることができる。

よって箱を $V$ の降順に並べ、ある仕切りを境に $V$ が大きいほうでは $1-P$ が大きいもの $M-1$ 個、 $V$ が小さいほうでは $\max(V-P,0)$ の総和を求めると、これが箱木さんの利益の候補となる。あとは仕切りを全探索すればよい。

ここまでたどり着くのに2ペナ支払っていたが、さらに実装ミスで仕切りが左端にあるケースを考慮できておらず、 $M=1$ のケースで落ち続けてしまった。この修正にさらに2ペナ＋15分かかり、ACした時点で53位。もう一問解かなければ決勝に進出できないのに、時間が16分しか残っていない。

とにかくD問題に取り組んだ。Polish数列の判定は後ろから $1-V$ の累積和を取れば簡単に行えること、これを用いてprefixが $A$ と一致しsuffixをdpで数える方針が立つこと、さらにdpの遷移がランダムウォークになっており値をcombinationで書けそうなことまでは考察が進んだが、詰める時間がまったくもって足りなかった。

3完72位。惨敗。

コンテスト後からCGRまでの30分とCGR後の1時間半を使ってD問題をupsolveした。ようやくTLEを解消したと思ったら今度は大きめのケースでWAが出るなど、かなり苦労した。最後に残ったミスは $1-A$ の和がオーバーフローしていたこと。この辺りをもうちょっと真剣に考えていたら、dpの区間和をWolfram|Alphaで閉じた式にしなくても、解説で言われているようにそもそも $O(N)$ 点しか見ないことに気づけたのだろうか。

午後11時半からはCGR27に出た。

Dashboard - Codeforces Global Round 27 - Codeforces

書く

www.youtube.com

今日も動画を撮っていたが、コンテスト本体の2時間＋3時間に加えARC-Dのupsolveに2時間、ARCの振り返りに1時間、CGRの振り返りに2時間かけており、録画を終えると午前7時になっていた。

動画をアップロード・公開したあと日記を書き、午前11時くらいに布団に入った。しばらくハーメルンを読んで午後0時半就寝。