01/10(月)

先週の週記を投稿してからの話。結局この日は徹夜っぽい感じに過ごすことになった。

午前中の間は、他の人の日記を遡ってずっと読んでいた。書いた人が考えていることが伝わってくる文章で、読んでいてとても楽しかった。わが身を振り返ることにも繋がる。自分の考え方との違いを探ってみたりして、ああこの人も生きているんだなあ、というようなことを感じた。僕は基本的にTwitterしか見ないし、Twitterで積極的なコミュニケーションを取るわけでもないので、最近はアカウントを血の通った人間が動かしているということがあまり実感できなくなった気がする。

昼からは本を読んでいた。眠い目を擦りつつ何とか1冊読了。「私立シードゥス学院」3巻。シリーズ最終巻らしい。最後まで読んでみたところ、なんと1年目のクリスマス前で終わっている。なんと中途半端な時期か。しかし学院のイベントが盛りだくさんなため、それぞれで1つずつ話を作ったらこのような感じになってしまったのだろう。実のところ、話に出ていたものすべては回収できていないような気もする。最終話の主題は主人公三人組のうち獅子王琥珀ただ一人で、ほかの二人についてはシリーズ全体を通してあまり掘り下げられた感じがしなかった。そのためか二人の区別があまりついておらず、今回もセリフの発話者を逐一確認しないとすぐよくわからなくなってしまって読むのが大変だった。内容的には特に感想が見つからない。

CodeChefの1月Longが終わっていた。先週この↓ようなことを書いたが、結局今日、本を読みつつ格闘して最終問題も何とか通ってくれた。レートの変動はやはりなさそう。CodeChefのレーティングシステムがよくわかっていない。

月曜日の夕方まで開催されているので、問題には言及できない。今のところ最終問題が解けていない。
週記（2022/01/03-2022/01/09） - kotatsugameの日記

https://www.codechef.com/JAN221A

RIFFLESはしばらく実験していたが、functional graphということに気づけばループを見るだけでよい。XOREDはよくわからない。 $1\dots N-3$ をまず固定して、残りの状態で場合分けした。 $2^{17}$ は常に使えるので、それを使って当てはめられるならよし、そうでない場合は $2^{17}+2^{18}$ を使ったりしている。残り2要素のXORが $0$ になってしまった場合は $N-3$ も弄っている。MASTERは左から重複を抜いていったとき各要素が残るような区間の選び方を考えるとよくて、式を整理すると $k$ の係数と定数項の2つで表せる。両方区間SUMのセグメント木で管理する。

GENECYCは難しかった。まず $1$ の辺だけでサイクルを成している必要がある。これをサイクルに分解した後、間に浮いている辺でサイクルを切っていってvertex inducedな状態にすればよい。サイクルで切るときの操作コストは、多角形の三角形分割を考えると3倍がちょうど満たされる。しかし数回試して通らなかったので絶望していた。眠気でシバシバした目でコードをにらみつけてもよくわからない。これまで、間に浮いている辺があるかのチェックと同時に、重複する頂点が存在する場合はそこでも切るようにしていたが、重複する頂点のチェックをしないようにしたらACケースが増えた。よくわからないまま、重複する頂点のチェック→浮いている辺のチェック、というように完全に順序付けて処理してみたら通った。

後から何が起こっていたかを理解した。重複する頂点がある場合、そこから伸びている辺であってすでにサイクルの別の場所で使われているものも、間に浮いている辺として検出されてしまう。そこでサイクルを切っていくといずれ2頂点のループを作る羽目になる。これ自体は辺のラベルを変化させないが、操作コストが増えてしまう。それでコストに関する条件を満たせなくなっていたようだ。実際、長さ2のサイクルは答えに含めないような処理を入れると、処理が順序づいていなくても通った。操作コストが超過している場合exit(1)する提出もあったのだが、どうやらこれはWAとして扱われてしまうらしい。

$1$ の辺だけ見てパスを伸ばしつつ、パスに含まれる頂点と隣接した瞬間そこでサイクルを作って辺のラベルを全部入れ替える、という操作を繰り返す解法をTLで見た。シンプルで頭がいい。サイクルの集合がXORで閉じているという性質をより直接的に使っている。

午後7時就寝。

午前1時に目を覚ます。新春TechFUL Coding Battle 2022の結果が出ていた。全完だがペナ差が響き、なんとか8位に滑り込んだ……ように見えたものの、よくよくスレッドを確認すると問題に不備があったらしく、1問が採点対象外となっていた。順位表ではそれも含めた点数が表示されているため、まだ確定ではないようだ。順位表で僕の下にいるように見えた人たちも、1問解けなかったのではなく1問解かなかっただけなのかもしれない。これはマズいか。ともかく、ようやく各問題についての感想が書ける。

https://techful-programming.com/user/event/2497

「Make Unique」の制約がよくわからなかった。コンテストサイトを信用していないので、 $0\le K\lt \sum A_i$ という制約から $0\lt\sum A_i$ を読み取ってよいのかがよくわからない。恐々投げたら通ったが、実際ほとんど関係ないコードではある。「Mex Sum」は難しかった。 $i=0\dots M$ について $1\dots i$ を全て含む列の数を数え、足し合わせると答えになる。しかし肝心の列の数は重複組み合わせを使った包除原理の式になってしまう。しかしここで、出現する重複組み合わせが符号を含めてほとんど同じ形をしているため、何回出現するかを数えればよいことに気づいた。具体的には $(-1)^i{}_{M-i}\mathrm{H}_N$ が $\sum_{j=i}^M {}_j\mathrm{C}_i$ 回出現する。この和はWolfram|Alphaに投げると ${}_{M+1}\mathrm{C}_{i+1}$ と閉じた式で表せたのでよい。この問題には14分強かかっており、なんとかタイムボーナスは満点だったものの、解答時間の総和ではかなり遅れを取ってしまった。

「楽しいすごろくゲーム」の四捨五入の部分は、以前のTechFULの経験から何も考えずsetprecision(2)するとよいということが分かっていたので、それで投げた。数値計算の誤差がヤバいはずなので問題文がかなり怪しいと話題になっていた。テストには誤差で答えが変わりうるケースが入っていないと聞いたが、特に問題文に記載はない。そもそもTechFULにはスペシャルジャッジの概念がないため、仕方なく四捨五入をさせるような出力形式になっているらしい。「Domino Tiling」はやるだけ、だが最初に変な貪欲を書いて時間を浪費した。「複雑なあみだくじ」はインデックスのペア $(i,j)$ があみだくじを辿った後に $(k,l)$ になっている場合の数、というのをまとめて行列累乗で計算できるので、適切に足し合わせると解ける。しかしこの問題が不備によって採点対象外となったものなので、せっかく解法がすぐ見えたのに意味なし。

ここから追加された問題。「01-prefix」はTrie木でprefixごとにカウントするだけ。「Kが日」は合わせるのに大変時間がかかった。未証明だがAlien DPだろうという予想はついて、dpも意味のある遷移が $N\times 51$ 種類しかないので間に合う。しかし答えが全然合わなかった。まずペナルティはdoubleで考える必要があって、しかもちょうど $K$ 回ペナルティが発生する場合があるとは限らないので、真の値を得るためにはペナルティに使った回数ではなく $K$ を掛ける必要があった。それをroundにかけて出力したらやっと通ったが、3ペナと80分を使っている。実は最近のABCでもAlien DPが出ていたらしい。未ACで解説も読んでいなかった。

布団でしばらくラノベを読んで、午前5時に再度就寝。

01/11(火)

午後0時起床。学食で昼食を摂った。今年初めてとなる。帰省から帰ってきてずっとパックご飯にインスタント味噌汁で耐えていた。

帰宅したらFHC Tシャツが届いていた。袖の部分に「TOP 200」と書いてあるのが、上位200人の特典のようだ。

FHC Tシャツ届いた。袖にTOP200って書いてあって草 pic.twitter.com/dZ9AmS1a4I
— こたつがめ (@kotatsugame_t) 2022年1月11日

ABD1の43ptで82位。R2を59位で通過したとき、Tシャツにバッジが付くのがR3の上位200人であることを知って残念に思っていたが、結局R3でもそれなりに良い成績を残せた。
週記（2021/10/04-2021/10/10） - kotatsugameの日記

先週土曜日のABC234-Dの最短コードが取られていた。答えが単調増加になることを利用すると、全体で線形時間で解けるようだ。うっかりしていた。

atcoder.jp

はてなスターの仕様変更があった。ビジュアルや操作感はかなり向上している。特に、スターを付けると目に見える動きがあるのがうれしいところ。一方、記事内の特定の文章にスターをつけるためには、その部分を選択した状態でページ最下部のボタンを操作する必要があるようで、結構難しくなったと感じる。

star.hatenastaff.com

しばらくラノベを読んで、午後4時からインターン先定例会のための進捗報告スライドを作り始めた。月曜日が休日だったので火曜日にずれている。年末年始は本当に何もやっていないうえに、今週もゼミ発表があって木曜日までは動けなさそう。さらに金曜日に1on1の予定があって、しかも同じく金曜日は年末から残していた業務の期限になっているらしい。ひたすら怠惰。

いつもの時間になっても始まらず、よく見たら予定がいつもと微妙に異なっていた。思いがけず時間が空いたため、せっかくなので少しだけ業務を進めていた。しばらくして定例会が始まる。自分の現状を赤裸々に報告するとメンターさんに大変に心配して頂いて、申し訳なさがすごい。実際はちゃんとやれば間に合うはずなので、そんなにマズいわけではない。

勉強会について。今日の発表に対して自分が行った質問は頓珍漢なものだったので、反省のため少し詳しいことを書いておく。テーブルデータの学習について、ある項目がどれくらい予測精度に貢献するかを探る話。素直に考えれば、ある値を無視して学習を行いその精度を比較する方法があるが、これは項目ごとに都度学習を回す必要があって計算時間的に嬉しくない。そこで、その項目の値を全データでシャッフルし、学習済みのモデルで再度評価した精度を見てもよいらしい。こちらは追加で学習を回す必要がなくて嬉しい。自分は「学習」と「評価」を混同していて、何が嬉しいのかよくわからず質問したのだった。

布団に入ってラノベを読んでいたが、午後7時半に寝落ち。午後10時過ぎに少し目を覚ましたものの、またすぐ二度寝した。

01/12(水)

午前1時起床。

ラノベを1冊読了。「『ずっと友達でいてね』と言っていた女友達が友達じゃなくなるまで」。非常に良かった。この巻は終始距離感が近すぎるヒロインに悶々しつつ進んで、その様子も微笑ましかったが、終盤でお互いがお互いへの好意を自覚し、両片思い状態に突入した。そのまま進めば2巻では学校生活も描かれるはずで、楽しみ。

Pythonの講義の課題が昨日出ていて、そのうち講義のキーワードを抜き出すものの期限が今日になっているので、忘れないうちにと提出しておいた。その後午前2時からゼミの発表準備を始め、午前6時前に切り上げて布団に入った。しかし布団の中で2時間くらいYouTube shortsを見続けてしまい、すっかり日が昇ったのを見て諦めて起きていることにした。YouTube shortsは自由に動画を探すのが難しく、特に次の動画に進む操作をするとYouTubeが勝手に選んだものを見ることになる。これがむしろ時間を溶かすのに向いているようで、冷静になると全然興味がない動画も何となく見てしまうことになって常に新鮮な刺激が得られる。

ラノベを1冊読了。「友人に500円貸したら借金のカタに妹をよこしてきたのだけれど、俺は一体どうすればいいんだろう」。良かった、はず。主人公が無自覚モテ男であるという設定が好み。イラストも好きだった。しかしそれ以外のストーリー的な良さを探そうとしても見つからず、何をもって良いと感じたのかは謎。

今日これまでに2冊ラノベを読んだが、どちらも秋ごろの新刊である。最近買うペースよりも読むペースのほうが速いため、ついに積読の山に手が伸びるようになった。特に1冊目のラノベはすでに2巻の発売が間近に迫っていて、TLに感想が流れてきてもいたため、気になっていた。

雪が降る中学食に向かい、昼食を摂って、注文していた本を受け取ってきた。

夏の終わりを感じる…… pic.twitter.com/x2vVWY8eWv
— こたつがめ (@kotatsugame_t) 2022年1月12日

帰宅して、午後2時くらいまでインターンの業務を進めていた。コミュニケーションのため昼間に進める必要がある部分を終わらせ、次にゼミ準備を再開。ラノベを読みつつ進めていて、途中で1冊読み切った。「転生魔王の大誤算」4巻。終盤は展開に引き込まれ、ゼミ準備の手が完全に止まっていた。主人公の前では内気な少年だがそれ以外の場所では冷酷無比という描かれ方をしていたサ藤というキャラがいて、この巻はずっと彼に焦点が合っていた。いつか何かやらかしそうという印象だったが、友人を得て人間的に成長した。展開としても好みのシーンが多く、最後はキッチリ主人公の無双で締めていて大満足。

ゼミ準備のラストスパート。ルジャンドル記号の話で、 $(n\mid p)$ （テキストでは横に書いていた）を求めるのに $n^{(p-1)/2}\bmod p$ を求めるのは大変だから、 $m=\sum_{t=1}^{(p-1)/2}\lfloor tn/p\rfloor+(n-1)\times\frac{p^2-1}8$ を計算して $(-1)^m$ としてもよいですよ、ということが書いてあった。しかしこれは別に楽になっていないだろう。というわけで、それがなぜかということについて余談という形で話すことにした。前者が $O(\log p)$ で計算できるのは明らかだが、実は後者もfloor_sumを使えば同じく $O(\log p)$ で計算できる。肝心のfloor_sumを説明するためにブログ記事などを読んでいた。計算ステップ数については、オーダーこそ同じなものの、明らかに定数倍から前者のほうが高速になるはず。一方後者は $p$ ではなく $2$ で割ったあまりを求めることになるので、非常に大きな $p$ に対しては後者のほうが高速になるのかもしれない。

floor_sumのアルゴリズムの初出を聞かれるかもしれないと思ってそれについても調べていたが、結局よくわからなかった。Library Checkerには一番最初からある問題のようで、特に説明などもない。

午後7時半くらいに完成。とりあえずホスフィンに投げつけ、見直しは明日起きてからする。今週の頭から溜めていた日記を書き進めた後、午後10時就寝。

01/13(木)

午前9時前に起床。昨日の夜にチュウニズムで激ヤバリザルトが出ていたのを知った。

間に合った❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️❗️ pic.twitter.com/u7HocKnmnQ
— すと (@Kokor0_N) 2022年1月12日

年に一度、チュウニズム（を含む音ゲー3機種）の全国大会があって、それの予選として用意された3曲がついに通しで理論値陥落したらしい。昨年は不正な操作で一瞬理論値がランキングに出たことがあったが、今年は真っ当に理論値が出されている。また達成の瞬間が動画に収められていたらしく、別の人からツイートされている。この動画も、世界で一番チュウニズムが上手い人の体の動きが見られるという点で非常に貴重なものである。一般に上からの手元動画は星の数ほどあるものの、横からの手元動画になると途端に数が少なくなり、全身が見られるものなどはほとんど存在しないはず。一方チュウニズムが上手い人は手元が落ち着いていると言われており、これについては横や後ろから見たほうがわかりやすいので、上手い人の体の動きが見られる動画は嬉しい。

すとら、こわいよ〜〜〜〜〜〜 pic.twitter.com/ZwCqWmmkHN
— 蓬莱 (@hr_haruka) 2022年1月12日

昨日作ったスライドについてホスフィンからありがたくもフィードバックをもらったので、それに沿って少し修正。紙に印刷して見直ししつつ、教科書に書いてあるのに書き忘れたこと、また他に伝えておきたいことがないかを調べて書き込んでおく。それも終わったので、しばらくラノベを読んでから正午に家を出た。雪が少し残っているので、地下鉄で山に登る。確か2019年の冬だったか、原付の冬用タイヤを購入したのだが、次の春に普通のタイヤに戻してからこれまで1回も交換していない。昨年はコロナでほぼ山に登らなかったからで、今年も同様。週に1回しか山に登る用事がないうえに実際に積雪するのは数週間程度ともなれば、タイヤ交換代より地下鉄を連打するほうが安くなると気づいてしまった。

遅刻もせず、ちょうどいい時間にゼミの教室にたどり着いた。コロナが最近また蔓延し始めたため、次回からオンラインに戻ってしまうらしい。原付のタイヤを交換しなくて正解。発表はかなり下手くそで、何度も言葉に詰まってしまった。また勢いで正しくないことを口走ることも多い。もちろんすぐに訂正するとはいえ、伝わりにくさに一役買っているだろう。昨日の日記に書いていた計算量の話をするため、控えめな分量で用意してきたはずだったのに、3分の1くらいが終わらなかった。計算量の話は図を黒板に書きつつ説明したかったので、キリのいいところで切り上げてそちらに移ったが、これもまたずいぶんと下手くそだった。式変形を追うだけだとよくわからないアルゴリズムだと思っていて、グラフを書いて格子点を数える話に持ち込み、図を横から見ることで計算量のトリックが理解できますということを言いたかったのに、どういう図を描くかを全然考えていなかった。ただまあ、最後の黒板発表で好きなことを喋り散らかせたので、そういう満足感はある。終わってから黒板を消す前に写真を撮った。

ゼミでfloor_sumの話した pic.twitter.com/Ic9lkO1E6r
— こたつがめ (@kotatsugame_t) 2022年1月13日

発表用スライドもここに置いておく。

Apostol_Chapter9_9.1-9.6.pdf - Google ドライブ

ゼミ後、今日もまた部屋を移動してボードゲームで遊んだ。今日が最後になり、寂しい。ずっとスカルをプレイしていた。今日も適当にかなり大きな数でチャレンジして遊んでいた。この場合場に1枚しかない状態で早めにチャレンジを始めると成功しやすい感じがしたので、自分から積極的にチャレンジをしに行った。すると、もっとタイルを重ねたい人もいたようで、後半、初手は2枚重ねて出すという独自ルールを入れて遊んだりもした。そうやってプレイしていると頻繁にチャレンジ失敗するので、自分のタイルがどんどんなくなってしまう。5人いるのに2人消え、1人も残り1枚になってしまうという状態が2回発生したが、こうなると理詰めで必勝パターンがありそうだったりして、スカルってそういうゲームだったのか……みたいな気持ちになった。

眠くて途中一瞬寝てしまったのを見られたりしつつ、今日は名残惜しむように午後8時まで4時間近く遊んでいた。当然学食も閉店しているため、コンビニでパン類を購入しつつ帰宅。眠気に耐えつつ今朝読んでいたラノベを読み進め、午前2時前に読了。「前世は剣帝。今生クズ王子」3巻。主人公の自分語りが多すぎるといって1巻の印象は悪かったものの、それから自分の中での評価が単調に増加している。おそらく、ストーリーが進むにつれて主人公の対外的な露出が増え、実力を発揮するシーンが多くなってきたからだろう。一般に主人公が無双していると面白いのだ。

午前2時半就寝。

01/14(金)

午前9時起床。

眠気がかなり強く、午前中はYouTubeを眺めていたら終わってしまった。最近またデュエルマスターズの対戦動画を漁り始めてしまい、よくない。「しゃまのデュエマちゃんねる」に上がっている、「かんぜさん」との対戦動画が、その空気感も含めて好き。実はしゃまさんはつい最近YouTuberを引退されたらしく、それについての動画がYouTubeでおすすめされて、熱が再燃したという事情がある。

www.youtube.com

学食に向かうも、明日から共通テストということで今日は休講日らしく、空いていなかった。仕方なく購買で惣菜パンを購入。ついでに、倉庫からの出荷メールが来て数日経過していた本が入荷していないか確認した。ちょうど明日が発売日の本。これまで、予約した本の出荷自体は発売日の数日前に行われるも、入荷メールは毎回発売日後に届いていたので、実はメールが届いていないだけで本はあるんじゃないかと思ったのだ。しかし本自体も届いていなかった。一般の本屋なら発売日の1日前から並び始めることが多いと思っているが、そのあたり大学生協はかなり律儀らしい。本を1割引きで売れる理由も含め、良くも悪くも普通の本屋ではないということか。

大学生協の本はなぜ安い？〜書籍の再販制度を問い直す〜 - THE KINGDOM POST

帰宅してしばらくインターンの業務を進め、午後1時半から1on1。進捗こそほぼないものの、今後の動きを確認しているうちに話が弾み、いい感じの雰囲気のまま午後3時まで話していた。また業務に戻り、午後5時前にほぼ完了。何とか期限内に終わらせられた。Slackを見ていると、サークルの定例バチャが行われていることに気づいたため、急遽参加した。

https://kenkoooo.com/atcoder/#/contest/show/c9be0204-c369-489f-91df-6342eb964c77

なんとなくPythonで参加した。全問、素のPythonで通るコードが書けている。ABC132-Fで商が同じになる除数の区間を求める必要があるが、これを $\sqrt N$ で分けてごちゃごちゃするのではなく、単純な一つのループで統一的に求める方法が美しくわかりやすいため、バチャ後の感想会で強くおすすめした。下の提出の3行目から9行目である。 $N$ を割った商が $q$ になる最大の数は $\left\lfloor\frac N q\right\rfloor$ である、という事実に基づいている。

atcoder.jp

日記を書こうとしつつボーっとしていたら、たまたま以下のツイートを目にした。コードゴルフの時間だ！

【常設コンテスト追加のお知らせ】
アルゴリズムと数学　演習問題集https://t.co/bletLqBtwS
— AtCoder (@atcoder) 2022年1月14日

急いでコンテストページに飛び、上の問題からなぎ倒していく。案の定最初のほうは非常に簡単で、これはコンテストの存在にいかに早く気付くかだったな～と思いつつ最短コードを確認したら、昨年末からの提出がたくさんあってさすがにひっくり返った。どうやら本にでもURLが記載されていたのか、トップページに載ってこそいないものの以前からアクセスできたコンテストだったらしい。そ、そんな……。URLで検索したところ、以下のツイートが引っ掛かった最古のものだった。これは辛い。

Atcoder に専用のジャッジまで用意されてるhttps://t.co/fMYlG9JTZn
— ワドリア海の赤い豚 (@rosso016) 2021年12月29日

それでも全然ゴルフし切れていない提出が山のようにあるため、午前4時までノンストップでコードゴルフし続けていた。問題自体が簡単なため特に見るべきものはない。グラフ問題のTLが1secになっていてnetworkxが死ぬほどTLEした。また3問ほどテストケースに改行がついていなかったり変な風になっていたので、報告しておいた。面倒なことが目に見えていたため飛ばした問題もそこそこある。

CFを開いたらメッセージが来ていた。Good Bye 2021の商品として、仮想通貨「NEAR」がちょびっと貰えるらしい。コンテストのAnnouncementによれば僕は「Ⓝ4」貰えるはずで、検索したところ価格が2300円弱と出たから、素直に考えればおよそ9000円か？かなり高額であると感じる。しかし受け取るためにはウォレットを作る必要があるなど、実際に日本円にするまでが非常に面倒そうだったので、放置することに決めた。いつだかのTCO Regionalの交通費もPayPalに塩漬けになっている。今調べたら18694円だった。とにかく面倒である。

午前5時就寝。

01/15(土)

午後1時前に少し起きていた記録があるが、しばらくしてまた寝たはず。午後8時起床。睡眠負債がたまっていたらしい。

atcoder.jp

$5\times 10^5$ 文字の括弧列がvalidか判定する問題。拡張正規表現の再帰機能を使って判定する方法があるが、さすがに間に合わないだろうと試しもしていなかった。爆速で通っていてびっくり。

atcoder.jp

$\left(\frac{N(N+1)}2\right)^2$ を例の素数で割ったあまりを求める問題。それほど大きくない値だからと素直に2乗してから余りを取っていたところ、この演算に|コマンドが使えるのをすっかり見落としていた。今日更新されているのを見てかなり衝撃を受けた。

食事してシャワーを浴び、午後9時からABC235に出た。

HHKB Programming Contest 2022（AtCoder Beginner Contest 235） - AtCoder

Aは少し考えると $111\times(a+b+c)$ とわかる。dc。Bはやるだけだが短い書き方がわからず、AWKで適当に出したら2ペナついてしまった。CはとりあえずRubyのgroup_byを使った。ここからC++。DはBFS。Eは一瞬、パスに含まれる重み最大の辺を探しそうになるが、冷静になるとクエリごと重みでソートしてクラスカル法をすればよい。Fは桁dp。最初場合の数だけ数えていて、あとから急いで総和を求めるdpを付け足した。計算量が $\sigma=10$ として $O(\sigma 2^\sigma\log N)$ 、つまりおよそ10⁸に定数倍がかなり付くため、700msを超えている。Gはしばらく方針ガチャを回し、包除原理を引き当てた。 $\sum_{i=0}^A {}_n\mathrm{C}_i$ みたいな値を $0\le n\le N$ で求める必要があるが、 $n\rightarrow n+1$ と計算すると毎回定数時間で差分更新できる。この着想は、パスカルの三角形において1段下がることに対応→2つ用意してずらして足し合わせるとよい、という観察から得られるし、具体的な値を $\sum\left({}_{n+1}\mathrm{C}_i-{}_n\mathrm{C}_i\right)=\sum{}_n\mathrm{C}_{i-1}$ から導くこともできる。

Exはすんなり解けてしまった。グラフが木ではなくてびっくりしたが、最小全域木さえ取ればよい。クラスカル法のマージ過程を表す木で木dpをする。操作を行った回数に対して場合の数を持ち、その列を畳み込むような遷移になる。ただし、今見ている集合のすべての頂点を赤く塗る場合は1回で操作できるので、それを足して代わりにマージ前のそれぞれの集合を1回ずつ赤く塗る場合を引く更新を加える。2乗の木dpの亜種で計算量が $O(NK)$ になるというのが、つい最近のOpenCupで出た。うっかり固定長配列を毎回 $O(K^2)$ かけて畳み込んでしまったので提出直前に計算量解析が壊れていることに気づき、ACLのconvolutionで書き直した。畳み込みの高速化は今回の場合あまり意味がないものの、便利ではある。

2乗の木dpで配列をKK番目までで打ち切ると、計算量がO(NK)O(NK)になるという話を聞いた。
週記（2021/11/22-2021/11/28） - kotatsugameの日記

全完14位。学生5位に滑りこんだかと思って喜んでいたものの、トップページを確認すると4位以下は飛び賞しかなくがっくり。これはBの2ペナがなくても変わらない。

Dは $1$ からではなく $N$ からBFSすると値の大きさに気を使う必要がなくなって簡単。Fはこの計算量が想定解でびっくりした。G問題の解説では、経路の数え上げに帰着して差分更新を行う方法が記載されていた。結論こそ同じであるものの、経路に帰着する方法はあまり成功した覚えがない。かろうじてカタラン数のような途中の値に制限がある問題を解いた記憶だけがある。

コードゴルフ。ABはコンテスト中のものが最短。CはAWKで書くと短くなった。 $a_i=0$ が存在するので、$++iを条件式にするとループを最後まで回すことができない。これまではi++<NFを使っていたところ、今日新たに$++iに空文字列を連結して無理やり文字列にする方法が出た。値を出力するときに散々使ったテクだが、ループの条件式に出現したのは初めて目にした気がする。この更新で取られた。DはPerlで、BFSを深さごとに区切って一段一段進めていく書き方をしたら縮んだ。Eはコンテスト中に出ていたPerlコードに隙がない。以降は手付かず。

午後11時半からCF #766 div.2に出た。全完13位。

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

Aはよい。BはTinaが四隅のどこかに座ることが分かって、最も遠い隅への距離を各マスについて求めたら、その値が小さい順に塗っていくのが良い。すると、出力は小さい順にソートした列そのものになる。Cはなぜか辺の重みがdistinctである必要があると勘違いして1WA。次数3以上の頂点があるとダメで、そうでない場合、つまり直線グラフは2と3を交互に塗っていくとよい。Dは $10^6\dots 1$ の順にそれがgcdとして出現できるかをチェックした。倍数が列にあるかは愚直にチェックしても調和級数で押さえられて、倍数のうち最小のものとそれ以外でgcdを計算してチェックしたのでlogが2つついているが爆速だった。Eは気合いでdp。最小になり得ない値を削除しておけば、はしごに至るまでのコストは直左と直右から計算するだけで十分になる。Fは行を行き来する切り離し方に気付かず1行ずつ見るdpを必死に書いて1WA。切り離すラインは $(0,0)$ から $(K/2,K/2)$ までグリッドを辿る移動とそれを180度反転したものになるので、いくつのペアが分かれるかをカウントして最短経路問題を解く。途中で交差してしまうような経路は最短にはなり得ないため、これでよい。

Eを実装している途中に津波注意報のエリアメールが来てびっくりした。地震速報かと思って身構えたが、特に揺れもないし沿岸部でもないので一旦無視。全完後に調べたところ、遠く離れた火山の噴火によるものだったらしい。

次のようにすると、Dのlogを1つ落とせるらしい。

Dは「aの部分集合のgcdが何通りありますか？」に帰着できるので、xの倍数の個数をdp[x]として、dp[x]=dp[i*x] となる i が無い x を数えれば良い
— (nは自然数) (@n_vip) 2022年1月15日

午前3時半から日記を書き始めた。実は月曜日の前半を書いてからずっと放置していて、今この部分まで書いたところで午前10時半になった。実に7時間かかっている。

火曜日に出ていたPythonの講義の課題に取り組んだ。日曜日が期限になっている。今週はニューラルネットに三角関数を学習させるというもの。Kerasを使って一通り動くようなコードが与えられて、改善する例が示されているので、組み合わせて精度を高めるらしい。適当に層を増やしたり素子数を調整したり活性化関数をReLUにしたり、組み合わせ方は星の数ほどあるが、面倒なのでちょろっと試して一番良かったものがいいですね～という感じでお茶を濁した。しかし、一番良かったはずのモデルも再度動かしてみたら他のものとあまり変わらない結果になってしまったので、これまでの学習は実質乱数のご機嫌伺いをしていただけだったらしい。足元を崩されたような感覚を得た。

ラノベを1冊読了。「俺は星間国家の悪徳領主！」2巻。すでになろうのほうで読んでいて、さらに2巻は（というかこのシリーズは全部）文庫がぶ厚かったので、微妙に読むタイミングを逃した後はずっと本棚に安置してあった。1巻を読んでから丸一年空いてしまったようだ。非常に面白かった。良質な勘違いもの。僕の知る勘違いものは、どうしても主人公の自己評価が低くなりがちで、そういう意識を持つ主人公という視点から見ていると何となく場違いさを感じてしまう。この本では「悪徳領主のつもりが名君」という勘違いを主軸に書かれるため、主人公のふるまいも堂々としていて、読んでいて安心できた。展開というか勘違いの伏線もそれなりに手が込んでいるように感じられて驚かされる。

3巻に手を出すも急激に眠くなり、午後3時半就寝。

01/16(日)

午後10時半起床。食事してシャワーを浴び、午後11時半からECR121に出た。

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

Aは2文字あるものを1文字ずつ左右に並べ、その間を1文字しかないもので埋めた。今書いていて気付いたが、文字列をソートするだけでよかった。Bは足して桁が減らない場所があればそのうち一番右のものを選び、そうでない場合は一番左の2文字を足すとよい。Cは問題文を読んですぐdpに飛びついたものの、遷移を書くのがかなり面倒なことに気づいて方針を変えた。貪欲っぽいことをしてよいはずで、ダメージの棒グラフがなす三角形をstackを使ってシミュレートする。直前のspellからリセットできない限り、それをpopして三角形のサイズを合わせるのを繰り返した。Dは度数分布に直した後、左右それぞれのサイズとして何を使うかを全探索した。この時中央のサイズは小さければ小さいほど良いことが言え、またそのサイズのみが答えに関係するので、左右から被らず決めたサイズをオーバーしない範囲で貪欲に取れる。この貪欲は毎回計算しても間に合うところ、尺取りの要領で少し高速化している。

Eはひたすら面倒で、しかも日記のこの部分を書いている間にHackケースを思いついてしまった。黒い頂点を適当に1つ根にする。根の直接の子のうち、部分木に黒い頂点を含むものが2つ以上あるか、もしくは1つであってもその部分木に黒い頂点が2つ以上、祖先関係にあるように存在すれば、どの頂点の答えも $1$ になる。要するに、黒い頂点を3個以上含むようなパスが存在するかをチェックしている。それ以外の場合は、黒い頂点に隣接する頂点から伸びる「分岐」だけ $1$ にしてよいはず。ただ、この分岐というのを検出するのが難しく、何とか熱烈場合分けで対処しようとしていたものの、本質的にdfsを遡るような更新が必要なことに気づいてしまった。

介錯は不要…… pic.twitter.com/2duHUJEiSe
— こたつがめ (@kotatsugame_t) 2022年1月17日

Fは微妙に難しい。まず、1から16までそれぞれ割る・割らないでどう変化するかをまとめたい。これは ${\rm lcm}(1\dots 16)=720720$ で割ったあまりで場合分けすればよい。樹形図みたいな分岐を考えて、そこに属する「場合の数」と「現在の値の総和」を持っておく。各段、その後の分岐がさらに $n$ のべき乗あるのを掛けつつ答えに足す。1段進める際は、値が変わらない $n-1$ 通りと値が減る $1$ 通りをそれぞれ求めればよい。ところが、実装が終わって提出しようとしたらこどふぉのサイトが落ちていた。これは結局コンテスト終了まで復活しなかった。後から出したら通った。

ラノベを1冊読了。「俺は星間国家の悪徳領主！」3巻。相変わらず面白く、爽快。ただ主人公の婚約者となったヒロインの背景設定がかなり重かった。特定の血統に連なる人をネチネチ虐める組織が存在するというのは、スケールの違いこそあれ、読んでいて辛くなるタイプのR18作品の設定を思い出してしまう。最終的には主人公の力ですべて解決してハッピー。

しばらくコードゴルフをした。「アルゴリズムと数学　演習問題集」で金曜日飛ばした問題からいくつか解いた。幾何の問題で、線分と点の距離を求めることになって、場合分けが多くて面倒かと思っていたらかなりきれいに書けた。簡単のため、原点と点 $a(\vec{a})$ を結ぶ線分と、点 $b(\vec{b})$ を考えることにしよう。まず点から線分（を延長した直線）に降ろした垂線の足を求めることになる。これは $\vec{a}$ と $\vec{b}$ がなす角を $\theta$ とすれば、原点から点 $a$ の方向に $|\vec{b}|\cos\theta$ だけ進んだ位置になる。点 $a$ までの距離に対する割合に直せば、 $|\vec{b}|\cos\theta/|\vec{a}|=\vec{a}\cdot\vec{b}/|\vec{a}|^2$ になるので、この値に $\vec{a}$ を掛ければ求まる。今回は直線ではなく線分を考えるので、垂線の足がはみ出す場合をケアしなければならない。実はこれも、先ほど出した割合を $0$ と $1$ でclampすればよいだけ。肝心の割合も、 $a$ と $b$ をそれぞれ複素数と見ると、なんと ${\rm Re}\;b/a$ で求まってしまう。逆にここまで単純化すれば、やっていたことが「線分を単位長に合わせつつ実軸に揃える」→「点から実軸に降ろした足を見る」だけだったとわかる。