09/04(月)

午後4時半前に起床。インターン先定例会に参加した。進捗報告はあまり時間がなかったので「少しだけ進んでいます」と何の具体性もないことを言った。この少しというのは昨日寝る前に稼働した分である。

チラッとTLを見たら言語アップデートがされたとのツイートが目に入った。過去の問題を開いてみると確かに最新の言語が使えるようになっている。一昔前なら即座に何もかも忘れてコードゴルフに没頭していただろうが、今はちょっと……時間もモチベもない。特に何もせず会議に戻った。

勉強会は声について、特に機材と喋り方の話だった。オーディオインターフェイスや専用マイクに少しお金をかけるのはありかもしれない。喋り方の改善はかなり大変そうだから、もし本格的にやるなら一人ではなくボイトレに通うべき。語尾が速くなってしまいがちとのことだがこれは自分にも当てはまりそう。どうせイントネーションから聞き手側が補完できるだろうと思い、尻切れとんぼな話し方をしてしまうことがある。

解散後はずっと先週の週記を書いていた。週記を書く上で大変なのは本の感想とコンテストの感想で、前者は量はそこまででもないが文章に悩むことが多く、後者は逆に文章にはあまり詰まらないものの量が多い。普段は本の感想を優先して書いているが今回は時系列順に書いてみた。するとタイピングするのと文章を考えるのがちょうどいいバランスになって、集中が長く持続しよく書き進められたように思う。

日付が変わる直前に投稿。その後ABC関連を書き足し、残すはUCのみとなった。今日書き始めた時点ではかなりの量の穴あきがあったので、ここまで埋められたのには驚き。

急激に眠くなったので逆らわず布団に入り、午前2時半就寝。

09/05(火)

午前6時半くらいに目を覚ました。1時間ちょっと二度寝を試みていたが寝付けなかったので、シャワーを浴びてPCの前に座った。

AtCoderの言語アップデートスプレッドシートを参考にNibblesの環境構築をした。普通にGitHubから落としてきてコンパイルするだけかと思っていたら失敗する。手元のGHCのバージョンを確認すると太古の昔の8.4.2だった。これは2018年4月のバージョンだからPC購入時に入れたきりだったらしい。更新しようにも当時どうやって入れたか覚えていなかったのでやり直し。

スプレッドシートに合わせGHUupを使うことにした。本当はこの前に直接バイナリを落としてきたのだが、ライブラリを入れるためのCabalがなかったのでこちらに切り替えたという経緯がある。これでインストールしても失敗、スプレッドシートの方法を愚直に再現してバージョン8.10.7を指定してもまた失敗だった。

GHCup

理由はすべて同じで、import Stateが動かない。このStateとはControl.Monad.Stateのことだと思ったので、コードを全部書き換えてもう一度やってみた。詰まっていた部分を乗り越えて興奮したものの、ほどなく型のambiguityでエラー。この解決は自分のHaskell力では完全に不可能である。

これまではWindowsのCygwin上でやっていたので、Ubuntu機でも同じことをしてみた。バージョン指定なしだと同じエラー、ちゃんと8.10.7を指定すると確かにうまくいく。どうやらCygwinのほうではバージョン指定がうまくいっていないようだ。ghc -vで調べると確かに最新のコンパイラが使われたままになっていて、ghcup set ghc 8.10.7としてから再度コンパイルすることでついに成功した。

次にコンパイルコマンドを整備する。実行ファイル生成までにいろいろなファイルをまき散らすので、専用のディレクトリを用意してその中で作業することにした。シェルスクリプトを起動するとそこに移動して引数で渡されたファイルを処理する。HaskellのopenFileが絶対パスを読めなかったが、渡されたファイルをコピーしてくることで対処した。

整備したNibblesを使ってしばらくコードゴルフをした。最近のABCのC問題くらいまで。書いた問題が軒並み大幅に縮むのでキリがない。

昼過ぎに購買に行った。体調を崩したのは先週木曜日で、それから5日経過したから出かけても大丈夫だろう……と思っていたが、コロナへの対応としては発症日を0日目として5日間は外出を控えるべしとのことだから今日はギリギリ5日目だったらしい。まあ症状は特にないし行動制限の制度もすでに存在しないため許してほしい。お菓子、総菜パン、ラノベを買ってきた。

またコードゴルフ。午後5時半から3時間ほどは仮眠を取っていた。起きてからもコードゴルフを続け、午後10時からはUniversal Cup 2回目に参加した。

書く

感想戦後はラノベを読んでいた。「最強の力を持ってしまった幼なじみの2人、ダンジョンにて全力で蹴落とし合う」を読了。面白かった。恋愛感情など生じようもないくらい気心の知れた男女というものが実は大好物で、どうやらそういう設定らしいから購入したところ、あまりにも期待通りで完璧な関係性だった。外面が非常に良いというのも好み。

ほとんど主人公の一人称視点で進むので、恋愛感情のないヒロインとの間には甘酸っぱいシーンなど存在しない。その徹底っぷりが嬉しかった。一方、二人の距離感が近すぎて傍からはイチャイチャしているように見られているらしい。台詞で触れられるのみだったが別の人の視点からも読んでみたいなという気持ちがある。またこの巻ではダンジョン要素がそれほどなかったので、今後はそちらにも期待したい。

そこからコードゴルフして午前11時就寝。

09/06(水)

午後6時前に目を覚ましたらホスフィンからDMが届いていて、以下の記事のチェックを行った。以前から書いているとは聞いていたが無事完成したようで何より。自分とたいぺーで読んでも特に問題なかったので、その後そのまま公開された。

mine691.hatenablog.com

ハーメルンで「依存症な彼女たち」の更新が来ていたため読み、ついでに何気なく感想を確認したところ、ラノベの新刊予定にこの作品らしきものがあったとの投稿を目にした。探したところ確かに発見。書籍化するらしい。正式発表の前にこういう形で知ってしまったのを申し訳なく思う気持ちはあるが、ともかくめでたい。

syosetu.org

www.kadokawa.co.jp

ラノベを読んだ。「ガリ勉くんと裏アカさん」2巻。前半は怒涛のようにお色気シーンが続いたが、後半には裏垢の身バレという驚くべき展開が待ち受けていた。ラストシーンは丸く収まったような雰囲気になっているものの、冷静になると何も解決していない。解決していないからよくないというわけではなく、ここからシリーズが続くとしたらどんな展開になるのだろうかという興味がある。まあ一応第一部完ということらしい。

次のラノベを手に取ったが急激な眠気に襲われ、逆らわず就寝。午後9時から午前1時半まで寝ていた。

起きて「最強魔法師の隠遁計画」17巻を読了。12巻を読んだときに以下のような感想を残していて、確かこれはテンブラム編に対する言及だったと思うが、それが今になってようやく進み始めた。その間はずっと書籍オリジナルのストーリーだったはず。ようやくか……という思いが強い。

「最強魔法師の隠遁計画12」。この巻からしばらくは、Web版で僕が一番辛かったところであるような記憶がある。
週記（2021/03/22-2021/03/28） - kotatsugameの日記

テンブラム編の敵キャラ・アイルはヒロインの唇を奪うという全く受け入れられないことをしでかしたため、自分はかなり嫌っている。その描写は書籍版でもWEB版からあまり変わっていなかったはずで、学園祭中だから8巻あるいは9巻か。もう十分待ったのでとっとと破滅してほしいが、一筋縄ではいかなそうな雰囲気が濃厚だから下手したらまだ数巻かかるのかもしれない。

布団から出て一瞬だけコードゴルフをした。ABC318BはCartesian productとuniqでかなりシンプルに書けるのにTLEが取れない。コンパイル言語のくせに何が遅いのだろうと不思議に思っていたが、どうやらuniqが遅いらしい。そういえばgroup byでも重複を除いた要素数を求めるには十分だなと思って試しに使ってみたら爆速になってびっくりした。uniqを使うと許されなかったImplicit Argsも使えて良いことづくめである。

実装など調べたところHaskellのnubが遅いという結論になった。Ordでない型でも使えるよう、要素ごとにこれまで登場したか線形探索しているとのこと。どうせNibblesで扱えるデータはすべてOrdなのだから実装を変えればいいのに……と思う。思うだけでIssueを立てたりする気力はない。

oropon.hatenablog.com

atcoder.jp

シャワーを浴びて少し日記を書いた後布団に戻った。眠気を待ちつつラノベを読んでいたが、睡眠時間が3時間程度になりそうだったので寝るのを諦めた。

正午くらいに学食に行ったらサークル活動をしている学生でめちゃくちゃ混んでいてびっくりしてしまった。昼食を摂り、コンビニに寄って帰宅。コンビニは昨日の大雨で床が水浸しになった様子だった。

午後1時からオンラインでのセミナー。今日は来年こちらの大学院へ進学することが決定した学生による、最近勉強していたことの発表だった。グラフ理論を使う問題設定はあるが基本的に確率論の話なのでちょっとついていくのが大変。自分でもいくらか計算してみて今日やった範囲は納得できたと思う。ただ、質問する前に自己解決してしまったので無言で発表を聞いているだけになった。

2時間ほどで発表が終わった後、次の2時間くらいは先生と1対1で修論に関して話した。自分は今のテーマに結構興味があるはずなのだが、面白いからという理由だけでそのテーマの意義はうまく説明できない。進捗もないようだし基本に立ち返ってもうちょっとわかりやすいテーマを探したらどうかという提案をされた。これから行ってみたい計算はいくつかあるものの、それらを一通りこなしたら方針転換することになるかもしれない。そのような時間はあるのか。

解散して午後5時半就寝。

09/07(木)

午後10時起床。しばらく布団でスマホを弄った後、起きて食事し、午後11時半からCF #895 div.3に出た。

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

Aは $|a-b|/2$ を $c$ で割ってceil。Bは二分探索したが、すべての $i$ に対し $k\lt s_i/2+d_i$ を満たす最大の $k$ なので単純に上限のMINを取るだけでよい。Cは基本的に偶数と偶数に分ける方針で、それが不可能なのは $r\le 3$ あるいは $l=r$ が奇数のとき。 $r\le 3$ は不可能。 $l=r$ の場合は最小の素因数を探した。

Dは順列の各インデックスがscoreにどれだけ寄与するか考えると $+1$ がいくつ、 $-1$ がいくつ、残りは $0$ と計算できる。あとは貪欲に置いてよい。Eは遅延セグ木に乗る。Fは辺 $i\rightarrow a_i$ でfunctional graphにするとループごとに一匹だけ売値が倍にならない動物が生まれる。順番の決定は面倒なだけ。

Gはある区間を積で置き換えて値が $n$ 以上になったとき、区間をすべての $a\ge 2$ なる要素を巻き込むように拡大するほうが得になる。そうでない区間は $a\ge 2$ なる要素を $O(\log n)$ 個しか含めないので、適切に1を圧縮しておけば調べるべき区間の数が $O(n\log n)$ 個になる。あとは比較。全体の積だけオーバーフローする可能性があるが、適当に大きな値とのMINを取っても他の区間の積が $n$ 未満なので大小関係は保たれる。

全完8位。

www.youtube.com

ラノベ「バスタード・ソードマン」を読了。「東方遺骸王」の作者がここ1年くらい集中的に更新しているランキング最上位のハーメルンが原作。気になりつつもずっと読むタイミングを見失っていたので書籍を購入した。しみじみと面白かった。主人公はチート持ちでこそあるらしいもののそれを大っぴらに振るう様子も細かい説明もまだない。そうやって実力を隠して行動するのは将来的なカタルシスの前振りに過ぎないと認識していたが、この作品ではその起伏のない日常描写こそが良かった。

シャワーを浴びて日記を書き、午前6時半就寝。昨日何も考えずに生活リズムをぶち壊してしまったが、そういえば明日の昼からAGC格のコンテストがあるのだった。失敗。

09/08(金)

午前11時半起床。微妙に天気が悪かったので歩きで学食に行った。いい眠気覚ましになった。午後1時からWTF2022 day1。

World Tour Finals 2022 Day1（Open Contest） - AtCoder

Aからよくわからない。例えば勇者の攻撃を最大限防ごうとするとモンスターは高々 $A-B$ 体しか倒されない。また攻撃される回数が少ないほうからモンスターを守ろうとすると $B$ 回の防御でカバーできる数だけ生存させることができる。ただしこれらの観察は勇者の攻撃の順番を考慮していない。自分の防御行動に応じて勇者が行動を決めたときどうなるかが全然わからなかった。

しばらく唸ってから順位表を確認したらあり得ないくらいバンバン通されていてひっくり返った。上の二つからそれぞれ得られる答えの下限のMAXを出力したら通ってがっくり。何も証明していない。この時点で順位は60位、普通のAGCならそこまで悪いわけではないが、今回は上位陣がごっそり抜けているため大変まずい状況だった。

Bは辺 $i\rightarrow P_i$ で全体が一つのループになっているときに解ける必要があって、逆にこれができれば適宜 $(l,r)=(1,1)$ を挟むことでどんな $P$ でも可能になる。ループの辺を適切な順序で選んでいけば可能だったりしないか？と考えたが、さすがにそれはないかと考え直し、適当にループを切って再帰する方針で考えを進めた。ちなみに $2,4,1,3$ がループの辺だけ使う方法の反例らしい。

ループを切るときは、前後の操作が支障なく行えるようにできるだけ端のほうで切りたい。そこで左端二つ・右端二つつまり $a,b,\dots,c,d$ がループ上でどの順に並んでいるかを $a\rightarrow c\rightarrow b\rightarrow d\rightarrow a$ と固定してみて、紙とペンでいろいろ試した。

$d$ の直前の要素に対し $P:=c$ と書き換えると、 $c\rightarrow b\rightarrow c$ というループができる。これを再帰的に揃えた後 $P$ を戻すと $a\rightarrow c\rightarrow d\rightarrow a$ になるようだ。ここで右端二つ、 $c$ と $d$ をswapすると $a\rightarrow c\rightarrow a$ となって、これも再帰的に揃えることができる。また操作の区間もちゃんと交差しないようになっている。

この方法を $a,b,c,d$ の順番すべてに対して特定し実装しようとしたがさすがに面倒。もっと統一的な処理を考えたらすぐ見つかった。実は上の処理では、 $a$ と $b$ がどのような順番で並んでいるかなど全く気にしていない。そこで「 $d$ の直前の要素に対し $P:=c$ と書き換えて $c\rightarrow c$ というループを揃える」「 $c$ と $d$ をswapする」「改めて $c\rightarrow c$ というループを揃える」と捉えればどんなケースでもうまくいく。

実装は右端二つではなく左端二つを考えた。まず愚直を書いて正しい操作列が出力されることを確認し、次に高速化。左端2要素を取得するためにはループに含まれる頂点集合を管理できれば十分である。再帰の深さは $O(N)$ なので普通にやると2乗の計算量になってしまうが、マージテクの逆をするとsetへの出し入れも含め $O(N(\log N)^2)$ になる。ループの前半後半のどちらが短いかは、ループを同時に辿って先に終わる方を見ればわかる。こうやってループを分解する方法はTUPC2022Jで出題されて知っていた。

手元で正しく高速に動作することをチェックし、提出してAC。なんと5位に浮上した。

その後はC問題に取り組んでいた。消せる頂点集合の必要十分条件を考えてdpしようとしたがうまくいかず、サンプルを合わせるための条件エスパーに走ってしまってあまり進展がなかった。

結果は2完8位でパフォーマンス3302、レートは2916→2961(+45)。かなり良かった。パフォーマンスが想像以上に低かったが、本来はこの上に10人以上いるはずだったと思えば妥当なところなのかもしれない。

また、500点の速度だけで順位が決まるというようなことにならなくてよかった。最初は500点なんてないほうが良いだろうとさえ考えていたが、蓋を開けてみればなんとも異質……というか、ともかくWTFに相応しくないとはとても言えない問題だったと思う。

AとBの解説をチェックした。Aはやっぱりわからない。丁寧に考え方が紹介されているのに自分の感覚ではうまく飲み込めなかった。Bは天才すぎる。確かめれば実際にそうなっているが……。

www.youtube.com

春から我々のセミナーに参加している海外の学生がついに秋から東北大学に留学してくるらしく、そのチューターを指導教員の先生から依頼されて引き受けた。時給900円はさすがに人を舐めているとしか思えないものの、自分と似た経緯で応募する人は多いのだろう。英会話については不安だが、オンラインならともかく対面で、非言語コミュニケーションも使い倒せばまあ伝わるだろうと楽観視している。

午後9時20分からyukicoder 404に出た。

yukicoder contest 404 - yukicoder

Aはよい。Bは何回目で当たるかの確率を愚直に計算し、定義通りに期待値を求めた。これが等比数列の和になっていることにはまったく気づいていなかったので解説を読んで仰天。Cはimos法で各時刻に演奏している人数を求め、目立ち度の累積和を持って指示ごとに目立ち度への寄与を足した。

Dは全探索。操作を繰り返す部分は、現在束の上から何枚目まで見たことがあるかということを考えればすぐ式が出た。一発で合ったのにはさすがに疑心暗鬼になったが無事AC。

Eは解けなかった。サイクルを取り除きながらdfsしても、取り除いていない辺を何度も見ることになると計算量が抑えられないのではと思っていた。また、入次数と出次数が等しくなるように辺を足してからサイクルに分解し、足した辺を含まないサイクルを削除するということをやってみたが、これはサンプル2で落ちた。

Dまでが速かったのでEが解けなくても10位に入った。直後に解説を見てEをupsolve。見た辺のindexを管理するテク自体はサイクルに分解する時にも使っていたから、あとは「一度見た辺が取り除かれていないならサイクルに含まれないのでもう見なくてよい」ということに気づけていればよかったらしい。通した後に「現在の順位表」を見に行ったらupsolveのスコアが反映されて1位に浮上しており面白かった。

日付が変わったあたりで猛烈な眠気に襲われ即座に就寝。

09/09(土)

午前5時過ぎに目を覚ましてしまった。シャワーを浴びてしばらくラノベを読んでからいざ二度寝しようと思ったら全然寝付けない。結局午前9時まで布団の上でゴロゴロしていた。

正午起床。鬼のように眠い。生活リズムの調整は完全に失敗してしまった。ちょっとした不安を抱きつつ、食事して午後1時からWTF2022 day2。

World Tour Finals 2022 Day2（Open Contest） - AtCoder

Aは論理学の講義で共有知識についての話が出たときに聞いたゲームと似ていた。ただしこの情報は解くのにあまり関係がない。ただ問題の把握はやりやすかったと思う。

3時間ほどずっと規則性を探っていた。一番最初は後ろ数文字で場合分けしていたが、さすがに面倒すぎたのでそこそこで切り上げ、各ラウンドで誰が帽子の色を特定できるか考えていった。ちなみに今から書く考察の具体例には間違いが含まれている。

サンプルの六つ目のprefixBRBRRBRRRを例に説明する。1ラウンド目ではprefixRRRのみが特定できる。2ラウンド目では「7、8、9人目（後ろから3文字）が一致し、6人目とは異なる」と全員が知っているため、その前のRRBが特定できる。3人目が特定できなかったことから全員は新たに「4、5人目が一致して3人目と異なる」と知り、3ラウンド目では同様にRBが特定できる。最後に残った1人目は、先頭3文字がRBBかBRBかわからないのでどうやっても特定できない。

ここから、同じ文字が連続する区間とその前の1文字がペアになってラウンドごとに決まっていくように見えた。知っている情報は帽子の色が同じとか異なるとかだけなので、可能な割り当ては部分和問題を解くことで列挙できて、そこから自分の帽子の色を特定できるか判定できそう。しかしサンプルが合わない。

考察のミスというのは2ラウンド目の回答によって共有された知識である。この言い方だと4、5、6人目がBBBでも全く同じシチュエーションが発生するように見えるが、実はこの時4人目は自分以降にRとBが3文字ずつあって絶対に特定できないことになる。ところが4人目は特定できているのだから、そこからさらに情報を絞り込むことができる。またBBBRRRのようなケースにおいては「同じ文字が連続する区間」でも分割されてしまうため、各ラウンドの回答の変化からは「帽子の色が異なる」ことを判定できない。

ここでしばらく判定方法を変えつついろいろ試してみたが、やはり最後のサンプル二つが鬼門となる。手で計算してもどうなっているのか全然わからない。しかし次第に、ごく特殊なケースでしか適用できない判断がいくつも存在することに感づいた。例えば上に上げた「BBBRRRがあり得ない」というのもその一つである。

ここに至って規則性はないものと結論付け、大胆に方針を転換して愚直にシミュレートを行ってみることにした。人 $i$ にとっての情報はそれだけで独立して扱う必要があるから、「人 $i$ は『人 $j$ より後ろにRが $k$ 個ある可能性がある』と思っている」という感じで管理すればどうだろうか。これを $k\in(i,j)$ と表現する。試しに手で小さいケースを試してみたらうまく計算できそうだったので、実装した。

集合 $(j,j)$ のサイズがちょうど1であるということが、人 $j$ が帽子の色を特定したことに相当する。そしてこのラウンド終了後、人 $j$ が自分の帽子の色を特定できたという事実はそれぞれの人 $i$ が考えている人 $j-1$ の状況に影響する。つまり、 $k\in(i,j-1)$ なら $k-1\in(i,j)$ または $k\in(i,j)$ のはずで、このタイミングで特定できるならどちらか片方しか成り立ってはならず、逆にそうでない $k$ を $(i,j-1)$ から削除できるのである。

実は同様のことが帽子の色を特定できなかった人 $j$ についても行える。つまり、このタイミングで特定できないなら両方成り立っていなければならない。これらの更新は $j$ の昇順に行わなければならないことに注意。降順に行うと同じラウンドの情報が伝播してきてしまう。

また処理の後に $k-1,k\notin(i,j)$ なら $k\notin(i,j-1)$ とかその逆の整合性も保っておく。これでシミュレートしてみたところ、ある程度のprefixについては正しい答えが出るようになった。しかし先頭のほうでは0が続いてしまう。いろいろ考えて、シミュレートのラウンド数が足りないことに気づいた。答えが変化しなくなったらループを止めていたが、情報の伝播に時間がかかるのでちゃんと $N$ ラウンドほど待つ必要がある。

ここを直したら見事にサンプルが合った。あとはbitsetを使って書き換え。整合性を保つ部分のループの回数がよくわからないが、それ以外の部分は $O(TN^4/\mathrm{wordsize})$ になっている。ランダムケースで十分高速に動作することを確かめて提出。無事通ってくれた。

4時間時点でのACとなり結構順位が低い。残り1時間でBに取り組み、実験から「ある値が移動できる範囲は固定された要素を除いて区間になる」「区間が中途半端に重なることはない→包含関係から簡単に数え上げができる」などそれらしいエスパーをいくつかしたものの、肝心の区間が愚直ですら求められず終了した。

結果は1完37位、パフォーマンス2790でレートは2961→2945(-16)。0完太陽を避けられたのだけはよかった。

ここでWTF二日間を通しての感想でも書いておこう。自分は精進をしないので、難しい問題に時間をかけて取り組む経験に乏しいと自覚している。そんな中それの極致みたいなコンテストがRatedで開催されることになって戦々恐々としていたが、蓋を開けてみれば二日目のA問題など4時間唸りつつもちゃんと通すことができた。問題の相性もあるにせよ、こういう体験は自信になる。

問題自体については、取り組んだもの以外はチラッと見ただけなので言えることが少ない。ただ自分が解いた問題に限っても何というか「競技プログラミング」の一段上にあるように感じられた。どれだけ精進してもこんな雰囲気の問題を安定して解けるようにはならないのではないだろうか。すごいコンテストに参加したなあと、終わった今では楽しかったという印象が強く残った。問題が解けたからそう思えるだけかもしれない。

www.youtube.com

ラノベ「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」9巻を読了。シリーズ最終巻。ラスボスの正体が結構驚きのもので、背景設定も壮大で良かった。ただその結末にはあまり納得がいっていない。言ってしまうと、一旦和解したのに別の世界線の主人公に倒されてしまうという……。エピローグは登場人物たちのその後が書き連ねられるという好みの形式で、ここは満足だった。

疲れ果て、ボーっとTLを眺めて過ごしていた。午後9時からABC319に参加。今日から7問らしい。

AtCoder Beginner Contest 319 - AtCoder

Aは面倒なだけ。どう書いても短くならなそう。Bはややこしい条件に混乱しつつ言われたことをその通りに実装した。実は $j=n/\gcd(n,i)$ らしい。Cは順列を全探索して丁寧に条件をチェック。Dは二分探索。Eは周期 $\mathrm{lcm}(1\dots 8)=840$ を持つのでその回数だけ解く。提出したら1000msくらいかかっていてビビった。

Fは大変。薬を飲むより敵を倒すほうを優先してよいので、飲んだ薬の集合と最後に飲んだ薬が分かっていれば新たに訪れられるようになった頂点が特定できる。つまり、祖先に最後に飲んだ薬があるか薬を飲む前は倒せなかった敵がいるような頂点である。よって達成できる強さの最大値を計算するbitDPが可能。遷移のたびに $s$ 最小の頂点に訪れるため優先度付きキューを使って探索するので $O(N\log N)$ かかるが余裕。

Gは頂点1から距離 $k$ の頂点とそこに至る最短パスの本数がわかっているとき、 $O(N+M)$ かけて距離 $k+1$ について計算できる。各頂点についてそれに接続していない頂点を見て、距離 $k$ の頂点の数と最短パスの本数を数えて全体から引けばよい。これを500回くらい回したらWAだったが、距離 $k+1$ の頂点が存在しなくなるまで回したら通った。実は最短パスの長さを $d$ とすると $\binom{d}{2}$ 本くらい存在しない辺があれば十分で $d\le\sqrt{2M}$ くらいでしか評価できないため、650回ほど回さなければならなかったらしい。

1ペナ全完で9位。今日はA、C、Fの実装に苦労して「そういう」セットかと思った。

コードゴルフはAとBのみ。Aは埋め込みを頑張る。Nibblesはコード末尾に16進法で整数を書けるらしく、レートから3480引いた値を379進数として解釈して埋め込んだら結構短くなってくれた。BもNibbles。整数列に文字をappendしたらどちらかが文字コードとして解釈されると思っていたが、試したら普通にto_stringされたので助かった。

www.youtube.com

シャワーを浴びて日記を書き、午前4時就寝。

09/10(日)

午前7時半に目を覚まし、眠れずスマホを触ったりラノベを読んだりしていた。

午後1時からJAG夏合宿のための内部コンテストに参加した。これに関する作業をコンテスト終了後もしばらく続け、午後9時から仮眠に入った。

1時間半ほどで気合いで起床。食事して午後11時からCF #896 div.1に参加した。開始時刻が普段より30分早い。

Dashboard - Codeforces Round 896 (Div. 1) - Codeforces

Aから詰まった。beautyの上界は、 $m$ 個の数のMEXと捉えれば $m$ 、また各 $v$ が $n$ 個の数のMEXつまり $v\le n$ なので $n+1$ という評価もできる。このうち小さいほうを達成できるのではないかと考えた。実際、 $n\lt m$ のとき $n+1$ 列を使って $v=0\dots n$ を作れればよく、これは $0\dots n$ をずらしながら $n$ 行に渡って書き込むことで実現可能。残りの列はどうでもよい。

さらに $n\ge m$ のときは $m-1$ 行を上のように埋め、残りの行に適当にコピーすることで $v=0\dots m-1$ が作れる。 $m=1$ はコーナーケースとして処理すれば、これでbeautyを $\min(m,n+1)$ にすることができた。

B1は大変。 $m=\sum_i a_i/n$ と置くとすべての $a$ を $m$ にするのが目標である。 $a\ne m$ のとき、 $a+2^x-2^y=m$ となるような非負整数 $x,y$ は高々一意に定まるので、これを $x\rightarrow y$ という辺と見てサイクルを作ればよい。 $a=m$ の場合は $x=y$ なら何でもよいのでどこかのサイクルに割り込ませて処理する。

ただしサイクルの最初の人だけは $2^y$ 引かれてから $2^x$ 足されるので、 $a\ge 2^y$ である必要がある。このチェックをかなり頑張っていたが実際には必要ないらしい。後からチェックを省いて出したら通っただけで証明は謎。

B2はさらに大変だった。 $+2^x$ と $-2^y$ のどちらかを削除してもよいことになると、揃え方が一意に定まらなくなる。B1の解法を修正するのは不可能に見えたので、まったく別のアプローチを取った。

2進数で下の桁から順に揃えていくことにする。 $|a-m|$ が奇数なら $\pm 1$ のどちらかを行うことになるが、その後符号が逆の操作しかできなくなるので $|a-m|\ge 3$ ならどちらを行えばよいかは決まる。 $|a-m|=1$ のときはどちらでもよいので、 $\pm 1$ のペアが作れる範囲でできるだけ $|a-m|=0$ となるように操作してみた。実はここは適当に決めてもいいらしい。

最下位桁が揃ったら全体を右に1回シフトして継続する。より下の桁で $\pm 1$ を行った要素はその後 $\mp 1$ しかできないので、そのフラグはしっかり立てておく。最初に操作する人の $a$ が負にならないかのチェックはもはや不可能で、諦めて提出したら通った。

Cは面倒。木に含まれる長さ $L$ のパスについて、 $s\ge x$ となる場合の数は $m^n-(x-1)^{L+1}m^{n-L-1}$ なので、これを $x=1\dots m$ について足し合わせたものがscoreの和に対する寄与となる。 $L\le2\log_2 n$ かつ $m$ の総和に制約がついているので和を取るのは愚直でよい。難しいのは $L$ に対するパスの数え上げとなる。

パスのLCAを固定して数えた。左の子までの距離を全探索し、そのような距離にある頂点を数えて掛け合わせる。とりあえず愚直を書いて合わせてから算数を頑張って高速化した。

例えば頂点 $u$ の左の子以下にある距離 $k\ge 1$ の頂点は区間 $[2u\times 2^{k-1},(2u+1)\times 2^{k-1})$ となる。実際には頂点番号が $n$ 以下の範囲だけ見るため、 $u$ がどんな値かによって頂点数は定数だったり $u$ の一次関数だったりする。これが右の子に対しても起こるため2乗和の公式など持ち出す必要があった。

残り30分ほどしかなくDは間に合わなかった。結果はCまで解いて105位、レートは2935→2869(-66)。自分はAからCまでどれでもかなり苦しんだのに、高速に通している人が多くて愕然とした。

Dのupsolveをした。ひたすら場合分けする問題で、構築の方針は公式解説と同じだったからあまり多くは述べない。終盤の場合分けは2本の長いパスのどこかから余った頂点を生やせるか判定していて、不可能なケースを漏れなく考えるのがなかなか大変だった。 $d=2$ なる頂点が存在しないときは先に $d\gt 2$ の頂点だけでサイクルを作ったので少し楽になっているかもしれない。

www.youtube.com

シャワーを浴びた後、朝方はインターンの作業をしていた。いよいよ機械学習。命名が思いつかずにMyModelとかMyDatasetとかを使ってコードを書いている。このあたりで悩むのはコードが形になってからでよいはず。実行の度いろいろなファイルを読み込むので動作チェックが重く、微妙な待ち時間が辛いフェーズに入った。

少し日記を書いて午前10時半就寝。