週記（2023/10/30-2023/11/05）

10/30(月)

午後4時過ぎ起床。半からインターン先定例会に参加した。

先週の1on1では今後の予定を立てたが、それから金土日と相変わらずずっと学習を回していた。今週からぼちぼち実装に取り組んでいきたい。というかむしろ、金曜日が祝日でセミナーが休みとなった今週しかタイミングがないような気もする。

勉強会はAHC025の話。重みを推定すると一口に言ってもやり方はいろいろあるらしい。今日聞いた方法は、重みの列をN次元の点、クエリの回答を超平面による空間の分割だと思って、クエリを聞くたびに得られた超平面の法線ベクトルに沿って点を遠ざけることを繰り返し、収束させるというものだった。面白い。

解散後、学食に行って夕食を摂った。閉店間際の少ない選択肢からうまく組み合わせて一日分のミールカード1200円分をほぼピッタリ使い切ることに成功したが、唐揚げ丼に加えカレーにも唐揚げを乗せたのは完全に余計だった。

帰宅してからは週記を書き、Universal Cup以外を全部埋めて投稿。直後の午後11時半からCF #907 div.2に出た。

Dashboard - Codeforces Round 907 (Div. 2) - Codeforces

Aはデクリメント操作で大小関係を変えられない区間に分割し、それぞれソートされているかチェック。Bはxとして累積MINを更新する点だけ考えてもよい。Cは1種類目の攻撃がちょうど\left\lceil\frac{\sum a}2\right\rceil回であり、残りのモンスターはできるだけまとめて倒していくためaの降順に見る。Dはfとgを決め打って区間を調べたらたった71種類しかなかった。

Eは大変。操作によって減らせるsadnessを求め貪欲に取っていく。sadnessにカウントされるペアの連結成分だけ取り出し、さらに1と1以外でも切って考えた。1と1以外が隣り合っているsadnessについては1のほうに押し付けて考えるのが良い。その結果1が数列の端にあるかどうかで場合分けが必要になった。

Fは簡単。オフラインなので最初に木を作ってしまえる。あとはdfsして、クエリ番号を添え字としたBITに祖先に対するクエリだけ乗せれば値の取得ができる。Eを飛ばした人が多かったようで真面目に前から解いた自分はペナルティ的に少し不利だったが、4位に入った。

www.youtube.com

ハーメルンで「TS転生したので幼馴染系ヒロインムーブする」を読了。いい感じの幼馴染ものだった。TS要素についてはこの作品に限らずあまり気にしていない。避けはしないし、特に好みもしない。

syosetu.org

シャワーを浴びてゴミを出した後、布団でしばらくラノベを読んで寝た。午前10時半だった。

10/31(火)

午後9時起床。しばらく布団でネット小説を読んでいた。

Yandex CupのQualificationを通過できたようだ。結局通過基準はよくわからなかったが、少なくとも他大会のQualとは違い完数ではなく順位で決まるようだ。以下のコメントによれば最初3問を解いただけでは不十分とのこと。

https://codeforces.com/blog/entry/121128?#comment-1082037

朝までかけてラノベ「魔術探偵・時崎狂三の事件簿」を読了。デート・ア・ライブのスピンオフで本編終了後の話。大学生になった精霊たちが描かれ、それだけで最高だった。口絵も非常に良い。霊装姿の狂三は本編でも何度も見たが、精霊から人間に戻って左目の時計も消えた状態だと印象がガラッと変わる。具体的にはコスプレっぽくなっていた。ここは話にも関係してくる。

内容としては……実は勝手にデート・ア・ライブ要素が強めであることを期待していたのだが、違った。思ったより真面目にミステリをやっている。しかし魔術が強すぎてちゃんとしたミステリにはなっていないので、中途半端な印象を受けてしまった。狂三主人公のスピンオフとしては完璧だと思う。

マット素材表紙だったのが目新しかった。記憶している限りでは、他には「アサシンズプライド」シリーズしか思い当たらない。

昼まで日記を書いた後購買に行き、ラノベやお菓子を買ってきた。昼食も摂るつもりだったがうっかり2限終了とかち合ってしまい、混雑に負けて帰宅。

森見登美彦さんの新作が出るらしい。

少しだけラノベを読んで午後2時就寝。

11/01(水)

午後10時半起床。

10月分の読書記録をツイートした。寝る前に購買で買ってきた15冊は11月分に算入することにした。基本的に起きてから寝るまでを一日と考えているので、このあたりの扱いは正直微妙。前例がなかったか探しに行ったが見つからなかったし、そもそもここの一貫性を気にしても仕方ないなと感じたので、今回はこのようにした。読んだ冊数については昨日の分を数え忘れていたため後から修正した。

布団に横たわり、寝そうになりつつ何とか耐えてラノベを2冊読了した。

「極めて傲慢たる悪役貴族の所業」2巻。相変わらず面白かった、が主人公を振り回すキャラがどんどん増えてきたなという印象。これ以上登場されるとちょっと印象が悪くなってしまいそう。それはそれとして、自分がネットで読んだのはこの少し先までだったはずだから、3巻が楽しみ。

「バスタード・ソードマン」2巻。こちらも相変わらず、という表現になってしまうが面白かった。1巻にもまして主人公のしょうもない日常が描かれていたように思う。その起伏のなさこそがこの作品の持ち味ではないか。こう書くとなぜ自分がこんなに面白いと思っているのかよく分からなくなってくる。主人公が隠している実力の気配に惹かれているのかもしれない。

今日は混雑する前に学食に行った。昼食を摂った後パンを買い込み帰宅、午後1時就寝。

11/02(木)

午後11時起床。相変わらず布団でラノベを読んでいたが、昨日とは違い途中で寝落ちしてしまった。午前4時前だったはず。ここで日記を区切っておく。

11/03(金)

午前6時前起床。

ラノベ「かませ犬から始める天下統一」を読み終えた。組織のボスとして君臨する設定は好みだが、そういう立場と比べて憑依した主人公が小心者すぎると感じた。いや用心深いだけかもしれない……ここを区別するのは不可能だろう。外面は完璧だから良いとして、内心でももうちょっと堂々とした様子を見せてくれるとより嬉しいという自分の嗜好の話。

先週金曜日のSRM850-Easyのリジャッジが完了していたため、週記の該当部分に追記しておいた。その後2時間ほどインターン関連のコーディングを行い、プログラムの実行を待つ状態になったところで切り上げた。

午後2時外出。まず大戸屋で食事した。今日から始まったらしい初冬メニューから、鶏肉と白菜の麻辣土鍋定食。辛くておいしい。ちょこんと乗っている生姜と一緒に食べると、バンコクで食べたハーブの効いた鍋を思い出す味になった。

ゲーセンで8クレだけ遊んだ。チュウニズムデュエルを終わらせるのがメインで、以前詰め切れなかった14+も触った。「Odin」だけSSSが出ずに終わった。先週プレイしたときより鍵盤が下手になっている気がする。

午後6時くらいに帰宅してシャワーを浴びた。冬の乾燥に顔面が耐えられないため薬局でニベアの高保湿乳液を買ってきて、今使ってみたが、自分の身近に出現するとは思わなかったいい香りが漂って気分が高揚した。

午後7時から2時間ほど仮眠して、午後9時20分からyukicoder 411に出た。

yukicoder contest 411 オムニバスコンテスト - yukicoder

Aはサンプルからエスパーすると偶奇が等しければOK。Bは二分探索。Cは選ぶ行数を全探索したが、選ばない行を考えたほうが分かりやすそう。またK=0という存在しないケースに対処していて微妙にタイムロスした。Dは操作を逆から考えて、最後に残す要素の左右に何個要素があるかを状態としてdp。

Eは直前の行に秘宝をいくつ埋めたかという情報だけで、つまりどこに埋めたかに依らず遷移が書けてしまう。正直半信半疑だったが、適当に考えた係数で計算したらサンプルが一発で合ってびっくりした。

Fはイエローカードを1枚提示された選手が何人いるかを状態としてdp。この情報から退場になった選手の人数もわかる。Gは頭を使うのが面倒だったためサイクルグラフの彩色多項式をググって計算した。Hは木dp。

全完9位。速度でも9位だったらしい。DとEで少し詰まってしまい残りの問題の順位がひどいことになった。

Yandex CupのQualのupsolveが可能になっていたので、書いてあったFのコードを提出しておいた。無事AC。やはりStern-Brocot tree上の探索を\log一つで行うことが求められていたようだ。これを区別しようとしてくるのも、実際区別されてしまったのもすごい。

https://contest.yandex.com/contest/54452/run-report/95793857/

午後11時半からECR157に出た。

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

Aはy\le xやx+k\lt yなどで3種類に場合分け。すべてサンプルに含まれており優しかった。Bはx座標にする数とy座標にする数を決めたら両方ソートして辿るのが良い。この時の長さが最小化されるのは、a自体をソートして前半と後半で分割したときである。Cはs_iとs_jの長さの組を全探索。それぞれ必要な処理が微妙に違うのを見落としてサンプル1が合わず、少し手こずった。

Dはb_1を決めると全部確定する。桁ごとに見て、そのbitが立っている数の個数が0\dots n-1の順列として相応しくなるように、b_1の該当するbitを立てるか下ろすか決めればよい。どちらでもよいというケースもある。

Eはdefenceの値ができるだけ大きなカードを出すべき。自分が出すカードを決めるごとにこの戦略を相手と自分で1回ずつ行うと、次に出すことになるdefenceの値が確定する。これを辿ると勝つか負けるかループに入るかわかる。

Fは面白かった。隣接項の差がk以下であるような数列のうち、最小値がx+k未満かつ最大値がx以上のものを数えればよい。最小値がx+k未満であるような列は階差数列(2k+1)^{n-1}通りと最小値x+k通りの積で数え上げられる。ここから最大値がx未満の数列を行列累乗で求めて引けば求まる。

Gは解けなかった。文字列を後ろから見て、見ている位置より左にある赤い1の数を変数と見て利得を書き表すと、下に凸な関数となってslope trickが使えそうな形になる。文字0は傾きが変化する点をr-bに一つ追加することで表現できる。文字1は傾きの変化点のうち大きいほうからr-b個をデクリメントすることで表現できるようだが、ここを高速に計算する方法が全く分からなかった。

6完14位。

www.youtube.com

このタイミングでDMOJのコンテストに参加した。来週火曜日までなので、感想は来週の週記で。

Singularity Cup - DMOJ: Modern Online Judge

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

11/04(土)

午後5時起床。コンテスト開始ギリギリまで寝ようとしたが、思ったより空腹だったので起きて食事を摂った。

午後6時からYandex Cup Algorithm部門のSemifinalに参加した。

https://contest.yandex.com/contest/54740

Aは少し昔のAGC-Aを思い出すようなパズル。とりあえずa=6は必要条件で、対称になるよう間に挟むとbが2の倍数か3の倍数なら作れる。実はこの二つは組み合わせることができて、b\ne 1なら必ず作れてしまう。とまあわかってしまえば簡単だが3WAも出してしまった。

Bは典型。2乗のことを桁を二つ選んだ積の和だと思って分解する。

Cは面白かった。説明のためartistによる絵をa_1,\dots,a_N、NNによる絵をb_1,\dots,b_Nとする。a_iが全体でK番目以降にある条件はa_i\gt b_{K-i}であるから、これをもとに二分探索して条件を満たす最小のインデックスiを求める。

bのほうでも同様のことを行いたいが、実はa_{i-1}\lt b_{K-i+1}より求めるインデックスはK-i+1だと判明している。あとはこの二つを比較して小さいほうを出力。数列の前後に\pm\inftyが並んでいると思えば端のほうでも全く同様に処理することができる。

Dは簡単だった。区間と一切交わらないサイクルだけ抜き出したときの頂点番号の最小値、あるいはnが答えとなる。lを固定したとすると、区間とサイクルの交差はサイクルごとにl以降で最も近い頂点だけ見ればよいから、そこにサイクルの頂点番号の最小値を乗せたセグ木でrより右の区間MINを取ることで交差しないサイクルだけ抜き出せる。lを昇順に見ればセグ木を更新していけて、lより左で完結するサイクルと合わせて答えが求まる。

Eは解けたと思うがデバッグが間に合わなかった。まず問題文が読めない。最初はサンプルからエスパーしてbがaの部分列として出現するか調べるコードを提出し、WAだった。以下では改めて読みなおした解釈に基づく解法を説明する。まだupsolveが不可能なので合っているかは不明。

aの連続部分列a_i\dots a_{i+k-1}であってa_i\ge b_1、a_{i+1\dots i+k-2}=b_{2\dots k-1}、a_{i+k-1}\ge b_kを満たすようなものが存在するか判定すればよいはず。k=1は簡単なので省き、k\ge 2とする。

条件のうち真ん中の部分はaのsuffixとb_{2\dots k}のLCPで書けて、それに末項を加えた場合a_{i+k-1}=b_kならLCPがk-1以上、a_{i+k-1}\gt b_kならLCPがk-2以上かつ辞書順でaのsuffixのほうが大きければよい。

これを満たすようなaのsuffixはSuffix Arrayにおいて区間をなすから、それを特定した上でa_iとして可能な最大値を求め、b_1以上であるか判定する。ここはSuffix Arrayでa_{i+1\dots N}が現れる位置にa_iを持ったセグ木で区間MAXを取得すればよい。

4完で30位弱だったはずが、後から確認したらなぜかペナルティ無視で順位が再計算され19位と表示されていた。決勝進出か……？しかしルールではペナルティを含めて計算することになっているから謎。結果は11/15までにアナウンスされるとのことなのでそれを待ちたい。ところでそれから12/02の決勝まで2週間ちょっとでカザフスタンに集合するのは普通に無理だと思う。

Rules — Yandex Cup

シャワーを浴びて午後9時からABC327に出た。

HHKB Programming Contest 2023(AtCoder Beginner Contest 327) - AtCoder

Aはsed。FAだった。Bはオーバーフローに気を遣うのが面倒だったためRubyで書いた。Cは最近頻出の実装ゲー。Dは二部グラフ判定。

Eはkを決め打つと\sum(0.9)^{k-i}Q_iに関する一次関数になるから、ここをdpで最大化すればよい。遷移は0.9を掛けて新しいパフォーマンスを足すことによって行えるが、これはレートの計算に関する知識があれば式をじっくり見なくても直感で導ける。

Fは時刻を平面操作で、座標を遅延セグ木で処理。座標Xに落ちてくるりんごがあることとLがX-W\lt L\le Xを満たすことは同値なので、区間ADDでLに対して得られるりんごを数えられる。実はつい昨日TwitterでStarry Sky Treeの話をしていたのだが、その由来となった問題「Starry Sky」と同じアイディアだった。

starry_sky - 星空 (Starry Sky)

6完まで15分13秒と最速だったのにGに手も足も出なかった。22位。Eはdp配列を適当に-\inftyで埋めているとそこからの遷移が正しい値に勝ってしまいWAとなるようだ。なんとなく回避していて助かった。

コードゴルフは、Aは最初のsedがそのまま最短らしく、BはNibblesで書いて負け。CでRubyを使いSageMathにあるらしい数独ソルバに勝とうとしたが、テストケースハックを含めても届かなかった。

www.youtube.com

食事した後YouTubeを見て時間を過ごし、午前2時からMHC R3に参加した。

Meta Hacker Cup - 2023 - Round 3

Aは連結成分のサイズを列挙した後Nの約数Kに対して実際に分割できるかチェックしたい。これは全探索するしかないように見える。解が見つかったら終了するとか、途中で多重集合として同じ分割に到達したらやめるとかの基本的な高速化を入れてランダムケースを試すとそこそこ高速に見つかったので、祈ってfull inputで実行。爆速だった。

BはAがデカくてびっくりしてしまうがM\le 5000なことに注意。つまりハッシュとしてあり得るのはH:=8192未満であり、それぞれ作れるかどうか探索すればよい。単純にbool値のdpをするとO(N^2H)になり、各ハッシュを最速でどのインデックスまでに作れるか調べると遷移の列挙と合わせてO(H^2+N^2)になる。

このテクは少し前のCFの別解と同じ。数列から連続部分列をたくさん取り出してXORを計算するという問題設定が似ていてすぐ思い出せた。XORが登場するのは状態数を押さえるためであり、本質的なのは連続部分列として使わない要素があってもよいという点。普段連続部分列に「分割」ばかりしているのでなかなか気づけない。

Problem - E - Codeforces

Cはこのセットで一番面白い。二人の経路が交差する様子を観察すると、左上から入って、直線状にしばらく同じ移動をし、右下に抜けていくようになっている。つまりPlanktonの経路のうち極大な直線部分を取り出すと、そこと交差する移動は経路の他の部分に邪魔されず、またどこから入ってどこに出ていけるかも分かる。

入る前と出た後を前計算しておくことにより飴をどれだけ集められるかが求まるので、これをもとに直線をジグザグにつなぐdpをする。状態数O(RC)、遷移がO(R+C)個。自分は判定問題を解いてしまったためここに\logがついた。

ここまで解いて順位表を見たらDがめちゃくちゃ提出されていてひっくり返った。実際簡単。uとvを固定すると、uからv以外の方向にそれぞれ進んだとき取れるパスの長さの列とvに関する同様のものを求め、降順ソートして対応する値の\minの和が個数となる。

この列は「v以外の方向」という条件を無視すると全方位木dpで前計算できて、舐めるときにvの方向をスキップすればよい。つまり計算はuとvの次数の\minに対する線形時間。すべての辺uvについてこの和を取ると、一般論として辺数MのグラフでO(M\sqrt M)になる。次数を\sqrt Mで分けるテクで示せる。木ならO(N)まで落ちるが、いずれにせよ十分高速。

https://codeforces.com/blog/entry/122011?#comment-1083147

Eはギャグで、結論から言えばパスグラフが最適。最適なグラフにもし次数3以上の頂点があったら、そこに生えているパスを2本取って片方をもう片方に繋げても損しない。similarityに新たに寄与した部分木を適当に組み替え、寄与しなくなった部分木を単射となるよう取ることで示した。示していても度胸試し感は拭えなかったが、validation inputはそこそこ強そうだった。

2時間弱で全問提出した後はそわそわしながら日記を書いていた。結果は……全完！8位！MHC Final Round初出場である。結果が怪しいYandex Cupとは違いこちらは確定と思ってよいだろう。オンライン開催なので参加のハードルも低い。

結局全完は49人も出ていた。決勝進出者を決めるセットの難易度としては見劣りする印象。ただこういう速度勝負だったからこそ自分が勝てたという側面もある。

Aは探索の状態数が分割数で押さえられるので十分高速ということだったらしい。つまり解が見つかったら終了するという処理は不要であり、そのもとでM=0を試しておけばコードに自信を持てたはず。Eはどんな木にもパスが\binom{N+1}2本含まれるところから直ちに従うようで、これを思いついていたら本当にギャグだった。

その後も日記を書き続け、午前9時就寝。

11/05(日)

午後2時起床。しばらく布団でうごめいてからPCに向かい、撮影の準備を整えて午後3時からAHC026に出た。

Toyota Programming Contest 2023#6（AtCoder Heuristic Contest 026） - AtCoder

最初に提出したのは、次に取り出す箱の上にあるものを全部一気に動かす貪欲だった。動かす先は最小値が最大となる山。これが1356657点で、わかりやすい解法だから貪欲のベースラインになったようだ。ただ今回はAHC021とは違いあまり強くないし、最上位には全く違う解法が来ていた。

ここから自分は最後まで上の箱をどかす方法をいろいろ試していた。完全に貪欲のみである。まず小さい値が上のほうにあると嬉しそうだったので、上から見た時の累積MINで分割して逆順に積んでいくことにした。1384343点。全部同じ山に積むと箱が多すぎる山ができて嬉しくなさそうだったので、均等に振り分けてみた。1381809点で減少。

操作前の山の最小値を計算しておいて、それがギリギリ上回る山を狙って置いてみた。まとめて動かせないから強くないかと思ったが1401977点が出て1位に立った。これが強すぎて1時間ほど何をやっても点数が伸びない。終盤空き山が増えてきたときにバラバラに置くようにすることで1402010点と微増した。

最初に行き先の山を決めているが、当然動かしている途中で行き先を変えてもよい。自分より後に取り出す荷物の行き先になっていない山だけ見て、新たに積んだ値も考慮した最小値で行き先を再検討してみた。これで1402579点。実は実装にバグがあってちゃんと最小値が計算できていない。しかし修正すると点数が落ちてしまった。

この修正をするかしないかなどいろいろ実装していた途中の処理を全部試し、得点の最大値を計算するようにしてみた。どうせそんなに伸びないだろうと思ってこれまで解法一つだけで勝負していたが、上のバグを修正するかしないかで結構点数にばらつきがあったため実装。出すと1402916点に伸びた。

行き先を決めたら同じ行き先の要素をまとめて動かしているが、これを累積MINで分割して逆順に積んでいくことにした。すると1403501点と思ったより伸びた。あとは少し試す処理を増やし、1403535点が最終結果となった。

19位でパフォーマンス2568、レートは2239→2313(+74)。実は録画していて、結果が良かったので投稿した。

www.youtube.com

最上位は山ごとにソートしていたらしい。まったく違う解法であるが、ビジュアライザを見ていると自分の解法も山の上のほうは自然とソートされていくようだ。また1手先読みして貪欲法による結果で評価するなどでももっと高いスコアが出るとのこと。

転倒数については結構考えていたが、最終的にはこれで評価しても強くないという結論に落ち着いた。転倒数を小さくしてもまとめて動かせるようになるだけなので、箱をk個動かしたときの体力消費量k+1について+1の部分しか減らせない。それよりは山の最小値の上により大きな値を積まないようにするべきなのだ。1401977点解法の強みはここであると認識している。

途中1位に立ったからかwataさんにコードを読まれていたらしくびっくりした。

仮眠のため午後9時に布団に入ったが、うっかり1時間ほどカクヨムに溶かしてしまった。寝落ちして、午後11時半起床。午前0時からUniversal Cup 8回目、Guilinセットに出た。

The 2nd Universal Cup. Stage 8: Guilin - Dashboard - Contest - QOJ.ac

チームでMGKCHBIJEDをこの順に解いて10完9位。自分はMKCHEDを解いた。

まずMを読んだら自明だったので解いた。GにACが出たのでNyaanさんが読みに行って解いた。KにもACが出たので自分が読みに行って、これもやるだけ。やるだけと言いつつmが大きいケースと小さいケースの境界の設定については何度かテストして決めなければ分からなかった。

risujirohさんがBの実装に入ったのを横目にCを考えたら、解けた。選んだ部分列のLCMがXORの約数であるという条件は、XORが0であるか、またはLCMとXORとMAXが等しいことと同値。XORが0の部分列を数え上げるのは基底を数えるのと同じだとNyaanさんに教えてもらった。基底の数が少ないので後者もMAXごとに求められる。PCを空けてもらって実装、AC。

ここからしばらくはrisujirohさんのB、自分がNyaanさんから考察を引き継いだH、NyaanさんのIが全部WAになる苦しい時間だった。

まずHが通った。砂糖がちょうどk個でなくても、k個以上かつ偶奇が等しい連結成分が取れればそこから葉を切り落とすことでちょうどのものを作れる。よってそれを数えた。これまで取った個数と今残っている砂糖の個数のペアを最大化する、砂糖の個数の偶奇も状態にした木dp。連結成分はLCAを見ているタイミングで取るので、その下の砂糖は全部無視してよい。連結成分を取ったり、あるいは捨てたりするときの遷移が正しくなかった。砂糖が0個になるので状態は偶数のほうに持たなければならない。

その後BとIも無事通った。自分はEに取り組んでいて、判定が頻度配列を左から舐めるdpで行えるのでこの遷移をセグ木に載せればよいという方針を立てた。順子の二つ目と三つ目、雀頭を取ったか否かで3^2\times 2=18状態。ところが頭が壊れていて、遷移がある状態を別の状態あるいは不可能状態に移すという風に書けると勘違いしており、それを列挙し番号をつけることでセグ木のノードのマージを高速化しなければならないと思っていた。

書き始めてから気付いてPCを空けたらrisujirohさんによってJが通された。実は18\times 18のbool行列を持って行列積でマージしても通るんじゃないか？と思っていたので、もう一回PCを貰って書いたらランダムケースで爆速。出したら普通に通った。何をしたい問題だったのか不明。

その後は全員でDを考えていた。例えばX座標が互いに2以上離れていた場合、平面の下のほうに\max a本の線分を並行に作り、適当な本数だけ∧みたいに持ってくることで構築できる。X軸ではなく適当な傾きの直線に射影しても同じことはできないか、という方針。

射影すると分かりづらいが下ろしてくる垂線のほうで考えるとやりやすい。垂線は傾きから決まる整数の組(a,b)についてax+by=kという式になり、このkが互いに2以上離れていればよい、とかなり綺麗に整理できた。正確にはその間に引く直線上にも格子点がなければならないので、aとbは互いに素になるように取りたい。(a,b)=(10^4,3)を用いた。

あとはrisujirohさんのAとNyaanさんのJを応援していた。Jはちょっと前にTLで話題になった話でWikipediaに考察が書いてあるが、円分多項式をどう分けてよいか分からないとのこと。Aは残っている木の中心と直径に加え、点がいくつか消えている方向が高々一つだけあるはずなので、その情報を持てばdpが書けそうらしい。自分も同意していた。しかし実装が難しい。結局1時間半椅子を温めて終わった。

シチャーマンのサイコロ - Wikipedia

感想戦。Gはまあ簡単枠だった。Bはかなり苦しまれており、コンテスト中は大変そうだなあと遠巻きにしていた。結局大きいほうからm個を対応させることになって、必要なインクリメントの回数より余る要素のほうが多い間、最小値にインクリメントして捨てることを繰り返せばよいとのこと。ここで「必要なインクリメントの回数」が途中で変わるケースにハマっていたそうだ。話を聞いていた自分もまんまと同じ嘘解法を生やしてしまった。どうしようもない。

IはMEXを決め打ったらそれを含まない極大な区間を取ってよい。MEXが大きすぎても答えには寄与しない。これでRange Set Queryになり、ABCから窃盗して解いたそうだ。Jはどれだけずれるか全探索すると、AのsuffixとBのprefix、BのsuffixとAのprefixを辿る問題になる。AやBを頂点だと思うとハミルトン閉路問題になるが、辺だと思うとオイラー閉路問題になって解けるというテク。

F - Range Set Query

午前6時解散。食事とシャワーを済ませた後は日記を書いていた。正午前に就寝。