05/27(月)
午後3時起床。今日から集中講義である。登校し、購買で買った総菜パンを食べて教室に向かった。
数学科の集中講義は、初日だけ談話会という独立した内容になっていて、講義に関連する話題について1時間程度の発表を聞くことになっている。擬似ランダムネスや脱乱択化など去年のCOSSで見聞きしたものに再会し懐かしい気持ちになった。ただそういう応用が重点的に紹介された一方で、明日から何を学ぶのかについてはピンとこなかった。談話会の性質上仕方のないことだとは思う。
1時間で終了。講義に来ていたホスフィンと学食に行って、夕食を摂りつつしばらく話した。食べ始める前から満腹で、完食まで非常に苦労したが、よく考えるとパンを食べてから2時間も経過していなかった。午後6時半くらいに解散して帰宅。
先週のAHC033が終了した。結局先々週の1回しか提出しなかった。全部のクレーンを使って限界までコンテナを搬入した後、大クレーンだけ使って一つずつ搬出していく解法。操作回数は大体250回から300回となっていた。最初は搬入から大クレーンだけで行おうとしていたが、複数のクレーンを同時に使うと思った以上に操作回数が減ることに気づいたため、並び順が悪くてもとりあえず搬入してしまうことに。ただそれ以上を実装するにはやる気が足りなかった。
TLの感想戦で、途中ほぼ満点を取っていた人の失点をうまく分数で表現することにより、最適な操作回数が70回弱であるということを見積もった話が流れてきた。相対スコアの順位表でもそうやって情報が取り出せるのだなあと感動。
Toyota Programming Contest 2024#5（AtCoder Heuristic Contest 033） - AtCoder
日付が変わる前に週記を投稿。その後30分ほどしたら眠気に耐えられなくなり、布団に倒れこんで寝た。
05/28(火)
午前5時起床。
ラノベ「煽り煽られしてたネトゲ仲間が品行方正な美人先輩だった話」を読了。思ったより「煽り煽られ」していて、ノリについていけなかった。なじみのないネトゲ用語が飛び交うのも苦しかったが、これはこちらの問題だろう。最近のラノベにおいてはバトルロイヤルゲームは前提知識。
先週の週記をいくらか書き足し、シャワーを浴びて午前9時頃布団に戻った。そこからまたラノベを開き、うっかり読み切ってしまった。
「異能学園の最強は平穏に潜む」2巻。面白かった。1巻と同じく、主人公がまず敵に負けて警戒を外し、その後裏から手を回して勝利するという流れ。負けるのが策の一部であるということを何度も念押しされており、読んでいてストレスを感じなかったのが非常に良い点。暗躍することとバトルで存在感を示すことが高いレベルで両立されていた。
1巻を読んでから1年以上間を開けてしまったため、設定や人間関係をすっかり忘れてしまったのが痛い。能力のランク付け4段階のうち、上から3番目が「王」系統、2番目が「加護」系統らしい。自分が単語に対して抱く印象としては逆だったので、途中までそのつもりで読み進めており、しっくりこなかった。
いくらか仮眠しようと思ったものの、結局眠れずにYouTubeを眺めていた。午後1時頃に登校。今日は雨が降っているので地下鉄を使う。山に登る前に川内の購買で食事し、ラノベを受け取っておいた。午後2時半ごろ教室に到着し、しばらくハーメルンを読んで開始を待っていた。
午後3時から集中講義一日目。昨日の談話会はスライド発表だったが、今日からは板書らしい。書く手間があってゆったりとしたスピードの講義となり、内容がまだ講義資料を読めばわかる範疇だったので、少し退屈さを感じていた。ただ、途中途中で別の先生と議論しているのに耳を澄ませると、証明手法や式の解釈についてさらなる知見を得ることができて非常に有益だった。こういうのは講義資料にないし、板書もされない。
午後6時終了。ホスフィンが用事があるとのことで、一人で学食に行った。今日も満腹だったので主菜と副菜だけ時間をかけて食べた。午後7時半くらいに帰宅するとすぐ着替えて布団に入り、それから眠くなるまでずっとハーメルンを読んでいた。
最近読んでいるのは「最強の魔法使い(自称)が暴れるそうです。RE：」。能力てんこ盛りのチートオリ主だが、文章はなかなか抑制が効いていてそこまではっちゃけておらず、寒いノリもないため読みやすい。しかしこれはリメイク後だからだったようで、まだリメイクされていない第四章に突入すると……お察し。設定は好みなので頑張って読み進めていきたいとは思うものの、耐えられるだろうか。
午後11時過ぎに寝落ち。布団に入ってからなぜか腰と足に痒みが生じ、掻けば掻くほど悪化してなかなか辛かった。
05/29(水)
午前10時起床。ハーメルンを読み、シャワーを浴び、少しだけ日記を書き進めて午後2時半に出発した。今日は晴れたので原付。ここ二日の反省から、夕食時に満腹とならないよう昼は菓子パンで済ませた。
午後3時から集中講義二日目。前半までは昨日と同じく楽。しかし後半で講義資料の2章に入ってからは、資料の順番から外れ、また説明でも感覚的な話が加わってきたため、ちゃんと聞いていると面白くて退屈さはなくなった。そういう資料にない話の中で演習問題の解法について触れていたが、問題の状況にそぐわず、質問したところ仮定が足りないということになった。こういうところは集中講義後のレポートで苦しむより、対面で質問できるうちに潰しておきたい。
今日は午後7時までかかった。ホスフィンと食事して午後8時過ぎ帰宅。PCの前に座ってみたがうっかりスマホでハーメルンを開いてしまい、また寒さからそのスマホを握りしめたまま布団に引っ込んだところ、すぐ寝落ちした。午後9時。
05/30(木)
午前6時起床。ハーメルンやYouTubeを見ていたら二度寝できる雰囲気ではなくなったため布団を出た。少し日記を書き、指導教員の先生に出された課題を解いたら午前11時になったので、シャワーを浴びて登校。今日は集中講義の前にセミナーがある。夕方から降水確率40%だが原付で向かった。
学食で食事し、正午からセミナー開始。後輩の発表。これまでずっと離散的なものを扱っていたからさえ扱えればよかったのだが、今日は連続なものに一般化する話だったので積分が登場して大変だった。慣れていないし学部時代の知識も抜けてしまい、何ができて何ができないのか曖昧である。
午後3時になって教室を移動し、集中講義三日目。資料の1章を二日目前半までかけて全部きっちり話していたから、2章の昨日触れなかった分も今日やると思っていたが、すぐ3章に入ってしまった。順番を変えたのではなく、単に飛ばしていたらしい。さて、3章はいよいよ講義のメインテーマに近づく章であった。登場する式は添え字が大盤振る舞いされていて手ごわいものの、今日もイメージの説明がふんだんに含まれていて、気持ちの上では十全に理解できたものと思う。
今日も午後7時まで延長し、3章の内容が終了。この章はどこも飛ばされなかった。ホスフィンと食事して午後7時半ごろ帰宅し、荷物を整理してまたすぐ出かけた。ゲーセンに行く。一昨日から痒みに悩まされているため、途中のドラッグストアで痒み止めのクリームを購入した。
ゲーセンには午後11時くらいまでいて、15クレ遊んだ。先週始まったMuse Dashコラボの新曲埋め。「それはもうらぶちゅ」は周央サンゴさん歌唱ということで、こういう形でVTuber曲が入ることには驚いた。ポプアニではなくVARIETYジャンルだが、バージョンアップで削除されないと思ってよいだろうか。曲はかなり好みだったので理論値を狙った。
良すぎる pic.twitter.com/f5MbCVmS1k
— こたつがめ (@kotatsugame_t) 2024年5月30日
ドンキで買い物して帰宅。急いでシャワーを浴び、午後11時半からECR166に出た。
Dashboard - Educational Codeforces Round 166 (Rated for Div. 2) - Codeforces
Aはパスワードがソートされているか判定すればよい。Bはコピーする要素を固定すると、どれだけインクリメント・デクリメントしてからコピーすればよいかは算数でわかる。Cはどちらかのポジションが埋まる位置を二分探索で求める。取り除いた人の寄与は適切にキャンセルする。
Dはかっこ列の累積和グラフにおいて上下反転するような操作になっている。よって高さが同じかつその間に高すぎる山がないのが条件。高さを固定し、含んではいけない山で区切って数えた。Eはまたは
として出現する要素の順序が決まるので、その間に未確定の要素を詰めることで数え上げられる。左または右の値以下なら詰められるので、大きな値から順に入れられる隙間を数えていくとよい。
Fはよくわからないが、直感的に良さそうなものが通った。まず根付き木を貪欲に葉からのパスへと分解していく。これは子から伸びてきたパスのうち最も長いもの以外を切ることで行える。その後、パスの長いものから本に対応する葉と根を適切に繋ぐことで、パス上の辺が橋でなくなり、また条件を満たすようになる。これが最適らしい。
全完2位。
いつの間にか布団に吸い込まれており、午前3時半ごろ寝落ち。
05/31(金)
午前10時起床。2時間ほど布団でYouTubeを見てから起き上がった。一本メール返信をして、今日は地下鉄で登校。学食で食事して教室に向かった。
ここ二日の講義時間延長を鑑みて、集中講義最終日の今日は1時間早い午後2時開始。資料の4章が全部解説された。これまでの講義で培った知識やイメージを総動員して、ついに講義の最終目標だった定理の理解までたどり着けて感動。初日は板書が遅くて退屈とか言っていたが、終盤は逆にそうでないと途中で置いて行かれたと思う。最近セミナーで復習した線形代数も非常に役立った。最後の余談では自分が今まさにセミナーで扱っていることに触れられて、大変興奮した。
実はこれまでの講義で結構質問を飛ばしていて、たいていは些細なミスの指摘だったのだが、今日は証明における本質的なミスを発見した。期待値の記法によってパッケージ化し、確率変数の意味を考えることで等式を示すのは、イメージとして把握しやすいもののミスが怖い。総和記号での厳密な計算もできると安心。
今日もしっかり4時間かかり、午後6時終了。ホスフィンと食事して帰宅した。ちんたら歩いていたら午後7時からCFがあることを思い出し、早歩きでギリギリ帰宅に成功。CF #949 div.2に出た。
Dashboard - Codeforces Round 949 (Div. 2) - Codeforces
Aは数の大きさに対するスコアとして2べきが最適で、制約の範囲内に必ず存在する。Bはのbitwise ORで、bitごとに考える。Cは2進数表示したときの桁数が
で遷移していく形になっている。上限があるので、途中の値はできるだけ小さくしておく。
Dはまずとして素数を選ぶのが良い。すると積の一致が2数の選び方の一致になる。そこで使う素数を頂点、2数の選び方を無向辺だと思うと、数列は長さ
のパスになる。正確には頂点の共有のみを許すウォークか。また自己ループも可。そして、使う素数の種類数つまり頂点数をできるだけ少なくしたいので、完全グラフの辺をできるだけ使いたい。
頂点使うとすれば、
が奇数ならそのまま、偶数なら
本取り除くことで一筆書きが可能になる。よって
に対し可能な
が求まるので、あとは気合いでパスを構築。
Eはの値を横軸に、区間を縦軸にして考えると、ある区間から左右を向いて「見えている」区間、つまり
かつ
なる
が存在しないような辺
だけ考えればクラスカル法が行える。
のタイブレークは適当にやってよい。区間setを使って実装した。
Fはが間に合うと信じたが16secかかって全然ダメ。自分の書いたコードにおいてMEXを計算する集合からの削除操作がundoのみであることを利用し、双方向連結リストでMEX関連の操作を全部定数時間にできたのは楽しかった。
5完7位。振り返りをしている間にyukicoderが始まりそうになったので、録画を続けたまま参加した。yukicoder 431。
yukicoder contest 431 - yukicoder
Aは丁寧に式を写す。Bはからdfsで全探索。メモ化しなくても通ったのはよくわからない。Cはかなり時間がかかってしまった。
とおくと
となるので、
と
をそれぞれ
以下で全探索すればよい。Dは1文字につき25回聞けるから、全部違ったら最後の1文字にすればよい。ただしその部分でバグらせてしまった。
Eはひし形の条件を対角線が中点で直角に交わることとし、その対角線を全列挙して数えた。Fはのうち安いもの
個を購入し、その際高いたこ焼き器に割引率の高いクーポンを使いたい。つまり
と
をソートし、適当にずらしながら積和が計算できればよいが、これは片方を反転して畳み込む典型問題。
Gは、次に使われる椅子の候補として、人が座っていない椅子の区間に対しその真ん中の椅子だけ考えればよい。これらを気合いで管理する。HはbitDP。
全完、CとDで手間取ったのが響いて7位。CFの振り返りを終わらせ、追加でyukicoderの振り返りも撮った。
午前3時過ぎ就寝。
06/01(土)
午前8時に目が覚めてしまい、ニコニコ動画を見ていた。「The Game of Sisyphus」という苦行系ゲームの淫夢実況。適切な倍速・カットがないと見ていられない苦しさだった。調べたら最近VTuberの配信でもちょくちょく扱われていたらしいが、こういうゲームの配信が人気とはいったいどうなっているんだ……。
二度寝するのを諦めたつもりだったが、布団に横たわったままでいたら正午くらいに寝落ちしてしまったらしい。起きたら午後1時45分だった。慌てて飛び起き午後2時からUniversal Cup。シーズン3の第0回目、トライアルコンテスト・Americaセットに出た。
書く
急いでシャワーを浴びて、午後9時からABC356。
AtCoder Beginner Contest 356 - AtCoder
Cまではよい。Dはbitごとに数えればよく、あとは算数。10進数での似たような計算は最近のSRM855Medで苦しんだ記憶がある。Eは同じ値をまとめて処理することにして商を固定すると調和級数。Fは値の大小関係で隣り合う、差がより大きいペアを列挙した。
Eまで10分弱、Fもそこから9分で解いてなかなか調子が良かったのに、Gが解けなかった。575点だからといって舐めていたつもりはないのだが……。苦しんでいる最中に順位表を見るとみんな解けていなかったのでちょっと安心した。
1m泳ぐときの体力消費率の昇順に並べたとき、
が累積MAXを更新する泳ぎ方以外は不要。それらを取り除いた中から
の昇順（これは同時に
の昇順にもなっている）に三つ泳ぎ方を取り、二つ目の泳ぎ方を一つ目と三つ目の泳ぎ方で再現したとき、必要な秒数がどうなるかを考えた。
計算を進めると常に二つ目の泳ぎ方のほうが良いという結論に至ったため、最適解は並べた泳ぎ方から隣り合う二種類を組み合わせるものに絞られる。特にが
をギリギリ超える泳ぎ方と超えない泳ぎ方を選ぶべき。このようにして解いたところ12ケース落ちで、適当に探索範囲を増やして少しACするテストケースを増やしたところでコンテストが終了した。
解説を読んで自分がどこでミスしたかに気付いた。ある泳ぎ方を別の泳ぎ方で再現する部分で、自分はベクトルを考えていたが、ベクトル
で考えなければならなかった。言葉で言えば、1mあたりの体力消費「率」を揃えるはずだったのに、実際に1m泳いだときの「量」を揃えてしまった……とでも言えるだろうか？
ベクトルをピッタリ再現できるとは限らないものの、「率」つまり傾きを一致させることはできて、そのときより大きな
が得られるなら元の泳ぎ方を無視してもよい。この操作が凸包を取ることに対応する。前提の部分で躓いているように見えるのに後の議論は正しかったらしく、凸包に含まれる泳ぎ方だけ残して投げなおしたら通った。
Fまでの6完最速で17位。AとBをNibblesで実装しておいた。Aはピンとくる書き方がない。Bはfoldrで先頭要素から残りを引こうとしたが、全然短くならなかった。まずリストを反転する必要がある。さらに引き算のオペランドの順序も重要だから、special foldsが使えない。
午前2時頃布団に倒れこんで就寝。
06/02(日)
午前7時頃目を覚まし、寝たり起きたりしつつハーメルンを読み進めていた。
正午くらいに「私が白亜の神鳥と呼ばれるまで」を読了。勝手に祀り上げ救いを求める人間の様子に少しイライラしてしまったが、神鳥は罰することなく、もちろん応えることもなく無関心を決め込む。上位存在としては完全に正しい反応なのだろう。自分はそこまで高い視座を持つことができなかった。
布団を出て、TCBの2024/05回に参加した。来週火曜日までなので、感想は来週の週記に回す。
https://techful-programming.com/techful/event/5706
論文を読んでいたら午後8時を回っていたため慌ててシャワーを浴び、午後9時からARC179に参加した。
AtCoder Regular Contest 179 - AtCoder
Aはをソートすればよさそうだが、そんな簡単なわけがない。制約を確認したら負の数があったので、
が問題。この場合は累積和のすべての点で
以上になっていてほしいから、逆に降順ソートが最適ということになる。
なら不可能。
BはbitDP。一瞬、各に対しどの数が出現したか全部持とうとしたが、冷静になると
だけ見ればよい。状態数
で遷移が
通りなので、遷移先の計算は定数時間で行いたい。これには
なる
を集めたbitを計算しておくとよい。
Cは最大値と最小値なら必ず足せるらしい。もっと一般化して小さいほうから個目と大きいほうから
個目が足せると思い込んだが、それは正しくない。これに気づかず、また実装ミスも相まってペナを二つ出してしまった。冷静になると、最大値と最小値を足すたびに挿入位置を二分探索することで、常にソート済みの列が手に入る。最初のソートも合わせて比較回数は
と見積もることができ、足りる。
Dは解けなかった。ゲートの移動まで一緒に考えるのが辛かったので、まずゲートが設置されたことのある頂点集合を決めて考えてみた。するとそれは部分木をなすこと、操作の始点と終点として葉を含むことが分かった。よって決め打った頂点集合の外側を木dpで、内側をゲート移動を使用しない通常の木上の巡回で考えれば良さそう。
ここで後者は有名問題であり、最遠点対を始点と終点にすることで経路長を最小化できる。ここから頂点集合が直径を含むだろう、つまり木dpの根として木の中心を選んでよいだろうと考え、実装。しかし3ケース落ちてしまった。残り時間は14分しかなかったので、修正を諦めて根をランダムに試していた。1ケース落ちまで減らしたものの時間切れ。
結局、直径を含むというのが嘘だった。よって全方位木dpで根をすべて試さなければならない。自分は頂点集合の外側について考える際、何度もゲートに戻ってくると考えて面倒なことをしていたが、実は2回以上戻ってくるならゲートをもう少し遠くまで持っていったほうが良いらしい。この考察ができていると、全方位木dpに拡張できるような実装が手に入る。
3完140位。
5月の読書記録をツイートした。良いペースで読み進めていたが、下旬はハーメルンに負けてしまい、結局一日一冊ペースには届かなかった。また積読の増分も残念ながら正。ちなみに今、購買に受け取っていないラノベ新刊が10冊溜まっている。6月も積読は増える一方になりそうだ。
5月の集計
— こたつがめ (@kotatsugame_t) 2024年6月2日
買った：29冊
読んだ：27冊
積読：+2冊
積読（累積）：+107冊
しばらく日記を書いて午前4時前に寝た。
