04/03(月)

頭の痒みで飛び起き、シャワーを浴びてまたすぐ寝た。午後1時くらいだった。

午後4時半ちょっと前に起床し、すぐにインターン先定例会に参加した。先週はちゃんとコードを書いたのでそれを報告。他の方が報告している間は聞きながら勉強会スライドの仕上げをしていた。

午後5時過ぎから勉強会。発表と質疑応答がそれぞれ1時間くらいだった。終了後にスライドを公開した。

勉強会をしました。今日のテーマは「ACLにおける定数倍高速化」です。スライドを公開します。https://t.co/UCxyBozKzf
— こたつがめ (@kotatsugame_t) 2023年4月3日

単に定数倍高速化テクを列挙しているだけだから、とっ散らかった内容になってしまった。発表する際も話題があちこちへ飛ぶのでやりにくさを感じた。スライドも申し訳程度に文字に色を付けただけだから、もうちょっとやりようはあっただろうなと思う。

しかし質疑応答では結構突っ込んだ話もしていただけて、伝えたいことが伝わっていたと知り一安心。Twitterで公開したらいいねやRTが結構来たのも嬉しかった。スライドの構成云々はもはや関係ないので、単純に内容を評価していただけたんじゃないかと思っている。

その内容について自分のコメントを少し。まずassertに関して、分岐予測が競プロ界隈で話題になったことはほとんどない気がする。実際小手先の改善ではどうしようもないケースが多そうで、予測を効かせられるならいっそ分岐を消してしまうのが確実だからだろうか。

vectorのreserveはまあいつもの話題。emplace_backは使っている人をよく見かけるが個人的にはほとんど効かないと思っていて、ACLにも一切（一切！）使われていなかった。

dequeが遅くてメモリもたくさん食うという話は自分が何度かTLに流している。日記でも触れたことがあるし、今回も話した。結構お気に入りの話題である。

queueはdequeによって実装されている。dequeのほうに問題があるようだ。以下のヘッダファイルがdequeを実装している部分である。2時間ほど格闘して何とか必要な部分が読み解けた。
週記（2022/08/15-2022/08/21） - kotatsugameの日記

最小費用流におけるdijkstraの高速化はかなり面白かった。ポテンシャルの導入によってコスト0の辺が多くなるのに気づいてハッとした。その前は、問題を最小費用流で表現するとコスト0の辺を多く使いがちだからかなと考えていた。それも少しは効いていそう。またゴールにたどり着いた瞬間計算を終了してよい場合push_heapが遅延できるというのは、一般に適用できる方法である。

コンビニに行ってパン・おにぎり・サラダを買い、一部を食べてから先週の週記を書き始めた。日付が変わる直前に投稿したが、週末に参加したコンテスト五つばかりを空欄のまま残している。

投稿後もしばらく書き進めていたが、うっかりハーメルンを開いたらのめり込んでしまった。朝までかけて「輝かせたくて」を読了。

syosetu.org

同作者の「輝きたくて」と世界を共有する、これまた逆行転生のVTuberモノ。しかし逆行の根幹をなす設定が異なっており新鮮だった。「輝きたくて」では未来知識はVTuber関連のもの以外外れていたが、こちらではギャンブルに災害予言と縦横無尽に的中させている。相変わらずこの時期のVTuber騒動には詳しくないものの面白く読めた。

先週の週記にさらに加筆して午前8時就寝。

04/04(火)

午後6時台に起きていたような記憶があるが、二度寝した。

その後午後11時起床。半からCF #863 div.3に出た。

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

Aは左から見て初めて現れる $d$ 未満の数字の直前に挿入するのがよい。

Bはスタートとゴールがそれぞれどのループにあるか計算し、外・内にずれる必要のある回数を答える。計算式でtypoしてしまい少し手間取った。外周から何マスあるか数えた $\min(x,y,n-x+1,n-y+1)$ という式を覚えておきたい。

Cもかなり手間取った。 $b_i$ と $b_{i+1}$ の大小関係によって特定できる $a$ がずれるので、どう処理したものかかなり悩んでいた。しかし実は $a_i=\min(b_{i-1},b_i)$ とすればよい。この式が可能な最大の $a$ を与え、そこから小さくする意味はないから。 $b$ の元となる $a$ は必ず存在するので特にチェックも必要ない。

Dはサンプルの説明の図を見ると黄金螺旋が思い浮かぶ。可能な正方形の組み合わせはこれしかないので、大きいほうから順に $(x,y)$ を含まないように取り除けるかチェックした。

Eは $k$ を9進数表記にし、4以上の文字を一つずつずらしたものが答え。見覚えのある問題だった。

Fは面倒だった。図のように、長さ $k$ のサイクルの各頂点にこれまた長さ $k$ のサイクルがくっついているようなグラフを $k$ -flowerと呼ぶらしい。問題文を読んでも何を出力するのか分からなかったが、Outputの説明を読む限りでは入力されたグラフがある $k$ に対して $k$ -flowerとなるか判定すればよいようだ。

まず $n=k^2$ かつ $m=k(k+1)$ から $k$ を特定できる。その後頂点の次数に注目した。次数4の頂点は長さ $k$ のサイクルをなす必要がある。さらに、次数4の頂点ごとにそこから次数2の頂点に向かって出ている辺がちょうど2本存在し、その頂点間に次数2の頂点による長さ $k-2$ のパスがdisjointに存在しなければならない。以上のチェックを通ればOKである。

Gはそこそこ簡単だった。後ろから見て「そこ以降で作れるniceなパスの最大長」と「その長さを達成する場合の数」を持つ。遷移は $k$ タイル一気に行う。 $k$ タイルのうち一番後ろのタイルを $O(n)$ 通りから試すことで、場合の数とそれ以降のパスの最大長が分かる。長さを更新するなら場合の数をリセットするなどすれば、先ほど挙げた二つの値が求まる。

適当に書いたら $O(n^2)$ になっていたので、とりあえずG1に提出。G2は $n\le 10^5$ とかかなと思っていたら2乗が許される制約だったので、慌てて配列長だけ書き換え提出した。

全完後、今日も動画を撮っていたのでいつものように振り返りをしていたら、Fでパスの長さが $k-2$ であることを確認していないのに気付いたため再提出した。コンテスト終了後に最初の提出をHackしたが、無事再提出したもので穴埋めされ全完は保たれた。しかし他の人がかなり落ちていて怖いので、open hacking phaseが終了するまで動画は公開しないでおきたい。アップロードだけ済ませておいた。

M1秋学期の成績をツイートした。すっかり忘れていた上3月末は学務情報システムがメンテナンスで見られなかった。もう1年の頃のようなひどい成績を取りようがないので何の面白みもないが、せっかく5年続けてきたのでこのまま最後までやり通したい。

単位取得状況 8/8
単位取得率 100%
このツイートいる？いる pic.twitter.com/mDhcZe4xUZ
— こたつがめ (@kotatsugame_t) 2023年4月4日

朝までかけて「28歳フリーターが総理大臣と総選挙で戦ってみた」を読了。セリフや展開に引き込まれる面白い本だった。ラストも劇的。「政治家に期待をした時から民主主義は破綻する。期待は見返りとセットだ」という言葉に納得感があり、印象深かった。ただこれは明らかに理想論であり、政治家を志すほど強い動機のある人間は稀だから大多数の人は候補を選んで期待するのが精一杯となる。それで破綻を始めていたとしてもなお、民主主義は「最悪の政治形態、ただし他に試みられたあらゆる形態を除けば」なのだ。

先週の日記に加筆した後昼前からセミナー準備を開始した。2時間ほどで切り上げ外出。生協に行って昼食を摂り、ラノベを受け取り、散髪した。床屋ではずっと寝ていた。

帰宅したらECRのopen hacking phaseが終了していた。無事Fが生き延びたので動画を公開。順位はコンテスト終了直後に30位ちょっとだったのがセルフHackで少し下がり、その後上がどんどんどんどん落ちて行って最終的には12位となった。

www.youtube.com

午後4時半ごろ就寝。

04/05(水)

生活リズムの狭間に消えた。

04/06(木)

午前1時前後の1時間くらいは起きてネット小説を読んでいた形跡がある。その後二度寝に成功したようだ。

午前5時起床。食事してからセミナー準備を開始した。今回は1.9章の飛ばした内容を拾いつつ4.6章、引いては4章を終わらせる。1.9章で話すべきことが意外に多く、午前9時過ぎになってようやく完成した。すぐに出発したが、学食で悠々と朝食を摂っていたらまた今日も少し遅刻してしまった。

今日は最初に、先生が春からの講義で出題する予定の複素積分を1問解いた。留数定理を使う問題だったがありとあらゆることを忘却しており大変だった。先生の助けを多分に借りつつ何とか計算。符号回りでミスを犯してしまったあたり、計算能力もかなり錆び付いているようだ。

これだけで午前中の時間をすべて消費し、少し早めの昼食休憩を1時間挟んで午後からセミナー。

まずは同級生の発表。彼は今日から5章、彩色の章に入る。最初は平面グラフの五色定理をケンペ鎖を使って示す話で、まったく同じものを昨年の集中講義でも紹介されたが、平面グラフについてしこたま学んだ今だともうちょっと精密に議論ができるようだ。具体的には、2本ケンペ鎖を取ったときに交わってしまうという部分。

また少し休憩を挟み、午後3時から自分の発表。今日からセミナーの教室が去年の春学期使っていたところに戻り黒板が倍くらいに広くなったためかなりやりやすかった。内容に関してはグラフの平面性というかなり強い性質もいろいろ同値な言いかえを知って扱いやすくなったなあという感想。

午後5時頃帰宅。言語アップデートコンテストに更新が来ていたが、自分がスプレッドシートに記入したRakuもOctaveも残念ながらまだ使えなかった。Rakuはコマンド記入ミスでRE、Octaveはそもそもインストールに失敗するらしい。スプレッドシートを見に行ったらすでに誰かが修正してくださっていた。

1時間ほどしてまた外出し、ゲーセンに向かった。このあたりでTwitterに登録して10周年の通知が来た。

Twitterに登録した日を覚えていますか？ #MyTwitterAnniversary pic.twitter.com/etRprkhutt
— こたつがめ (@kotatsugame_t) 2023年4月6日

今日はまず新曲を一通り触った。SSが一発で出ない14+が二つあって絶望。その後ワールドイズマインの理論値粘着をしていた。前回ゲーセンに来た時も1時間くらい、今日も1時間くらいかけてようやく出た。これに時間を取られたため他のことはほとんどできていない。

ワールドイズマイン　理論値 pic.twitter.com/6geq4J7AiW
— こたつがめ (@kotatsugame_t) 2023年4月6日

夜中のECRに備え午後10時過ぎ退店。ラーメンを食べ、大町西公園の桜を少し見て帰った。

シャワーを浴びて午後11時半からECR146。

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

Aは $n$ が偶数または $k$ が奇数ならOK。制約を読んでいなくて、 $n$ が奇数のとき $n\ge k$ もチェックしていた。

Bは最終的な足の長さを $m$ とすると $\lceil a/m\rceil+\lceil b/m\rceil+m-1$ が答え。 $m$ を大きくしていく場合 $\lceil\ast/m\rceil$ が変化する直後の値だけ考えればよいから、それを商列挙で求めて全部試した。Bにしては複雑だと思っていたが当然想定解ではなかった。

Cは $\sum_i r_{a_i}\times i\times s_1+\sum_i r_{b_i}\times i\times s_2$ が答え。 $k$ について考える必要はなく、 $i\times s$ を十分な量列挙し小さい順に $r$ の大きいものとマッチングさせていけばよい。

Dを読むも解けない。writer解に間違いがあるとアナウンスされたので、こんなに解けないということは解法が破綻していたのだろうと考えてEに進んだが、別にそんなことはなかったようだ。ともかくEを先に解いた。

Eは $n-1$ 本の辺からいくつか選んで和を求め2倍したものの最小値が答え。ここで両端の辺は必ず選ぶ必要があり、また選ばない辺が2本以上連続してはならない。選んだ辺によって連結になった要素の間で値を入れ替える場合、各辺を2回ずつ通ることになるので、こういう式になる。ほとんどエスパーだった。

実はセグ木に乗るので更新にも対応できる。ノードに対応する区間の最適な選び方を、両端の辺を選んだかどうか4パターンに応じて求めておけばよい。遷移でミスして1WA。

Dに戻ってきたら解けた。答え $n$ は必ず達成可能なので、 $n-1$ 以下になるかチェックしたい。この時変化しない $p=p_i$ が一つ以上存在するからそれを決め打つ。すると $\min_i p_i$ の候補が $p-k\dots p$ となるので、それぞれ対応する範囲に $p_i$ を収めるコストを、 $i$ ごとに考えた。 $i$ を全探索し、 $\min$ のほうはまとめて計算した。

まず $f\le k$ の場合、取れる値の間隔が十分狭いので、適切に $d$ を選ぶことでどんな最小値にも対応できると考えてよい。最初から範囲に入っているケースにはコスト0、それ以外にはコスト1を加算する。

$f\gt k$ の場合対応できない最小値があるが、 $d$ を適切な範囲で全探索できるので、使える $\min$ に対してはコスト0または1を、そうでない $\min$ に対してはコスト $\infty$ 、の代わりに $n$ を加算した。

以上の区間加算はimos法で行える。最後に集計して計算。 $d\le 0$ も可能だとしてしまって1WA。

Fは解けず5完24位。今日も動画を撮ろうとしたが、Dあたりであまりの眠気に言語不明瞭になってきたため止めた。そしたら少し目が冴えて謎。ともかく寝落ちせずEまで解けたのはよかった。

少しだけネット小説を読み、午前2時半就寝。

04/07(金)

午前11時頃に目を覚まし、ハーメルンを読んでいた。「駄目ウマ娘製造機」を読了。幼少期にこれでもかというくらいネームドウマ娘と関わっており、フラグの乱立っぷりがすごい。今はちょうど主人公がトレーナーになってそれらを回収するパートに入った所のため、この先が非常に楽しみ。

syosetu.org

午後2時から二度寝し、今度は午後4時に起床。大学のガイダンスにZoomで出席しつつインターンの進捗を産んでいた。午後5時からは1on1なのでそこで退室した。

1on1はほぼペアプログラミング。先ほど実装していた機械学習の精度評価について、実データで計算した結果を見ながら指標の調整を繰り返していた。これと言って正解がないため難しいが、これまでに挙がった考慮すべきポイントについてはちゃんと実装に反映されたものと思う。コストがちょっと特殊な編集距離のdpを使っており、少しだけ競プロっぽさがある仕事で楽しかった。

来週のタスクについて確認し、午後8時終了。予定より1時間長くなってしまった。付き合っていただけてありがたい限りである。

食事してしばらくハーメルンを読み、午後9時20分からyukicoder 383に出た。今日はTUPCのボツ問セットらしい。全体testerとして携わった自分が出て大丈夫かと心配していたが、コンテスト中は見覚えのある問題に出会わなかった。あくまでコンテスト中は、の話。詳しくは後述する。

yukicoder contest 383 - yukicoder

Aは $x$ を1000個まで探索すればよい。

Bは要素を $\bmod P$ で分類し、それぞれ作れるペアの個数を数えた後要素を $P$ で割って再帰的に計算する、というコードを書いた。手元でのチェックに失敗していたらしく、要素が十分少なくなったら全探索を始めたりとちょっと面倒なことをしていた。

Cは昔のABCで見た符号を全探索して絶対値を外すテク。 $\pm A\pm B\pm C\pm D\pm E$ を2⁵通り試し、同じ符号の付け方をした数との差を求めたらその最大値が答えになる。

D - Patisserie ABC

Dはファレイ数列やStern–Brocot treeで検索していろいろ眺めていたが特に進展がない。しばらくしてからsolved数を見てEに進んだ。

Eは入力を二部グラフの隣接行列と見なしたときに $M$ 個の完全マッチングに分解する問題。実は次数に関する自明な条件が満たされていればそのような分解は必ず可能である、というのをつい昨日辺彩色について調べていたときに知った。かなりタイムリーな話題だった。

二部グラフの辺彩色数はグラフの最大次数に一致するという定理があるらしい。入力のグラフを $M$ 色で辺彩色できるのなら、同じ色で塗られた辺は完全マッチングをなす。構築のためライブラリを窃盗してこようとしたが、冷静になると制約がかなり小さいので毎回完全マッチングを求めても十分間に合う。

Fを考えていたがサンプル4が全然合わず終了、4完。コンテスト中は一切見なかったが実はG問題はほぼ知っている問題だった。改題前の問題だけ解いて放置していたらいつの間にかボツになっていたもの。

yukicoder-G

もともとはこれ（転倒数）だったんですが，これをこたつがめさんに投げたところ，平方分割でない解法で O(Q log^2 N) で解かれてしまったので，いろいろあって substring sum を求めることになりました pic.twitter.com/F5EGqJoEG7
— とりゐ(競プロ) (@torii_kyopro) 2023年4月8日

改題前の問題の解法について。インデックスに対し一律で $X$ をXORするのは、セグメント木で表せば $X$ の立っているbitに対応する深さの子二つを入れ替える操作になる。これに関して転倒数はかなり性質がよかった。二つの子の間だけ見た時の寄与が左の子にある1の数と右の子にある0の数の積だから、左右を入れ替えたとしてもそれ以外の部分と独立に計算できてしまうのだ。

だから各ノードに対し、それ以下のノードが入れ替わった場合とそうでない場合を深さごとに計算しておくことで、一つのノードの更新・取得が $O(n)$ になる。全体では $O(Qn^2)$ 。

ハーメルンから「腕の良いアホトレとモブウマ娘」を読了。あまりにも強すぎるためいつも大差勝ちで、レースの描写がほとんどないのがかなり新鮮。レースに懸けるウマ娘たちの熱い想いを丹念に描く作品が多い中で、そういうものを完全に省いてしまったこういうノリも面白いものだなと感じた。

syosetu.org

朝まで日記を書いていた。布団に入ってハーメルンを読もうとしたら寝落ち。午前9時だった。

これは今日見た音MAD。前半は普通だったのに後半豹変してめちゃくちゃ笑った。リズミカルで聞いていて気持ち良い。

www.nicovideo.jp

04/08(土)

午後2時前に起床しUniversal Cup 11回目に参加した。今日はShanghaiセット。

2022-2023 ICPC Asia East Continent Final (EC-Final 2022) - Dashboard - Contest - QOJ.ac

書く

食事して午後9時からARC159に出た。

AtCoder Regular Contest 159 - AtCoder

Aは1回辺を通った瞬間頂点番号を $\bmod N$ で考えてよくなる。さらに $s=t$ なるケースは存在しないから、最初から $\bmod N$ で扱える。クエリごとに $O(N^2)$ のBFSで計算した。始点の距離に0を書き込まずにBFSを開始することで、 $s\equiv t$ の場合に距離0としてしまわないようにした。

Bはとりあえず $(a,b)\leftarrow(a/g,b/g)$ として、操作を1引くことに言い換えておく。次に $\gcd$ が2以上になるまで $k$ 回かかるとすると、その $k$ は $\gcd(a-k,b-k)\gt 1$ となる最小のものである。これが求められればその間の操作をまとめて行えて、 $\log$ 回ほど計算するだけで操作が終了する。

$\gcd(a-k,b-k)=\gcd(a-k,|a-b|)\mid|A-B|$ なので、あらかじめ $|A-B|$ の素因数を列挙しておき全探索することで高速に求められる。 $|a-b|=1$ の場合どんな $k$ に対しても $\gcd\gt 1$ とはならないことに注意。

Cは大変だった。操作回数 $M$ を全探索すると操作後の数列の総和、ひいては $A$ がどの値に揃うことになるかわかる。つまりどの要素にどれだけ値を足すかもわかって、これを順列でカバーする方法を構築することになった。昨日のyukicoder-Eと全く同じ話で「 $1\dots N$ を $M$ 回ずつ使い、各要素に $M$ 個ずつ値を足す」方法さえ作れればよい。

よくわからない貪欲をして通した。大きな値から順にどこに足すか決めていく。この時の評価基準は「残りの足さなければならない値」割る「残りの足さなければならない回数」が最大のものを選ぶようにした。正当性は謎。優先度付きキューに分数を詰めて実装。

ここの計算量は $O(MN\log N)$ 、さらに $M=0\dots 10^4$ で全探索しているはず。しかし爆速だった。作れる場合は小さい $M$ でも作れるし、作れない場合はそもそも数列の総和を $N$ の倍数にできないからチェックですぐ弾かれる、ということだろうか。復元は $O(MN^3)$ だが1回しか実行されないので問題にはならない。

Dは簡単。まず考察として、区間 $[l,r]$ から要素 $x$ をLISに使った場合、 $x\dots r$ を全部使うものとして損しない。これをもとに座圧した $r$ をインデックスとする実家dpが考えられた。 $l$ より前から持ってくる場合はLISが $r-l+1$ だけ伸びるので、単に区間MAXから遷移すればよく簡単。

$l$ 以降から持ってくる場合は増分が直前の $r$ に依存するため、あらかじめそれを引いておいた値を別のセグ木に乗せておいた。遷移してきた値を問答無用でセグ木に書き込んだらもともとの値を小さくしてしまうケースがあったようで1WA。

Eは解けなかった。問題文を頑張って解釈した結果、まず $(l,r,t)=(1,N,0)$ というノードが根にあって、ノードが持つ区間 $[l,r]$ から1点 $m$ を選びその左右を切ってそれぞれ1段深い別のノードにする、という操作を繰り返しているように解釈できると分かった。

ノードに対応する $\sum_j|x_j-x_{j+1}|$ を求める際、実は $(l,r,t)$ を全部考える必要はなく、 $(r-l,t\bmod M)$ だけわかれば十分。これをもとにメモ化再帰を書いてみた。毎回区間長が指数関数的に縮んでいくから、それほど深くならないうちに計算が終了してくれるはず。しかしTLEで、特に高速化する余地もなかった。

4完59位。Cは操作回数の余裕を利用し、便利な操作を作ってチマチマ揃えていくのが想定解だったらしい。まるで考えもしなかった。

5分後からCF #864 div.2。

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

Aは4近傍に障害物を置けばOK。2点それぞれについて4近傍のうち何マスが迷路の中にあるか数えると、小さいほうが答えとなる。 $\min(n,m)\lt 4$ だった場合それも答えの候補になるのでちゃんと対応しておいたが、コンテスト後に制約を確認すると $n,m\ge 4$ だった。

Bはとりあえず180度回転させても一致するように揃えておいて、操作回数が足りるか、余りをちゃんと消費できるか判定。 $n$ が奇数なら中心のマスに操作し続けることでどれだけ余っていても問題ないが、 $n$ が偶数だと2回ずつしか消費できない。

Cは最初斜め移動ができることを見落としていたため時間がかかった。盤面の左上と右下を聞くことで、候補の点が高々2点、あるいは縦または横1直線に並ぶ。前者は追加で片方を聞けばよい。後者は直線の端を聞けばよい。

Dは各頂点について「子の集合」「親」「部分木のサイズ」「importance」を管理する。子の集合を、部分木のサイズと頂点番号のペアを入れたsetで管理しておけば、 $son_x$ が高速に取得できる。これと親 $fa_x$ を使ってrotate操作をする。管理している値が変化するのは $x$ 、 $son_x$ 、 $fa_x$ のみである。

子の集合と親については単に書き換えればよい。部分木のサイズは、 $fa_x$ に対しては変化なし、 $x$ に対しては $son_x$ 以下のぶん減る、 $son_x$ に対しては直前の $x$ の値がコピーされる。importanceはこれとまったく同様に変化する。

E。まずエラトステネスの篩のようにして $\phi$ 関数のテーブルを $5\cdot 10^6$ まで作っておく。実験により制約の範囲では $x\leftarrow\phi(x)$ という操作を高々23回繰り返したら値が1になることが分かった。これを元に解く。

まずクエリ1は、まだ値が1になっていない要素のインデックスをsetに入れることで処理できる。クエリの度、setから区間内のインデックスを取り出して操作し、まだ値が1になっていなければ戻す。この入れる・出す操作が全体で高々 $23\times 2\times n$ 回しか行われないので十分高速。

クエリ2はセグ木に乗せてみた。区間に対し、そこの要素を揃えられる最大の値と、それにかかる操作回数、また区間長を持つ。二つの要素を揃えるため大きな方に $\phi$ を適用するのを繰り返す……ということを考えたら、揃えられる最大の値を仮に選んでおいても問題ないことがわかる。またこの操作はモノイドの積の計算方法にもなっている。繰り返す回数が少ないので間に合う。

Fは大変だった。各頂点 $v$ に対し、ペア $(u,v)$ （ $u\lt v$ ）に関する三つの値を管理する： $v_1$ は $\min=u$ となる個数、 $v_2$ は $\max=v$ となる個数、 $v_3$ は $\min=u$ かつ $\max=v$ となる個数。 $v_1+v_2-2v_3$ の和が答えになる。

これらが分かっていれば、頂点追加クエリは簡単に処理できる。追加する頂点の番号 $v=n+j$ はこれまでで最大だから、前から存在した頂点が管理する値を変更する必要はない。 $v_1$ でカウントすべきパスはパス $(u,k=k_j)$ で $\min=u$ なるものに頂点 $v$ を追加すれば得られるから、 $u=k$ のケースも考えて $k_1+1$ となる。 $v_2$ は明らかに $v-1$ である。 $v_3$ は $v_1$ と同じ値になる。

よって最初の木における各値が求まればよい。まず $v_2$ は頂点番号の昇順にマージしつつ、連結成分の頂点数を数えることで求まる。 $v_1$ も同様、頂点番号の降順にマージしていくが、書き込む対象が $u$ ではなく $v$ なので、連結成分全体に $+1$ するという操作になる。しかしこれも、成分全体に加算された値を持ちながらマージテクすることで求まる。

$v_3$ が問題で、自分はここに重心分解を使った。ちょっと前のインドで似た問題を解いており、そのコードをほぼ流用できた。

BEAUTY_SUMのupsolveをした。コンテスト中はパスのLCAを固定して木dpっぽく計算することを考え、出来ずに終わった。ところがなんと重心分解なら似たことが可能なようだ。
週記（2023/03/27-2023/04/02） - kotatsugameの日記

重心分解した木の上でパスのLCAを固定し数え上げる。LCAで切った2本のパスに対し $(\min,\max)$ を求めておいて、 $\max$ のほうでソートし、 $\min$ をインデックスとしてBITに乗せることで、必要なパスがうまく数え上げられた。 $\max$ のほうを固定しているので、 $v=\max$ に関するカウントを増やすという要求にも対応できている。 $O(n(\log n)^2)$ 。

残り7分で何とか全完、7位。

今日はARCとCFまとめて動画を撮っていた。ARCの振り返りを間の時間にできなかったのでこのタイミングで行い、動画を投稿した。

【競技プログラミング】ARC159+Codeforces Round #864 (Div. 2)【実況】 - YouTube

食事して日記を書きながらハーメルンを読んでいた。「ハルウララ　～有馬突破のキセキ～」を読了。

syosetu.org

2年前、アプリ版ウマ娘の記事を読んだ時も泣いたし、今日も泣いた。二次創作という形で描かれる話も良かった。非常に。非常に！

ウマ娘とハルウララについての話が流れてきて、読んだだけで感動してすぐに泣いてしまった。涙もろすぎる。
週記（2021/03/01-2021/03/07） - kotatsugameの日記

note.com

同作者の次回作も読み始め、のめり込んで止まらなくなった。布団に入ってもなお読み続け、午後0時半くらいに寝落ちした。

04/09(日)

午後8時半起床。ABC297に参加した。

AtCoder Beginner Contest 297 - AtCoder

Aはよい。Bは正規表現で言うと/B(..)*B/かつ/R.*K.*R/であればよい。sedで書いた。andよりorのほうが表現しやすいので、条件を否定して/B(..)*.B|R[^K]*R/か判定するコードを直後に出しなおした。

Cは行ごとに貪欲に埋めてよい。C++で書いた後、これもsedでs/TT/PC/gとすればよいことに気づいて出しなおした。

Dは $A\gt B$ という関係が続く限りの操作をまとめると $A\leftarrow A\bmod B$ のようになっている。ただし $A\bmod B=0$ の場合に注意。そうやって操作を飛ばし飛ばし行えば、やっていることは $\gcd$ の計算と同じだから十分高速に終了する。

Eは面白かった。純粋な閃きによって、金額をBFSで探索できることに思い至った。あとはBFSする際金額を昇順に見るようにして、 $K$ 種類見た瞬間答えを出力して終了する。 $K$ 種類それぞれから $N$ 個の次の候補があり、金額を昇順に見るため優先度付きキューを使っているので計算量は $O(NK\log NK)$ と少し重い。

Fは少し難しかった。Bounding Boxのサイズに対してそれを達成するマスの選び方を数え上げた。この値に位置は関係ないので、適切に係数を掛けて足し合わせることであり得る選び方全てに対してマスの個数が求まることになる。ここから期待値はすぐに出る。

Bounding Boxのサイズを $h\times w$ としよう。まず $\binom{hw}{K}$ 通りあって、そこから包除原理することを考えたが、何を引いたり足したりすればいいのかよくわからなかった。そこで除原理で押し切ることにした。

$1\le h'\le h$ かつ $1\le w'\le w$ なる $(h',w')$ について、サイズ $h'\times w'$ のBounding Boxが $(h-h'+1)(w-w'+1)$ 通りだけ中に納まり得る。この係数付き場合の数を $(h',w')\ne(h,w)$ の範囲で足し合わせ、 $\binom{hw}{K}$ から引くことで、ピッタリ $h\times w$ となる場合だけが残る。

係数となる式を展開すると、今 $h$ と $w$ は定数だと思ってよいので、 $1$ 、 $h'$ 、 $w'$ 、 $h'w'$ の四通りの値が掛けられた場合の数が欲しいということになる。それぞれ二次元累積和で求まる。

GはGrundy数を求める。少し手で考えてもよくわからなかったので実験したら一発で規則性が見えた。周期 $L+R$ を持ち、1周期では0から順に $L$ 個ずつ並んでいる。つまり $\lfloor(A\bmod{(L+R)})/L\rfloor$ がGrundy数となる。

Exは何も分からなかった。7完21位。

コードゴルフについて。AはAWKで負け、Bはコンテスト中のsedで勝ち、Cもコンテスト中のsedが最短だったが速度差で負け、Dはdcで勝ち、GはPerlで勝ち。他は手付かず。特に目立った工夫はできていない。

次のコンテストまでは昨日と違い1時間ほどある。撮った動画をすぐアップロードし、食事して備えた。午後11時45分からCF #865 div.1。

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

Aはインデックス $i$ に対する操作による変化を $b_i$ と表し、これに関する条件から考察した。基本的には $a_i+b_{i-1}+b_i\le a_{i+1}+b_i+b_{i+1}\Leftrightarrow a_i-a_{i+1}+b_{i-1}\le b_{i+1}$ として2項ごとの式が得られる。ただし端のほうで例外があって、 $b_1$ と $b_{n-1}$ はなんでもよく、 $b_2$ には $a_1-a_2\le b_2$ 、 $b_{n-2}$ には $b_{n-2}\le a_n-a_{n-1}$ が課せられている。

$b_1$ に制限がないことから連鎖して、 $i\equiv 1\pmod 2$ のとき $b_i$ の値に制限はない。 $b_{n-1}$ も同様。よって $n$ が奇数のときすべての $b$ に制限がないことがわかるので、どんな $a$ でも条件を満たせる。

$n$ が偶数のとき、 $b_2$ が下から、 $b_{n-2}$ が上から抑えられているため、この間をまとめることで $a_1-a_2+a_3-a_4+\dots+a_{n-1}-a_n\le 0$ という式が得られ必要十分条件となる。 $n=2$ のケースでは $b_2$ や $b_{n-2}$ が存在しないが同じ式で表現できる。

Bが解けなかったのでCに進んだ。ペア $(a,b)$ を $b\rightarrow a$ という有向辺だと思ってグラフで考えると見通しが良い。1は1個しか使えないので、そこから距離1にある値は高々2個しか使えない。以下同様にして距離 $d$ にある値は高々 $d+1$ 個しか使えないとわかる。逆に、1からたどり着けない値が存在するならそれをいくらでも多く置くことができるため、答えはINFINITEになる。

また、高々と言ったが実はピッタリ達成可能。説明のため距離 $d$ にある値を集めた列を $L_d$ とする。 $L_1+L_0+L_1$ と並べることで、距離1の頂点同士の条件も満たせることが確認できる。さらに $L_2+L_1+L_2+L_0+L_1+L_2$ と並べると距離2以下の頂点同士の条件が全部満たされている。距離2の値が距離1を挟んでいるのは当然として、逆に距離1の値が距離2を挟んでいるというのも重要。以下同様。

Bに戻ってきた。パスが作れなかったのでとりあえず木を作ってみたがどうしようもない、というのがCに進む前の進捗だった。改めて考えてみたところ、クエリ1で $x=n-1,n+1$ を投げることで $n$ が偶数ならパスを作れることに気づいた。

パスが作れたら答えが求まる。例えば $p_1$ から他の点への距離を聞き、その距離が近い順に $p_1$ の左右どちらかに繋げていくことでパスを復元できる。パスの向きの対応はわからないが、両方試すことで $p$ を2通り作れて、それらを出力すればよい。パスを作るのに2回、 $p_1$ からの距離を聞くのが $n-1$ 回、パスの復元にさらに $n-1$ 回でクエリは~~ちょうど~~ $2n$ 回となる。

04/13追記：パスの復元は高々 $n-1$ 回であった。例えば等距離に2点存在するとき、どちらが左かわかればもう片方が右になる。等距離に1点しか存在しない場合はそれ以降左右のどちらかに伸び続けるので聞かなくてよい。よって丁寧に実装すれば $n/2$ 回くらいになる。

$n$ が奇数の時も、 $n\leftarrow n-1$ だと思って解きつつ孤立点を見つけ次第別に取っておくことで同様に答えられる。 $p_1$ が孤立点だった場合困るので、どの点を基準にするかは丁寧に決める必要がある。

ひいこら実装した後ジャッジも自分で書いてデバッグをしていた。パスの復元時にインデックスの対応で頭を壊してしまっていたようで、それを修正するのに時間がかかった。提出するもWA。単なるバグのほかに、なぜか無意味に特別扱いした $n=2$ のケースで答えを出力した後の入力を読んでいなかった。Cを通してから70分経ってようやく通った。

Dを読み、 $m=2$ 以外はギャグ、 $m=2$ は桁dpで求まるところまで考えたところでタイムアップ。3完遅めの251位で2895→2755(-140)となった。Cは $x=n,n+1$ とすれば $n$ が奇数でもパスが作れたらしい。またパスの復元も、 $p_1$ から最も遠い点を端としてそこからの距離を再度聞き、ソートするだけで十分だった。

Dをupsolveした。XOR和を $X$ としたとき、まず明らかに $X\le n$ かつ $n$ と $X$ の偶奇が等しい必要がある。またそのような $X$ について、 $m\ge 3$ なら $a=[X,(n-X)/2,(n-X)/2,0,\dots,0]$ と定めることで実際に達成できる。 $m=1$ は自明。よって真面目に取り扱うべきなのは $m=2$ のケースのみとなる。

桁ごとに $a_1$ と $a_2$ がどうなっているか考えると、 $X$ と立っているbitが重ならない数 $t$ が存在して、 $a_1=X+t$ 、 $a_2=t$ となるべきだとわかる。つまり $t=(n-X)/2$ だから、 $X$ と $(n-X)/2$ のbitwise ANDが0に一致するような $X$ の総和が答え。これが桁dpで計算できる。ケアレスミスで2WAしたが本質部分の実装は難しくなかったはず。シンプルに時間が足りなかった。

ABCとCFの動画を公開した。

www.youtube.com

それからは日記も書かずずっとハーメルンを読んでいた。午後1時くらいに寝落ち。