03/28(月)

先週の週記を投稿してから布団に入るまでは早かった。しかしすぐには眠れず、少しハーメルンを読んでから午前5時過ぎに就寝。

目覚ましのスヌーズを繰り返し、午前8時50分に起床。午前9時からパ研合宿2021第2日「SpeedRun」に参加した。

パ研合宿2021 第2日「SpeedRun」 - AtCoder

AはText。Bはdc。CはRaku。Dはすぐ短くなりそうには見えないので、とりあえずRuby。Eはdc。Fも最初からdcで書こうとして、 $\frac 1 N\lt \frac 1{N-1}\lt\frac 2 N$ を出力したところほとんどWA。こりゃ難しいぞとしばらく紙の上で考える。とりあえず $\frac 2{N(N-2)}$ は達成できそうだったので、ペナルティもないことだしとりあえず出してみるかと思ったらACした。 $\frac{N-3}{N-2}\lt\frac{N-2}{N-1}\lt\frac{N-1}N$ である。 $N$ が小さいケースは良しなに。この問題を含め、以降はSpeedRunと言ってもコードゴルフ向けではなさそうだったので、C++で書いた。

GはbitDP。Hは各条件についてそれを満たす数の範囲が二分探索で求まるので、共通部分があるか調べる。Iはよくわからなかったので、連結成分ごとに全域木を取って葉から揃えた。それも、いったん根まで値を持ち上げてから再度下に持っていくという、いかにも無駄なことをしていそうな操作。そういう簡略化をしても実装が面倒なことに代わりはなく、さらに操作回数を上から抑えられたわけでもない。適当に $N$ が最大のケースでチェックした後エイヤと提出したら通った。Jはdpを睨むと値が2通りしかないことに気づく。Kは対応する括弧のペアに対して、それらの内側を作る操作を他と独立に考えてよい。その方法の数は、内側の括弧列をまた独立したいくつかに分解して、それぞれの操作回数を掛け合わせたものと、操作順序の決め方の積になる。実装で少し悩んだが、stackを使う簡潔なコードが思いつけて良かった。

Lは、辺とそれを通る向き、またジグザグにおける山か谷かを状態として、それぞれコストを求めていくdijkstra。本当に何も考えていなかったので毎回次の頂点から出る辺を全部見ているため、ウニグラフで $O(M^2)$ になってしまう。テストケースが弱かったらしく爆速で通り、後からTwitterを見ていて気付いた。正しくは頂点ごとに辺の重みでソートして、隣接する辺にだけコストを移すというようなことをしないといけない。Mは、順列 $P=(P_1,P_2,\dots,P_N)$ が与えられたとき、 $P_i$ を $Q$ に追加したときの転倒数の増分がそれまでの $Q$ の構築によらず $\min(\#\{j\lt i\mid P_j\lt P_i\},\#\{j\lt i\mid P_j\gt P_i\})$ になることに気づく。あとは挿入dpを考えればよい。転倒数の和のほかに場合の数も持たなければならないように見えるが、実はただの階乗であるためその場で計算してもよい。

Nは $f(k)-g(k)$ を最高次から計算していった。 $i+1$ 次以上の項だけを計算した状態から $i$ 次の項を計算に含めるには、それまでの計算結果を $v\leftarrow vk+a_i-b_i$ のように更新する必要がある。ここで $|a_i-b_i|\le 2\times 10^5$ のため、 $|k|\ge 2$ の場合ひとたび $|v|\ge 2\times 10^5$ になれば二度と $|v|\lt 2\times 10^5$ にはならず、したがって $v$ の符号だけ見ていればよいとわかる。 $|k|\le 1$ の場合は普通に計算していけばよい。日記を書いているときに、ACしたはずのコードでしきい値を間違えていることに気づいた。OはSuffixArrayと高さ配列を使うことで、各 $l$ に対し $S[l:r]$ が良い文字列となるような最小の $r=r_l$ が求まる。クエリ $(L_i,R_i)$ に対しては $R_i\le r_l$ なる $l$ のみを考えたいので、 $R_i$ や $r_l$ で降順ソートして順に処理する。 $r_l-l+1$ をセグメント木のインデックス $l$ に置いて区間最小値を取った後に、 $l\le L_i$ かつ $r_l\lt R_i$ なるもののうち $l$ が最大のものを見つけて $R_i-l+1$ も計算に含めることで答えが求まる。

Pで30分くらい粘ったものの全く光明が見えず、最後10分程度はコードゴルフなどしていた。聞いたところによると1600点問題の強化版らしい。無理だ。結局PのACは出ず、それ以外を全問解いて優勝。Lで完全に頭がついていなかった以外は良かった。

コードゴルフ。A、B、Eは特に変なことをする必要もなく、速度差で最短を取れた。Cはコンテスト中のRaku 39Bに対し、Rubyでも39Bが出るらしい。これも速度差で危ないところだったな、と思いつつ眺めていたら1B縮んだ。Fはdcで $\frac 1 N\lt \frac 1{N-1}\lt\frac 1{N-2}$ 。 $N$ が小さいときの場合分けや、出力でfなりpなりを使って何とかいろいろ流用するのを頑張った。Mもコードゴルフしてあって、Ruby。これらと以下で述べるD以外は手付かず。

DはRakuでTLEしてしまったためRubyを書いておいたら普通に負けた。.tally.valuesした列をソートして $-M$ 番地にアクセスし、nilだったら代わりに $0$ を出力すればよいらしい。まったく同じことを、.tally.valuesの部分をシェルスクリプトで、残りをPerlで書いたら縮んだ。夕方になって、数列を空白区切りから改行区切りにする部分はdc -e?fよりfactorのほうが短いという更新で取られたため、Rakuでもうちょっと粘ってみた。いったんwordsで全部読んでから2行目だけ[2..*]で取り出していたのが遅かったらしく、2行目だけwordsで読んでそのまま.Bagに投げると2secギリギリで通った。

3回目のワクチン接種は今日の午後2時15分に予約してあった。仙台駅近くのヨドバシカメラまで行かなければならない。午後1時半過ぎに家を出た。

途中クリーニング屋に寄り、卒業式のときに着たワイシャツを預けた。このクリーニング屋は平日も休日も午後7時まで開いているらしいので、取りに来るのは結構簡単そう。オタク早口に加え、店の奥で人が電話していたので思わず小声になっていたこともあり、これだけの情報を聞き出すのにしばらく時間がかかった。

仙台駅東口についた時にはワクチンの予約時間を過ぎていた。構わず丸亀製麺で腹ごしらえしてから会場に向かう。特に何か言われることもなく、ガラガラの会場をスイスイ進んで10分程度で完了。経過観察を終えて出た。副反応に備え、駅の薬局で買い物。ゼリー飲料は必須として、薬は2回目のものが残っているので良い。冷えピタが残っているか全く覚えていなかったので、念のため買っておいた。また無関係な買い物として、ついに柔軟剤のボトルを見つけたので買ってしまった。先週せっかく洗ったボトルだが、めでたくお役御免となる。

柔軟剤は、いつの間にかリニューアルされてしまったのに店頭では詰め替え用しか見当たらなかったので、仕方なく現在使っているボトルを洗って詰め替えることにした。
週記（2022/03/21-2022/03/27） - kotatsugameの日記

しばらく駅前をうろうろしてから帰宅。棚を開けると冷えピタの箱がデンと鎮座していた。基本買い得だろうと思っていたのだが、部屋に2箱ある状態を眺めると明らかに邪魔。失敗。

帰宅してすぐインターンの定例会。木曜日のミーティングで出たタスクに手を付けられていないので、先週の進捗はミーティングをしただけ。お先真っ暗。今週の勉強会はAHC009の話題で、全然考察できなかったな～と思いながら聞いていたのだが、途中急激な眠気に襲われしばしば意識を飛ばしてしまい、さらに申し訳なかった。気づいたこととして、コスト計算が経過ターン数 $t$ に対して $S=401-t$ のところ、 $S=201-t$ だと勘違いしていた。ゴールさえすれば $S\gt 200$ になるので、手数を多くしてでもゴールする確率を高められれば得ということになる。この事実が、先週の週記で触れた以下の方針（いわゆるハイパーロボット）でそこそこ点数が出た理由なのだろう。

できるだけまっすぐ進むような経路を作るのは、それなりに良い方針だったらしい。通路のつきあたりまで進むような移動でゴールにたどり着けない場合も、できるだけ近寄ってからフラフラ移動することを考えれば、疑似的にスタートとゴールの位置を近づけるという意味で十分効果があるようだ。
週記（2022/03/21-2022/03/27） - kotatsugameの日記

勉強会まで終わったあたりで、すでに腕の痛みが強くなってきていた。自転車で駅前から帰ってくるのも、ワクチン接種後に避けるべき激しい運動の一種だったのかもしれない。キーボードは打てるのでこのままコーディングし、先ほど述べたタスクをこなすことにした。改善案の実装はすぐ終わり、手元のデータで試した感じも問題なさそうだったので、デプロイ作業に入る。事前に用意してあるテストを走らせて、正常終了することを確かめる必要があった。しかし、触れていないはずの部分でめちゃくちゃエラーが出てしまった。しかもコンパイル時に警告が出たり出なかったりする。どちらも何が原因か全然わからないため、SlackにHELPを書き込んで今日は諦めることにした。

布団に入ってしばらくラノベを読み、午前0時半就寝。午後11時くらいに測ったときは熱は出ていなかったが、頭痛があったので冷えピタを貼っていた。

03/29(火)

副反応ツリー↓

ワクチン接種3回目 14:54
— こたつがめ (@kotatsugame_t) 2022年3月28日

午前3時、目を覚ます。明らかに熱が出ている。38.1度。薬を飲んですぐ寝た。午前5時半、再度起床。体温はあまり変わらず。布団をひっかぶっているのに汗が全然出ていないのが気になる。またすぐ寝た。午前7時、三度起床。まだ体温変わらず。今度は眠れなくてラノベを読んだ。

1冊読了。「私より強い男と結婚したいの」。陰キャだけど実は喧嘩がめちゃくちゃ強いヤンキー主人公のラブコメということで、つい最近同じようなラノベを数冊読んだ記憶があり、さすがに短期間に出すぎじゃないかという気持ちになった。それらと比べると喧嘩シーンの描写は結構短い気がしたが、書いてあることはなかなか過激で、ヒロインが殴られたり蹴られたりしていた。この作品のヒロインはこれまたヤンキーだったという事情もあるか。1巻の中にヤンキーを倒すことで問題を解決するシーンが複数盛り込まれており、インスタントな爽快感が得られた。ところで、このラノベも「漫画動画」が原作らしい。これまた最近本当に多い。

別のラノベを開いて少し読み進め、午前9時就寝。午後2時半起床。37.1度と微熱程度に落ち着いた。午後3時からパ研合宿2021第3日「パ研杯」に参加した。

パ研合宿2021 第3日「パ研杯」 - AtCoder

まずHに0を提出しておく。Aはdcで書いた後、grep -c 1111で良いことに気づいた。ただこれは答えが0のとき正常終了しない。同じ現象が発生した最短コードはほかにも複数あって、dcからシェルスクリプトを呼び出すことで+1Bで対処できる。ここからはC++。Bは列を2倍にして尺取りした。Cは5のべき乗を桁ごとに眺めて、周期が2のべき乗になっていることをエスパーした。

Dは難しく感じた。前提として、使う問題は2人とも解くか、太郎くんのみ解くとしてよい。まず、部分点は $A$ でソートして順に使うか試していくdpで解ける。ただここから先に進む方法がわからない。直感的に $A_i\gt B_i$ なるものは使わないのではないかと感じたものの、証明できなかった。実際これは正しくないようで、満点を取ったコードにこのフィルターを入れるとWAになった。 $A$ の昇順に見ると、 $A$ は使うなら見た順番に使えばいいので、 $B$ を使う基準を設定したい。適当なしきい値 $L$ を設定して、 $B\lt L$ なるものだけ全部使うようにすることを考えたが、これもダメ。しばらく苦しんで、ふと $B$ の昇順に見ることを思いついた。dpにおいて、 $A$ は使うか使わないかを全探索していると考えられる。だから $A$ の昇順に並べずとも答えは出せて、一方 $B$ を昇順に並べておけばそちらは順番に使っていくことができる。部分点のコードでソートの比較関数を変えると通った。

Eも難しい。小課題1はクエリごとに $O(N\log N)$ かけることができて、 $s/A_i$ をDSTに乗せ、二分探索でGCDが $1$ であるような区間を求めて数えればよい。小課題2は最初に全区間のLCM（ただし $10^9$ 以下）をカウントしてmapに持っておける。これまたDSTに乗せて、LCMが変化するタイミングは各左端に対して $O(\log N)$ 回しかないことを利用する。ここまでで350点で、Gに移った。

Gはオイラー路の存在判定。出現する頂点の次数が偶数であることと、連結であることを判定したい。小課題1は愚直にやってよい。小課題2は連結性とほとんどの頂点の次数が偶数になることがわかるので、 $i\lt j$ なるペア $(i,j)$ であって $u_i=v_j$ であるようなものの数を数えればよい。小課題3は辺を必ず2本ずつ使う必要があって、このとき頂点の次数は必ず偶数なので、逆に連結性が判定できれば良い。辺数が半分になるので $O(M^2\times\alpha(N))$ の定数倍8分の1が通らないかと思って出したが、当然のようにTLEした。この問題も350点で終わり。Fに移った。

Fは部分点の意味がよくわからないうちに直接解けた。 $u\rightarrow v$ （ただし $u\lt v$ ）という移動が $M-1$ 個あって、それぞれ $S-T$ 間のワープ路でどれだけ縮むかがわかればよいことになる。 $u,v,S,T$ の位置関係で場合分けしてみる。先に言っておくと、解法では区間内の値の個数とその総和を持つセグメント木を使う。

$u\lt v\lt S\lt T$ 、 $S\lt T\lt u\lt v$ のとき

縮まない。

$u\lt S\le v\le T$ 、 $S\le u\le T\lt v$ のとき

$u\lt S\le v\le T$ について、 $(v-u)-(S-u+1+T-v)=2v-(S+T+1)$ だけ縮む。 $u$ と $S$ の昇順でソートし、 $u\lt S$ という条件を満たす $(u,v)$ だけを考えた状態で、それぞれセグ木のインデックス $v$ に値 $v$ を入れればよい。取得する区間は $[\lceil(S+T+1)/2\rceil,T]$ である。 $S\le u\le T\lt v$ も左右反転して同様に行える。

$u\lt S\lt T\lt v$ のとき

$(T-S)-1$ だけ縮む。これも上と同様に値を入れたセグ木で、個数だけ取得することで求まる。

$S\le u\lt v\le T$ のとき

$(v-u)-(u-S+1+T-v)=(T-S+1)-2(v-u)$ だけ縮む。難しい。まず $v\le T$ のみを考えた状態で、セグ木のインデックス $v-u$ に値 $v-u$ を入れておく。取得する区間は $[\lceil(T-S+1)/2\rceil,N-1]$ である。これで、大小関係でいえば $uvST+uSvT+SuvT$ が得られた。次に、 $u\lt S$ のみを考えた状態で同じことをし、取得した値の符号を反転する。今度は $-(uvST+uSvT+uSTv)$ が得られた。互いに打ち消しあって $SuvT-uSTv$ が残る。

最後の $uSTv$ 、つまり $u\lt S\lt T\lt v$ について、この時実は $v-u\gt T-S+1$ なので、 $(T-S+1)-2(v-u)$ は必ず負になる。それらのキャンセルをキャンセルすればよいので、 $u\lt S$ のみを考えた状態で、セグ木のインデックス $v$ に値 $v-u$ を入れておき、区間 $[T+1,N-1]$ で取得することで必要な値が求まる。

以上ですべての場合が尽くされた。各 $(S,T)$ ペアについて、元の距離からの減少分が全 $(u,v)$ まとめて対数時間で求まることがわかる。最後のキャンセル以外を考察して書きあげたのがコンテスト終了20分前で、そこから詰めの解法をひねり出し、何とか終了10分前に通すことができた。

残り時間はE問題の小課題3を考えて、更新のたびに左右を見てLCMの変化をチェックすればよいなと考えつつ実装もせず終了。3000点で4位だった。マラソンを手付かずの0点にしておいたのは思想である。

コードゴルフ。Hは速度差で負け。Aは深夜になって、1111にマッチする行を抜き出すのではなく0にマッチしない行を抜き出すという方法で縮められていた。完全に頭から抜けており、縮められているのを見て放心した。他は手付かず。

インターンの業務を進める。昨日出ていた警告とエラーについて。まず警告が出たり出なかったりしていたのは、コードに変更がない限り再コンパイルしないというプロジェクト管理ツールの親切設計が原因だったらしい。詳細表示のオプションを設定して、コードに適当に変更を入れつついろいろ試していたら解決した。JavaのGenericsでComparableインターフェースを実装していることを要求するとき、<T extends Comparable>と書いてコンパイルが通ったので安心していたが、そこを咎められていたらしい。<T extends Comparable<T>>にしたら解決した。調べた感じ<T>ではなく<? super T>にするのが標準的に見えるものの、そんないろいろな型で使いまわす予定のコードでもないのでOK。

エラーについては結局わからなかった。昨日Slackに書き込んだHELPから進展がないうちに、エラーが出ずに正常終了することが何度か続くようになり、少なくとも今回の更新の問題ではないものと判断された。他の人の環境では再現しなかったらしく、かなり謎である。まあともかくデプロイは終了した。

37.3度。布団に戻ってハーメルンを読んだりYouTubeを見ていたら、chokudaiさんからリプライが届いていた。僕をあーだこーだーのゲストとして呼んでほしいという希望が来たらしい。chokudaiさんもリプライしてくるぐらいだから乗り気なのだろう。僕ももちろん悪い気はしないため可能であるとの返事をした。結構すぐになりそう。

@kotatsugame_t あーだこーだーゲスト希望来てますよ！！！！！！ pic.twitter.com/5vY6TMdFQN
— chokudai(高橋直大)🍆@AtCoder社長 (@chokudai) 2022年3月29日

午後10時にまた就寝。ここで日記の日付を切り替えておこう。

03/30(水)

午前0時、目覚ましで起床。SRMを逃したかと思ったが、午前1時開始だった。もう30分ちょっと寝てから改めて起きた。体温は36.1度と平熱に戻った。まだ腕が痛いのと、さらにそれを庇うような姿勢でいたからか全身が微妙に痛む。

午後1時からSRM826。直前、また証明書チェックに失敗していた。3か月周期か？という話が出ていた。

SRMにレジろうと思ったらアプレットが開けなくなっていた。証明書の確認に失敗している、というエラーが出る。PCを再起動するといけるという話を聞いて試すも効果なし。結局、Javaの設定を変えて証明書失効チェックを「チェックしない」にすると開けた。
週記（2021/12/27-2022/01/02） - kotatsugameの日記

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19128

Easyはさいころの出目を全探索したくて、実際できるので簡単。決めた出目数に対して勝ちパターン数と負けパターン数の差を計算して、これの和でdpを書く。Medは謎。問題文が微妙に長い。猫2匹とネズミの位置関係すべてに対して、問題文中に示されたターン数以内にネズミを捕まえるための、次の猫の移動方法をそれぞれ定めるということらしい。ある状態から勝ちパターンへの移動方法の列を出力するのではなく、状況ごとの最適解をそれぞれ見つけよということだと気づくのに少し時間がかかった。状態の遷移が有向グラフと見なせるので、トポロジカルソートの要領で書いた。少し怖かったのでテストを書きたかったが、あまりに面倒だったので諦め、祈って投げた。ターン数の制限もチェックしていない。これについては、BFSみたいな書き方をしているから必ず最短で、どうせ制限を満たしているのだろうと思えた。

Hardは面倒。まず適切な処理を行って、「各 $1\le i\le N\le 13$ に対して整数 $0\le x_i\le r_i$ を決めて $L\le\sum_i x_i\le R$ とする通り数を求めよ」という問題に帰着できる。ここは単なる面倒パートなので、問題の評価を下げるだけ。解法に至るまでの僕の思考は、 $x_i$ に関する条件を多項式 $\frac{(1-x)^{r_i+1}}{1-x}$ として表し、これらの積について次数 $L$ 以上 $R$ 以下の項の係数を足し合わせればよいというもの。 $1-x$ で割るのは累積和を取るのと同じだと思い出せば、 $\prod_i(1-x)^{r_i+1}$ の項 $2^N$ 個それぞれ独立に考えることができ、累積和を $N+1$ 回取った後の係数を組み合わせの形で書くことで $L$ 以上 $R$ 以下における和を求められる。コンテスト後のTLで見たが、これは包除原理の計算と同じであるようだ。 $r_i$ の制限を外すことを考えれば、そちらのアプローチになるのか。

サンプルを合わせて出したものの落とされた。ミスは2点。1点目は、負号の存在を忘れていたこと。2点目は、これらを任意modで計算しなければならなかったことによるミスである。組み合わせ $\binom{n}{r}$ を、 $r\le 13$ の範囲で求める必要がある。任意modなので割り算はできないため、 $n\times (n-1)\times \dots\times(n-r+1)$ が $r!$ で必ず割り切れることを利用する。 $n,n-1,\dots,n-r+1$ という列を用意して、 $1\le i\le r$ とのGCDを計算したりして割れるだけ割っていくのだ。最後は分母が $1$ になったような形になるため、分子だけmodを取りつつかけ合わせればよい。僕はここでGCDを使わなかったのでダメだった。

EMの2完で11位、レートは2587→2613(+26)でhighest。昨年の最後に記録したものをようやく上回れた。今年初めの-133が大きすぎた……。

CLISTに登録して、競プロサイトのアカウントをいろいろ紐づけてみた。826回コンテストに参加しているらしい。

https://clist.by/coder/kotatsugame/

TCO22 Stage3の結果が今日のSRM826で確定していた。僕はSRM825に参加していないのでちょっとひやひやしていたが、それ以外の成績がまあまあ良かったので問題なくRound4への進出が叶った。TCOの予選はcombinedのratedなので、毎年通行料などと言われて評判は良くない。Topcoderのシステムでcombinedにするのはさすがに時代遅れ。ナウなヤングはFull-Feedbackにしか出ない。

https://clist.by/standings/tco22-algorithm-stage-3-28608402/

朝からは日記を書いていた。調べものでYouTubeを開いた結果、午前10時から2時間ほどを適当な動画を眺めるのに費やしてしまい後悔。正午あたりにAmazonから荷物を届けたというメールが来た。部屋のチャイムが鳴らなかったので外に見に行くと、宅配ボックスに入れるでもなく地べたに放り出してあった。いわゆる置き配というやつらしい。どうやらデフォルトでは何もかも置き配になってしまうようで、アドレス帳から切り替える方法を教えてもらって設定しておいた。

また日記を書きつつ、ラノベやハーメルンを読む。途中で隣室に引っ越してこられた方とのエンカウントがあった。いい機会だと、自分が四六時中パソコンから出している音声が漏れていないか聞いてみて、特に何も聞こえていなそうなので大丈夫だった。ただ、初対面でいきなり騒音について気にするのは過去のトラブル（もちろんそんなものはないわけだが）を想起させるかもしれず、かなり良くない行動だったかもしれない。今になって悶々している。

集中を切らしてひたすら脱線しながらも、夜になってなんとか今日の部分まで追いついた。すでに1万文字を超えている。シャワーを浴びてから少しコードゴルフした。

パ研合宿3日目のB問題で、僕が尺取りで解いた問題。現在の最短コードは累積和を取った配列 $S=\left(S_0=0,S_1,\dots,S_N=\sum_i A_i\right)$ を用意して $S_i-X$ や $S_i-Y$ がまた $S$ に含まれるかチェックするという方針で、賢い。配列に要素を足しつつ逐一チェックしなくても、 $S$ と $\{S_i-X\}\cup\{S_i-Y\}$ をそれぞれ用意して共通部分を見ればよい。RubyのArray#&を用いて実装したのだがTLEした。まさか各要素が含まれるかチェックしていて遅いのか？と思うもさすがにそんなわけはなく、 $\{S_i-X\}\cup\{S_i-Y\}$ を作るのにflat_mapの代わりに使ったsumメソッドが遅かっただけだった。ここを修正してとりあえずAC。その後、 $S_0=\sum_i A_i$ から引いていく形で累積和配列を作ったり、flat_mapではなく普通のmapで済むように用意する配列2つの役割を入れ替えたりして縮めた。引いていく形の累積和配列だと最後に $S_N=0$ であるかチェックするだけで $A$ の総和に関する条件がチェックできて便利。加えて少しだけテストケースハックもしている。

atcoder.jp

午後9時就寝。

03/31(木)

午前4時起床。しばらくハーメルンを読んで、昨日まででほぼ最新話に追いついていたものを2作読了した。

1作目、「魔法科高校の劣等生・来訪者編クリアＲＴＡ」。基本的には面白かった。来訪者編という、原作で1年生時代終盤となんとも微妙な位置にあるシナリオをクリア目標にするのは目新しい。ただ、そこに至るまでのイベントがかなりすっ飛ばされがちだったのと、終わってからも原作が続いたことを知っている以上中途半端な終わり方に感じられたのがちょっと残念。シリアスなシーンでも主人公が語録ばっかり喋っているのが気になった。

syosetu.org

2作目、「たまに寄り添う物語」。ウマ娘二次創作でトレーナー主人公。8話しかないぞと軽い気持ちで読み始めたら、1話1話が長くて読むのに気合いが要り、大変時間がかかった。時間がかかったせいで内容を覚えていない……。何やら裏設定があって徐々に明かされている気配を感じるが、さすがにこのペースでは何かが判明する前にエタるだろうと思ってしまう。

syosetu.org

食事し、さらにハーメルンを読んで、午前9時頃再度就寝。次に午後3時半起床。またしばらくハーメルンを読み続ける。

午後5時過ぎに布団から出た。サークルの今年の入部届に関する質問が現サークル長から来ていた。僕も昨年、同じ問題に突き当たったので、そのとき碧黴さんとやり取りした文面をそのまま横流しすることにした。ちょうど1年前の日記に当時のことが記録されている。どういう質問かも書いてあるので、それごと以下に引用しておく。

弊サークルの入部届は、formの回答を送信すると記入したメールアドレス宛にメールが届き、そこに記載されたSlackの招待リンクやサークルで使っているGoogle ドライブへの招待を通じて活動に参加するという形になっている。どうやら去年のものをコピーしてきただけの入部届ではうまく動いていないようだった。そもそもどういうシステムでそのような連携が可能になっているのかわからなかったので碧黴さんに確認して、返信を待つことにした。
週記（2021/03/29-2021/04/04） - kotatsugameの日記

頭痛も腕の痛みもほんの少し残っているが、それ以外は回復したと考えてよさそう。今日はゲーセンに行こう。ついでに、今週月曜日クリーニング屋に預けたワイシャツがもう受け取れる状態になっているので、それも受け取ろう。そう思いつつシャワーを浴びたりしていたら、クリーニング屋閉店の10分前になっていた。慌てて家を飛び出し、チャリで爆走して、ギリギリで駆け込んだ。そんなピッタリに店を閉めているわけでもないらしく、問題なく受け取ることができた。ハンガーが大きくてリュックに入らなかったので取り外してもらい、畳んで持って帰ることにした。

クリーニング屋の近くに一風堂というラーメン屋があることを知っていた。普段の行動範囲から微妙に外れていたため、これまで入ったことがない。いい機会だと思い、今日はここで食事した。

その後ゲーセンに向かい、閉店までプレイした。先週火曜日の開店直後からいろいろ物が増えていて、チュウニズムの待ち椅子だったり、荷物入れやおしぼりが置かれていたりして、なかなか遊びやすそうな設備が整っていた。今日はもっぱら低難易度の99AJ埋め。12で12譜面、12+で1譜面、13+で8譜面、14で1譜面。特に12は全99AJを達成した。

Lv.12 全99AJ pic.twitter.com/SJUYquGGQ3
— こたつがめ (@kotatsugame_t) 2022年3月31日

「祈 -我ら神祖と共に歩む者なり-」を解禁した。昨年9月末に追加された楽曲なので、ちょうど半年遅れか。走るべきマップが多すぎる。譜面動画も手元動画も、何なら公式音源も何度も聞いていたのだが、やはり筐体で聞くと各別に感じる。譜面はクソ難しいとはいえ、3分で4444ノーツとかいう頭のおかしい密度をしているので、何もわからないまま適当にやっていても案外失点せず、僕が目指していたSSの難度としては特別高くもない。3回で乗った。

祈 SS出た！ pic.twitter.com/ycS42Mlc0q
— こたつがめ (@kotatsugame_t) 2022年3月31日

いい汗かいて帰宅。そういえば日付が変わったので、身分はついに大学院生か。もしかして大学生協の会員カードも切り替わって、新しいものが届くまでラノベを割引価格で受け取れないか……？と思って焦る。調べると、学部生時代のカードをそのまま使えるらしかったので一安心。

YouTubeを見たりラノベを読んだりしていた。午前5時頃今年のJOI春合宿の過去問が公開されたが、特にコードゴルフできそうでもないためスルー。

午前6時頃にラノベを1冊読了した。「継母の連れ子が元カノだった」8巻。相変わらず面白かった。ここ数巻、主人公たちだけでなく、彼らを取り巻く人間関係の間にあった恋愛模様も一緒に描いていた覚えがある。この巻ではそれらをまとめてゴールインへと推し進めるような向きが感じられた。実際、ほとんどのペアは少なからず前進している。ほとんどと言ったが、では進まなかったのはどのペアか。……主人公たちである。もちろんイチャイチャシーンもそこから生まれた葛藤もあり、しかし何か具体的な成果に結びつきはしなかった。伊理戸きょうだいだけ、本当に一歩も進んでおらず、読みながら作者の良い意味での悪意を感じていた。ラスト、ヒロインの心にほんの少しの勇気が描かれるも、直後に特大な不穏の種が言及され、次巻が怖くも楽しみである。

布団に入ってハーメルンを読んだ。「東方遺骸王」の作者は感想にも逐一返信しているが、内容は肉まんと呼ばれるAAに鳴き声で統一されている。今日四月一日は、一年で一日だけその返信が日本語になる日だ。昨年はすっかり忘れていたので、今年こそ何か質問をしようと思い、しかし特に思いつかなかったので応援コメントだけ残しておいた。ちなみに設定としては、作者が日本語を喋っているのではなく、我々が作者の言語を理解できる（してしまう）ようになっているというものらしい。徹底している。

https://syosetu.org/?mode=review&nid=37761&volume=610

午前8時就寝。

04/01(金)

午前11時くらいに、隣室に引っ越されてきた方からご挨拶があった。寝起きで頭が回らないまま対応したため、あまりコミュニケーションをうまくできず残念。またすぐ寝た。

午後4時起床。ちょうど今年のJOIG春合宿の過去問が公開されたばかりなのを発見。どうせ難しいだろうと思ってあまりコードゴルフする気もなかったが、念のため確認してみると最初の問題は簡単だったので、縮めようと思い布団から出た。YouTubeを見たりしつつ、深夜までかけてA-Fをダラダラ解いた。

JOIG 2021/2022 春合宿過去問 - AtCoder

Aは簡単。適当に選んだ3人をどのように並べるのが最適か考えると、 $B$ が最小のものは $A$ が、それ以外は $A+B$ が記録に寄与する。よって $B$ の降順にソートし、 $B$ が最小のものを全探索することで解ける。これだけコードゴルフしておいた。Rubyで、ソートだけシェルスクリプトで書く。Bも簡単。次に行く地点の候補が複数あるなら左右それぞれ一番近いところだけしか考えなくてよく、それを4回繰り返しても16通りにしかならないため全探索できる。E問題もすぐ解けた。まずダブリングを思いついて、書き始めてから、後ろから見れば1ステップだけ進めた後は先に計算した答えを流用できることに気づいた。

残りは全部難しい。次にFを解いた。各予定が占有する時間をチェックしたとき、同じ時間に $N$ 機より多い飛行機のスケジュールが入っていなければよい。とりあえず決まっているスケジュールを入れた後、隙間にできるだけ離陸の予定を詰めたい。スケジュールを入れる方法が問題で、例えば滑走路1番から順に空いたところを使ってみるとサンプル4で上手くいかない。しばらく考えて、「離陸の予定でも埋められず無駄になってしまう時間」が最小の滑走路から離陸させればよいと気づいた。直前の飛行機が時刻 $prv$ に滑走路を占有し終わり、今新たに時刻 $A$ から飛行機が着陸することを考えると、間に詰められる離陸の予定は $\lfloor(A-prv)/K\rfloor$ 個で、無駄になる時間は $(A-prv)\bmod K$ となる。この値が最小になる滑走路は、使用可能な滑走路の $(prv\bmod K,prv)$ をmultisetで持っておけば二分探索で容易に求めることができる。あとはその滑走路が再度使用可能になるまで適当なvectorに退避させておけばよい。時刻 $T$ に $N$ 機の飛行機が着陸するとしておくと実装がシンプルになる。

次にC問題を2次元のデータ構造でぶん殴った。 $X$ 最大を固定する方針だと、1点更新と領域MAXができればよくなる。解説を読んでひっくり返った。言われてみれば簡単なことに見えるのに、全然気づけないものなんだなあ。代わりに、2次元のデータ構造に対する理解が深まった。

あらかじめ更新する点を列挙しなければならない代わりに座標が10⁹などでも使える2次元セグ木について。とりあえずX座標だけ集め（て座圧し）、セグ木を作る。領域クエリが来たら、そのX座標の区間を $\log$ 個の区間に分割する。あとは、その区間に対応するY座標たちでもセグ木が作ってあれば、そちらから値をクエリのY座標の範囲で取得しまとめることで答えが得られる。この「各区簡に対応する点のY座標たち」をあらかじめ集めておくために、更新する点を列挙する必要があった。逆に更新する点が分かっていれば、各点のX座標は高々 $\log$ 個の区間にしか含まれないので、全セグ木の要素数の和が元の点の $\log$ 倍で抑えられる。

まったく同じ要領で、今セグ木だった部分をBITに変えることで定数倍が良くなる。今回は両方BITに変えられるタイプの取得クエリだったが、実装を簡潔にするためX座標のみBITに変えている。1500ms。

解けた問題としては最後、D問題。最後の状態における $Y$ は $S$ の部分文字列（空文字列を含む）である。またその $Y$ を $X$ に作った時の $Y$ もまた $S$ の部分文字列となる。このことから、 $Y$ は常に $S$ の部分文字列だとわかる。よって「 $X$ に $S[l:r]$ を作るための最短時間」をdpで求めればよい。遷移は、 $l$ を1文字左にずらすか、 $r$ を1文字右にずらすか、または $Y=S[l:r]$ として、 $l$ スタートの部分文字列を作るときに貼り付け操作を何回か行うか。貼り付ける位置は $l$ から貪欲に決めてよく、操作回数を全部試しても全体であまり大きくならない。なので、貼り付けられる位置を高速に取得できればよい。

$r-l$ の昇順に状態を見て、各インデックス $l$ に対し $S[l:r]=S[i:i+(r-l)]$ なる $l\le i$ の集合をsetで管理する。削除タイミングはZ-Algorithmで $l$ ごとにまとめて計算できる。貼り付けられる位置の取得にsetの二分探索を使うとTLEした。そこで、最初の1回は二分探索を行い、その先はその位置で二分探索したときの結果を保存することで定数時間で取得できるようにした。これで何とか通って2100ms。解説を見ると、Z-Algorithmの結果から直接次に貼り付けられる位置が出る、つまり $i$ ごとに線形時間かけることで、各長さ $k$ に対し $S[i:i+k]=S[j:j+k]$ かつ $i+k\le j$ であるような $j$ のうち最小のものが求められるらしい。これを実装すると500msと爆速になり、コードも縮んだ。

CDEFのFAである。さらにCとDはJOI春合宿と共通の問題だったようで、そちらに提出してもFAだった。問題idが異なるので、一問解くだけで一気に2つのFAを取得できてしまった。部分点が違うらしいので、問題idを変えてあるのはその兼ね合いだろうか。いやC問題は全く一緒の問題だな……。

解く合間に行ったことをいくつか。まず3月分の読書記録をまとめてツイートした。先月もハーメルンに時間を吸い取られてカスみたいな結果に。

3月の集計
買った：27冊
読んだ：9冊
積読：+18冊
積読（累積）：+15冊
— こたつがめ (@kotatsugame_t) 2022年4月1日

午後6時頃、大学院入学手続きを完全に完了した。学務情報システムにログインして記入する箇所は、アカウントが大学院のものに更新される4月に入ってからでないと行えなかったのだ。試しに単位取得状況を確認してみると、学部時代に必死でかき集めた単位のリストが影も形もなく、ああ卒業したんだなあと感慨深かった。

昨日寝る前に「東方遺骸王」につけたコメントに返信が来ていた。これからも更新は続いていくということだ。今この作品は、特に曜日を決めず大体週に1回くらいの間隔で更新が続いている。これくらいのペースが一番安心感があるし、もう7年以上連載しているので、エタる心配はまったくしていない。逆に、つい最近まで毎日更新していた作品が急に止まったりするのに数回遭遇したので、そういうペースには少し不安感が出てきた。エタるときは本当にパッタリ止まる、と感じたが、よくよく考えてみれば更新の間隔を「頻繁」か「皆無」でしか把握していないからな気がしてきた。

夜中から朝にかけてはハーメルンを読みつつ日記を書いていた。午前9時くらいに今日の分に追いついて、ちょうどGCJ2022のQualification Roundが始まったところだったので参加した。

codingcompetitions.withgoogle.com

Aはいかつい見た目をしているがAAを出力するだけ、Bは各色で使えるインクの量を計算して貪欲に使う、Cは面数が少ないサイコロから順に使う、Dは木dp。どれも自明レベルとはいえ20分弱かかった。E問題はGCJあるあるの確率解インタラクティブで、全然わからない。しばらく考えているうちに椅子の上で意識を飛ばしてしまったので、諦めて寝ることにした。午前10時就寝。

04/02(土)

午後6時起床。ABCまでは昨日のGCJ-Eを考えたり、食事したりしながら過ごした。

GCJ-Eについて。適当にテレポートを繰り返して頂点の次数の平均を見るのがよいかと考えた。これはローカルテスターでは全ケース通るものの、提出するとWA。ローカルテスターをよく読むと乱数シードが常に固定されていたので適当に弄れるようにしたが、全ケース通るのは変わらない。グラフがランダムグラフなので、次数に偏りがあるグラフで困っているんだろうなと感づいた。次数がメチャメチャ大きい頂点は、適当にテレポートした頂点から何歩か動いたらほぼほぼ到達できるので、その事実を使ってチェックする方針だろう。しかし具体的にどう考慮するのかは上手い手が思いつかず、放り出した。

午後9時からABC246。

AtCoder Beginner Contest 246 - AtCoder

Aはパッとは縮まない。C++でmapを使った。Bはdcで書いて、一瞬コードゴルフして少し縮めた。そこからまたC++に戻る。Cは無駄にならない範囲で使った後、値段のあまりをクーポンのあまりで貪欲に処理する。Dは $a^3+a^2b+ab^2+b^3=(a+b)(a^2+b^2)$ と因数分解してみてどうにもならないことに気づき、 $a$ を全探索する方針に修正。 $b$ は二分探索してもよかったが、 $a$ を増やすと $b$ が減っていくことに気づいたので、適当にループでデクリメントすることにした。

Eは、ビショップの動きは下に書いてありすぐ角行のことだと思い出せた一方、ポーンの動きはどこにも書いておらず困った。困りつつ問題文を読み進めると、そもそも動かす必要のない壁役だとわかり安堵。今いるマス目に加えて直前の移動の方向を持つ探索を思いつき、それが01BFSで書けることもすぐに気づけた。Fは包除原理。Gはとりあえず答えを二分探索して、判定問題を解く。追加で必要な手数を持つ木dpで書けることの見当はついていたが、その頂点で移動をストップする場合にどうするかなど考えていると、木全体（つまり根の部分木）とそれ以外の頂点の部分木で解くべき問題が異なるような気がしてきて、合わせるのに時間がかかった。根にも整数 $0$ が書かれていると考えればわかりやすい。TLが6secでかなり謎だった。Exは左からdpを考えると行列積の形で書けるので、セグ木に乗る。公式解説が3行3列行列で書いていたところ、自分は2行2列行列を掛けて2行1列行列を足すという形で書いてしまったので、遷移を記述するのが少し面倒だった。

ノーペナ全完で5位。Exがすぐ解けたのはよかった。一方Gに20分以上かけているのは意味不明なので反省。

コードゴルフ。Aは列ごとに対称差集合を取る方針を考えていたが、bitwise XORでよい。演算子(^)が+^となり1B縮む。2要素のリスト3つを列ごと、つまりインデックスごとにこの演算子でfoldするのは、演算子にメタ演算子Zを前置したものでfoldするのと等しい。Rakuの機能をふんだんに生かして23B。Bは、コンテスト中は $\frac{A}{\sqrt{A^2+B^2}}$ と $\frac{B}{\sqrt{A^2+B^2}}$ をそれぞれ計算していたのだが、 $\frac{A^2}{A^2+B^2}$ と $\frac{B^2}{A^2+B^2}=1-\frac{A^2}{A^2+B^2}$ を作ってそれぞれ平方根を取るのが短くなるようだ。コンテスト後に他の提出を見て気づいた。

CはRuby。 $K$ の値を使った分だけ減らしていき、最後に残った端数のうち大きいほうから $K$ 個を取り除いて和を取りたい。下手なことをするとすぐnilが帰ってきたりREになったりするので困っていたが、ソートしたリストに[..~K]でアクセスするとよいことに気づいて結構縮んだ。DはAWK。普通にやると精度が足りずWAになるので、bashから--bignumオプション付きで呼び出している。Fは毎回リストの共通部分を求めるとTLEになるので、泣く泣くビット列で表現してbitwise ANDを求めている。Crystalを持ち出すことも考えたものの、そちらはmod付きべき乗が言語機能にないため短くならない。そのほかは手付かず。

午後11時半からCodeChef、April Cook-Off 2022。DとFを縮めたのはこのコンテストの後である。

https://www.codechef.com/COOK140A

CHEFSHOPPINGから難しかった。Noteの部分に「各要素は2種類の操作をそれぞれ1回ずつしか行えない」という新しい情報が書いてあり、五度見くらいした。問題文から読み取れないことをNoteの欄に書くのはやめてほしい。隣り合った要素しか消せないことを見逃したりして時間を費やし、最終的には使う操作が左から見てR...R_L...Lのように分解できることに着目して耳dpした。SORTDISは簡単。 $A_i\lt A_{i+1}$ なら $K\le\lfloor(A_i+A_{i+1})/2\rfloor$ 、 $A_i\gt A_{i+1}$ なら $K\ge\lceil(A_i+A_{i+1})/2\rceil$ が必要な条件なので、それぞれセグ木に持ってチェックする。

次にDINTに進んだ。bitsetで部分和dpを書いて、その値が全体のmax以下であれば達成できると考えるもWA。あきらめてSEQCOSTに進む。 $X$ で三分探索できそうなことは見えたものの、コスト計算にどうしても時間がかかってしまいそう。これもしばらくして諦め、LCASUMを読んだ。この2問はsolved数が同じくらいだったのだ。普段2頂点の距離をLCAを使って求めるのと逆のことをすれば、LCAの深さは2頂点の距離と2頂点の深さで書ける。この事実を使うと思ったがどうにもうまくいかない。また諦めて、先ほど少し進んだSEQCOSTのほうに注力することにした。

$X$ を決めたとき、遅延セグメント木を使えば $N\log X$ くらいでコスト計算が書ける気がしたので、とりあえずこれを出してみようと思った。しかし $X$ ノードの遅延セグメント木は冷静に考えて不可能。そもそもコスト計算がどのように行えるか説明する。まず $X$ 個の列 $B$ を用意して、各インデックス $i$ ではそのうち $\min(A_i,X)$ 個の列の後ろに $i$ を挿入できる。この時、 $B$ の末尾のインデックスが小さい方から $\min(A_i,X)$ 個選ぶのが最適なのでそうする、というもの。ここで、末尾が同じインデックスである列を圧縮して保持すればよいのではないかと思った。逐一マージすれば、圧縮した塊は1回見るたびに削除され、さらにその塊は各インデックスで高々2個しか増えないので、見る回数が全体で線形になる。見るべき塊も、直前のインデックスで見た塊の直後からスタートするので探索の必要がない。自分は連結リストを用いて実装した。これでも三分探索の $\log$ はつくのでかなり怪しく、TL 1secに対し手元では2.5secくらいかかっていたが、祈るように出すと0.8secで通った。コンテスト終了10分前であった。

3完22位でレートは2744→2640(-104)。ダメダメ。

コンテスト後のTLより。CHEFSHOPPINGは、 $\min(L_i,R_{i+1})$ の和になるらしい。確かにこのようにペアにすると、操作はどちらかしか行えず、しかも全体で $N-1$ ペアしかないのでどちらかは操作しなければならない。どのように選んでも全部消せるという事実は、操作して消すのではなく操作して要素をマージすると考えれば明らか。この考え方も目から鱗であった。SEQCOSTで連結リストを使った部分は、dequeで実装したという話も聞いた。これだとイテレータを先頭に戻したりする必要がなくて楽そう。

LCASUMをupsolveした。片方の木でマージテクをすることで、そちらのLCAが固定できる。マージするときに集合から集合へ移動させる頂点を $u$ だとすると、 $v$ はマージ先の集合のどれかになる。つまり、もう一方の木に対して「1頂点と頂点集合のLCA」が計算できれば良い。実はこれはLCAをオイラーツアー＋RMQで計算することを考えれば可能である。深さが最大となりうるLCAは、考えている頂点集合と $u$ をオイラーツアー順で並べたとき $u$ に隣接している必要があるので、その高々2つをチェックすればよいのだ。集合として持つのを頂点番号ではなくオイラーツアー順のインデックスにすることで、setの二分探索で取得できる。普段LCAはダブリングで求めていたので、その隙を突かれたという感じがした。

ラノベを1冊読んだ。「公女殿下の家庭教師」11巻。前巻に引き続き主人公とヒロインはあまり動かず、2人の描写も少し減って、代わりに年少組の活躍が描かれていた。今進行している戦争では、基本的に主人公の属する陣営が勝ち続けている。ただ勝ち続けるのも本当は本意ではなく、何とか講和しようと努力していたのに黒幕に引っ掻き回されて勝たざるを得なくなっているというのが正しいらしい。そうやって攻め入った結果、相手方で交戦派の意見が強まっており、このままでは戦争が終わらなさそう。また前巻ラストで主人公とヒロインは黒幕一味の幹部に手ひどくやられているので、今のところ苦しい展開。あとがきによれば次巻で大きく動くらしいので、楽しみである。

午前9時前就寝。

04/03(日)

午後2時少し前に起床。即座にOUPC2021に出た。

https://onlinejudge.u-aizu.ac.jp/services/room.html#OUPC2021

まずAを読んで、先頭に簡単枠が置いてあるわけではないことに気づいた。どうせ解くので頑張ってみることにする。探索するのは不可能なので、何らかの不変量を調べるのだろうと予想がつく。今回の場合、凸と凹の数は一致している必要があるので、それだろう。与えられたピースの凸の数引く凹の数 $d$ を求めて、あとは普通の辺の数にも気を配って場合分けしてみる。

まず、パズルが1行あるいは1列である場合。これは普通の辺を3つ持つピースが必ず与えられるのでチェックできる。 $-2\le d\le 2$ があり得て、 $d$ が奇数なら3つが、偶数なら2つが普通の辺になり、残りは $d$ から復元できる。以降パズルは2行以上かつ2列以上なので、全体で普通の辺が2つあるピースが4つ、1つあるピースが偶数個存在する。

普通の辺が2つあるピースが3つしかない場合、 $d\in\{-2,0,2\}$ で、復元できる。普通の辺が1つあるピースが奇数個だった場合は $d$ だけでは決められない。ここで、普通の辺に隣接する辺の状態だけ見た時の凸の数引く凹の数 $d'$ を考えてみると、これも本来は $d'=0$ となるべきであるとわかる。つまり今 $d'\in\{-2,0,2\}$ となって2辺が決まり、最後の1辺は $d-d'\in\{-1,1\}$ で決まる。

いよいよラスト、求めるピースの4つの辺がすべて凸か凹である場合について。 $d\in\{-4,-2,0,2,4\}$ で、このうち $d\ne 0$ のケースは回転や裏返しによって全部一致するのですぐわかる。最後の $d=0$ のケースだけ、凸凸凹凹と凸凹凸凹の2通りがあって、これは $S=0$ と $S=1$ に対応する。

以上で場合分けは完了。普通の辺に隣接する辺だけ見る部分でミスして1ペナ付けつつ、26分時点で通しFAとなった。

以降はsolved順に解いた。BFGは簡単。Eは $20$ 以下に含まれる数で素因数の重複度がどれくらいになるか考えると、 $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19$ が最大なので、LCMとしては $(4+1)(2+1)(1+1)^6=960$ 通りしか考えなくてよい。それらを列挙せずとも、頂点ごとにそこにたどり着けるLCMをsetで持っておけば十分高速になる。Cは先頭車両から足りない強さをカウントして、見ている車両を守れる鬼狩りのうち守れる車両の範囲の端が一番右である人をドーピングすればよい。

Hは面白い。直接色を塗りながら数えることにする。 $dp_{i,j}$ を、色 $i$ まで塗ってボールを $j$ 個使ったときの、順列の決め方も含めた場合の数としよう。使ったボール $k$ の行き先 $P_k$ もまた $j$ 個のどれかであることがわかるため、このような定義ができる。すると $dp_{i,j}$ は、 $\sum_{0\le k\le \min(j,A_i)}dp_{i-1,j-k}\times\binom{j}{k}\times k!$ と書ける。二項係数はボール $j$ 個のうち色 $i$ を塗る $k$ 個の決め方であり、それらを $P$ で飛ばしても色 $i$ を塗る $k$ 個から外に行ってはいけないので、 $P$ の決め方は $k!$ 通りになる。二項係数を分解すると累積和が取れる形になるので解けた。 $k$ の上限をミスして1WA。後から気づいたが、これらの階乗や二項係数は最終的に打ち消しあって $N!$ になるので、普通に累積和だけ取って最後に $N!$ を掛けるのでも正しい値が出るようだ。

Iはちょっと面倒。スコアの定義から、長さの和がスコアの積になる。よってクエリ $(x,y)$ は「 $x$ から見た $y$ の部分木に対する $\sum_u 2^{dist(y,u)}$ 」と、その $x$ と $y$ を入れ替えたものを掛け合わせて、さらに $2^{dist(x,y)}$ を掛けることで答えられる。上のような $\sum$ は、根をずらすことによってその辺の両端についてしか変化しないため、全頂点まとめて全方位木dpで管理することができ、 $x$ の頂点にいるときに $y$ の部分木に対して $\sum$ を取得、逆も同様にすればよい。

ただこれはコンテスト後に思い付いたことであって、コンテスト中はそのまま $y$ から見た $x$ の部分木についても考えようとしてしまった。このとき、 $x$ から $y$ の方向に1歩進んだ頂点を取得して、その分キャンセルする操作が必要になる。この「1歩進んだ頂点」を取得するのに、最初隣接する全頂点を試して距離を比較するという方針を取り、TLEしてしまった。「dfs順で $y$ のほうが $x$ より先に出現した場合、求める頂点は $x$ の親になる」という事実に気づいてAC。

Dは難しかったが、簡単な実装方針を選べたと思う。二分木の下から、持っている情報の範囲を管理しつつマージしていく。範囲のマージには、範囲の両端、コストの和、さらに左から・右からのコストの累積和「の総和」が必要になる。そのような範囲は各ノード高々2個なので十分高速。

107分で全完、最初Aに26分かけたペナルティが響いて5位まで落ちた。

OUPC終了時間とOpenCupの開始時間が一致していたので休憩なしを覚悟していたのだが、思いがけず時間が空いたので食事したりしていた。午後5時からOpenCup。

まずKが通された。次に僕がBを通した。整数の平方根を $10^6$ 回求める必要があって、二分探索は少し怖い。sqrtlにかけてから微調整する方法を教えてもらい、それで実装した。見落としていた条件があり1WA。次にGが通された。Cを解けた気がしたので書いて、サンプルが合わなかったのでいったんPCを開けて考え直す。その間にEが書き上げられ、投げられた。ちょっとしたミスがあったらしいが、Cの修正もすぐ終わったので先に書き上げさせてもらい、投げた。Eも直後に投げられ、どちらも通った。ここからしばらく時間が空く。

I問題が通っていたので、考える。長さ $N$ の順列 $P$ であって、「 $l\le \forall i\le r.\;P_i\ge h$ 」という形の条件 $M$ 個のうち $M-1$ 個以上を満たすようなものを構築せよという問題。各 $i$ に対し関係する $h$ を大きいほうから2個（ $h_1\ge h_2$ ）持って考えていたら、チームメイトに「 $h_1\gt h_2$ ならば $l\le i\le r$ かつ $h=h_1$ な条件は1つしか存在しない」ことを指摘された。このとき、各条件についてそれを削除することで値の下限が変化するインデックスを毎回全部見ても全体で $O(N)$ になることがわかる。あとはまあ良しなにできるはず。実装はそのチームメイトにお願いした。

Hに進んだ。先に言っておくが、この問題はかなり面白い。funnyのほうである。 $q$ （素数）桁の $n$ 進数（ただしleadgin zeroを許す）がluckyな数であるということを、各桁の積と各桁の和の和が $\bmod n$ で $s$ に等しいこととして定義する。luckyな数 $a_1 a_2 \dots a_q$ のスコアを $(a_1+1)(a_2+2)\dots(a_q+q)+2^0 a_1+2^1 a_2+\dots+2^{q-1}a_q$ と定義したとき、すべてのluckyな数のスコアの和を $\bmod q$ で求めよ、という問題。

まずこのバカみたいなスコアの式を何とかする。数 $a_1 a_2 \dots a_q$ がluckyなら、それをrotateしたもの $q$ 通りも全部luckyであるから、それらを全部足して $q$ で割ってみる。すべてのluckyな数に対し、それぞれrotateしたもの $q$ 個を集めてくると、同じ数が $q$ 個ずつ出現するので、それを $q$ で割ればスコアが求まるからだ。……と思っていたのだが、後から見ると $q$ で割ったり割らなかったり、ちょっと怪しい部分が多い。ひとまずコンテスト中の考察を述べる。

$(a_1+1)(a_2+2)\dots(a_q+q)$ について。適当に実験してみると、 $\bmod q$ で消えないのは $\prod_i a_i$ と $\frac{(q-1)!}{q}\sum_i a_i\equiv-\frac 1 q\sum_i a_i$ に見えた。次に $2^0 a_1+2^1 a_2+\dots+2^{q-1}a_q$ について、 $\frac 1 q\left(\sum_{i=0}^{q-1}2^i\right)\times\sum_i a_i=\frac 1 q(2^q-1)\times\sum_i a_i\equiv \frac 1 q\sum_i a_i$ となる。足し合わせると $\prod_i a_i$ だけが残る。

あとはluckyな数の定義について考える必要がある。この「各桁の積と各桁の和の和」という条件は本当に何も良い性質がなく、かなり無理な雰囲気が漂っていた。しかしよく見ると、luckyな数 $a_1 a_2 \dots a_q$ の $q$ 通りのrotateが被ることがなければ、スコアは全部で $q\times \prod_i a_i\equiv 0$ だけ増えることになる、つまり考えなくてよいということが分かる。つまりluckyな数であってrotateが重複する数のみを考えればよい。今 $q$ は素数なので、そのような数は必ず $a_1=a_2=\dots=a_q$ になる！！！

よって $a_1$ を全探索して毎回チェックしても間に合うことが分かった。実装してAC。さて、怪しい部分について正しい考察の道筋を与える。まずrotateに関する考察を最初に行う必要があった。ここでrotateが重複しない数のみを考えると、それらの全体はrotateで移り変わるもの同士を集めたサイズ $q$ の集合に分割できて、それぞれで上のようにスコアの和を取ることで、 $q$ で割ることなく即座にスコアの和が $0$ になることが導ける。

残り時間はDを考えつつ、チームメイトのJを眺めていた。よくわからない二項係数の和を高速化することになって、WolframAlphaにいろいろ式変形してクエリを投げていたらしい。最後に投げた提出はTLEで、そこから手作業の式変形でmodintの割り算を減らしたら通ったようだ。7完。Hは振り返ればギャグだった。考察を重ねて、最後のステップがギャグだったのでしてやられた感があって良質だなと感じた。luckyな数の定義もスコアの定義も嫌な形をしているので、こういう風にしか解けないのだろう。

G問題は一瞬で通っていたが、後から考察メモを見て僕の知らない高度典型であることを知った。長さ $n$ で要素が $[0,2^{19})$ の数列が与えられるので、 $1\le k\le n$ に対し「 $k$ 要素の連続するとは限らない部分列であって、bitwise ANDが $0$ になるもの」の数を求めよという問題。包除原理を考える。あるbitマスク $mask$ について、それを含むような数の個数 $c$ を数え、 $\binom{c}{k}$ に $mask$ のpopcountによって符号をつけて足し合わせる。 $c$ を一気に求めるのは上位集合に対するゼータ変換で行え、 $1\le c\le n$ に対し掛けるべき符号を集めて $a_c$ としておくと、結局各 $k$ に対し $\sum_{c=k}^n a_c\binom{c}{k}$ が求まればよいことがわかる。

そんなの無理だろという見た目をしているが、ここからが高度典型ポイント。 $f(x)=\sum_{c=0}^n a_cx^c$ とすると、答えの母関数は $f(x+1)$ になり、多項式のTaylor Shiftというやつで求まる。言われてみればそう、 $a_c$ から $f(x+1)$ の次数 $k$ への寄与は $a_c(x+1)^c=a_c\sum_{k=0}^c \binom{c}{k}x^k$ を考えればちょうど $\binom{c}{k}$ になる。これに気付いて感動した。聞けば少し前のARCのボス問あたりでも出たらしい。

今日のOPUC-Iについて。木で $u$ から $v$ の方向に1歩進んだ頂点は、ダブリングでLCAを求める前計算から $O(\log N)$ で求まるらしい。 $depth_v-depth_u-1$ 回 $v$ から登ってみて、その頂点の親が $u$ ならその頂点が、そうでないなら $u$ の親が答えになる。これはさらに一般化できて、 $uv$ パス上で $k$ 番目の頂点を求めるのは、 $u$ からLCAまで登る途中にあるか、LCAから $v$ まで下る（ $v$ からLCAまで登る）途中にあるかで分けられる。今LCAも「頂点 $u$ から $k$ 回上った頂点」、つまりlevel ancestorも $O(\log N)$ で求まるので、全体でも $O(\log N)$ 。

これが $O(1)$ になるらしい。LCAはオイラーツアーした後RMQをsparse tableで求めることで $O(1)$ になる。一方level ancestorを $O(1)$ で求めるのはなかなかすごいことをしているようで、理解していない。前計算 $O(N\log N)$ と前計算 $O(N)$ があるとのこと。

GCJのqualが終わっていたことに気づいた。出したものは全部通って当然通過。E問題の考察は、次数がメチャメチャ大きい頂点に着目するところまで合っていて、「テレポート→1歩動く」を繰り返せばよかったらしい。1歩動いてたどり着いた頂点はランダムに選択したものではないため次数を見積もるための平均には入れない、などすると通るようだ。

A問題はパンチカードの問題だったが、その言語を使って提出できたらしい。

GCJパンチカードで解答できたの気づかなかったなこれで全問解くのは狂気すぎる pic.twitter.com/zhiROQUGBa
— ゆきだるま (@yuki_prog) 2022年4月3日

今日はこれ以降コンテストがないのに日付が変わっていないのを見て、結構自由な時間があるなと思っていた。しかし午前0時半ごろ急激な眠気に襲われ、椅子の上で意識を飛ばしてしまった。1時間くらいして目を覚まし、こりゃまずいと思って日記も書かず布団に移動。そこからは朝までぐっすりだった。