02/01(月)

日曜日は週記を投稿してから比較的すぐ、午前6時半くらいに寝た。Chromeの履歴によれば、3時間後と5時間半後にそれぞれ少しずつ起きていたらしい。特に2度目の覚醒時、ICPCアジア地区横浜大会の暫定競技ルールが公開されたのを見つけ、少し確認していた。

2020 Regional Special Rule 暫定版 | ICPC 2020 Asia Yokohama Regional

実際に起床のツイートをしたのは午後4時前であった。夢を見た。前半部分はかなり喪われ気味であったが、数学的な用語が夢に登場するのはそこそこ面白く感じられたので、適当に復元してツイートした。

夢：友人と呑んだ。僕は帰ろうとしたが、友人はタクシーの運転手と一緒に別の呑み屋に入っていった。タクシーの運転手がこれに付き合うのはサービスの一環だろうと考え、では、いったいいくらのサービスなのか？40000円であるとの直観を得たが、示せない。友人達が入っていった呑み屋には、
— こたつがめ (@kotatsugame_t) 2021年2月1日

最近Chromeのタイムゾーン設定がバグっていてUTC -9らしい。この影響でせっかく埋めたAtCoder ProblemsのHeatmapが穴だらけになっていた。諸行無常を体現している。

yukicoderのほうでゴルフが盛んに行われているようだったので、粗探しをしていた。自分の手元のRakuはいまだに2016年1月版（これはAtCoderの言語アップデート以前の処理系に合わせていた）で、現在の環境に合わせてゴルフするのには向かない。いったん削除し、改めて入れなおすことにした。前回はインストーラ経由で入れたようだったが、今回はファイルを展開したらそのまま使えるようになっていた。Program Files下に移動させておく。cygwinからexeファイルへのフルパスを叩きつつ、やはりファイル名に空白が入っているのは正気の沙汰ではないという気持ちになった。

昨日上げたゆっくり実況について、ゆっくりの喋る速度がもっと速いとうれしい、という意見が来ていた。これについては僕も薄々感じていたこと、オタク早口は伊達ではない。今度動画を作る際には少し弄っておくことにした。

yukicoderでのゴルフに熱中していたところ、サークルの解説会の開始時刻である午後8時になっているのに気づかなかった。いつも僕がGoogle Meetで会議を立ててURLを共有しているのだが、今日は僕が15分経っても応答しなかったので、急遽ホスフィンが代わりに立ててくれた。気づいたのは午後8時20分で、慌てて参加した。1問ぶん聞き逃した。他にも、今週は僕が発表していないのだが、サークルメンバーが増えたと見るや否や解説役をサボっていると解釈され得るので気が気でない。決してそういうわけではなくて、僕もF問題の解説をしてやろうという気持ちはあったが、単純に何もかもを忘れてしまった。準備も始めてすらいなかった。

4年次ゼミの割り振りについて、現在僕が第一希望にしているゼミは定員より多い人数が希望しているため、何人かを第二希望以降に回す必要がある。

来年のゼミの希望を出すために教科書を眺める。最初は公理的集合論がよさそうだと考えていたが、整数論の教科書にメビウスの反転公式とかが書かれているのを発見して一気に興味を惹かれる。これを第一希望にすることにしよう。
週記（2021/01/11-2021/01/17） - kotatsugameの日記

その関係で簡単なアンケートが来ていた。ゼミで読みたい本の希望と、自分の将来のイメージと、現在の総取得単位数・残っている必修単位数。読みたい本の希望はいいが、自分の将来のイメージとはなんだ。この年になって夢を語るというのか。いくつになっても夢がある人間は強いですよ、といった意識高い系の話かもしれない。また3つ目の単位数に関する話も僕にとっての鬼門で、カウントする作業はいつやっても面倒で気が滅入る。

EMLauncherを解いた。黄diffは残り1問である。そこそこ時間をかけてコーディングしたところ、1発ACした。やはりすべて整数の範囲で計算したのがよかったのだろう。やること自体は明らかで、偏角ソートをある半直線を基準にして行うのがつらかった。書いているうちに微妙に怪しいところを見つけたので、このコードは最初のACのものではないが、実装方針は変わっていない。詳細を記しておこう。

atcoder.jp

ある点pを選ぶ。まずこの点に向けてビームを打ち、残りの線分は偏角ソートすれば区間スケジューリングの要領で計算できる。つまり、原点から点pへ伸ばした半直線と線分の交差判定、交差しない線分の（片方の）端点による偏角ソートができればよい。点qと点rを結ぶ線分を考える。前計算として、外積cross(q,r)が非負となるようにswapしておく。制約から線分は原点を含まないので、いい感じになる。偏角ソートには点rを使用することになる。

X=cross(p,q)、Y=cross(p,r)と置こう。X=Y=0の場合を先に処理する。このとき点pと点qの内積の正負で判別でき、負のとき半直線と交差しないので、線分を集合Rに追加する。

それ以外ならば、X<=0<=Yのとき、線分は半直線と交差する。このとき原点から見ると点q、点p、点rの順に並んでいて、しかも点qと点rの間の角度は180度未満（線分は原点を含まない）だとわかるからである。交差しないような線分に対しては、Y>0のとき集合Lに、Y<=0のとき集合Rに追加しておく。

集合Lと集合Rをそれぞれソートする。各線分に対してcross(p,r)の符号で分けているので、各集合内では単に外積の正負で順番を決定できる。集合Lの要素は集合Rの要素よりも先に位置するため、そのように連結すれば偏角ソートができたことになる。区間スケジューリングにおいてもまた半直線と線分の交差判定が必要になるが、同様にできる。

この問題の制約ならatan2を使用してもソートできるらしい。誤差の評価についてはmaspyさんが教えてくださった。

座標の最大値を X として、格子点 3 つの作る 0 でない角度 θ は、面積から X^2sin θ >= O(1) を満たします。
よって θ >= O(1/X^2) なので、eps を 1/X^2 より十分小さくとれば、登場する角度は区別されます。

X = 10^9 だとウンチの始まりです。
— maspy (@maspy_stars) 2021年2月1日

最後の黄diffである天下一最短路コンテストを考えていたが、解けない。午前2時半ごろに布団に倒れこんだところ、即座に寝落ちした。

02/02(火)

午前9時前に目を覚ました。ゴミをまとめて出す。久しぶりにポストを確認すると電気代のハガキが入っていた。先月は8000円弱だったらしい。エアコンをガンガン稼働させながら寝落ちしていたのが効いているのだろう。

mod上の逆元リストを必要に応じて生成する方法についての議論があった。前から作成する方法は、オーダーだけ見ればO(N)だが、実際は変数による除算や連続的でない配列アクセスなどがある。その点、後ろまで作ってから1回だけ逆元を計算する方法は、O(N+log mod)と変なのがついていても、定数による除算しか行わなかったりシーケンシャルアクセスが保たれたりと良いこと尽くめ。必要に応じて生成する場合も、倍々に増やしていくことで対応できる。これに関しては、呼び出しごとにif文による分岐が入るのが気になっていたが、分岐予測がかなり効くだろう、という話を聞いた。

形式的冪級数の逆元を初めて知った。うまく定義されるんだなあ。

paper.dropbox.com

朝の時点では計算方法に関してあまり考えていなかったが、冷静になるとO(N^2)かかるように見える。いくらか調べたところ、これもうまいこと計算できることを知った。

qiita.com

布団に転がって「東方遺骸王」を読み返していたところ、耐え難い眠気に襲われたので昼寝。閲覧履歴によれば午後3時半ごろから午後8時半ごろまで寝ていたようだ。

午後9時からサークルのバチャ。CF 698だったが、これはつい最近行われたコンテストで、C問題の解法をTLで見て覚えていた。最遠点を取り続ける解法。A問題はかなり詰まってしまったが、何とか1点を固定して差をとってgcdを見ればよいことが分かった。B問題は後ろから見ることに気づけば一瞬だった。Dを読んでいたが全然わからなかったので、終了までハーメルンに逃げていた。

東方の二次創作をいくらか読んで東方に関する知識を増やした後、再度「東方遺骸王」を読み返すと、話のいたるところに東方の影が見え隠れしていたことに気づいた。アハ体験みたいで面白い。「東方遺骸王」は東方の二次創作という形式ではあるものの、普通に読んでも非常に面白いと思っている。かなり長いので気軽なお勧めはしにくい。

syosetu.org

そのまま午前3時ごろまで読み続け、そのあと起きてシャワーを浴びて日記を書いた。溜めていた月曜日の分も含めて書き終わったら午前6時だった。布団に入り、また読み返し続ける。午前9時前に就寝。

どこかの時間で日曜日に出した動画を再度見返していたのだが、BGMの音量を絞りすぎたことに気づいた。これまでは元ファイルの25%設定で、今回はちょっと大きいかなと感じて15%にしたのだが、変えなくてよかったらしい。

02/03(水)

午後2時半、目を覚ます。布団に転がってハーメルンを読んでいた。寝足りない気がしたのでなんとなく寝ようとしてみたところ、午後4時半くらいに再度就寝。次に、午後6時半に起床した。このタイミングで起床報告のツイートを行った。

さらに1時間程度ハーメルンを読んだ後、布団を脱出して食事し、パソコンの前に座る。今日もサークルのバチャがある。始まるまで少し時間が空いたので、ようやく残っていたレポートに手を出すことにする。とりあえず講義資料を見なければ話にならない、ということで見ようとしたら、文章ではなく動画だった。非常につらい。

少し視聴して、途中で出されていた問題を1つ解いたらバチャの時間になった。今日はCF 604。ABCd（D1のこと）の4完だった。なかなか良い成績であったようだ。

A問題はよい。B問題はサンプル1みたいな構築しかしなくてよいものと決めつけてみたら通った。冷静になると証明もできる。0があったときに、離して置く必要性は薄い。実装方針もかなり当たり気味。C問題はつい最近のABCで見たような、スタートに戻る期待値DP。ちゃんと文字で置いて計算してみるとかなりきれいな形の式になった。分母は積で、分子は一次関数の合成になる。どちらもDisjoint Sparse Tableで持てるが、結局チェックポイントを持つのにsetを使うので、logは落ちない。

D1問題は、マッチを左右から貪欲にすることにすれば、あとはマッチしうるペアを全て試し、寄与を足し合わせればよい。ペアを試すのにO(N^2)、また寄与は二項係数の積の和になるのでさらにO(N)かかる、が、よく見ると定数倍がかなり軽そうに見える。実際Rubyで最悪ケースだと思わしきものの計算回数を求めてみると、6e8くらいになった。剰余などもあるので安心はできないが、とりあえず定数倍に気を使って書き、最悪ケースを試してみたところ、1secかからなかったので提出。サーバでも1secで通った。ここからD2につなげるとっかかりは見えず、またE問題も多く通されていたが、わからずじまいだった。

また講義動画に戻る。1回ぶんの動画時間が70分とか80分とかあってかなりつらい。飛ばし飛ばし見る。途中でレポート問題が挟み込まれるが、見落とさないか心配でたまらない。第4回まで視聴し、ふと期末レポートの問題を確認したところ、どうにも最低限の問題は既に解けそうであることに気づく。まだ少しは先に進む必要があるだろうが、全15回を全て見る必要はなさそうだ。これは朗報である。

ただ、途中に挟み込まれるレポート問題も評価に入るのだから、時間の許す限りは見ておかなければならないだろう気もする。期末レポートを出さなければお話にならないが、では期末レポートを出したとき、他のレポートはどれくらいやっておかなければならないのか？評価はこの際Cでも構わないので、最低限のラインを狙っていきたい。

金曜日の午後11時が締め切りである。まだ多少の余裕があるように見えるので、午前5時くらいに眠くなったのを受け、素直に寝ることにする。寝ている間に理解が進んだりしないかなと思うものの、成功した試しはない。それはそうで、数日漬けで何とかしようとしている内容は夢の中で考えられるほど定着していない。

布団に入ってから1時間程度ハーメルンを読み、午前6時就寝。

02/04(木)

正午、目を覚ます。二度寝しようかとも考えたが、レポートによる焦りもあってそのまま起きることにした。

今セメスターの講義の評価がいくつか出ていた。

自分のこれまでに得た単位と4年生になるための単位を比較して、今セメスター何が必要かをリストアップしてみた。
週記（2021/01/25-2021/01/31） - kotatsugameの日記

今セメスター
・線形代数学B
が浮いて
・幾何学序論A
・代数学概論A
の片方が浮いて
・代数学概論C
・幾何学概論B
の片方が浮けば、4年生です
— こたつがめ (@kotatsugame_t) 2021年1月29日

現在、幾何学序論Aと代数学概論Cの単位が来ている。先週のツイートと照らし合わせて、残り線形代数学Bの単位が来れば4年生になれるようだ。今見返したところ、代数学概論Cと幾何学概論Bのどちらか片方が必要と言ったのは間違いで、実は両方落としても4年生にはなれるようであった。この2つは選択必修の科目で、現時点では位相数学Bという講義の単位を同じ選択必修として持っているが、4年生になるにはこの1講義で十分らしい。卒業するためには2講義ぶん必要で、これが「どちらか片方が必要」の正体である。

また、今絶賛レポート取り組み中の幾何学概論Bには演習が存在するが、課題の締め切りはとうに過ぎ去っていたようだ。結局何一つ提出しないまま終わってしまい、評価はDではなくN/A（？）だった。

期限が書いてなかったからずっと遅延評価してたら、一度も提出せずに評価がついて、Dですらなかった pic.twitter.com/acsMxDKcTm
— こたつがめ (@kotatsugame_t) 2021年2月4日

昨日の続きで、また講義動画を視聴する。夕方、第7回くらいまで見終わったところで、昨日言及した期末レポートの最低限の問題全てに答えられる状態になったことを確信する。講義動画の途中に挟まれるレポートについては、見終わったと言った動画であっても計算の重そうなものは飛ばしてしまっているが、とりあえずこれからは期末レポートを完成させることを第一目標にして動こう。

最低限の問題というのは4問あり、うち2問は語句の定義に関してまとめよというものだ。証明や計算ですらない。まずこれについて書く。推敲が必要に思えるため、TeXで書くことにしよう。結構頑張って講義動画を解釈し、自分なりに納得を得た上で、定義に必要な準備から書いていったのだが、見返してみると結局講義で示された式を丸写ししているのと変わらない内容になってしまった。これはどうしようもなくて、わざわざ講義で使っている文字から変える必要もないため、本当にそのままの式になっている。

途中嫌になって本を読んだりしていたものの、なんとか2問書ききる。もう2問あり、片方は頑張って計算するもの。もう片方は証明だが、これは実は講義でやった。後者にまず取り掛かる。と言っても本当に同じことを講義でやっているので、これも丸写しと変わらない内容になってしまう。一応証明の方針だけ見て埋められそうな行間は自力で埋めてみた。講義で行った証明のほうが簡潔だったので何が違うのだろうかと考えていたが、講義では集合の等号を示そうとして片方の包含しか示していないように見える。

最後の計算が残って非常につらい気持ちになるが、実は期限まではあと1日ある。生活リズムも良くて、起きたら提出期限ギリギリだった、とかいうことにはならなさそうなので、これは明日に回してもよいだろう。Google Classroomをいろいろ見ていると、最初にこの講義についての説明があることに気づいた。PDFを読むと、レポートの提出形式についても書いてあって、「A4サイズの紙に解答を書き、スキャンしてPDFファイルにして提出する」とあった。まずい。TeXで書いたのを紙に写す作業が待っているのか……。

諦めきれず、今度は説明の動画で該当する箇所を視聴する。聞いている限りでは、PDFファイルを提出することが重要であるらしく、それ以外の要素についてはあまり触れていない。多少希望が出てきたので、いっそのこと直接確認することにして、教員に質問を送っておいた。

布団に入ってハーメルンを開いたところ、「このすば*Elona」が更新されていた。今話はかなり長めで、展開が非常に良い。主人公の見せ場直前、周囲のキャラクター視点の語りが続いて気持ちを昂らせ、そこで次の話に続く！とはならず本題の見せ場まで描かれている。満足。

午前4時就寝。

02/05(金)

午後1時半起床。学食に行く。

食事 pic.twitter.com/AE6X1MG55p
— こたつがめ (@kotatsugame_t) 2021年2月5日

開いていなかった。写真をよく見ると短縮営業している店舗もあることがわかるが、この時間はすでに閉まっていた。仕方ないので購買に行くも、パンが全滅していた。どうしようもないためお菓子を買って当座をしのぐ。その後生協に入っている床屋に行った。

帰宅して、コンビニで購入したパンを食べ、レポートを進める。期末レポートの最後の1問。

ある単体的複体のホモロジーを具体的に求めよというもので、講義では次元が1以下の単体のみを含むものについて計算していたので、同じ感じでやろうとする。ところが、今考えている多面体は次元が2の単体を含むので、ちょっとまずそう。H_1を求めるときに、境界準同型のKerもImも簡単な形にはならない。とはいえ、何らかの定理を適用するのもよくわからないので、とりあえず式で書いてみることにした。するとものの見事に係数が一致して、H_1が0の一点集合であることが明らかになった。かなりびっくり。

期末レポートはこれで完成である。手書きでなければならないかを問うコメントへの返事がまだ来ていないが、今更紙に書き写すのも面倒でしょうがないので、とりあえずこのまま出しておくことにする。期限までに返信が来てダメだと言われたら、またそのとき考えよう。

ラスボスを倒してしまったので気が抜けるが、まだいくらか時間はあるので、講義動画を見つつ途中のレポートを解く作業に移る。しかし、第8回を見て1問解き、また以前の講義に戻って飛ばした問題を1問解いたところで完全に気力が尽きる。第8回までで残っているものは1つだけ、また残りの講義は5回ぶんしかないので、（1回の講義でレポートが複数出る可能性はあるものの）多分全体の半分は解いただろう。提出作業に移る。せっかく問題ごとに分けてスキャンしたのだが、提出するときは1つのファイルにまとめなければならなかったようで、PDF結合のWebサイトを探してきてくっつける。ちなみに昨日の日記には「A4サイズの紙に」と書いたが、正確には「A4サイズのレポート用紙または電子ノート」とある。翻って自分はコピー用紙にレポートを書いてしまっている。まあ罫線の有無で採点をしてくれないほど心の狭い教員ではないだろう、ということでこれもそのまま提出。

以上でこの講義の課題についてはすべて終わったものとする。これにて春休みである！

評価がN/Aになってしまった演習が気になってClassroomを調べたところ、一番最初に授業についての説明PDFがあって、課題の提出期限も書いてあった。実は1/14が締め切りだったようで、何もかも間に合っていない。

あ！ヤッベ pic.twitter.com/WvFCQzVZa3
— こたつがめ (@kotatsugame_t) 2021年2月5日

途中でサークルに届いていた入部メールに気付いて返答した。9日間放置していたらしく、非常に申し訳ない気分になる。しかもそろそろ春休み期間で活動がお休みになるため、その前の数少ない活動に参加させてあげられなかったということでさらにつらい。

yukicoderに出る。7完。かなり面白いセットだった。

Aはよい。Bは前のほうから到達可能にしていきたい。Cはよくわからないが、aとbの符号を決めて貪欲に取ったら通った。解説が非常に賢い。Dは左と右から累積maxみたいな感じでやる。耳DPするというのを見た。Eは難しいが、実験すると適当に0で埋めて残りを110100の繰り返しにすると結構できることがわかる。

Fは非常に面白い。まずiとN+iがペアになることが分かって、そのペアの間でどのような操作に対しどのような結果になるかを観察すると、いい感じにできる。2回やると大体もとに戻るのが面白かった、が、これはペアに関する遷移で見ていたから非自明に感じられるのであって、元のxorで考えれば明らかかもしれない。GはDP。

直後のCF 699 div.2にも出た。5完トップで5位。Eで2WA吐いてかなり厳しい気分になっていたが、A-Dが爆速だったらしい。

Aはよい。Bはk<=1e9を見て考察を始めてしまった。頑張ればいろいろ1e9オーダーで解けそうだったが、冷静になって制約を見るとシミュレーションすれば解ける。Cは後ろから見る。面倒。Dはギャグ。Eは区間maxのセグ木……と思ったらWA。後ろのほうの塊をそのまま残すケースをうまく計算できていなくて、直すのにもミスして結局2WA。Fは少し考えたが嫌になって止めてしまった。

「あくまでも探偵は」という本を読んだ。良かった。キャラクターが良い。ミステリとして見るには、どうだろう。探偵役が秘密主義すぎて、いろいろ唐突に感じられてしまう。この本に限った話ではないが、連作短編をいくつか集めて大きなストーリーを1つ作るような本の構成だと、扱う事件の全てで黒幕が共通していて、ちょっと気になる。

部屋が非常に寒い。エアコンは23℃設定でガンガン利かせているつもりだが、エアコンと僕がちょうど部屋の対角線の両端に位置するような位置関係のため、温かさが伝わってこない。何か電気ヒーターみたいなものを購入して近くに置いておくのがよいかもしれない。

食事して日記を書こうとしたら、Twitterの貼り付けが一時うまくいかなくなっていた。今日の冒頭の部分を書いているときにはその状態で、書き進めて今この文章をタイプしている時にはすでに直っている。今日はTwitterのリンクを2つ挿入したが、再度貼りなおしておいた。

月曜日からバグり続けているChromeのタイムゾーンを直す。ちょっと調べたところ、Windowsのタイムゾーンを一度切り替えてもとに戻すとよいらしい。念のためすべてのタブを閉じてやってみたところ、無事直った。たったこれだけの手間を惜しんで、1週間ずっと頭の中でUTC -9からUTC +9に変換し続けていたのかと思うと、やるせない気分になる。

午前5時就寝。

02/06(土)

正午、起床。布団でゴロゴロしていたが眠れないので午後3時に起床報告のツイートをした。ハーメルンを1作読んだ。

syosetu.org

文章がカスだし未完。おススメはしない。以前からめちゃめちゃ長生きの主人公が好きだという話をしていたが、これの作者も同じ嗜好らしく、主人公が事あるごとに年齢マウントを取ってくる。

月曜日の続きで天下一最短路コンテストに取り組む。数日空いたが、その間たまに考えを巡らしたりしていた。考えていたのは次のような方針だ。

https://t.co/5YhFqMRhAr
天下一最短路コンテスト全然解けん。サンプル2を参考にして「高橋君が最後に通る3点が一直線に並ぶように置き、タクヤ君はそのうち真ん中の点をすでに通ってしまっている」ような感じで解こうとしていますが、どう思いますか
— こたつがめ (@kotatsugame_t) 2021年2月6日

嫌になったので解説を読む。最初のほうだけチラっと見ると、2x50という文言が目に入る。実際そのように配列して、番号を上手いこと割り振ることを考えると、タクヤ君が最後までいかずに戻ってくるような辿り方をしてしまうケースを作れることに気づいた。非常にシンプルな解法で、これが思いつかなかったのは意味不明。サンプル2を発展させようと夢中になっていたが、何の関係もなかった。

ともかくAC。これで黄diffがすべて埋まったことになる。

黄色diff埋まった！ pic.twitter.com/xrAEXDFqzS
— こたつがめ (@kotatsugame_t) 2021年2月6日

橙diffに進み、食事したりシャワーを浴びたりしつつさらに2問解いたところでABCの時間になった。

全完59位。Fに3000万年かかった。ペナルティもしょうもないことをして出している。

A、Bはよい。Cは、まず黒と白の境目の数を数えて、次にその境目が2つ並んでいるような場所の数を引けば、辺の本数がわかる。Dは気合い。Eは自明。Fは適当に部分集合を選んでそのgcdかつmin(A)より小さいもの、という条件であることがわかる。ここから、数列の先頭からありうるgcdを全部持って順に計算していくやつを4回くらい投げて全部TLEだった。バカ。どういうケースでめちゃめちゃ時間がかかるのか全然想像できなかったのが良くない。残り30分くらいになったので、とりあえずA問題のコードゴルフをして、再度考え直すと解けた。数列の各項について約数を全列挙できて、同じ約数を持つ項全部のgcdがその約数と等しいか判定すればよい。これは、できる。

コードゴルフをする。A問題はコンテスト後にさらに縮んだ。最初はVT<=D<=VSを(VS-D)(VT-D)<=0と変形して場合分けする解法。実はVT<=D<=VSはT<=D/V<=Sになる。ここから同様に積の形にして場合分け1回にまとめるよりも、うまいこと比較を2回するほうが短くなった。最初の比較に成功したら次の比較をするが、失敗したときも次の比較によってスタックが変な状態にならないように調整する。具体的には、文字列と数値を<または>で比較しようとすると、結局何もせず（スタックもいじらず）終わるという仕様を利用する。ここで!<や!>を使うと必ず成功してしまうのでまずい。

atcoder.jp

Bは全完後にAWKで20Bを出してニコニコしていたが、蓋を開けてみるとVimの13Bに蹂躙されていた。Vimを使うことに思い至れば20Bは切れただろうが、13Bのコードはよくわからない仕様を使っていて、自力ではたどり着けなかっただろう。Cはx20さんとバトル。負け。文字列のbit演算を使うという発想で、最初xorしていたのをandに直すことでキャプチャをなくした。

Dはよくわからない。まず有理数で頑張った。sqrtがまずいようで、全然通らない。結局そこは整数に直してbsearchで求めることにした。ところが1e4を掛けて整数で計算する解説の通りにやったところ、普通に短くなってしまった。ちなみにこちらでもsqrtの代わりにbsearchを使っている。Eはやっていない。FはTLが厳しく、Crystalを持ち出すことになった。Pythonみたいに等式・不等式をつなげて書くことができてびっくりした。

atcoder/modintでmodint1000000007とmodint998244353がこの形で定義されているのって、typoに確実に気付けるようにするためもありそう
— こたつがめ (@kotatsugame_t) 2021年2月6日

コードゴルフをしていたら午前3時になったので、SRM799に出る。午前2時開始だったのが別のコンテストと被ってさらに遅くなった。人権がない。

Medの1完。Easyを落としてしまったが、レートは2389→2404(+15)でhighest。Easyは、再帰的に計算するのはよかったが、分割した後それぞれ独立にできるわけではないことに気づかなかった。

Medは、直径の両端を全探索する。直径を与える組が複数あるような部分木については、頂点番号で何とかすると何とかできそう。ここまで考えたところでとりあえずO(N^3)のコードを書き、サンプルを試した。通ったのでさらにbit全探索のチェッカーを書き、ウニグラフっぽい直径を与える組がたくさんある木を試してみる。これも通ったので、ようやく高速化に着手した。2つの列で両方条件を満たすような場所の個数を探す必要があって、データ構造ではちょっと難しそう。ここでbitsetを思いつく。探索の順番をうまいことやる（直径の小さい順に調べる）ことにすれば、1回の計算はbitsetのandとcountで済む。直径を与える複数の組の頂点番号に関する条件もよさそうであることを丹念に確認し、実装して先ほどと同様のテストケースを試したところ、システスに通った。変わらずO(N^3)だが、64倍高速になる。

橙diffを1問読んで布団に入る。解けたあと少しなろうを読んで就寝。午前8時だった。

02/07(日)

午後2時くらいと午後3時くらいに2度、中途覚醒。別の橙diffを開いて考えながらまた寝た。結局起きたのは午後6時半だった。

yukicoderがあるので、それまで解けたはずの2問の実装をする。実際解けていて、通った。そのあとシャワーを浴びてyukicoderに臨む。

途中キーボードの接続がうまくいかずコーディングできない状態になったりしたものの、5完。全体的についている星よりも難しかった。

Aはよい。Bは飛ばそうかと考えたものの、少し立式したら解けた。ギャグの類。Cは難しい。dijkstraを元に考えると、最長路を計算することになってまずい。実際は街をソートして、到達可能性だけUFで扱う。UFに一緒に集合内の最大値を持たせる。

Dも難しい。まずAを小さいほうから試してmapでカウントしていく。B>=2なるペアが作れなくなったところで打ち切る。これは三乗根とかが出てくるので小さい。で、mapの要素を見ながらB==1の場合を足し引きしていく。具体的には、B==1なるペアが作れるAの個数が求まって、またmapの要素のうちB==1でも実現可能なものが判別できればよい。前者は二分探索でできる。後者は、A(A+K)=Xを式変形してA=(sqrt(K^2+4X)-K)/2になるので、このsqrt(K^2+4X)が求められればよい。K<=1e18なので__int128を用いて二分探索した。

EはNとMの両方が偶数の場合の構築ができたので、これで提出したところ、サンプル以外全ケースでWA。ここでいったん冷静になって、どうせ全部にコーナーケースが入ってるんだろ？というメタ読みをしてN=M=1の場合分けを入れたものを再度投げると、AC。

Fに取り組んでいる間に時間切れ。結局4分後に通った。純粋に式変形を頑張ると解けて感動。これに関してはしっかり解法を記録しておこう。

まず「円に内接する三角形」で検索して面積を求める公式を調べる。すると、辺の長さの総積/4であることがわかる。そこで点iとjを結ぶ辺の長さを計算してみる。

$\displaystyle\sqrt{\left(\cos\frac{2\pi T_i}{L}-\cos\frac{2\pi T_j}{L}\right)^2+\left(\sin\frac{2\pi T_i}{L}-\sin\frac{2\pi T_j}{L}\right)^2}=\sqrt{2\left(1-\cos\frac{2\pi(T_i-t_j)}{L}\right)}$

なので、3点i、j、kがなす三角形の面積の4倍（分母はいったん無視）は $p_i=\frac{2\pi T_i}{L}$ と置いて次のように表される。

$\displaystyle2\sqrt{2(1-\cos(p_i-p_j))(1-\cos(p_j-p_k))(1-\cos(p_k-p_i))}$

$1-\cos(p_i-p_j)=2\sin^2\left(\frac{p_i-p_j}{2}\right)$ なので、根号が外れて $8\left|\sin\left(\frac{p_i-p_j}{2}\right)\sin\left(\frac{p_j-p_k}{2}\right)\sin\left(\frac{p_k-p_i}{2}\right)\right|$ となる。

ここでi、j、kが偏角の順i<j<kであったことにして、点jを固定してみよう。 $\alpha=\frac{p_j-p_i}{2}$ 、 $\beta=\frac{p_k-p_j}{2}$ と置くと $0\lt\alpha,\beta,\alpha+\beta=\frac{p_k-p_i}{2}\lt\pi$ であるから絶対値が外れ、 $8\sin\alpha\sin\beta\sin(\alpha+\beta)$ になる。さらに式変形を進める。以下でスタイルが変わっているのは、eqnarrayを使おうとしたらpreタグが必要になったから。

公式解説ではこの変形について特に触れていないが、自分はなぜかめちゃくちゃ時間がかかった。

三角形の面積の総和、つまり任意のi<j<kに渡る上の式の総和を考えると、各i、j（ただしi<j）の組について $\sin(p_j-p_i)$ が総和に寄与する係数が求まる。三角形をなす残りの1点kとして、i<k<jなる点を選ぶかそうでないかで符号が変わり、実際の係数は点の添え字を0-indexedとして $N+2i-2j$ となる。 $\sin(p_j-p_i)$ もさらに分解することで、結局 $(N+2i-2j)(\sin p_j\cos p_i-\cos p_j\sin p_i)$ のi<jを渡る総和になる。展開して4つの項に分けると完全にiとjが分離できて、各項についてjを動かしながらiに関して和を取れば線形時間で求まる。あとは無視した係数を戻したり、期待値なので場合の数で割ったりすればよい。

まとめると、まず1つの三角形に注目して角度の差3つの式を作り、式変形してそれぞれ分離し、1つの角度の差に注目して寄与を計算し、さらに分離して「角度の差」ではなく「角度」の式にしたということになるのか。ここでいう分離とは、おおむね線型になって分配法則などが適用できる状態になること、を指す。三角関数の中で差を取ってるのがダメなことを自覚していなくて、うっかり文字で置いてしまったのが見えなくなった原因かもしれない。実際、根号が外れたところの式をWolframAlphaにぶち込むと最後の式が出てくる。

直後にこどふぉ。今日はCF 700 div.1だった。Aを落としてB1B2C。predictorによれば2675→2633(-42)。

Aは、区間の左端がその1つ左より小さく、右端がその1つ右より小さい、という状態を維持して区間を半々にしていく。落ちた原因はこれ。

あ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ pic.twitter.com/Xnjpxately
— こたつがめ (@kotatsugame_t) 2021年2月7日

はやく人間になりたい！

B1は、基本的にランレングス圧縮したあと個数と2のminを取ったものの総和になる。2個以上あるものだけ抜き出したときに同じもの（pとしておこう）が隣り合う場合は、間の1個しかないものを適当に動かして何とかする。何とかできるフラグをミスして1WA。正解は、問題のpとpの間に「1個しかないものであってpではないものが2つ連続している」ことが動かして何とかできる必要十分条件。

B2は左から見て列の右端を管理する実家DP。片方は必ず今見ているものが右端に来るので、もう片方を持つ。更新は全体に1足したり全体のminを取ったりするので、遅延セグメント木を使う。全体に加えられた値と全体のminを持っておけば、データ構造がなくてもできそう。Cは気合い。頭がバグっていて端数の処理に5万年かかった。D以降はやる気がない。