週記(2022/10/17-2022/10/23)

10/17(月)

午後2時過ぎに目を覚ました。もうひと眠りできるくらいの時間。ただし今日は、先週の週記を書き上げた上明日のセミナーの準備までする必要があるので、このまま起きて取り掛かる。まず週記を完成させることにした。

午後4時半からインターン先定例会。先週の進捗報告を休んだので、今週は2週分まとめての発表となった。大層なことをできていないので話す内容が増えてやりやすいという側面もある。

勉強会はプログラムの設計の話だった。開発をやりやすくするための設計方針はいろいろあるだろうが、どれに対してもそのアンチパターンこそが正解となるシチュエーションが考えられそう。ただそういうコーナーケースばかり考えていてもしょうがなくて、自分はまず何か一つの方針に則って設計するということを体験しなければならないはず。

勉強会の終了からしばらくして、週記が完成した。今週はなんと校閲まで済ませてある。午後8時に投稿した。ちなみに一つ前の週の週記は校閲が終わっていない。先週はその週の週記を書くことに注力していたのだ。

いよいよセミナーの準備に取り掛かろうとしたものの、眠気が強くなってきた。それでやる気も出ずしばらくTLを眺めていたが、さすがにこのまま過ごすのは効率が悪すぎるということで仮眠を取ることにした。夜中にコンテストがあるので、それまで2時間、午後9時半から午後11時半まで寝ていた。起きてすぐECR137に出た。

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

Aは6\binom{10-n}{2}aは読み捨てた。Bは1と2を両端に置けばよい。Cは蓋をされている箱が連続する区間を求め、その一つ左を含めた中でどれに蓋をしないのが一番被害が少ないか計算。うっかり右からdpしてしまって、蓋が左隣より遠くにある箱に被せられてしまい1WA。

Dはちょっと面白い。立っている最上位bitを最も大きな値にしたいので、s_1としてはs全体を選ぶのが良い。特にこの段階で先頭に1が現れるまで文字を削除しておくと便利。1が出現しなかった場合は別に処理する。次に、s_1で立っていない最も上位のbitを求める。存在しない場合はまた別処理。このbitを立てるのが次の目標になる。複数の方法がある場合は、そのうち答えが最も大きくなるものを選ばなければならない。

ここで入力がランダムであることが効いてくる。立っていない最上位のbitは上から少し探せばほぼ確実に見つかるのだ。あるbitを立てるためにはそれより上位からずらしてくる必要があるので、試すべき候補数が十分少ないことが分かった。あとは全探索すればよい。

Eは難しかった。二つのレーザーが同時に発射された直後の相手の耐久値でdpする。まず、以降二つのレーザーが同時に発射されない場合は単純な二分探索で答えが求まる。そうでない場合、次にレーザーを同時に発射するタイミングは必ず、どちらかのレーザーがちょうど何回目かのチャージを終えたタイミングになるとわかる。そもそもh回もレーザーを打てば耐久値を0にできるので、これは全探索してもO(h)通り。状態もO(h)通りなので間に合う。

Fもちょっと面白い。集合に入りうる各値について、それが入るような演算子の決め方が何通りあるか数えることにする。S_{i-1}まで決めた時点でxが入っている場合の数がaだとし、次のS_i=[l_i,r_i]op_{i-1}について考える。これまでの決め方が3^{i-2}通りとなることに注意。

l_i\le x\le r_iのとき、\cup\rightarrow 3^{i-2}\oplus\rightarrow 3^{i-2}-a\cap\rightarrow aより2\times 3^{i-2}となる。それ以外のとき、\cup\rightarrow a\oplus\rightarrow a\cap\rightarrow 0より2\times aとなる。まとめると、[l_i,r_i]に対して3^{i-2}をセットした後全体を2倍すれば表現できる。これは遅延セグメント木に乗る。

Gは面白かった。文字列の各prefixに対して、それを分割する方法を数え上げるdpをする。メモリの制限でdp配列を持つことすらできないが、実はそもそも見るべき位置が少ない。遷移してこれない位置にだけ着目すると、そのような位置から今見ている位置までの部分文字列がフィボナッチ文字列になっている必要があって、短いフィボナッチ文字列が少ないことからわかる。

ただこのままでは判定ができないので、もうちょっとインクリメンタルに更新する方法を考えた。今見ている位置までの文字列が、あるフィボナッチ文字列のprefixとなるような位置を持つことにする。これが十分少ないことは実験エスパー。特に今出現しうるフィボナッチ文字列は、f_0以外は十分大きな、例えばf_{32}のprefixであるから、f_{32}から適切な位置の文字を取得してきて今見ている文字と比較することで、その文字まで見てもまだprefixであるか否かが判定できる。長さがちょうどフィボナッチ数のprefixだった場合のみ遷移元として不適切となる。

フィボナッチ文字列から位置を指定して文字を取得するのは、フィボナッチ文字列の構成を逆に辿ることで行える。f_0の取り扱いに注意。出したら3300msで通り、全完4位。

朝までセミナーの予習をしていた。Dilworthの定理は半順序集合に対するものだが、Diestel 2.5.2の証明においては推移律しか使っていないように見える。反射律を入れても仮定は前順序というやつで十分。しかしどこを調べてもそういう内容が書いていなくて不安になった。ツイートしたらmaspyさんから同意のリプライがもらえたので、少し安心。

先週から発表の原稿を事前にメールで共有するように言われていたので、少し丁寧に書いたものをスキャンして送信。その後コードゴルフをして午前8時就寝。

10/18(火)

午前10時半にインターホンの音で起床。MHC Tシャツが届いた。注文してからまだたったの五日であるためびっくりした。

その後二度寝できずずっとTLを見ていた。正午くらいに布団を脱出し、生協に寄りつつ山に向けて出発。午後1時からセミナー。

最初2時間は先生が講義で使用するスライドに載せられた演習問題を解いて議論していた。実際に解けるのか、難易度はどうかとか。特に一つ目の小問は、最初問題だけを見せられると明らかに知識が足りなかったが、スライドにある事実を認めればアイディア一発ですぐ出る問題でちょっと面白かった。行列に関する命題を、行列を構成する要素を一列に並べて数列に関する命題に帰着するというもの。

その後2時間で自分の発表。後期から教室が変わって黒板が小さくなり窮屈そうだなと思っていたものの、今くらいのサイズのほうが全体を行き来できて、それがわかりやすいかはともかくやりやすかった。関連することをうっかり黒板の両端に書いてしまったりすることがよくあるが、特に問題にならなかった。内容は途中結構質問が入ったため、昨日準備したもので時間的にちょうどとなった。予習して自分だけ理解しているからといって、ぼんやりした説明のまま進めてはいけない。

その後しばらく来週のセミナーや木曜日のTAについて打ち合わせをして解散。ホスフィンに誘われて学食に行き、1時間以上話していた。

午後7時半帰宅。非常に眠いため、早々にシャワーを浴びて布団に入った。午後8時半から午前2時まで寝ていたらしい。

食事してTAの業務。木曜日の発表スライドがもう共有されていたので、読んでコメントや指摘をした。結構丁寧にやっているのでTAとしては明らかに過剰な業務となるが、絶妙に知っているようで知らない分野なので、読んでいて勉強になる。あとは単純にスライドに対してあれこれ言うのが楽しい。

それが終わってからTCB52に参加した。日曜日終了なのでここに感想を書く。

1問目が微妙に面倒。制約の「文字列の長さが4以上」と「tech型またはful型である」というのを最初読み落としてちょっと戸惑った。2問目から5問目まではよい。

6問目はちょっと読解に時間がかかった。i番目を含む周囲の文字からiを特定する問題とわかってしまえば、左右に追加で何文字聞けばわかるか調べる方針が出る。それぞれl文字、r文字とすると、Aの長さはl+r+\min(l,r)とできる。制約が小さいのでこれでも解けるが、実はl=0またはr=0の場合しか考えなくてよい。

7問目はSA+LCP。各suffixがSAにおいてどこに出現するかもセグ木で持っておく必要がある。クエリごとにそれを用いてどこからどこまでのLCPを求めればいいか計算する。8問目はどのインデックスの文字を持ってくるか貪欲に決定してよい。先頭から順に最も近いものを選ぶのが最適。すると単に数列の転倒数を求める問題となる。

9問目はtrie木。10問目はABCに2値に制限された問題がある。この二つで考察が必要なかったため、普段の回と比較して高速に解くことができた。30分ちょっとで理論値達成。この合計解答時間については、「解答所要時間」ではなくコードの詳細ページから「合格経過時間」を見て和を取れば正確な値がわかることを知った。

G - Range Sort Query

しばらく日記を書いた後、少しコードゴルフをして午前8時半就寝。

10/19(水)

午後2時前起床。準備してオンライン会議に接続し、いつも1on1をしている方とのペアプログラミングに臨んだ。

コードの仕様が少し変わって今のままでは対応できないので、書き直す作業が発生しているらしい。今日はその初手の設計段階だった。早速月曜日の勉強会で学んだことが活かせる機会、に見えて、元あるコードを書き直すのを優先すべきなので、コードの構造に対して何か変更を入れるというわけではなさそう。とりあえず肥大化したファイルの分割だけはどうしてもとお願いした。

3時間くらいかけ、大まかな話がまとまりつつあるところで今日はいったんお開きに。タスクとしてはコードを読んでおくよう依頼されたが、どうせ読むならという気持ちで自分でもブランチを切って書き直してみることにした。ペアプログラミングといってもこちらはずっと手を動かしていなかったため意欲が増すばかりで、その分この後4時間くらいずっとガリガリ書いていた。

コードが動くことは確認できても、出力を生成する段階まで書き直し終えないと正しく動いているかどうかがわからないのはちょっと困る。また出力が得られたとして、その形式がこれまでと変わっているので、比較する方法についても考えなければならない。

TCO22 Finalistへのインタビューが公開されていた。顔面と本名とハンドルネームが紐づけられた状態で大公開。ちなみにこの顔写真は一ノ関駅にあった顔出し看板で撮ったもので、当時の日記にも言及がある。

tco22.topcoder.com

一ノ関駅ピカチュウポケモントレインの顔出し看板があって、そこでもホスフィンに写真を撮ってもらった。

週記(2022/09/05-2022/09/11) - kotatsugameの日記

ホスフィンから競プロっぽいという論文が送られてきたので、YouTubeに気を取られつつ読んだ。タイトルになっている部分をなんとなく理解するまでで、他いくつか載っていた細かな話題に関しては見ていない。

Depth-First Search Using $$O(n)$$ Bits | SpringerLink

普通にdfsするとバックトラックのためにO(n)要素保存する必要があってO(n\log n)Bitsかかるが、そこを改善したらしい。改善といっても空間計算量を減らした分時間計算量に押し付けていて、O(m\log n)時間かかっている。保存する要素を直近のO(n/\log n)要素にすることで空間計算量を減らす。するとバックトラックが行えないタイミングがO(\log n)回あるので、それらについてはO(m)時間かけて頂点の訪問状態を見ながら再構築するようだ。頂点の訪問状態もまたO(n)Bitsで表現できる。

まだわからない部分もある。隣接リスト形式のグラフを扱っているので、各頂点についてリストのどこまで見たかを覚えておく必要があるはず。その情報分、O(\log m)Bitsはどうやって保存するのだろうか。グラフに多重辺が大量にあったりするとO(\log n)\subsetneq O(\log m)になってしまいそうなものだが。

しばらくコードゴルフした後、今日もまたTAの業務を行った。明日発表する人がそれほど時間を使わなそうということで、もう一人も少し発表する予定になっていて、その人の発表資料が共有されていたのだ。非常に面白いことが書かれていたのでぜひ図にしたいと思い、POV-Rayでプログラムを書いてGIF画像を作成した。

POV-Rayでアニメーションを作るのは少々面倒。基本的に一枚絵しか生成できないので、それを大量に用意してつなぎ合わせる必要があった。実行時に+KFF100などとオプションを与えると、ここに書いた数だけ生成される。画像を変化させるためには内部でclockという値を使うようだ。枚数によらず0から1まで線形に変化するので、適当に三角関数をかませることで、アニメーションらしく端でゆっくり動くような周期的な画像たちが得られるようにした。

上のツイートに貼ったGIF画像は実際に100枚連結している。これはImageMagickで作った。コードゴルフ大会で触れて以来久しぶりの登場。特に何か実装するわけでもなく、ググって出てきたコマンドをそのまま実行したら便利に動いてくれたので助かった。

少し日記を書いてから布団に入り、ラノベを読んで午前10時就寝。

10/20(木)

午後3時起床。眠気が強く、布団から脱出するまでにはしばらく時間がかかった。準備して大学へ。

教室に向かう前に生協に寄った。またしても出荷メールが届いてしばらく経つのに入荷メールが届いていない本があるので、それの確認。探してもらってみると、なんと出荷メールすら届いていない本もすでに入荷されていた。富士見ファンタジア文庫ラノベなのでちょうど今日が発売日。聞くところによると、メール送信に不具合があって一時期メールがうまく届かなかったらしい。もう復旧しているようだ。

前みたいに店頭に並べられたわけでもなく無事受け取れたので、特に問題はなかった。改めて教室に向かい、5限、TA。

一人目の発表者のスライドが60ページくらいあったのでもしかしたら今日だけで終わらないのではと疑っていたが、蓋を開けてみれば1時間も使わずに終わってしまった。必要なことが全部スライドに準備されており、もたつく様子がなかったのがすごい。

最後に付け足された発展的な内容、グラフの種数を用いたオイラーの多面体定理の一般化は非常に難しく、当人の説明の後先生に言われて自分なりに補足してみたりしたがそれでもあまり伝わった気がしなかった。どんな事実を認めてほしいか明確化するべきだったかもしれない。あとは具体例か。しかしトーラスの上に交差のないよう描かれた種数1のグラフを即座に作れるわけもなく。今考えてみれば、平面的でない簡単なグラフを適当にもってこればよかった。

余った時間で二人目。話し始めは少しまごついていた様子だったものの、一度軌道に乗った後はずっとスムーズに進められていて良かった。昨日自分が作ったGIF画像による図については、発表者の方でも何か用意してみてほしいとアドバイスをしていたが、さすがに昨日の今日では用意できていないだろうなと思っていたら、なんとすでに完成していた。GeoGebraによるもので、GIF画像に比べて手で動かせる点が優れている。

講義後しばらく、質問に来た学生と先生と話して終了。食事して午後7時過ぎに帰宅した。

しばらくYouTubeを見ていた。「総理大臣によるサーモンラン」という動画シリーズで、どういう技術が使われているかは知らないが岸田総理大臣っぽい声のスプラトゥーン実況。非常に面白い。基本的には実況らしい簡潔で的確な発言ばかりで構成されつつも、要所要所に政治家一流の迂遠な言い回しを用いているバランスがいい。時たま政治答弁みたいなゲームとほぼ関係ない話をペラペラ喋るのも面白かった。

そもそもスプラトゥーンというゲーム自体が面白いのかもしれない。初めて見るのに何となくルールが把握できるのはすごい。たまにTLで目にする「シャケ」とか「サーモン」が一体何なのか知れたのはよかった。その敵キャラを含め、命名が特徴的なのもいい感じ。

www.youtube.com

午後9時前に布団に入って就寝。起きたら午前2時半だった。ECRがあるのを完全に忘れており、目覚ましをかけてすらいなかった。マラソン以外皆勤の状態を4か月ほど維持していたのが途切れてしまい残念でならない。

意気消沈しつつもぞもぞ起きだして日記を書いていた。午前9時になって切り上げ、布団に入ってラノベを読み始める。眠れずそのまま読み続け1冊読了。

「転生魔王の大誤算」5巻。前の巻を読んでから結構間が開いたのでいろいろ忘れていることも多かったが、そもそも発売自体が遅かったためか要所要所には設定の大まかな説明があって、問題なく読み進めることができた。内容については4巻が非常に面白かったので期待していたものの、盛り上がりが物足りず残念。主人公の強みと敵の相性が悪くあまり活躍しているように感じられなかった。この敵は今後も登場するようなので、その顔出しという側面があったのかもしれない。

午後2時から1on1。水曜日にドサッと実装したので、それをお見せして判断を仰ぎたいと思いセッティングした。うっかり睡眠に失敗してしまいちょっと眠気が強い状態での会議になってしまったが、必要なところは聞けたし決められたのではないだろうか。水曜日に実装しながらメモを残していたため、うまく回らない頭でも議題を出せたのがよかった。気になっていた点のうちいくつかは、とりあえず動くものができてから考えるべきとの判断が下され、確かに……という気持ちに。ひとまず今あるコードを愚直に書き直していきたい。

しばらくコードゴルフして午後6時就寝。

10/21(金)

午前0時半起床。サークルのバチャとyukicoderをスキップしたのは、今度こそ自分の意志である。

寝る前に縮めたコードがさらに縮められていて、そこで新手が出ていた。AWK\max(\ast,0)を行う際は、先頭に文字列0を連結した後数値として解釈すればよいらしい。値が非負なら負号がないため全体が十進数として解釈されるが、負号がある場合はその直前で数値としての解釈が終了するため、0となる。

atcoder.jp

Perlにおける特殊変数$-に代入する行為も同じく\max(\ast,0)、正確に言えば\max(\lfloor\ast\rfloor,0)という効果を持つが、それを利用した最短コードが大量にあることからもうかがえるように、これは非常に影響範囲の大きな更新である。というのも、これを利用することで一般に\max(a,b)=a+\max(b-a,0)\min(a,b)=a-\max(a-b,0)と書けるからである。これまではa<b&&a=bとしていたところがa+=0b-aと書けるだけでも-1Bである上、bを変数に持つ必要がなくなればさらに縮む。

朝まで数時間最短コードのリストを探し続け、20個弱縮めた。中には8Bも縮んだものも。

atcoder.jp

午前8時から2時間ほど日記を書き、布団へ。横になって教科書を読むつもりが、少し目を瞑って考えているうちに寝落ちしたらしい。午前11時半に一瞬起きて、このタイミングで就寝報告のツイートをした。

10/22(土)

午後4時過ぎに冷凍弁当を受け取った。この前後合わせて1時間くらいは起きていた記憶がある。その後また二度寝した。

午後8時起床。しばらくコードゴルフして、午後9時からABC274に参加した。

キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274) - AtCoder

Aはまず\lfloor 10000B/A\rfloorを計算して出力する方法で解いた後、しばらくコードゴルフした。dcの出力を加工する方針には早々に見切りをつけて、printfとフォーマット文字列"%.3f"を使うのをいろいろな言語で試していたが、その方針なら当然ながらAWKが最短となる。これに気づくまで10分くらいかかった。

Bはよい。Cは入力の意味が少しややこしくて、題意も含めての把握に時間がかかった。Dは偶奇で分けると1次元の問題になり、さらにA_1以外は符号を好き勝手に決めてよい。復元が必要ないのがありがたかった。Eは巡回セールスマン問題をちょっと変えるだけ。

Fはxがちょうど魚iの位置であるとしてよい。このiを全探索し、すべての魚の位置を魚iに対する相対座標で表しなおすとかなり見通しが良くなった。各魚について、それが区間[0,A]にいるようなt全体の集合は、\emptyset\mathbb{R}_{\ge 0}または両端が有理数区間になるので、三つ目をイベントソートする。

Gはちょっと面白かった。まず監視カメラは障害物またはグリッドの端を背にしてしか置かない。さらに下向きに置いたカメラとそれが監視する最も遠いマスに上向きに置いたカメラは同一視できる。左右も同様。こうやって定めた置くべきカメラの候補について、それを置かなくてよいケースというのは、担当するすべてのマスを直交する向きのカメラで監視できている場合のみである。

ところがこうやってカメラだけに注目した言い換えをすると辛い。互いに干渉するカメラ間に辺を張ったグラフは二部グラフだし、いかにもフローで解きそうな見た目をしているのに、うまく流量や頂点の意味を設定できなかった。貪欲を考えてもすぐ反例が見つかる。しかし、この反例の図を描いているうちに「最小点カバー」という直観が得られた。

コンテスト中はこの段階で深く考えずに実装してしまったが、マスに注目して条件を観察すれば正当性もすぐわかる。各マスについてそれを監視できるカメラはちょうど二つしかなく、どちらかを設置しなければならない。つまり、その二つを結ぶ辺があって、選んだカメラ=頂点のどれかに接続している状態。これより選んだ頂点は点カバーとなっている。

二部グラフなので最小点カバーのサイズと最大マッチングのサイズは一致する。この事実を使った記憶が以前になく、その点に面白さを感じた。

Exは解けず。ローリングハッシュも値に乱数を割り当てたZobrist HashもXORで壊れてしまう。特に後者が壊れることについては実装が終わってから気づいたため、絶望してしまった。7完20位。Gは最初にマスに注目していれば燃やす埋めるがすぐ思いつけたかもしれない。

コードゴルフ。AはAWK解を提出するまでに10分経過していたため速度差で負けたかと思ったが、最短が取れていた。BはRakuで、各マスを0と1に変換した後列ごとの和を取る方針。2次元のリストの要素を変換するに当たってはメタ演算子Xが使えず、ネストしたリストにも再帰的に適用されるハイパー演算子>>を使う必要があった。Cは今の最短コードを縮められず。以降は手付かず。

しばらく無為にTLを眺めた後、午前2時から日記を書き始めた。午前6時就寝。

10/23(日)

午前10時半起床。

二度寝するつもりだったのにグラフのcutの定義を間違えていたことに気づき眠れなくなった。ちまちま教科書を読んでいたのがやり直しに。教科書の定義はWikipediaでいうcut-setであり、自分は単に取り除くとグラフが非連結になる辺集合だと思っていた。

Cut (graph theory) - Wikipedia

1時間くらい身悶えしたあと布団から脱出。準備して牛越橋に向かった。今日はそこの下の河川敷で競プロサークルの芋煮会を行う。昼過ぎから雨が降りそうなので徒歩。

到着すると、とりあえず火だけ起こされていて、近くに住んでいる人の部屋で具材が準備されるのを待つ時間だった。適当にうろうろしていたら雨が降り出したため、橋の真下に移動。改めて火が用意され、周囲に石を積んでかまどを作りながらさらに待機した。

具材と水が入った鍋が到着し、かまどが不安定なことが発覚。金網も購入されていたものの、その上に乗せても撓んで不穏なだけなので、直火で温めることになった。鍋は二つあったので、火を分割し、それぞれの周りに改めて石を組む。鍋が乗せられるよう思ったより小ぢんまりと作られた。この辺り自分はほぼ見ているだけだった。

鍋を温めている間にかかった費用の清算。大体1万円程度と聞いていたため、先輩風を吹かせ全額出すつもりで用意してきた。金は出すから準備は任せた!という気持ちでいたが、結局その場にいたもう二人のM1、ホスフィンとha15さんとの三分割になったし、その二人は結構準備や持ち込みをしていたため、自分だけ貢献度の低い人間に成り下がってしまった。

このころが一番雨が酷かったはず。橋の下にいるので大丈夫かと思ったら、上に排水口の出口があって大変だった。鍋を温めている位置が真下から少しずれただけの位置で、風の具合によっては見事吹き込んできたため、蓋を開けるときは傘でカバーしながら耐えていた。

煮えたら味を調え、完成。食後は焼きマシュマロをしたり、金網でソーセージや餅が焼かれたりして、お腹一杯になった。うっかりワインも飲んでしまった。

片付けが済んだらすぐ帰るつもりだったが、具材を用意していた部屋に数人集まるらしく、自分も転がり込んでよいようなので、そこからCFに参加することにした。ノートPCは一応持ってきてある。充電も満タンなので、2連戦には十分耐えられるだろう。

午後4時50分からCF #829 div.1。

Dashboard - Codeforces Round #829 (Div. 1) - Codeforces

A1はnが奇数なら明らかに不可能で、実は偶数の場合必ず可能。二つずつ見ると、[a_i],[a_{i+1}]とすればa_i+a_{i+1}[a_i,a_{i+1}]とすればa_i-a_{i+1}が達成できて、どちらかは0になる。それを集めてくればよい。A2も間の0を適切に扱うことで同様のことができる。

A1からA2に書き換える際、一か所そのままにしていて1WA。今思えばこの時点ですでにアルコールを摂取したことによる判断力の低下がみられる。

Bはa!a+1個集めて(a+1)!にするのを繰り返せばよい。配列で個数を数えながら計算する。これは簡単。

Cに1時間半かかって何もかもが崩壊した。初手がわからなかったため、手計算でサンプル三つ目のケースを求めようとしたのが間違いだったのか。そもそもこの計算すら失敗しまくって大変だった。最終的に正しい値が得られ、その途中計算をもとに実験エスパー+OEISで解いた。

それぞれの0に対しその前にある1の個数を数えた列を考え、これで状態を表す。サンプル三つ目のケースを解くためにはいくつかの状態に対して答えを求める必要があったが、それらはすべて15または75/4になった。いかにも何かありそうだ。期待値のループを解消したときに出てくる\binom{n}{2}を無視すると、値はnに影響されないようなので、そこだけ観察することにした。

Ruby有理数を使っていろいろ試してみると、15/449/36205/1445269/3600が登場した。まず分母が順にk!^2となっていそう。その時の分子の列は1,5,49,820,21076で、祈るように調べてみるとOEISに載っていた。まとめると、この数列は\sum_{i=1}^k 1/i^2らしい。

A001819 - OEIS

どういう基準でkが定まるのかはエスパー。作った列のうちkより大きな値がk個以下しかない、という条件を満たす最小のkが求めるものらしい。どういう計算になっているのか全く分からないまま実装し、AC。

残り10分ちょっとしかない。Dに進んだ。一応Cで詰まっている間に問題だけは読んでいて、空きマスの移動をグラフと見てdijkstraすればよさそうだとわかっていたものの、ダメなケースがありそうに見えてちょっとまごついていた。まあこの時間がなくても実装は間に合わなかっただろう。そのままコンテスト終了。

489位で2825→2668(-157)。ここ2回で300近くレートを落としている。2600台にまで落ちたのは去年の3月以来のこと。

次のCFまでの時間で少し感想戦を行った。Cは今ある値とソート後そこにあるべき値が異なる位置同士のswap以外無意味らしい。ソートを0だけ先頭に集めると読み替えて、0があるべき位置にある1の個数を減らしていくと見なせば自然だろうか。最初に転倒数を考えたので、そこで01列の転倒数をインデックスの差で計算する方法が思い浮かべば、もしかしたら至れた発想かもしれない。自分は期待値の線形性を利用できないか探るほうに進んでしまった。

素面だったとしても解けたか怪しい気がする。ただ、金輪際ratedの前に飲酒はしないだろう。

帰る人を見送り、15分後からCF #830 div.2。

Dashboard - Codeforces Round #830 (Div. 2) - Codeforces

Aからちょっと難しい。i=n-1,nで操作すれば条件を満たせるので、答えは3以下となる。あとは場合分け。Bは01列をソートする問題ということで、先ほどのC問題のトラウマが蘇ってきて苦しかった。連続する同じ文字を圧縮した列で実験して解いた。

Cは難しい。まず、区間を狭めてもXORの減少分が和の減少分を超えることはないため、最大値はf(L,R)となる。あとは区間の幅をどこまで狭められるか。狭めた区間でのfの値がf(L,R)と等しくなるためには、和の減少分がそっくりそのままXORの減少分に一致しなければならない。

とりあえずa_i\gt 0として考えると、区間の幅を狭めるごとにXORの立っているbitが狭義単調に減っていくと言えて、制約のもと幅30も縮めればXORが0になってもう狭められなくなる。よって全探索可能。a_i=0をあらかじめ削除しておけば元の問題でも同様に計算できる。

Dは計算量が謎。深く考えずに出したら通った。どちらもオフラインで解いた。D1はxに対してそれが挿入されたクエリ番号を覚えておき、同じkのクエリをまとめて倍数を調べつつ、クエリ番号を比較して早いクエリからどんどん答えを確定させていった。D2はkをまとめるときにクエリ番号をsetで持ち、倍数を調べるたびそれが集合に入っていない時間帯のクエリを削除するのが高速に行えるようにした。

Eは解けず。遅延セグメント木で、更新を区間の幅に応じて二通りの方法で行った。狭い区間の場合は単に全探索。広い区間の場合はxの約数を全探索し、それが\gcd(x,b)となるbの最小値を探す。後者についてはbの検索部分を前計算できる。ところが全く間に合わなかった。6完12位。

2連戦を終えて残っていたとりゐさんと感想戦。Dは最悪ケースの想像がつかないので計算量がよくわからなかったのだが、やはり小さいほうに詰まっているのが大変そうという結論になった。つまりいつもの調和級数

そろそろ帰るが、その前に部屋をちょっとうろうろさせてもらった。夕方この部屋にお邪魔したときからめちゃくちゃ広いなと思っており、興味に勝てなかった。ハリー・ポッターの本を見つけたので、自分は積んでいるのに「ハリー・ポッターと呪いの子」の話を振ってみたりした。

午後10時くらいにお暇し、コンビニに寄って解散。帰宅後疲れ切ってYouTubeを見ているうちに寝落ちしそうになったため、布団に滑り込んだ。午後11時半就寝。

午前3時に一度起きた。焚き火の煙で燻された服のまま寝てしまったため、布団にちょっと臭いが移ってしまった。とりあえずシャワーを浴びた。

TCB52が終了していた。今回は理論値達成者が多くいたが、そこでは2位に10分以上速度差を付け、全完者の中でも最速の圧倒的勝利。これで3連覇、しかもすべて理論値での優勝となった。最高の気分。

7問目は区間の幅が2以上の場合、LCPがすべて同じ文字になるらしい。気づいてみれば当たり前で、ある文字列とその先頭を削除した文字列の前からいくらかが等しい場合、その部分の文字が全部一致していなければならない。SAなど持ち出さなくても解けたようだ。

upsolve二つ。まず今日のdiv.1-D、やはりdijkstraで解けた。解説を見て正当性を理解。同じsunbetを2回動かしてしまったり、逆に2回動かさなければならなかったりする場合どうするか気になっていたが、そのようなケースはないらしい。2回目に動かそうとした時点でそこに十分なスペースができていることが、手で試せばわかる。

Submission #177691400 - Codeforces

次に今日のdiv.2-E。コンテスト中に試した2種類の更新を使って平方分割したら通った。バケットサイズガチャで4敗。バケットの中で一要素ずつ更新するには\gcdを計算する必要があるので、サイズは小さめがよいかと思ったが、一つのバケットに対して計算するのにもxの約数の個数だけ時間がかかるため難しい。というかなぜ通っているのかわからなくなってしまった。正しくは、各バケットとあり得るすべてのxに対して答えを前計算できるらしい。

Submission #177695805 - Codeforces

午前6時から4時間ほど日記を書いて就寝。