06/05(月)

午後2時に目を覚ました。布団でずっとハーメルンを読んでいたら午後4時になっていたので、昼食を摂って半からインターン先定例会に参加した。

先週は火曜日に一気に作業した他、水曜日の1on1でも重要な修正を行ったりしたため満足感がある。勉強会はアブダクションの話。 $P\Rightarrow Q$ と $Q$ から $P$ を導く、と聞くと論理学を学んだ身としては拒否反応が出てしまうが、確かにミステリー小説でさんざん見た考え方であった。

説明の流れでヴァン・ダインの二十則から「長編小説には死体が絶対に必要である。殺人より軽い犯罪では読者の興味を持続できない」が紹介された。現代では「日常の謎」ジャンルがあるから成り立たない……と思ったがよくよく考えると別に逃れられてはいない気がする。日常の謎で長編小説となるとどれも人の悪意を描いているからだ。それともこれは、自分の読む作品が偏っているだけだろうか？

解散して夕食を摂った後、テレビ番組「笑わない数学」の「カオス理論」回を見た。テレビの大画面で見るマンデルブロ集合は曼荼羅みたいで非常にきれいだった。

週記を書いて日付が変わる少し前に投稿。今週はUniversal Cup以外の部分が書き上がっている。ところで肝心のUniversal Cupはもうこれで3か月分くらい穴あきができてしまった。一応誰が何を解いたかくらいのメモは残しているが、実際の文章になるのはいつのことだろうか。

AtCoderのFastestの話が少し出ていたので言語アップデートコンテストをチェックしてみたところ、Pascalなどの高速な言語で前回アップデート以前のように0msが出るようになっていることに気づいた。

夜中はラノベを読んでいた。「さぁ、悪役令嬢のお仕事を始めましょう」を読了。最近なろうで悪役令嬢モノ読んでたし買うか〜くらいのノリで手にした正直あまり期待していない作品だったが、あにはからんやかなり面白かった。どう考えても楽しい気分にはならないテーマなのに、主人公陣営がかなり人情味のある人ばかりで、漂う悲壮感も無理なく乗り越えていける。

明日仙台に戻る。先ほど読み終えた本は実家に置いていくから感想を今のうちに書いておきたい。それを行って、午前5時就寝。

06/06(火)

正午ちょっと前に起床。急いで昼食を摂り、黒部宇奈月温泉駅まで送ってもらった。

仙台までの自由席特急券を買ったが、大宮に着いてみると接続が悪かったので、差額を払って指定席を取りそこからははやぶさに乗った。車内ではずっとラノベを読んでいた。帰省時に4冊持ってきたうちの最後の1冊である。

午後5時前に仙台に到着。アンパンマン像を撮りに行ったらいつの間にかヨドバシカメラが増殖していてびっくり。フラフラ吸い込まれてしばらく店内をウロウロしていた。ボドゲコーナーが充実していて楽しかった。

デッカ pic.twitter.com/X2mr8BWjXB
— こたつがめ (@kotatsugame_t) 2023年6月6日

目的のアンパンマン像もちゃんと撮った。

仙台駅を庇い石にされてしまったアンパンマン pic.twitter.com/E5QlNTsLJy
— こたつがめ (@kotatsugame_t) 2023年6月6日

少しゲーセンで遊んだ後丸亀製麺で食事して帰宅。微妙な眠気を抱えつつTLを眺めたり動画を見たりしていたら、CFまでに仮眠を取れるほどの時間が無くなってしまった。

セミナー準備をして時間を過ごし、午後11時半からCF #878 div.3。

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

Aは問題が読めなかったがサンプルからエスパー。先頭の文字を答えに足してもう一度同じ文字が登場するまで削除、ということを繰り返せばよい。Bは $\min(2^k,n+1)$ 。Cはやるだけ。

Dは答えで二分探索。3人でなくとも一般の人数で解ける。 $x$ が整数とは最初書いていなかったようだが、気づかず勝手に整数だと思い込んで解いた。 $x$ に半整数を使えると答えも半整数になるケースがある。

Eは $s_1$ と $s_2$ が食い違っておりかつblockされていない位置を管理し差分更新する。 $t$ 秒の扱いが分からなくてサンプルの説明を見たが、ご丁寧に用意されていた赤文字が最初間違っていて余計混乱した。ちゃんと入力を読むとサンプル1が優しいことがわかるので、それさえ合わせればよい。

Fはレールガンが打たれるタイミングでどの点にいられるか計算していく。ゴールに辿り着いたタイミングでその位置に打たれるレールガンやゴールした後に打たれるレールガンに翻弄されたがこれもサンプルが優しく、合わせて出したら通った。

Gはかなり苦労した。まずG1。返ってきた番号を記録しておくと、同じものが出現した場合にその間の矢印の移動距離として $n$ の倍数が現れる。つまり $\pm k$ の列であって「連続部分列の和として $1\dots 10^6$ が出現する」ものが作れれば必ず特定できる。

1から順に聞けばよいと思い込んで結構な時間をかけて実験したところ、全然足りないということが分かって絶望。あれこれ考えた結果、 $n$ を1000で割った商と余りに分割する方法を思いついた。まず1を999回聞き、さらに1000を1000回聞く。こうすると前者が余りを、後者が商を担当し必ず和が $n$ になる区間が現れる。

G2はこの方法では不可能。なぜなら1000回のクエリでは区間が $1000\times 1001/2\lt 10^6$ 種類しか存在しないからである。ここで、返ってきた番号を一致判定でしか使っていないことに気づいた。この値を適当にサンプリングすると $n$ 以下の乱数が得られるから、最大値は $n$ にそこそこ近い値になりそう。

サンプリングに $k$ 回使うとする。残り $1000-k$ 回でG1の方法を用い最大値を確定させるためには、サンプリング時点で $n-(1000-k)^2/4$ 以上の値が返ってくる必要がある。計算してみると $k=300$ をちょっと超えたくらいで失敗する確率が $10^{-17}$ を下回るようだった。

実際に提出するとクエリ回数が多すぎると言われた。問題文では答えを出力するクエリはカウントされないと書いてあるものの、実際にはカウントしているようだ。適当に1回減らして出しなおしたら通った。サンプルで落ちたからペナにならなくて良かった、いやそもそもジャッジが間違っているのは良くない。

全完5位。動画を投稿した。

www.youtube.com

午前7時に寝るまでずっとセミナー準備をしていた。今はDiestel 6.6章の内容で、ずらずら並んでいたconjectureに関する話題を一通り整理し終えたところである。

06/07(水)

午後5時半起床、大学に向かい購買で買い物した後夕食。帰宅後はセミナー準備の続きとして考え事をしていたが、急激な眠気に襲われて布団に倒れこんだ。

午後7時過ぎに寝落ちして、起きたのは午後11時。コンテストを寝過ごさないよう事前に目覚ましをかけておいた時間である。準備して半からRated for AllになったCodechef Starters 93に出た。

https://www.codechef.com/START93A

PALIXORは回文数を全列挙して試しても間に合う。少なそうという直感を得て、どのくらいあるか確かめてから書き始めたのだが、下半分を決めたら上半分が決まるので少ないのは当たり前だった。

K_POWGAMEは $K$ が奇数なら $N$ の偶奇で判定できるな、というところまで考察した後どうにもならなくなったので実験した。 $K$ が偶数の場合Grundy数が周期 $K+1$ を持つらしい。

MAIL_DELIVERは多始点BFSみたいにすればよい。移動できる距離が多く残っている頂点から遷移したいのでdijkstraを書いた……が、うっかり普通のdijkstraのように残りの距離が小さい頂点から遷移してしまったため1TLE。

LASTRBSはランレングス圧縮してdpして復元。MLTDVDは $G_i=\gcd(A^i)$ 、 $L_i=\mathrm{lcm}(A^i)$ と置いて計算すると $G_i=L_{i-1}$ と $L_i=L_0\times L_{i-1}/G_0$ が得られた。最初の $L_0$ 、 $G_0$ はosa_k法で素因数分解して求めればよい。

FLRCNTは商が一定の範囲を一気に処理する。各 $j$ に対して $i$ の区間を求めると、そこにimos法で特定の二項係数を足せば良いから楽である。しかしよく考えるとこの計算量は $O\left(\sum_{n=1}^N\sqrt n\right)=O(N^{3/2})$ であり当然TLE。 $i$ に対して $j$ を求めることにすると $O(N\log N)$ になるが二項係数の和が必要になる。Wolfram|Alphaに投げて閉じた式を求め、実装した。

SORTP9は結構面白かった。swapできるペアの間に辺を張り、できた連結成分ごとにソートすればよい。当然辺を全部張るわけにはいかないのでどうにかしてまとめたい。例えば超頂点を作る方法が考えられるが、それでUFを使うと余計な超頂点を迂回して思わぬところに繋がってしまうようだ。つまり「向き付きの辺を使った連結成分」が欲しいわけで、SCCを考えてみることにした。

$0\dots 2^{20}-1$ の超頂点を用意し、各頂点から立っているbitを一つ増やした頂点たちに向けて有向辺を張っておく。また要素 $A_i$ から値 $A_i$ へ、値 $2^{20}-1-A_i$ から要素 $A_i$ への辺も張っておく。

ある要素 $u$ から有向辺を辿って要素 $v$ にたどり着けるなら、 $v$ の直前の超頂点は $2^{20}-1-v$ であり、これは超頂点間の辺の張られ方から集合として $u$ を完全に含むため、 $u$ と $v$ に共通して立っているbitが存在しない。同時に $v$ から $u$ へも全く同様の理由でたどり着けるので、 $u$ と $v$ は同じ強連結成分に含まれる。この強連結成分が求めたかったものである。

全完4位でレートは2829→2852(+23)。最終問題以外はかなりやるだけという感じだった。解ける問題が多いと楽しいが、全員Ratedのコンテストなのは困る。

その後はずっとセミナー準備をしていた。定理6.6.1の説明を作って6.6章、引いては6章は終わり。ついでに関連するexerciseをいくつか解こうとして、そこでどん詰まりしてしまった。数か所分からないところを残したまま、眠い頭でこれ以上考えてもしょうがないなと思って寝た。午後2時だった。

合間にハーメルンを1作読了。「クラス転移したし最弱スキルだったけど元が魔王。」。もともといた世界に再度転移する、しかも当時の力がそのまま、というのは2年前に読んだなろう「影の勇者の再冒険」とも共通する設定で好みである。まだ5話しかないが先が楽しみ。

syosetu.org

06/08(木)

午後6時前に起床し1on1に臨んだ。

今日は自分がインターンを始めたころに1on1をしてくださった、日記ではずっとメンターと書いていた方と、自分が次に取り組むタスクについての話をした。自分が一番最初に携わった機械学習系の開発は結局形にならないまま終わっていたのだが、そこから技術的にも進歩しているし、やはり需要はあるようだからと、もう一度チャレンジしてみることになった。伺った手法を当時の記憶と照らし合わせてみると問題だったポイントが一つ解決していそうだったから、見込みはあると感じている。

1時間程度でサクッと終了。学食で夕食を摂ろうと思ったが、うっかりハーメルンの更新を読み始めてしまって行けなかったためいつものパスタになった。それから深夜までかけてラノベを3冊読了。

1冊目、「クラスで2番目に可愛い女の子と友だちになった」4巻。円満に解決したため読後感は悪くなかったものの、読んでいる最中はかなり辛かった。学年が上がって主要キャラのクラスが分かれたが、主人公の人間関係的なイベントは次巻以降ということで。それに関してはラストに意味深な描写もあったしかなり楽しみにしている。

2冊目、「なぜかS級美女達の話題に俺があがる件」。学校の外での主人公が格好いいとか、設定はかなり好みだった。ただし1巻の展開はあまり……という感じ。平穏な学校生活を守るためにヒロインを遠ざけるという理由だったとしても、わざと嫌われるような行動を取ろうとするのは肌に合わなかった。結局勘違いされて好感度を稼ぐ結果に終わるのだが。2巻以降に期待。

3冊目、「灰の世界は神の眼で彩づく」。面白かった。ダンジョン内で超強力な力を手に入れる話はよく見るが、その後その力を周囲にバレないように運用したり、あるいは主人公が自分の力の特異さに気づいていなかったりすることが多く、その不自由さにやきもきさせられていた。この作品では展開の都合上序盤から上位陣と太いパイプを持っていて、そのあたりが見事に解決されている。快適に読むことができた。

paizaのイベントでコードゴルフが行われているらしい。あんまり勝ち切る自信がなかったので流れてくるコードを見るだけにしていた。今日は特にビンゴを数える問題が話題で、どんどんテストケースハックが進み最終的には乱数で3ケース正答することを祈る状況に成り果てていた。anarchy golfを思えばこれもまたコードゴルフである。

ppg.paiza.jp

その乱数を得る方法もどんどん改善されていき、自分が見たときは変数のアドレスが使われていた。ところでこのための変数を自分で宣言するのは無駄に見える。ヘッダファイル内で宣言されているものが使えないか考えてみたところ、stdinがちょうど良いことに気づいた。これ自体ポインタのため&演算子も取り除けてさらに嬉しい。相変わらず自分で出す気はないのでTwitterに放流した。

頼んだ#import<ios>
int main(){putchar(48+(long)stdin%7);}
— こたつがめ (@kotatsugame_t) 2023年6月8日

関数名をそのまま入れても動きはするようだが実行の度に値が変化しないため乱数には使えなかった。アドレスを使う方法自体、その後clock()に負けていた。

シャワーを浴びた後少し服の整理を行った。mont-bellの長袖Tシャツは袖口の縫い目が斜めにずれているものばかりで実は結構気にしていたのだが、さすがにただ質が悪いわけじゃないよな……と思って調べてみたところ大当たり、特許も取得されている「スパイラルスランテック® カフ」という技術だった。こうすると生地の伸びが妨げられず着心地が良くなるらしい。

https://www.j-platpat.inpit.go.jp/c1800/PU/JP-2011-144461/F237B1336AB8993F0C93FD8CD290D78B76124A1A9309D71861302A47CDA3A80A/11/ja

セミナー原稿の見直しをした。昨日やり残したexerciseについては、どうせ次回の発表でそこまで進むわけないし後回し。前々回用意した分がまだ残っているので記憶を復元するべく読み返しておいた。

ゴミを出した後布団に入ってスマホでしばらくYouTubeを見ていた。午前7時過ぎ就寝。

06/09(金)

午後3時半起床。大学に向かう。

まず、先生に教えていただいた論文を読むため情報科学研究科の数学図書室に向かった。今日は数学資料室が臨時閉室である。載っている本は問題なく見つかったが大きかったため該当ページをコピーさせてもらうだけにした。その後購買で食べ物を買って夕食とし、午後5時からセミナー開始。

最初の30分は1章の演習問題の発表を聞いた。英語の発表だったが、大昔に共有されたきりの資料を引っ張り出すのに失敗していたため正直あまり聞き取れなかった……。最後の問題は資料を見せながらの説明だったので、それは辛うじてついていけたものと思う。

次の2時間は自分の発表。6.5章の内容を終わらせた。今週必死になって準備していた部分には一切踏み入れなかったが、これでも思ったより進んだなと感じるくらいである。もうちょっと飛ばしていかなければならない、と頭では分かっていても、いざ黒板の前に立つとネットリした説明になってしまう……のだろうか。自分ではよくわからない。

最後の1時間半は同級生の発表だった。先週やるはずだった分。そのとき自分が原稿を読んで指摘していた部分があんまり改善されていないように見えたので、チクチク口を差し挟んでしまったが、思い返すと口を出すタイミングが早すぎた気もする。もうちょっとじっくり聞くべきだった。

セミナーの終了時刻と今日のyukicoderの開始が同じため、どうせ間に合わないのならと参加者と思う存分喋ってから帰宅した。家に着いて午後10時半からyukicoder 392に参加。一応その前にも問題はチラチラ見て考えていた。

yukicoder contest 392 - yukicoder

Aは、ランレングス圧縮したときの長さが偶数なら、連続する同じ数を一つにまとめた後0と1を組み合わせることで0.5が何個か作れるためOK。長さが奇数でもどこかで区切ることで偶数の列二つができる可能性があって、これもOK。そもそもここまでの条件を正しく書くのに何ペナも支払ってしまったが、その間一向にWAのケースが減らなかった。

他にどんなケースで0.5が作れるのか頭では全然わからなかったので諦めて愚直を書いてみたところ、なんと0 1 0 1 0 1 0 1 0で作れることが分かった。ランレングス圧縮したときの長さが9以上になればOKという判定も加えてようやくAC。後からどうやって0.5を作るのか具体的な手順を調べておいた。

すいません、愚直の結果をそのまま出力すればよいです

0 1 0 1 0 1 0 1 0
↓
[{(0 1) 0} 1] {(0 1) 0} (1 0)=
5/8 1/4 1/2
↓
5/8 3/8
↓
1/2
— こたつがめ (@kotatsugame_t) 2023年6月9日

Bは法が2べきなのに注目。最初は十分な回数操作したら全部0になってしまうんじゃないかと考えていたが、実験してみると全然そんなことはない。 $\bmod 2$ のケースを考えるとリュカの定理を使う典型問題になって、確かに全然0にはならないようだ。

しかしこの方針はそれほど間違っていなかった。下の方まで影響を及ぼすのは偶奇部分のみで、それ以外は1段下がるごとにどんどん2が掛けられていくらしい。試しに長さが30になるまで $\bmod 2$ で計算し、残りを真面目に計算してみたところ、愚直と一致した。提出してそのままAC。

Cはずっと $\min A$ を真ん中にどう並べるかから考えようとしていたが、逆に両端から考えると人数の分布が高々一意になるようだ。それっぽく書いたら合って感動。

Dは時間が足りなかった。 $i\rightarrow A_i$ として作ったfunctional graphにおいて $A_i$ から $B_i$ へ到達できるかの判定だけで出したが当然WA。ここでコンテストが終了し、結果は3完14位となった。

ロスタイム10分弱でDをupsolve。functional graphのループ部分をまじめにやる必要があるのは分かっていて、落ち着いて考えてみると1回操作した瞬間ある要素への入次数が0となるのが重要だと気づいた。だからそういう頂点を作ってよいか、つまり $B$ として現れない頂点 $u$ があるか探し、そこを飛ばすように操作することでループの長さを1減らすことができる。飛ばされた $u$ について $B_u$ はループ上のどこでも可能だから、これも無視。

少し解説をチェックした後はずっと日記を書いていた。午前10時前に就寝。明日はUniversal Cupがない。今年1月に始まってから初めての休みである。

06/10(土)

午後5時に目を覚まし、布団でスマホを触っていた。2時間くらいしてようやく身を起こし、食事。その後日記を書き進めようとしたがどうにも集中できず、ハーメルンを読んだり動画を見たり散々だった。

午後9時からABC305に参加した。

KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） - AtCoder

Aは $\lfloor(N+2)/5\rfloor\times 5$ 。dcで書いた。FA。Bはどうしようもないので普通に。

Cは $a,b,c,d$ を決定してから答えを求める解法を書こうとしたが面倒。少し考えたところ4近傍に#が2個以上ある.マスが答えであることに気づいた。

Dは $f(r)-f(l)$ という形で求める。 $f$ の計算は二分探索。 $A$ の上で探索して計算すると就寝・起床のタイミングが偶奇に依るため扱いが面倒そう。そこで一度「寝ている時間帯」を表すペアを列挙してから考えた。

Eは水曜日に出たCodechef Starters 93のMAIL_DELIVERとほぼ同一の問題。ここまで一致していれば、もしかしたらコピペしてきたほうが速かったかもしれない。まあ普通に書いた。

Fはdfsをインタラクティブに行う。これまで辿ってきた頂点をスタックで持ちつつループで書いた。dfsで書いても良かったなと思うが、頂点から戻ってきたときに入力を読み込むのを忘れがちだったらしい。また操作が完了したときに入力される値OKが整数でないのがちょっと嫌らしいなと思った。

Gは $T$ の後ろ5文字を状態に持つdp、を行列累乗で高速化。 $N\lt 5$ のケースは別で全探索した。

Exは考察は（少なくとも自分が行った範囲では）一本道だったが大変だった。まず考えるべきは1日に解く問題を並び替える部分で、典型考察により $\frac{B}{A-1}$ の昇順に並べるのが最適と分かる。ここで $A=1$ の場合は無条件で一番後ろに入れてよく、単に疲労度を $B$ 増やす効果を持つ。

問題で問われているのは消費した体力の「総和」だから、 $A=1$ はどの日にやっても変わらない。よって全て取り除くことができる。 $A\ge 2$ の問題のみが残るが、これを1日に $c$ 問解くと疲労度が少なくとも $2^c-1$ になることに注意。つまり1日に解ける問題数は高々 $O(\log X)$ 個である。

1日にどの区間の問題を解いたら体力をどれだけ消費するか、という情報を $O(N\log X)$ 本の重み付き有向辺として表す。すべての問題を解くというのはこの辺を辿って最初の問題から最後の問題に辿り着くことであり、そのとき使った辺の本数が $K$ 、重みの和が消費した体力の総和となる。

本数と重みという2種類のコストを扱う方法を、自分はAlien DP系統しか知らない。以下の記事をガン見しながらチェックしたところ辺のMonge性は多分成り立つだろうと分かった。重み $X$ より大である辺を無視しているのはちょっと怪しいが……。ともかく、本格的に書いてみることにした。

Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms

記事通りの三分探索によって、日数を固定したときの消費体力の最小値が求まる。これが $X$ 以下になるよう日数を二分探索することで $D$ が決定でき、改めて消費体力の最小値を求めることで $M$ も求まる。二分探索に $O(\log N)$ 、三分探索は何も考えず記事に従って範囲を決めたため $O(\log X)$ 、またペナルティ付き最短路長を求めるのに辺を全部見て $O(N\log X)$ 。ペナルティに対する最短路長をメモ化して高速化を図った。

最初に無視した $A=1$ を答えに含め忘れていてしばらくサンプルが合わなかったが、それを修正すると見事に答えが一致してくれた。出したら2869msでAC。Alien DP系統の問題は、自分の今の実力では合うか合わないか運次第なところがあるので、一発で揃ったのには感動した。逆にこれでWAだったら自力では修正不可能だったろうと思う。

ノーペナ、67分45秒で全完。順位表を開いたら優勝していた。ABC302と違い、今日は動画を撮っている。振り返りまでしっかり行ってコンテスト後に投稿した。

www.youtube.com

Exの自分の解法は想定TLE解だったらしい。ここから高速化する部分の解説は読んでもよくわからなかった。メモ化がどれくらい効いたのかも知らないが、まあ通ったのでヨシ！ということで……。

コードゴルフはAとBのみ。AはFAがそのままshortestだった。BはRubyで適当に。

気持ちがふわふわして何も手につかないし眠くなってきたので布団に倒れこんだ。午前0時半から4時間ほど寝ていた。起きてからはずっと日記を書いていて、午前11時に再度就寝。

06/11(日)

午後3時前に起きてAHC020に参加した。

ALGO ARTIS Programming Contest 2023（AtCoder Heuristic Contest 020） - AtCoder

一読して「頂点集合を焼きなます」という方針に決めた。今回の出力は $P$ と $B$ だが、直接扱うのではなくそれを間接的に決められるものを焼きなますという手法。以前のマラソンで知って目から鱗を落とし、一度やってみたいと思っていた。

頂点集合を決めた後は、その間の辺だけ使って最小全域木を作り、その後各住民から最も近い頂点を調べてそこの出力強度を適切な値に設定する。全域木が作れなかったり出力強度が5000を超えたりするならOUT。このアルゴリズムでスコアを実際に計算し、その値を見て焼きなました。

パパっと書き上げて提出したら51分時点で459027742点が出て、2位になった。

開始1時間ちょっとが経過しました！（時計見忘れてた……）
現在のトップはJoshcさんです。ここからどう順位が動いていくのか……？ #AHC020 pic.twitter.com/7PSregBe9Q
— TERRY (@terry_u16) 2023年6月11日

しかしその後ちっとも伸ばせずコンテスト終了。以下では何をやったか記録しておく。最小全域木に選んだ頂点の間の辺しか使っていない点と、単に近い頂点から電波を飛ばしているので範囲に被りがあって無駄になってしまう点が気になっていた。

電波を飛ばす頂点をどこからにするか、山登りしてみたり焼きなましてみたりした。これらは全体の焼きなましの回数を大幅に下げるしスコアも結構減ったのですぐ捨てた。次に、頂点がカバーする範囲が十分被っていた場合どちらかに全部担当させてみることにした。これは単純な改善だから少しスコアが上がった。

全域木については、頂点集合ではなく使う辺集合を焼きなますということを一度やってみたが、これも微妙にスコアが下がったのですぐ捨てた。

最終的には、先ほど述べた $P$ の被りを減らす処理と、全域木を作ってみた後の連結判定を張った辺の本数を数えて行うなどの高速化に加え、焼きなましの最終温度をかなり高めにした結果の462043888点が最高スコアとなった。結果は173位でパフォーマンス1797、レートは2032→2044(+12)。

TLの感想戦を見ながら振り返り。結果的に頂点集合を焼きなますのは良くなかったらしい。またそうするとしても、選んだ頂点全体を連結にするのには「最小シュタイナー木」を考えるべきだったようだ。まともにやるのは難しいなとは思っていたが、ちゃんと名前の付いた概念であることを知らなかった。

あとは問題に対する取り組み方について。最初から焼きなましをするのは良くなかった。ちゃんと貪欲→山登り→焼きなましというステップを踏み、それぞれで工夫を入れるべき。しかし全体の構想をサッサと決めてすぐ書き上げられるのは短期コンだとそれほど悪いことではないはずで、初手ガチャに成功すればそこそこ良い順位が取れてしまう。これだから成長しないのだ。

疲れたのでラノベを読んだ。「攻撃力ゼロから始める剣聖譚」を読了。面白かった。副題に「幼馴染の皇女に捨てられ」とあるが、それを見返すような描写は今のところほぼない。牙を抜かれてしまった主人公が新天地で成り上がっていく話で、ギスギスした感じがなく登場するキャラも気のいい人ばかりで読んでいて快適だった。

その後日記を書き進めていたが、どうにも集中が持続しない。かなりの時間ハーメルンに気を取られていた。1作読了。「万魔殿の主〜胡散臭いトレーナーとウマ娘たちは日本を驚かせたい」。

syosetu.org

1年ちょっと前に一度最新話まで追いついておきながら更新が途絶えたタイミングで読むのを止めてしまったのを、改めて最初から読み直した。やはり面白かった。他のウマ娘の二次創作と比べると主人公陣営も普通に負けるし、現実のローテーションに合わせているのか出るレースが少ないため作中の時間経過が早い。序盤は主要キャラがじっくり掘り下げられ、後半はチームメンバーがどんどん増えていく様子を楽しめた。

午前7時半ごろ布団に入り別のハーメルンを読み始めた。午前9時を過ぎたあたりで寝落ち。

今週末はほとんどコンテストがなかった。それで空いた時間を何に使ったかというと……何にも使えていない。日記を書いた、とは言っていたがあんまり集中できなくて、YouTubeを見たりTLを読んだりと時間をドブに捨てるような真似ばかりしてしまった。普段通りでなかったからか何というかリズムが崩れてしまった感じがある。弱い自分にがっかり。

kotatsugameの日記

週記（2023/06/05-2023/06/11）