10/09(月)

午前9時頃に目を覚ました。1時間ほど布団でゴロゴロしていたが、二度寝にチャレンジするよりいったん起きてしまったほうが生産的だなと思って身を起こし、それから夕方までずっと週記を書いていた。

学食の夜の部に行ったら牛乳が値上がりしていてびっくり。自分が入学したころは68円だった。

助けて！！！（大声） pic.twitter.com/elToCZaUxa
— こたつがめ (@kotatsugame_t) 2023年10月9日

ラノベを購入して帰宅し、それから深夜までずっと週記を書いていた。切りのいいところまで書いたら仮眠しようとは思っていたがタイミングを逃した。午後11時過ぎに投稿し、半からECR156に参加。

Dashboard - Educational Codeforces Round 156 (Rated for Div. 2) - Codeforces

Aは $(1,2,n-3)$ と $(1,4,n-5)$ のどちらかを出力した。 $n=1\dots 6,9$ は不可能。Bは原点と点 $P$ がそれぞれ二つの円のどちらに含まれるか全探索。二分探索に見えたが必要な半径は算数で求まる。

Cはちょっと大変。「一つ後ろの文字より大きい」文字で最も先頭に近いものを削除していくことになる。削除後にその左右の文字を比較するため、双方向連結リストで文字列を管理した。双方向連結リストは自分で実装したが、標準ライブラリに頼ってもよかったかもしれない。eraseやinsertで他のイテレータが破壊されることはないようなので、最初にインデックスとイテレータの対応を求めておけばよい。

Dは簡単。挿入dpを考えると、 $s_i$ が?であるような $i$ に対する $i-1$ の積となる。 $i\ge 2$ は積を管理して、 $i=1$ だけ別で扱った。

Eはちょっと難しい。 $a$ をソートしておくと、各プロジェクトに割り当てるプログラマが区間になる。よって、割り当て終えたプロジェクトの集合を状態とし、それを達成するために最短で $a$ が端からどこまで必要かを持つdpが考えられる。遷移は前計算。割り当てに使う区間の $\min a$ を固定すると必要な長さがわかるので、これで区間の候補が列挙できる。

Fは解けなかった。答えを二分探索することにして、二つのダイヤモンドを盗む時間をそれぞれ固定すると判定が貪欲で行えるだろうと考えたが、WA。5完13位。

www.youtube.com

ゴミを出した。ついでに洗濯機の柔軟剤投入口にこびりついた柔軟剤を爪楊枝でこそげ落としたが、層をなして固まっていたものがごっそり取れて気持ち良かったものの、長時間に渡って洗濯槽をのぞき込む姿勢だったため腰が痛くて大変だった。

布団に入って少しだけ本を読み、午前5時就寝。

10/10(火)

午前10時起床。昼過ぎまで布団で本を読んだ後、学食に行って昼食を摂り、購買でラノベを買って帰ってきた。

来月のラノベ新刊を眺めたりYouTubeを見て時間を過ごし、午後5時半からインターン先定例会。昨日が休日だったためここにずれてきた。

先週も延々と学習を回す実験をし続けていた。コードの書き換えが一瞬で終わってしまうため稼働時間に算入できるほど働いていない。やるべきことはいくつか考えてあるから、タスクの性質上働けないとかそういうことはなく、ただ面倒がっているだけ。進捗としては実験結果と考察を述べておいた。

勉強会は四元数の話で、三次元空間の回転と球面線形補間についてだった。回転について、競プロの三次元幾何のことを考えると、軸と角度を正確に定めるのが難しくてそれさえ分かれば二次元の回転を無理やり合成して実装してしまえるのかなと思った。これなら高次元への一般化もできる。

深夜までかけて「午後のチャイムが鳴るまでは」を読了した。非常に面白かった。ある高校で同じ日の昼休みに起こった五つの出来事、日常の謎をそれぞれ描いた短編集。結末がどれも青春らしい爽やかなもので気持ち良かった。四つ目の短編は「九マイルは遠すぎる」のオマージュになっていて嬉しい。

また短編同士のリンクが非常に緻密だった。非常に限定された時間帯の話ということでいろんなニアミスがあったようだ。その描写や時刻の記述を元に出来事をパズルのように組み合わせ、時系列に沿ってどこで何が起こっていたか考える作業が本当に楽しかった。

実はもっと深いところでの繋がりがあって、それこそが作品のメインというかオチになっている。ネタばらしより前に気づけたので、最後の短編は答え合わせみたいな感覚で読めて、なかなかない体験だった。

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

10/11(水)

午前9時起床。昼過ぎまでラノベを読んでいたら学食の昼の部を逃しそうになった。

午後2時から午後4時半まで開いていないのは辛いなあと思いながら生協の営業時間を確認していたら、Beeカフェなら夕方まで開いていることに気づいたので、今日はそこで食べた。外からだと暗くて営業していないように見えたが、照明が控えめなだけ。

帰宅して3時間ほど寝た後はずっとラノベを読んでいた。

夜になって王座戦第4局が決着し、藤井聡太八冠が誕生した。これまでの勝ちっぷりを見ていると当然のようにも思えてしまうが、しかし本当に実現するのはやはり驚き。勝ち方も当然とはとても言えない波瀾万丈のものだったとのこと。

将棋といえば羽生善治九段、という感覚は自分の中で未だに根強い。おそらくこれは子供のころ公文式の教室で読んだ漫画が印象深いからだと思う。検索したらそれっぽいものが出てきたので一応リンクを貼っておく。ラストの七冠一歩手前で負けてしまうシーンにはそれまでの順風満帆な描写との落差もあって強い衝撃を受けた。ところが今、藤井聡太八冠はタイトル戦をなんと無敗で駆け上がったのである。

www.amazon.co.jp

「黄金の経験値」3巻を読了した。今巻もやっぱり面白い。ダンジョン運営を始めるともう一般プレイヤーとは完全に格が違う状態になり、一気に安定感が増して安心して読み進められる。また、PCとNPCの違いはシステムメッセージを受け取れるか否かでしかない、という1巻からある設定の力強さを再確認した。今回はNPCに憑依するとPCとほぼ同じことができるようになった様子が描かれていた。そうやって手探りでゲームの仕様を解き明かしていく様子にワクワクする。

就寝。午前3時くらいだったのではないかと思う。

10/12(木)

午前10時くらいに少し起きていた記録があるが二度寝に成功したようだ。午後3時半起床。しばらくラノベを読み、夜になって学食に行き夕食を摂った。

ツイッターを見ていたら綾辻行人さんのツイートが流れてきた。思わぬところですごい話題が出ているものだ。

きのう初めて存在を知って、んー？と思いつつ視聴してみたのだが、しぐれうい（９さい）恐るべし。曲が耳について離れん。
— 綾辻行人 (@ayatsujiyukito) 2023年10月5日

京極さんは「粛聖!!」もご存じでした。死角がないお人ですな。 pic.twitter.com/FH4S8Iq4Dx
— 綾辻行人 (@ayatsujiyukito) 2023年10月12日

帰宅して、研究のため論文サーベイをした。以前導いた等式がどこかで出ていないかを探す目的。もし出ているとしたら論文ではこれを引用しているだろう、という文献があるので、それといくつかのキーワードを使いGoogle Scholarで検索をかけ、出てきたものの数式だけザッと眺めてみた。

真に喜ぶためにはこの等式が既出でないことを確かめる必要がある。
週記（2023/09/25-2023/10/01） - kotatsugameの日記

結果としてはとりあえず見つからなかった。自分の目が節穴なのか、検索が悪いのか、等式が興味の対象にならなかったか……。新しければよいというものではない、というのはずっと言われてきたことである。とりあえず修論の骨格はこれにするとして、これから頑張って応用なり一般化なりで肉付けをしていかなければならない。

ラノベ「攻略できない峰内さん」を読んだ。ヒロインとボドゲで遊ぶ話。知っている、何なら持っているボドゲがいくつか登場したが、なんというかそれだけだった。プレイの様子がかなりあっさり目に描かれるので、知らないボドゲにはついていけないし、知っているボドゲだったからと言って話に深みが増すわけでもない。ボドゲでなくてもヒロインの可愛らしさは変わらなかったのではないだろうか。

午後11時半からCF #903 div.3に出た。

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

Aはちょっと手間取った。実際に操作を繰り返してみて、 $|x|\ge|s|$ となったステップ「の次」まで見ればよい。チェックは愚直で十分間に合う。Bは $a+b+c$ を $3\dots 6$ で割った値に分割できるか見る。Cはやるだけ。 $n$ が偶数なのが優しい。Dは素因数分解して指数ごとに見てよく、すると1ずつ動かして均す問題になる。Eはdp。

Fは、マークされた頂点を全部含む極小の木を取って直径を求めると、その端点のどちらかが最遠点になる。元の木の葉がすべてマークされていれば有名事実で、そうでない場合も取り出した木に向かうパスを取り除いて考えれば従う。

Gは長さ2または3の回文がないかチェックすればよい。区間の両端2文字ずつを持つ遅延セグ木を書いた。vectorで適当に実装したらTLEしたので固定長配列に直してAC。そこまで定数倍が効くとは思っていなかった。全完11位。

www.youtube.com

ラノベを読みつつセミナー準備をした。前回発表できなかった分が残っているので少し手直しするだけ。今取り組んでいる研究の動機を書いてみたが、もともと興味があったところからよく知らない方面に一般化していったため、周辺知識が足りずかなり書きづらかった。

研究の動機難しすぎるだろ。ついカッとなって……とかでいいか？
— こたつがめ (@kotatsugame_t) 2023年10月12日

午前9時就寝。

10/13(金)

午後2時起床。二度寝できないか機を伺いつつ1時間ほど布団でスマホを触っていた。そんなことをしていたら当然眠れるわけもなく、起床。準備し午後3時半に家を出て、Beeカフェで食事したり図書室に寄ったりしつつセミナーの教室に行った。

最初の1時間は留学生の発表。先週紹介した論文を読んできてくれた。もともと今週は忙しいという話だったから、とりあえず今の知識で読めそうかどうかを確認してくれれば良いと先週伝えていたのだが、思ったより先までの発表準備を整えていて大変驚いた。

次に自分の発表。先週は英語を喋ろうとしてボロボロになっていたので、今日は板書だけ英語にして日本語で発表した。原稿はほぼ先週用意したものだったから、証明の細部をどうするつもりだったかわからなくなって少し固まってしまったが、その場でひねり出したものが結果的にはなかなか良い説明になってくれた。

午後7時半に終了。閉店直後の学食に行ってみたら何とか滑り込ませてもらえたので、そこで先生と留学生と食事して帰宅した。

しばらくYouTubeを見て、午後9時20分からyukicoder 408。

yukicoder contest 408 - yukicoder

Aから難しかった。長さ2までは全探索。長さ3以上は値が区間をなすとしてよく、さらに値を追加する際は最小と最大だけチェックすれば十分になる。コンテスト中はそこまで整理できておらず、正負が入り混じる場合正と負を分けて考えてから最小値と最大値の積をチェックするということをしていた。また0だけ特別扱いしていたら数列の要素が全部0のケースで1WA。

Bは個数を決めたら降順に並べるべきで、転倒数を最大化するためには個数の2乗和を最小化すればよい。直感的には全要素を同じくらいの値に揃えられれば良いので、どの値に揃えるか二分探索した。

Cは最後に取るペアが必ず山の一番下のカード同士となるので、 $V_{1,2n}\le V_{2,2n}\le V_{3,2n}$ としたとき $(V_{1,2n},V_{2,2n})$ を選ぶのがよさそう。これは2回の比較で最大値を見つければよい。

すると $(V_{1,n+i},V_{2,n+i})$ まではペアを作って良いので、次に $(V_{1,n},V_{3,2n})$ または $(V_{2,n},V_{3,2n})$ を取ることになる。これも小さいほうが良いので、1回比較する。例えば $V_{1,n}\le V_{2,n}$ なら $(V_{1,i},V_{3,n+i})$ が確定し、最後に残った $(V_{2,i},V_{3,i})$ もペアを作って終わり。

これで合計3回。最適解っぽい雰囲気がかなり漂っていたが、一応 $(V_{1,2n},V_{3,2n})$ をペアにしても改善されないことを確認してから提出した。

Dは $x+y$ を状態とする。これが同じ値である座標間は自由に行き来できるので、それを十分行った後の移動方法の数は具体的な $(x,y)$ によらず常に等しくなる。これでdpを書くととりあえずサンプルの三つ目までは合った。このdpは直前2状態しか見ていないので行列の形で遷移できる。係数を手で書き並べてみたら前計算できる部分と定数になったので、AC。

Eは「 $n$ 回目の操作が行われる確率」を足し合わせれば答えになる。1回目の操作以降黒く塗られなかった頂点はパスをなすので、 $n\ge 2$ としてパスのLCAごとに確率を求めるのが良い。LCAを頂点 $u$ だとして、 $u$ を黒く塗らない操作の確率 $p$ 、 $u$ とその親の両方を黒く塗らない操作の確率 $q$ はどちらも簡単に分かる。すると求める確率が $p^{n-1}-q^{n-1}$ になり、無限和を求めることが可能になった。

Fは1行目と1列目を見ることで各行・各列にどのような操作をしなければならないかわかる。特に一つ固定すれば他が全部一意的に決まるので、まずこれで $b$ が作れるか判定した。

例えば1行目への操作を $x$ としよう。すると $j$ 列目への操作は $x\oplus a_{1,j}$ 、 $i$ 行目への操作は $x\oplus a_{1,1}\oplus a_{i,1}$ と書ける。またその操作を実現するのにかかる手数は0回から2回または $\infty$ 回（不可能）と分類することができて、操作する値と $R$ 、 $C$ または2べきとの大小関係で区別できる。

そこで $x$ をセグ木のインデックスだと思うと、「 $(x\oplus A)\lt B$ なる $x$ に対し手数を足す」ことで $x$ をうまく定めた時の最小値が求められる。そしてこれはbinary trieで実現可能。 $x$ が非常に大きくなる点も問題ない。

かなり面倒そうな問題だったが整理すると非常にシンプルな形に落ち着いた。一発AC。残り30分はG・Hに手も足も出ずコンテスト終了。全完が二人いて、自分はそれに続く6完3位だった。

Gを解説を読んでupsolveした。天才すぎる。似た話が以前数学基礎論の講義のレポートで出題されたことがあって、そのときも分からずネットで調べ、あまりの天才さにひっくり返ったことを思い出した。しかし肝心のテクニックはまだ自分の引き出しに入れられていなかったし、upsolveした今も残念ながらそうである。

arithmetic - How to define multiplication in addition terms in monadic second order logic? - Mathematics Stack Exchange

TLに流れてきた正規表現パズルに1時間ほど時間を奪われつつ、午前4時就寝。

10/14(土)

朝方2回ほど目を覚ましたが、今日はすぐ二度寝に入れた。午前11時半起床。悪くない睡眠時間である。

食事して正午から1時間AHC025に参加した。

AtCoder Heuristic Contest 025 - AtCoder

午後1時からTTPC2023。このコンテストは将来的にUniversal Cupに使われるということなので、同じチームで参加した。わざわざ組んでいたチームを崩してまでこちらに合流していただいたrisujirohさんに感謝。

Tokyo Tech Programming Contest 2023 - AtCoder

書く：TTPC、Iのupsolve

午後9時からABC324に出た。

Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) - AtCoder

A、Bはよい。Cにちょっと手こずった。まず $T'$ と長さが2以上異なる文字列は無視してよい。すると残りの文字列の処理には $O(|S|+|T'|)$ かけてよいため、 $S$ と $T'$ でprefix・suffixがどのくらい一致しているか求め、判定した。Dは平方数のほうを全探索。

Eは左端・右端から貪欲に $T$ を作った結果を見て、十分な長さが得られるペアを数えればよい。ところが貪欲に作るフェーズを関数に切り出したとき、うっかり $T$ 自体を値渡ししてしまい、 $N$ 回コピーが発生してTLEしてしまった。

Fは典型の二分探索。Gは点 $(i,A_i)$ をプロットすると列が常に長方形領域として書けるようになる。列の長さがrangefreqで求まるので、 $t=1$ での切り出しも境界を二分探索すればよい。自分の持っているrangefreqライブラリは $\log$ が二つ付いているので全体で $O(N(\log N)^3)$ 。Wavelet Matrixなら一つ減るだろう。

33分33秒で最速全完だがEでペナがついている。しばらく待ってから改めて順位表を確認したら一人に抜かされていて、結果は2位となった。しかし日本人内では変わらず1位なので、賞金50000円＋30000円獲得。久しぶりの賞金だし額面も大きくてかなり嬉しい。

コードゴルフはABF。AはNibblesで、なんだかぎこちない気がするが縮まない。BはBash、factorしてsed。テストケースハックで先頭桁が2と3以外の素数があったらNoとしているので、例えば $N=23$ で普通に落ちる。FはRubyで書いておいた。

www.youtube.com

夜中はTTPCのupsolveとしてチームメイトが解いた問題のうちP以外を自分でも通していた。すると午前3時になったので、ちょうど終了したUniversal Cup 5回目の感想戦に参加。この回は春先のMuscatキャンプday 7でも使われており、そちらで出てしまったので今回は見送っていた。

kotatsugame.hatenablog.com

今日は自分が抜け、さらにNyaanさんも出られずrisujirohさんが一人で走っていた。ありえないくらい難しいセットだということを知っており、TTPCと同日にこれとソロで格闘するのはさすがに無理に見えたが、なんとGを通していた。しかもコンテスト開始4時間半の時点である。そこまで戦い続けていられること自体頭が下がる思いである。

自分が持っていた解説pdfを見ながら2時間ほど喋っていた。Gの解法は解説でuglier wayと言われていたものらしい。説明されて雰囲気は何となく捉えたが細部を詰めるのは不可能だろうという印象。こちらからは参加記にもあるBとEの話をした。

話の流れでYandex Cupに参加登録した。去年も存在は知っていたが、アカウント作成がロシア語で放り投げた記憶がある。今日は自動翻訳と見比べながら何とか登録に成功した。

Yandex Cup — championship for developers

食事して日記を書き、午前6時就寝。

10/15(日)

午後2時半起床。午後3時という変な時間から開催されたTROC #34に出た。

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

A、Bはよい。Cは場合の数を出力するのだから不可能な場合答えは0だろうと思っていたら-1で1WA。サンプル2の出力が間違っていることに気づけなかった。

Dは階の移動と頂点の移動を独立に考えてよい。前者は中央値が最適。後者は全方位木dpですべての頂点について答えを計算できる……と思ったら実装ミスで1WAした。このあたりで完全に頭が回っていないことに感づいた。

Eはちょっと難しい。 $x=1\dots 10^5$ に対し「選んだ値のうち $x$ の約数だけ取り出したときのLCM」を管理して、値の昇順に作れるかどうかを見ていく。必要でない値が作れてしまったらアウト。必要な値が作れなかったら新たにそれを選び、更新は倍数だけ全部見ればよい。雑に見積もると $\log$ が二つ付くが間に合う。さらに $10^5$ より大きな値が作れてしまわないかを見る必要があって、こちらは $A$ 全体のLCMを計算してみればよい。

ところが倍数を列挙するループなのに値を1ずつインクリメントしてしまったり、「 $A$ に値 $i$ が出現したか否か」というbool値をA[i]として持ったのに $A_i$ そのものと混同してしまったりで2WA。ひどすぎる。

Fは各要素がピークになる場合の数を、端に置かれた場合とそうでない場合に分けて数えた。算数。Gはド典型マージテク。

Hは操作とその組み合わせがmin-plus半環の $8\times 8$ 行列で書けるので、それを持って区間更新・1点取得。ACLの遅延セグ木を使ったらTLEしてしまったが、双対セグ木に書き換えてunroll-loopsを指定したら621msと爆速になった。特に前者が効いているらしい。要素を64bit整数で持っていたので空間計算量の削減が効いたのだろう。

全完、ペナまみれで7位。レートは2868→2875(+7)ということでこの順位でも微増してくれた。

シャワーを浴びて食事した後、しばらく日記を書いて、午後9時からARC167。今日はpotato167さんがwriterである。

AtCoder Regular Contest 167 - AtCoder

Aはいまいちよくわからなかったが、直感的には美味しいほうから $2M-N$ 枚のトーストを1枚ずつ、残りは最小と最大を組み合わせて2枚ずつ皿に乗せるのが最適に見える。これを出したら通った。皿を全部使い切ったほうが良いことから枚数の分布が確定し、あとは計算でこれの最適性を示せる。

Bはまず $A=\prod_i p_i^{e_i}$ と素因数分解した。すると $A^B$ を素因数分解した形もわかる。そして $A^B$ の約数のうち素因数分解したものに $p_i^e$ （ただし $0\le e\le Be_i$ ）が現れるものの個数が $\prod_{j\ne i}(Be_j+1)$ と書けるので、約数の総積を素因数分解したものには素因数 $p_i$ が $\frac{Be_i\prod_j(Be_j+1)}2$ 個現れる。

これを $e_i$ で割って切り捨てた値は $\left\lfloor\frac{B\prod_j(Be_j+1)}2\right\rfloor$ となり $i$ に依らない。よってこれが答えとなる。オーバーフローで1WA、またfloorを忘れてもう1WA出した。除数 $e_i$ がうまく消えてくれるから割り切れるものと錯覚してしまった。

Cは順当に解けた。 $A$ をdistinctとし、 $P$ を決める代わりに $A$ 自体を並べ替えていると見なす。また頂点 $u$ に値 $A_u$ が割り当てられていると書く。このもとで重みが $A_i$ であるような辺が何回使われるか数える。

$[i-K,i+K]$ にある値が $A_i$ より小さい頂点との間の辺が候補である。まずそのような頂点が三つ以上存在する場合、いずれか二つの頂点は距離が $K$ 以下となり、辺が張れる。するとクラスカル法から必ず連結になっているので、新たに辺は高々2本。1本の場合をデフォルトとし、0本と2本の場合を数える。

0本のケースは簡単で、区間に $A_i$ より小さい値がなければよい。インデックスと値を決めるごとにそのような $A$ の並べ方は算数で数えられる。これでもう2乗になっている。

2本のケースは少し面倒。できるだけ近い頂点に辺を張るものとすると、その対象になった二つの頂点の間には $A_i$ より小さい値が登場しない、という条件になる。愚直に求めようとすれば先ほどのようにインデックスと値を固定した上、2頂点がある位置 $u,v$ （ただし $i-K\le u\lt i\lt v\le i+K$ ）も必要で4乗になる。

数え上げの式は、 $A_i$ より大きな値を $n$ 個として ${}_n\mathrm{P}_{v-u-2}\times{}_{N-n-1}\mathrm{P}_2\times(N-(v-u+1))!$ となる。これをよく見ると $n$ と $v-u$ しか登場していない。

インデックス $i$ については $i-K\le u$ と $v\le i+K$ より $v-K\le i\le u+K$ 、つまり $2K-(v-u)+1$ 通りであり、 $u$ や $v$ の位置は全部をひと固まりにしてほかの値と並べ替えることを考えれば全通り試したことになる。よって本当に必要なのは値と2頂点の間の距離のみである。これでこちらも2乗になった。

Dはもう大変だった。先頭から貪欲に改善していくことを考えると、自分より右にあって自分と連結でない値のうち最も小さいものと入れ替えることを繰り返したくなる。ただしこれだけではサンプルの一つ目を連結にできない。そこで、この操作をした後各連結成分が区間になっていることを使い、改めて別の方法で連結にすることにした。

そういう2段階に勝手に分けてしまってよいものか迷いつつ、思ったより時間が経過していたので実装に入ることにした。ところがそもそも1段階目の貪欲を実装するのが難しい。連結成分をsetとマージテクで管理し、各連結成分について値の最小値だけ取り出して別のsetで管理する方針を取っていた。そのsetのtop2を見れば自分と連結でないものが見つかるという寸法だが、「自分より右」を実現していない。

いろいろ考えてもわからなかったので、連結成分のsetを自分の左右で分割し、二つ組で管理していくことにした。正確には最初右だけ見ていればいいと思っていたが、それだと左の要素が更新されずいずれ矛盾が生じてしまう。何とかデバッグで気づけた。ひたすら実装して残り10分強で提出したらWA。

絶望したが2段階目の貪欲が間違っていた。隣り合う連結成分について、前者で最も後ろにある値と後者の最小値をswapするのが最適なのに、最小値と最小値をswapしようとしていた。ここを修正して何とかAC。2段階に分けてよい理由は、恐らく見る場所が後ろの方と前の方で異なり干渉しないからだろう。

4完遅めペナまみれで84位。Dで苦しんでいる途中順位表を見たら200人近く解いていて本当に腰を抜かしたものだが、CまたはDだけ解いた人も多かったようで、ちゃんと4完したら2桁順位にはなってくれた。

www.youtube.com

Dは結局3500Bほど実装した。解説を読んでもいまいちピンと来なかったが、1点、連結成分のインデックスと $P$ の値をあまり区別しなくてもよいというのは発見だった。結局ループなので集合としては等しくなるのだ。これを元にして書き直してみた。

まず $P_1$ の改善を試すわけだが、これはつまり $2\dots P_i-1$ の間に別の連結成分の頂点があるかどうかを見ているのである。あれば頂点番号最小の頂点を擁する成分と連結にすることになる。これを繰り返すので、基本的には $P_i$ の改善を試すタイミングでは頂点 $i$ は頂点 $1$ と連結になっている。よって「別の連結成分の頂点」は「頂点 $1$ と連結でない頂点」と読み替えられ、条件が変わらないので尺取り法っぽく探索してよい。

そうでないケースでは、頂点 $1$ を含む連結成分は $1\dots i-1$ とちょうど一致するはずである。この場合 $P_{i-1}$ と他の連結成分の最小値を交換するのだった。その最小値とはつまり $i$ であるから、これもswap操作が特定できる。それを実行した上で改めて先ほどの改善を試すことにすれば、処理がまとめられてかなりすっきり書けた。