07/25(月)

午後0時半起床。午後1時からMulti-Universities Campの3回目。3日連続5hでもうヘトヘト。

"蔚来杯"2022牛客暑期多校训练营3_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

これまでの2セットは結構簡単だったので舐めてかかっていたらボコボコにしてやられた。チームでAJHCFDの6完。僕はCとFを書いた。

Cは01234のみからなる文字列が与えられるので、自由な順序で連結して辞書順最小にせよという問題。有名な話で、 $a+b\lt b+a$ という比較関数でソートすることで達成される。しかし制約がドヤバい。文字列の数 $N$ が $2\times 10^6$ 、文字列長の総和 $|S|$ が $2\times 10^7$ であった。しかも問題文の下のほうに、 $O(|S|\log|S|)$ で出すならよく考えろとか、線形時間以外で通るとは思っていないとか書かれている。

しかしコンテスト開始直後からバンバン通されていたし、一方まともに解こうとするとtrie木や文字列アルゴで気合いを入れるしかなさそうだったので、実は $a+b\lt b+a$ でソートして通るのではないかという話になった。これはそもそも $O(|S|\log|S|)$ ですらないはず（解説スライドにはマージソートだと $O(|S|\log N)$ だと書いてあるが、謎）。一度は出して落ちたものの、コードを見ると毎回文字列の足し算をしていて、ここを手で1文字ずつ比較するように実装したら通った。本当はその間に全然違うことを書いて1WAしている。

Fは無向グラフが与えられるので、頂点 $x$ と $y$ を両端に持つ全頂点の並べ方であって、すべてのprefixとsuffixが連結成分をなすようなものが存在するか判定する問題。ただし $x,y$ も大量に与えられる。最初は2辺連結成分が重要だと思っていて、それに分解した後の木がパスで $x,y$ がパスの端点の成分に含まれるか判定していた。これはWA。考え直すとダメなケースがいくつも見つかって、結局どれも橋ではなく関節点が重要だということに気づいた。

関節点に注目するようなグラフの分解はないかと聞くと、チームメイトからBlock Cut Treeがそうであると指摘を受けた。うしさんのブログから拝借して貼り付ける。木に分解されるのは同じだから、パス云々は特に書き換えなくてもよさそう。これで出すと、なんとREしてしまった。かなり念入りにコードを眺めているのに全くミスが見つからず、半ば絶望していたら、いつの間にかリジャッジで通っていた。このせいで1時間くらいドブに捨てたことになる。最悪。

このあたりで午後4時半になったので、インターン先の定例会に参加した。その後も考察はしていたものの、実装には手を出していない。Bが解けたと主張したが後から確認すると全然詰め切れていなかった。

定例会は特に何もなし。進捗もない。毎週ミーティングだけしている気がしてかなり罪悪感がある。人の話を聞いているだけでは何かを生産していることにはならないのだ。勉強会は数理最適化の話だった。

終えてから先週の週記を完成させにかかった。最近毎週こうなってしまっている。午後11時半になってようやく読み返しまで終わり、何とか日付が変わる前に投稿できた。

今日のコンテストのupsolveを3問ばかりした。GAJの順。AJは簡単枠なので特にいうことなし。Gは非常に苦しかった。問題は単純で、二次元平面に凸多角形が二つ与えられ、それぞれ直線移動するため、衝突するタイミングを求めよというもの。方針はコンテスト中に固まっていて、実装をチームメイトに託したが、残念ながらWAが取れなかったらしい。

まず、最初から衝突している場合を取り除く。これは一方の多角形にもう一方の頂点が含まれるかチェックすればよい。普通にやると多角形の頂点数を $N$ と $M$ として $O(NM)$ になるが、これでは $N,M\le 50000$ という制約から厳しそう。ただ、二分探索することで $O(N\log M+M\log N)$ にできる。昔PCKの問題で出題されていて、その時にライブラリを整備しておいた。

凸多角形をN-2個の三角形に分割したあと角度に関する二分探索で調べる範囲を限ればO(log N)で解けるようだ。
週記（2020/11/16-2020/11/22） - kotatsugameの日記

あとは相対速度を考え、動かすほうの多角形の頂点が、固定されたほうの多角形の辺に衝突する時間を求めるのを、多角形を入れ替えつつ2回行えばよい。どの辺に衝突するかは二分探索できるはずだが、その範囲がわからなくて難しい。最初に、速度ベクトルと直交する方向に各点が符号付き距離でどれくらい離れているか見ておいて、それの最大・最小で切ることでやっと二分探索の準備が整う。

速度ベクトルを原点からの直線と見たとき、それと一致する辺があるケースに苦しめられていたようだ。最終的には、二分探索で衝突する辺が見つからなかったと判定されたときも、端の辺を使って交差判定しつつ答えを求めるようなコードにしたら通った。よくわからない。精度にはかなり気を使っていて、最終的に答えを求める部分まで全部整数で書けている。直線と直線の交点を求める式をよく眺めると、方向ベクトルに適当な有理数を掛けることで求めていたため、その有理数部分を抜き出した。

一応提出を貼っておくが、これもログインしないと見ることができない。もっぱら将来の自分のためである。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=52904615

別の問題に手を付けようか迷っているうちに布団に倒れこみ、そのまま寝落ちした。午前3時だった。

07/26(火)

午前10時くらいに目を覚ました。強烈な頭皮の痒みによる酷い目覚めで、慌ててシャワーを浴びた。すぐ布団に戻り、ラノベを読む。

「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」2巻を読了。特に記憶に残るシーンもなく、普通……という感想。1巻で出てきたヒロインたちと仲を深める巻として位置づけられており、終始安穏と進行していった。書くことがないので1巻の感想を確認してみると、学内での関係性に変化があることを望んでいたようだ。ところが、この巻は冒頭で夏休みに突入してしまったため、学内の様子がまったくと言っていいほど描かれなかった。

学食で食事し、予約していたラノベを受け取って帰宅。また別のラノベを開いて読んでいた。午後3時半ごろに再度就寝し、次に午後7時半に起床。やるべきことはいくつか思い浮かぶがどれもそれほど切羽詰まっていない。よって今日は、昨日に引き続いてupsolveを行うことにした。深夜までかかってHDBを通した。

Hは簡単枠で、入力される文字列を全部連結してSA＋LCPを求める。文字列長の総和が10⁶なのにTL 1secで、SA-ISを要求されている。それなら最初から最後まで全部線形時間でできるのかなと思っていたのに、一番最後の答えを求める部分で少しデータ構造を使う必要があって $\log$ がついた。 $\log$ の中身が文字列長の総和10⁶ではなく文字列の個数10⁵だったのが重要なのかもしれない。

Dは面白い。 $N$ 頂点の根付き木が与えられる。 $K$ 本の辺をランダムに選んで根の方向に向き付けたとき、頂点 $s$ から「その頂点が始点となっている辺をランダムに1本選び進む」操作を繰り返して根にたどり着くまでの、操作回数の期待値を求める問題。 $K=0$ の形が非常にきれいで、本質的だった。

辺がすべて向き付けられていないとする。頂点 $u$ に対し、 $u$ からスタートして $u$ の親に初めて進むまでの操作回数を $f(u)$ とおく。 $u$ の子の集合を $C_u$ とすると、 $f(u)=\frac{1+\sum_{v\in C_u}(1+f(v)+f(u))}{1+|C_u|}$ が成り立つ。 $f(u)$ を左辺にまとめることで、 $f(u)=1+\sum_{v\in C_u}(f(v)+1)$ を得る。ここで $F(u)=f(u)+1$ とおくと $F(u)=2+\sum_{v\in C_u}F(v)$ 。また $C_u=\emptyset$ のとき $F(u)=f(u)+1=2$ なので、実は $F(u)$ は $u$ の部分木に含まれる頂点の個数の倍と等しくなっている。

以上より $K=0$ のときの答えは、根と $s$ を結ぶパス上の（根以外の）頂点 $w$ に対し $f(w)=F(w)-1$ 、つまり $w$ の部分木のサイズ $\times 2-1$ を求め、和を取ったものになる。

さて、辺を1本向き付けたとき、 $F$ に対する影響はどうなるか。 $u$ とその子 $v$ について $v$ から $u$ に向き付けられたとすると、 $C_u\leftarrow C_u\setminus\{v\}$ とすることに等しい。つまり $F(u)\leftarrow F(u)-F(v)$ である。ここから一般に、 $v$ の先祖であって $v$ との間に他に向き付けられた辺がない頂点に対し、 $F$ は同時に $F(v)$ だけ減ることが分かった。

この考察を元に、それぞれの向き付けられた辺 $u\leftarrow v$ について、 $K=0$ のときの答えから $F(v)$ を引く際の係数の期待値を求める。上と同様に定めた $w$ について、 $u$ が $w$ の子孫だとして、辺 $uv$ が選ばれかつ $wu$ パスの辺がどれも選ばれない場合の数を考える。これは $wu$ パスに含まれる辺の数だけに依存する。しかも肝心の辺の数は $w$ を全部見たときある区間をなすため、あらかじめ前計算して累積和を用意しておくことで総和が直ちに求まることが分かった。ここから期待値が出る。

Bも面白かった。 $N$ 人の人と $K\le 10$ 個の仕事があり、人と仕事の組に対してコストが定まっているので、仕事 $i$ に $e_i$ 人割り当てたときの総コストを最小化する問題。 $\sum_i e_i=N$ である。

単純に最小費用流をすると間に合わないが、このグラフをよく見ると、人→仕事→人→仕事→……という風に通常の辺と逆辺を交互に通るのを繰り返していることがわかる。このうち仕事→人→仕事の部分をまとめることで頂点数を $O(K^2)$ にするのが根幹のアイディア。あらかじめすべての人を仕事 $1$ に割り当てておくことで、最初の人→仕事の部分が消えるため、より扱いやすくなる。

辺の数が $O(NK)$ に見えるところ、 $K^2$ 本のpriority_queueを使って管理することでこれまた $O(K^2)$ 本にできる。これで $O(K^2)$ 頂点 $O(K^2)$ 辺のグラフになって、各 $2\le j\le K$ に対し $1\rightarrow j$ に $e_j$ だけフローを流すのをシミュレートすると、流量 $1$ につきSPFAで $O(K^4)$ 、辺の更新に $O(K^2\log N)$ 。SPFAは平均的にはもっと速いはずなので、余裕を持って通る。ただし辺の管理をサボってsetで書いたら落ちた。

コンテスト中に解けたと主張したときの解法とよく似ているが、あらかじめ割り当てておく仕事を各人についてコスト最小のものにしていた点が異なる。これだと仕事→人→仕事の辺のコストが必ず非負になるので嬉しいと思っていたものの、割り当てを変更するときにそうではなくなる可能性がある。

また他のチームでは、あらかじめ適当に割り当てた後負閉路を探して解消するのを繰り返したらしい。祈ったら通ったとの話だが、その回数が実は $N$ で抑えられていたりするのだろうか。

少しコードゴルフをした。先週Rubyで書くBITが少し縮んだという話をしたのだが、その時縮んだコードの一つにBITの配列を0-indexedにしているものがあった。それを流用することでそもそも取得・更新すら0-indexedで行えるようになったらしく、わざわざ $+1$ していた部分がなくなって縮んでいた。

RubyでBITを書くとき汎用的に使えるテクが生み出されていた。
週記（2022/07/18-2022/07/24） - kotatsugameの日記

まず更新がi|=i+1となってこれまでのi+=i&-iより短い。なぜこれで正しいのかはピンとくる説明が得られていないものの、手でいくつか確かめれば納得できる。取得はどうにもならなかったようで、普通に1-indexedの変数を用意してアクセス時に1引いているが、これはつまり閉区間 $[0,i]$ にアクセスするために変数を $i+1$ にセットしなければならないということで、逆に開区間になったと思うとより自然さが増したと感じられる。

atcoder.jp

それからI問題を考えていた。解説を読むのすら大変で、昼前までずっと考え込んでいた。とりあえず納得できたところで今日は終了。頑張っていろいろ意味づけを考えたりしたので1本記事を書きたいと考えているが、いつになるやら……。内容が多いため日記に書ききるのは諦めた。

08/03追記：記事を書いて投稿した。

kotatsugame.hatenablog.com

I問題を考えつつラノベを読んでいた。「精霊少女に『カッコいい俺』だけ見せていたら、いつの間にか最強になっていた」を読了。パッケージングから期待していたほどには面白くなかった。「無双」と帯に大書されていたため、そんなに無双するなら爽快だろうなと思って読んだものの、相手をバッタバッタ倒すシーンの描写は飛ばされがちだった。ちゃんと主人公が格好良かったのは嬉しい。そもそもこの作品の元になったカクヨムを昔に読んだことがあって、当時の感想を日記から探してみると、かなり微妙な評価をしていたようだ。以下の引用では書籍化前のタイトルが書かれている。

1作読了。「美少女精霊たちに愛されたいと頑張ったら最強の精霊使いになっていた」。
週記（2021/09/06-2021/09/12） - kotatsugameの日記

午前10時からSRM834に出た。なぜか300点が2問あってRoomのチャットで話題になっていたが、コンテストが始まってしばらくして、片方がdiv.2の問題であったこと、全員に表示されているので何も特別な対応は取られないことがアナウンスされた。

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

Easy一つ目、WordleColors。Wordleにおける同じ文字の扱いがどうなっているのか知らなかったのだが、少なくともこの問題で説明されていたアルゴリズムでは一対一対応からあぶれたものは灰色になるようだ。つまり、Eが2文字しかないのに5文字全部Eで埋めると、うち3文字が黄色ですらなく灰色になるということ。さすがdiv.2由来、しかもdiv.2でもEasyに配置されていたらしく、実装は書いてある通りにやるだけ。

Easy二つ目、MatchingPatterns。パターン文字列を展開した後の長さが確定するので、まずこれが揃っていないとダメ。次に、英小文字と各変数の各文字に番号を振ってUFを作り、展開後のパターン文字列を見て一致すべき文字をマージする。異なる英小文字がマージされなければよい。復元もUFを見て、英小文字と同じ集合に入っていたらそれ、入っていなければ適当に全部aなど割り振っておく。

Medは面倒なだけ。各クランについて現在のパワーと誰がどの順で待っているかを持っておく。パワー最大のクランを求めるのにはpriority_queueを使った。待っている人がいないクランに人が来るか、パワーが更新される度にキューに入れる。取得時に本当に人が残っているかチェックすればよい。待っている人はクランごとにqueueで持ちたくなるが、クランが最大10⁶個あり、queueがデフォルトで512要素分のメモリを確保することを考えるとさすがにまずい。vectorで持って先頭インデックスを管理した。

Hardはちょっと変わった二部マッチング。まず条件として、黄色または灰色で塗られた同じ文字を集めてきたとき、先頭から連続するいくつかだけが黄色になっていないといけない。これが満たされていれば、その文字が答えに少なくとも何文字存在するかわかり、さらに灰色に塗られた文字があったらちょうどその文字数だけ存在していることも言える。このことは、問題を文字列における位置と文字の二部マッチングだと思って最大流で解こうとしたとき、文字側の頂点から終点に向かう辺に流量下限制約がついたことに相当する。これを表現して、あとは色に応じて位置と文字の間に辺を張ればよい。

考察の初手では緑色の文字を無視したものの、実際に解く際は辺を適切に張ればわざわざ無視しなくともよくなる。サンプルが通った段階で残り8分くらいで、そこから丁寧に確認していたら判定の抜けを見つけて冷や汗をかいた。修正し、それまで以上に念入りに確認して、残り3分くらいで提出。

チャレンジフェーズは特に何もせず。Medでqueueを大量に持っていた人が落ちていたらしい。システスで周りの人は結構落としていたところ、全部通って6位に浮上した。レートは2828→2881(+53)でhighest。丁寧にやりすぎて全完最下位になってしまったが、ちゃんと全部解けたのだし、結果的には注意力コンテスト気味だったためよかった。

しばらく日記を書いてから午後3時半に就寝。

07/27(水)

午後9時起床。

昨日読んでいたI問題の解説は、 $k$ が小さいときに第二種スターリング数 $S(n,n-k)$ が高速に計算できるという事実を使っていた。同様にI問題に関連して、 $\bmod$ の値が小さい場合にはどこでも高速に計算できるという事実があるようで、maspyさんが記事を書かれていた。

maspypy.com

3時間ほど布団で教科書を読んだ後、食事してPCの前に座ってセミナー準備をしつつ、明日Vtuberを引退される黛灰さんの生前葬配信を見ていた。

www.youtube.com

黛灰さんは、時折切り抜きで姿を目にするだけで特別追っていたわけではない。しかし有名Vtuberの引退というのはそうそう立ち会えないことであるし、その上生前葬というかなり特殊な企画なのだから、見ておいて損はないだろうという気持ちだった。コンテンツとして消費している感じがするため、彼のファンの方には申し訳ない。

どれも非常に良かった。正直なところどなたもあまり知らない上、黛灰さんとの関わりとなるとなおさら疎いのだが、それでも今交わされているのがほとんど最後の会話だと考えると自然とこみ上げてくるものがあった。自分が見た部分では、夏色まつりさん、伏見ガクさん、ハイヨカイさんの部分が好き。

夏色まつりさんについて。切り抜きから察するに、数年前はホロライブのVtuberとにじさんじのVtuberのコラボも頻繁に行われていたらしい。今はほとんどないし、調べた感じ僕が知らないだけではなさそうだった。そんな中でこうやって凸待ちにやってくるのを目にできてまず嬉しいというのがある。彼女が黛灰さんのファンであるということもにじさんじ非公式wikiに書いてあって、その関連で以前の凸待ちの切り抜きを見たことがあったので、やはり最後となれば万難を排して駆けつけるんだなあと感動した。勝手な想像だが、この「万難を排す」というのも過剰な表現ではなさそう。

伏見ガクさんについて。これは最後のやり取りがたまらない。黛灰さんからの呼びかけを受けて一瞬言葉に詰まったあたりに抑えきれなかった情動を感じる。

ハイヨカイさんについて。名前被りからデビュー時に少しやり取りがあったという縁で参加された方。登録者数が1万人に到達したらコラボしたいと昔言っていたのに、こういう形で顔を合わせることになって悔しいと話していたのが印象的。ラスト、お互いに「じゃあな、もう一人のカイ（灰）」と言い合っていたのがなんとも劇的だった。

ほんの数分の通話の間にチャンネル登録者数が1000人以上伸びていてすごい。一方で、「通話中に1万人まで伸ばそうぜ」というコメントやそれを諫めるようなコメントが散見されたが、二人の登録者数に大きな違いがある以上こういうことが起こるのもお互い織り込み済みだろうから、外野がとやかく言うことではないのだろうなと思った。数分で以前の倍になった登録者数を抱えて活動を続けるハイヨカイさんにも、彼なりの苦労があるのだろう。

朝方セミナー準備を終え、少し日記を書いて布団に入った。午前7時就寝。

07/28(木)

正午くらいに目を覚まし、スマホでYouTubeを開いたところ、昨日の生前葬がまだ行われていて本当にびっくりした。途中で枠が変わり昨日聞き逃した部分がアーカイブに入っていたので、それを少し見ていた。

その後ゴロゴロしながら教科書を読み進めていたら指導教員の先生からメールが来た。今日はオープンキャンパスなのでセミナーも休みにしませんか、ということだ。全く問題ないと返信した。代わりに来週木曜日、午前中に今日の分の時間を取ることになった。2回分時間があるのにずっと僕が発表する予定らしく、なぜ交互でないのかがわからないが、進みも悪いことだし自分が多くやる分には構わない。

閉店間際の学食に駆け込んで食事、予約していたラノベを購入して帰宅。しばらくラノベを読んだ後、午後5時から午後8時まで寝ていた。

起きたらちょうど黛灰さんの最後の配信が始まっていたので、それを見つつ火曜日に解説を読んだI問題の実装をした。巨大な $n$ に関するベル数の実装はよくわからず色々試行錯誤したが、それ以外は解説に沿って順当に実装が進む。手元で動かす場合コンパイルオプションでスタックサイズ制限を大きくしないとセグフォするのには困った。2時間くらいかけて何とかAC。

日付が変わる直前、黛灰さんが画面上から姿を消し、それから十数分のエンディングが流れた。最後に表示された「THE END」「THE STORY DOES NOT CONTINUE」を見ながら、Vtuberの引退について考えていた。つい三か月前にVtuberを見始めたばかりの人間が何をと自嘲する気持ちもあるが、考えたものは仕方ない。ここに書いておく。

黛灰さんが配信上で独自の物語を展開していたというのはちょっと調べればすぐわかる情報。そして、その物語を引退と同時に見事完結させたということになる。こんなに綺麗な終わり方があったのだろうかと、物語の細部を知らないなりにもそうやって感じ入っていた。そのころにはもうTwitterアカウントに鍵がかけられており、僕はフォローしていなかったため実際に目にできてはいないのだが、最後のツイートも配信画面と同じ文面だったらしい。

https://twitter.com/mayuzumi_X

一方、綺麗でない終わり方のことも考えていた。具体的には炎上による引退、もっと言えば潤羽るしあさんのことである。当時僕はまだVtuberというものから距離を取っていて、騒動を野次馬のような態度で眺めていた。それから少し経ち受験シーズンが終わったあたりで、受験勉強のため動画を見るのを止めていた潤羽るしあさんのファンのツイートが流れてきた。記憶によれば、無事合格したのでこれから配信アーカイブを思う存分見るぞという内容だったはず。しかし残念ながら、活動終了に伴って動画はすべて非公開になっていたのであった。

この人は受験生ということもあって特別期間が開いているが、普通のファンにとっても、普段通りの活動を続けていたのに突然炎上してそのまま引退ということになってしまったのはかなり辛いことだったろうと容易に想像できる。今回のようにお別れの心構えをするような期間もなかったわけだ。まあ実際のところ、潤羽るしあさんは無事転生されている。ただしそれでもキャラクターとしての死は確かにあった。

Vtuberには炎上による引退のほかにフェードアウトという結末も考えられて、そういう終わり方ではなくちゃんと期限を切って精いっぱい名残惜しむ時間が与えられたのは、……良かったと書こうとしたが、これは特にファンではない自分が言えた言葉ではない。名残惜しんでいるわけではないから。とにかく、そういう点まで含めて綺麗な終わり方だったと感じた。

何か作業したり書いたりする気になれなかったため、朝までラノベを読んでいた。2冊読了。

「VTuberなんだが配信切り忘れたら伝説になってた」4巻。特に何か思うこともなく読了してしまった。相変わらず配信シーンはギャグ一辺倒で、そこにストーリーとしてちょっとシリアスな話が混ざるものの、長引くことなくすぐ円満に解決する。細かいことを考えずただその場その場のギャグで笑って読み進められる本は、その時の気分によって受け取り方が異なるのだと思う。少なくとも今の感傷的な気分には合わなかった。

「純白と黄金」2巻。1巻に引き続き面白かった。相変わらず形容詞が軒並みヤンキーっぽい語彙に書き換えられていたのが笑える。内容としては、「天下逆上」というチームの元メンバーたちの関係性がメインで描かれていた。その分主人公が表舞台に立つことはほとんどなかったのだが、一方で今はもう実力を真面目に隠している様子でもなく、総合すれば主人公の最強さはかなりちょうどいい頻度で発揮されていて、最初から最後まで楽しめた。

少し気持ちが上向いてきた。2時間くらいインターンに関連する作業を行った後、なろうの更新を読んだり少し日記を書いたりして、午前10時過ぎ就寝。

07/29(金)

午後3時少し前に起床。

すぐミーティング。先週もほぼ同じ時間にミーティングを行っていた。今日はそれの続きで、昨日の朝方急に作業していたのはこのためであった。用意したものをお見せしてかなりじっくり説明を受け、今後やることを確認して終了。また2時間という長丁場になってしまったが、その分自分の疑問点について隅から隅まで解説してもらえたのでかなり良かった。

眠すぎてしばらくボーっとしながらYouTubeを眺めていた。気合いを入れてシャワーを浴びるなどの準備をし、ゲーセンに向かう。

まずスーパーノバの目の前にあるやよい軒で食事。食べ終わっていざゲーセンに向かってみると、チュウニズムの配置が変わっていた。なぜだろうと思いつつ筐体にAimeカードをかざすと、反応しない！画面にAimeカードを使用してのプレイができないと書いてあって、4台全部で試したがどれも同様の表示が出るだけに終わった。ネットワークに接続されていないのだろうか？

一時的な配置換えだからケーブルはわざわざ繋げなかったのか、など考えていたものの、なんにしてもログインできないならプレイする意味がない。GiGO仙台に河岸を変え、そこで閉店までプレイした。

ちなみに新規プレイを始められるのは午後11時10分までだった。先週以下のようなことを書いたので確認。ただし以前の制限について詳しく覚えていないため、あまり意味はなかった。

新たにプレイを始められる時刻の制限が以前より早められた気がする。
週記（2022/07/18-2022/07/24） - kotatsugameの日記

今日は理論値+2、14のAJ+3。すでに14は大変なものしか残っていない。

Theme of SeelischTact ULT AJ pic.twitter.com/UaTfuZFmQV
— こたつがめ (@kotatsugame_t) 2022年7月29日

追加されたときにSSS+を出して放置していたが、今日久しぶりにプレイしてみるとラストが押せるようになっていたため狙ってみた。ホールド3鍵＋タップの部分でやたらアタックを出していたのにも改善が見られて、いい感じに精度も取れるようになってきた頃合いで最高精度で噛み合った。

Twilight AJ pic.twitter.com/d6EwDUHXfu
— こたつがめ (@kotatsugame_t) 2022年7月29日

これも最高精度。中盤から終盤にかけて一生2連打とフリック＋エアーが降ってくるため、非常に体力を使う。昔詰めたときは、プレイする度に疲れ果ててラストでいつもヘロヘロになっていたため、諦めたのだった。今日は端フリックだったり2連打を両手で取ったりいろいろ体力を温存する押し方をして耐えた。忙しい中でも落ち着いてそういう運指を実現できるようになっていて、嬉しい。

CITRUS MONSTER AJ pic.twitter.com/hxHyYXmV5p
— こたつがめ (@kotatsugame_t) 2022年7月29日

ラストのタップスライドが難しすぎる。最初に遅めのものが降ってくるせいで以降ずっとそのスピードが頭に残っており、爆速のタップスライドも遅く擦ってしまっていたらしい。なるべく速く擦るようにしたら改善した。それでも噛み合い待ちには結構なプレイ回数がかかってしまったのだが。連奏すると序盤の速い配置がうまく押せなくなるのも辛い。いつもそこに癖がついて諦めることになる。今回もギリギリだった。

立ち食いそばを食べて日付が変わるあたりで帰宅。すぐシャワーを浴び、しばらくYouTubeを見た後日記を書いていた。布団に入ってまた少しYouTubeを見て、午前6時就寝。

07/30(土)

午後0時半起床。準備して午後1時からMulti-Universities Camp 4回目。そしてまた今日から3日連続5hである。

"蔚来杯"2022牛客暑期多校训练营4_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

チームでDNKCGLAHMEJIの12完、9位。自分はGAJを書いた。

Gは大変。長方形があって、辺上（かつ頂点上ではない箇所）にいくつか点が置かれている。その点に対して好きな順序で操作する。操作では、その点が置かれた辺と直交する方向に、別の辺または壁にぶつかるまで壁を伸ばすということをする。全部操作した後、辺と壁によって分割されたいくつかの長方形が得られるが、最も広いものの面積は最大でいくつにできるか？という問題。

最初に操作する点が縦方向に壁を伸ばすと決め打つ。縦縦と連続して操作するなら、その間に囲まれた空間が答えになるべきである。縦横と操作した場合、もう一度横に操作するのは縦縦のケースとほとんど同様で、縦横縦と操作するケースは横縦縦と一緒なので無視してよい、はず。あとは、最初の縦で一つ長方形が確定する場合と、縦横で角を囲って確定する場合を個別に処理した。WA。

実は縦横縦と操作するケースで横縦縦と一致しないものがある。これに気付くまで1時間ほどかかった。具体的な形は、うまく言葉で説明できないのでそれっぽい記号を探してきた。デュエルマスターズの第2弾拡張パックのシンボルマークみたいな囲い方（から1辺除いたもの）である。基本的には横縦縦でもっと広いものを作れるが、そうすると端のほうで縦が足りないケースが生じる。

DM Card DataBox**シンボルマーク・リスト**

AはHELPが来て読んでみたら誤読だった。 $(w,p)$ という組が $n$ 個あって、そこから $m\le 20$ 個選ぶ。基本的には選んだ $w$ の和を最大化したいのだが、そこにこれまで選んだペアの $p$ の積が係数としてかかるという問題。 $(w_i,p_i)\lt(w_j,p_j)\Leftrightarrow w_i(1-p_j)\gt w_j(1-p_i)$ という比較関数でソートして、順に取るとしてよい。係数がかかるのが面倒。しばらく考えて、ペアを逆順に選ぶことでこれまでの $w$ の和に係数を掛けて表せることに気づき、解けた。

Jは整理すると $\sum_{k=1}^L\min(A-k,B-2k,C-3k)$ が高速に求まればよくなった。ただし整理するのに数回失敗して時間を浪費している。このような $\min$ は機械的に処理できて、 $A-k\le B-2k\land A-k\le C-3k$ のケースと $B-2k\lt A-k\land B-2k\le C-3k$ のケースと $C-3k\lt A-k\land C-3k\lt B-2k$ のケースで漏れなく重複なく分割できている。それぞれ $k$ の区間を求めて、 $[1,L]$ に収まるように整えた後は $\sum$ を展開するだけ。

しばらくYouTubeを見たり少し日記を書いたりして、午後9時からARC145に出た。

AtCoder Regular Contest 145 - AtCoder

Aから大変だった。まず先頭の文字をA以外にはできないため、先頭がAで末尾がBだとアウト。一方先頭がBの場合、その後ろに対して順に操作することでBAA...ABという文字列を作れるため、OK。残りは先頭も末尾もAの場合で、これは両端を無視することで同じ問題に帰着できる、と考えた。WA。BAだけが残った場合にまずいことに気づき、対処するも、まだWA。

ここでようやく、BAA...ABと同様の操作を逆向きに行うことでAB...BBAが作れることに気づいた。つまり先頭がBまたは末尾がAならOK。逆にそれ以外のケースでは、先頭の文字をA以外にすることはできないし、末尾の文字をB以外にすることもできないため、どうしようもない。この判定は先頭文字以外・末尾文字以外に操作を行うため $N\ge 3$ を仮定しているので、 $N=2$ のケースを特別扱いし、ようやく通った。

Bは簡単。まず $A\le B$ なら最初に取れるだけ取ることで勝てるため、 $A\le n$ であるような $n$ を数えればよい。 $A\gt B$ のときは $A\le n$ かつ $(n\bmod A)\lt B$ である必要がある。 $0\dots N$ を $A$ 個ごとに分けて求めた。

Cも簡単……と言いつつ少し時間がかかっている。明らかに $2N$ と $2N-1$ 、 $2N-2$ と $2N-3$ 、……をペアにするのが良い。後からペアの順番 $N!$ 、ペアの左右の決め方 $2^N$ を掛けることにすれば、問題はちゃんとペアを作れる順列がどれだけあるかを求めるものになる。

dpを高速化する方針で考えていた。その時点で取った $A$ の要素数と $B$ の要素数の差を持って更新できる。しかし実は、数え上げる対象は順列であって $A$ と $B$ の分け方には興味がない。つまり、 $A$ と $B$ が両方同じ要素数なら次の要素は $A$ のほうに入れると決め打つべきで、すると先ほどの差は常に非負となる。手でdpテーブルを書いているうちにこれがカタラン数であることに気づき、ググって式を書いて通した。

Dは解けなかった。初手で要素ごとの差を取ったのがまずかったか。しかもその差を $1\dots N-1$ だと固定して、適当に並べ替えて $y-x\ne z-y$ の条件を満たせないかずっとガチャガチャしていた。そもそもこれをもとの要素に戻すと最大 $N(N-1)/2$ になって制約違反してしまうので、全くもってナンセンス。さらに悪いことに書いたジャッジが間違っていて、解けたと思い込んで一通り実装し提出までしてしまったため、この方針を捨てることができなかった。

コンテスト後にUm_nikの提出を見ると、差を取る前の状態で小さい値から貪欲していて本当にびっくりした。僕も差を取った状態ながらそういう貪欲を考えてはみたものの、手計算だったため、最初数項が大きくなるのを見て以降どのような構造をしているか明らかにせずに諦めてしまっていた。実際はフラクタルのようになっていて、ところどころ大きくなってしまうだけだったようだ。

こういう問題は手元でジャッジを書いておくと便利ではある。しかしどつぼにはまった後も真面目な考察に戻れずずっとガチャガチャし続けてしまうことがあり、今日はそれだった。ほかにも、一旦計算量の悪い解法で答えが出せてしまったら、以降ひたすら高速化を試み続けることもある。まとめると、ある程度進んだ考察から戻ってこれないということが自分の弱点。5hもあれば話は別だが、普段のコンテストで途中で頭を切り替えるというのはなかなか上手くいかない……。

コードゴルフ。Aはsedで、コーナーケースの対処には文字列がBAでないことを判定するよりBAであることを判定したほうが短くなった。つまり、先頭がAで末尾がBの文字列またはBAならNo、それ以外はYesという書き方。BCはdc。Cは $\frac{(2N)!}{(N+1)!}\times 2^N$ を $2\times\prod_{i=N+2}^{2N}2i$ と見て計算するのが良い。 $N=1$ を特別扱いしない方法が思いつかず、場合分けでどうしてもコードが長くなってしまっている。

Bは公式解説の式を変形し、 $\left(\lfloor N/A\rfloor-1\right)\times\min(A,B)+\min((N\bmod A)+1,B)$ と $0$ の $\max$ を出力。途中で $\min$ が2回出現するのが面倒。ここでたまたま奇跡的なスタック操作が実現でき、1B縮んだのが面白かった。

最初に $x=(N\bmod A)+1$ と $B$ の $\min$ を求める。 $x\le B$ のときスタックには $x$ だけが詰まれ、 $x\gt B$ ならばスタックには $x$ と $B$ が詰まれることになる。直後に $A$ と $B$ の $\min$ を求める。この時も $A\le B$ ならばスタックには $A$ だけが積まれ、 $A\gt B$ ならば $A$ と $B$ が積まれる。さて、この状態でスタックの3番目を取り出す操作3Rを行うと、何が得られるだろうか？

$x\gt B$ のとき、 $x=(N\bmod A)+1\le A$ より $A\gt B$ であることに注意。つまり、スタックの状態は4通りあるように見えて実は3通りしかなく、それぞれ $x,A,B$ 、 $x,A$ 、 $x,B,A,B$ となっていることがわかる。この状態で3Rをすると、スタックの深さが足りない場合は一番底のものが取り出されるから、順に $x$ 、 $x$ 、 $B$ が得られる。つまり $\min(x,B)$ 。変数に退避させたりduplicateしたりすることなく取得できるのが更新ポイントだった。

午前1時からTCO22 R4。開始数分前に30分こどふぉってびっくりした。空いた時間はハーメルンの更新をチェックしていた。

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

Easyは面倒なだけ。少し前にABCで似た問題を見た覚えがあって、これ答えが高々1通りになるんじゃなかったかと思いながら書いていたら、PrePostInとPreInPostの組み合わせで左右の部分木が特定できないことに気づいた。やはりちゃんと掛け算して $\bmod$ を取る必要があるらしい。再帰呼び出しの回数も爆発しそうだったので、メモ化したり、vectorを毎回生成せずインデックスの区間で管理したりと、少し時間をかけて高速化を施した。

F - Pre-order and In-order

メモ化配列は二つの区間つまり4変数に対して持つとREしてしまったので、区間の長さが常に等しいことを利用して3変数に状態を圧縮。時間がかかるケースがすぐ手元で作れるわけではないし、もうコンテスト開始から30分近く経っているのだからと提出してみたら、それがRoomで最初の提出だった。やはり普段のコンテストとは配点こそ同じでも難易度が全く異なるらしい。

Medは謎。小さい値を優先的に埋めたくなって、とりあえず書いた。当然のように2べきの数が表れている。ここで順位表を見ると、爆速で提出している人がちらほら見受けられるから、その人たちはたぶんこの解法なんだろうなと思った。ただ、こんなのがMedに置かれるわけがない。しばらく実験してみると、大きい値をたくさん使うことで使った値の範囲を狭められることに気付いたため、今度は大きい値から順に埋めてみることにした。適度にbitsetを使ってdpしているから制約が小さいことを利用していると言えなくもない。実行してみると先ほどまでの解よりかなり良いものが見つかったため、提出した。

Hardに進んで問題文を読み、何もわからなかったのでMedのテストをすることにした。現在使える最大の値を常に使うようにしているが、これは本当に正しいのだろうか？実際に試してみると、 $B=8$ 、 $P=2$ のときに $A=38$ で答えが見つかるのに $A=39$ だと見つからないということが発覚した。この時点で残り3分、急いで $A\dots 1$ を順に試すように書き直し、リサブした。

他に $(B,A,P)=(8,85,8)$ なども僕の最初のコードでは落ちる。当然、小さい値から優先的に埋めていくともっと大きな値が出現してしまうため、部屋にもちらほらいた300点以上を取っている人たちはこのケースで軒並み落ちるだろうと予想できた。チャレンジフェーズが開始してすぐ、初動の被りを避けるためレートが低い人の提出ではなく敢えて順位が高い人の提出を見に行った。チラッと見ると明らかに小さい値から埋めているので、先ほどのケースでチャレンジし、落とした。

部屋の他の人に動きがないのをいいことに、そのまま順に提出を開いて、さらに二つ落とした。他にもう二つよくわからない提出があったが、これらもええいままよとチャレンジすると見事に落ちた。ほとんどノールックみたいなもの。この時点で部屋で通っているMedは僕ともう一人、埋め込みしていた人のものだけになった。

その後適当にEasyを眺めていたら僕のコードも落とされた。まあ当然で、先ほどの $A=38$ と $A=39$ の違いは値を決めていく途中でも生じ得るから、途中も含めどうにかして全探索するしかなかったのだ。先ほど取り上げた $B=8$ 、 $P=2$ のケースも、 $A$ が $38$ よりもう少し小さくても可能らしい。システスではなんと埋め込みしていた人のMedも落ち、Easyもポロポロ落ちて死屍累々。通った人の提出と見比べると微妙に値が異なっていたことが分かった。

部屋運で稼がせてもらいました…… pic.twitter.com/IbXGVCqphZ
— こたつがめ (@kotatsugame_t) 2022年7月30日

Easyの点数は決して高くないのに、チャレンジで+250pt稼いだ結果6位になった。もしかしてFinals出場だろうか。Medの提出が多く、強い人が少ない部屋だったということで、運がよかっただけの結果に思えてしまいあまり釈然としない。MedかHardを通した人が合計9人しかいないのだから、どうしてもEasy 1完の人がFinalsに進出することになって、それが僕だったと思えば少し楽になった。もちろんEasy 1完で通っているのは僕だけではない。

レート変動は次の日に確認したが、わかりやすさのためここに書いておく。2881→2969(+88)でhighest。一気にTargetが現実味を帯びてきて怖い。

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

07/31(日)

午後3時半起床。今日はOpenCup、ABC、CFがある。特にABCはオンサイト予選を兼ねており、落ち着いてちゃんと参加したいため、OpenCupをずらして午後3時50分から5時間で参加しましょうとチームで合意が取れていた。その時間から5時間、1時間40分、2時間30分、次の日の午後1時からさらに5時間と、連続する26時間10分のうち合計で14時間10分コンテストに参加することになるらしい。楽しくなってきた。日記を書くのが全然間に合わないのだけが辛い。

さて、まずOpenCup。今日はGrand Prix of China。チームとしてAILEBCDJHGを解き、なんと優勝した。japan25というのが僕の参加しているチームである。終盤ペナ差で抜かされ、さらに完数で差をつけられて、さすがに優勝なんて夢のまた夢かと思っていたら、残り1分を切ってからチームメイトが投げたGが通ったと聞いて本当にびっくりした。ペナ差も逆転していて最高。

GP of China is just finished. I'm the author of ABCDGHL, developer of KM.

Congratulations on japan25 winning the contest and japan02 solving 11 in the testing contest.

And another two puzzle-themed problems in the problemset, which are solved very early in the testing contest. pic.twitter.com/YmwAonWv5L
— apiad (@xudyh) 2022年7月31日

ただ、この結果はチームメイトの力によるものがほとんど。自分はAIBDを解いたが、AとIは簡単枠である。よって実質的な貢献はBとDのみ。その上Bも簡単寄りだった。

Bは、長さ $5000$ 以下の文字列が与えられるので、その部分文字列であって、空でない文字列 $A,B,C$ によって $A+A+B+C+A+B$ と表せるようなものを数え上げよという問題。ただし位置が異なれば違う文字列だと見なす。この $A+A+B+C+A+B$ とは一体何かというと、"114514"のことであるらしい。これが問題文中に何食わぬ顔して例として挙げられており驚いた。

問題としてはまとも。いろいろ方針はあるようだが、自分はまず2か所の $A+B$ を全探索して、最初の $A+B$ の位置に $|A|$ としてありうる値を記録しておき、次に $|A|$ とそのスタート位置を全探索した。可能な $|A|$ は2か所の $A+B$ を決めるごとに $1$ 始まりの区間になるので、それで管理する。2点からスタートする文字列がどれくらいの長さまで等しくなるかを知りたくなって、その部分にZ-algorithmを使ったりSA＋LCPを使ったりしたら、手元では十分高速なはずなのにTLEして大変だった。実際はオーダーを変えずdpなり愚直で求まる。手元で倍速になったので出したら通った。

Dは面白い。二次元平面上に2点と2本の線分があるので、2点を線分と接したり交差しない折れ線で結ぶとき、曲がる回数の最小値を求める問題。めちゃくちゃ遠い点を経由することで2回で必ず可能で、また0回の判定も容易なため、1回でできるかどうかを判定すればよい。

1回曲がるとして、その曲がる点は、与えられた2点からそれぞれ線分に邪魔されず辿り着ける必要がある。点の位置をほぼ無限遠点だと思えば、これはある角度であって2点からその角度に進んだとき先に線分がないようなものを探す問題になる。ここで片方の点をもう片方の点に揃え、それに伴って線分もコピーしてずらすと、4本の線分が1点の周りを囲んでいるか調べる問題になった。

特にこのとき線分は2本ずつ並行になっているため、2回曲がるケースがどんな形をしていなければならないかわかり、確かに最大2回でできるのは正しそうだなという気持ちになった。

あとは実装。線分を端点の偏角で並べて、一周をカバーしているか調べればよい。カバーがちゃんと繋がっているかの判定は外積を使って頑張る。ただし一気に180度飛ぶ、つまり片側180度にすべての線分が集まるケースで壊れるので、それを防ぐため、全ての点を見てその両側に点が存在することをチェックした。この「全て」の部分で1点だけチェックしてしまい1WA。解決するのに1時間くらいかけた。

午後9時からABC262。前半の実装が軽めと予告されていて、どのくらいコードゴルフするか迷いそうだなと思っていた。実際はそんな余裕などどこにもなかった。

AtCoder Beginner Contest 262 - AtCoder

Aは何か簡単なやり方がありそうに見えたが、よくわからないのでとりあえず $\lceil Y/4\rceil\times 4+2$ を出した。WA。正しくは $\lceil(Y-2)/4\rceil\times 4+2$ である。Bは普通に3重ループで、特に短い書き方もなさそう。ここからC++を使っていた。

Cは $a_i=i$ かつ $a_j=j$ のケースだけ数えてサンプルが合わず首を傾げた。しかも数えるときも $i\lt j$ を確かめるためにと思い込んで不必要なBITを使っており、大変焦っていたのが見て取れる。 $a_i=j$ かつ $a_j=i$ のケースは $i$ を全探索すれば十分。Dは取る個数を決め打って毎回 $O(N^3)$ のdp。ちょっと実行時間が怖い気もしたが、手元で試すと爆速だった。

Eが全然わからない。まさかこんな急激に難易度が跳ね上がるとは。初手が見えなかった段階でいったん一息つこうと順位表を見ると、AのWAが大きく響いて3桁の順位に位置しており、真っ青になった。そこから20分くらい考えて、どうにもわからないのでFに進むことにした。

Fはまず先頭要素が決まる。 $i\le K+1$ または $N-i+1\le K$ であって、 $p_i$ が最小となるもの。前者は前の項を削除することで、後者は末尾からrotateしてくることで先頭に持ってくるのを意図している。それぞれ試す。

前の項を削除する方は簡単。以降rotate操作は使わないから、全体で $K$ 個スキップすることになる。今 $p_{[i,N]}$ を見ていて、残りの削除回数が $K$ 回だったとすれば、 $N-i+1\le K$ なら全部削除、そうでない場合 $p_{[i,i+K]}$ の中で最小値を達成するものを選んでその手前を削除するのが良い。セグメント木で書ける。こちらは先頭要素をあらかじめ決めなくてもよかった。

後者も最初にrotateしておけばほぼ同様。ただし、一度rotateした要素を削除するのにコストがかからないことに注意。見ているインデックス $i$ がrotateしてきたものの一部だった場合、先ほど使用した「残りの削除回数」に、 $i$ 以降でrotateしてきたものの個数を足しておく必要がある。あまり詰めずに書き始めたが、先に前者の実装を行ったため、それから変わる部分を丁寧に考えることでスムーズに書き切ることができた。サンプルを合わせて投げると1発で通った。

Eに戻る。昨日のARC-Dと同様こちらも考え方が凝り固まってしまったように感じられたので、いったん席を立って気分転換した。その間にふと、もし $K=1,2$ ならどうなるかというのを考えてみた。 $K=1$ なら次数が偶数の点を選ぶしかない。 $K=2$ なら、2頂点の次数を足した後、選んだ2頂点の間に辺があるかないかを考え……。

考える必要がない！なぜなら、選んだ2頂点の間に辺があったとして、それは必ず2回カウントされて偶奇に関係しないからだ。つまり、次数が奇数の点を偶数個選ぶような方法を数え上げればよい。慌てて着席しガガッと書いたら当然のようにサンプルが合い、そのままAC。順位表はちょくちょく見ていたので、なるほどこれはいろんなレート帯の人が爆速で通しているわけだと納得した。

何とか1ページ目に上がって一安心。Gに取り掛かった。スタックに入れたり出したりすることを忘れ、元の列の要素を適当に捨てたり並べ替えたりして広義単調増加にするのだと思うことにする。並べ替えはそれほど自由ではないが、しばらく考えているうちに、二つのブロックを適切な順序で連結して新しいブロックにすることを繰り返すことで、ちょうどすべての場合を考慮できそうだと分かった。よって区間dpを考える。

$dp_{l,r,x,y}$ を、元の列の $a_{[l,r)}$ を使って作れる、要素が $[x,y]$ に収まる広義単調増加列の最大長と定義しよう。とりあえず $dp_{l,r,x,y}\leftarrow\max(dp_{l+1,r,x,y},dp_{l,r-1,x,y},dp_{l,r,x+1,y},dp_{l,r,x,y-1})$ としておく。あとは $l\lt k\lt r$ と $x\le z\le y$ を用いて、 $[x,z]$ と $[z,y]$ で作った列をマージするケースを考える。まず、 $[l,k)$ で $[x,z]$ の列を作った後に $[k,r)$ で $[z,y]$ の列を作る場合。これは両方とも好きなように操作してよいため、 $dp_{l,k,x,z}+dp_{k,r,z,y}$ となる。

次に、逆に $[k,r)$ で $[x,z]$ の列を作った後に $[l,k)$ で $[z,y]$ の列を作る場合。今度は $[l,k)$ の部分はスタックを掘る方向でしか積み重ねられないので、 $dp_{l,k,z,y}$ ではなく、 $a_{[l,k)}$ を逆順（スタックに入れて出すと反転するから）で使って作れる $[z,y]$ の広義単調増加列の最大長を使う。この計算を別途行うのは面倒だったので、dp配列をもう1本用意して似た遷移を行うことで求めた。

ここまでたどり着くのに2WAしている。dp配列をそのまま使ってはいけないケースを見落としていたものと、どの遷移を修正するか間違えたもの。いよいよ通るだろうと出したら2ケースだけWAだった。dpの遷移順が怪しいと睨んでもう1WAしたあと、 $x,y$ の範囲を $[1,50]$ ではなく $[1,N]$ としていたことに気づいた。これを修正して投げ、AC。定数倍軽めの $O(N^6)$ で1sec。

7完5WAで15位。Eで信じられないくらい詰まったところから何とか持ち直すことができてよかった。コンテスト前はめちゃくちゃ舐めた態度だったのに普通に落ちかけて、本当に恥ずかしい思いをするところだった。

Eは1頂点ずつ青から赤に塗り替えることを考えても同じ結論が出るらしい。青い頂点を赤く塗ったとき、端点の色が異なる辺の本数の偶奇が変わるのは、頂点の次数が奇数であることと同値であるとわかる。この事実には僕も早い段階で気づいていたはずなのだが、そこから次数が偶数の点を削除してみたりとよくわからないことを考えてしまい、袋小路に迷い込んだようだ。色を変えるのではなく色を新しく塗ることを考えていたと言える。

午後11時からCF combined。CodeTON Round 2とタイトルがついている。

Dashboard - CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aは $a$ の先頭 $n-m+1$ 文字に $b_1$ と等しい文字があるかと、末尾 $m-1$ 文字が $a$ と $b$ で等しいか判定。Bは先頭からありうる $v$ を区間で管理して、区間が消えるタイミングで答えに加算。Cは未感染の家を連結成分に分解し、長いものから順に両端を保護するのが最適っぽい。あまり細かくは証明しなかった。

Dは謎。全然わからなかったので、先頭から操作を巻き戻すようなことをしてみた。 $j=1\dots m-1$ について $d=\min_i c_{i,j}$ として、 $c_{i,j+1}\leftarrow c_{i,j+1}+c_{i,j}-d$ と更新する。このときの $c_{i,j}-d$ を $i$ ごとに足しておいて、出力してみると、なんと差が答えになっていた。半信半疑で提出するとAC。運が良い。

Eも謎。トポロジカルソートをして、頂点ごとに値がどのタイミングでインクリメントされるか考えてみた。初期状態においてそのタイミングは区間 $[0,a_i)$ になっていて、区間 $[l,r)$ を有向辺の先に送ると $[l+1,r+1)$ になる。頂点ごとにこの区間を長さを保つようにマージしておく。ここで、 $r$ はいくらでも大きくなりそうなものの、 $l$ は高々 $n-1$ であることがポイント。このため、 $r\ge M=998244353$ のとき $r\leftarrow M+(r\bmod M)$ とすることで、必要な大小関係を保ちながら $\bmod$ を取ることができる。区間の個数が最大どれくらいになるのか何も考えていなかったが、通った。

Fは実験。基本的に自分の手番では自分の色を1個だけ含むように操作することができて、その時に相手の色も1個消せるとうれしい。よって両者とも2色まとめて消すのを優先的に行う。2色が並んだ部分は先手でも後手でも操作できるので、2色まとめて消すことができなくなった状態においては、先手と後手が同じ回数だけ操作したか、先手が1回多く操作したかのどちらかになる。前者なら初期状態でRの個数がBの個数より多い場合に勝つ。後者なら「より多い」の部分が「以上」でも勝てる。

よって、Rの個数とBの個数の差が $0$ だった場合だけ、2色まとめて消す操作ができなくなったほうが負けというゲームになる。2色が交互に並んだ区間に分割し、その長さが偶数の時と奇数の時に分けてGrundy数を計算して眺めると、それぞれ長さ17の周期が存在することに気づいた。小さいところは微妙にずれているので200個程度は計算し、より大きい部分は周期を使って求めてみる。なんだか騙されたような気分になりつつ提出したら通った。

H1に進むも解けず。システスは全部通って6完55位、レートは2959→2944(-15)。微妙。

DのTLに流れてきた説明が面白かった。 $c_i$ を何らかの数列の頻度配列だと思うと、操作1では数列の総和が不変な一方、操作2では1回ごとに $+1$ する。よって元の数列に直して総和の差を見ると解けるらしい。自分の解法も整理すると大体同じことをやっていた。Fは遷移をよく見ると偶奇で分ける必要がないことに気づく。コンテスト後のTLで周期34と見てひっくり返ったが、単に17＋17だった。

最適。
D:cが、ある配列aの頻度配列であるとみなす。操作1はaのある2要素に+1,-1する操作と見なせ、操作2は、aのある2要素に+2,-1する操作と見なせる。操作1により総和は不変、操作2により総和は1増える
E:まずn回愚直にシミュレーションする。これによって、aが正の頂点はdagの終点まで連結になる。残
— くで (@kude_coder) 2022年7月31日

ABCのコードゴルフ。Aはdcで、上で示した式を特に工夫なく書いている。 $\bmod 4$ をうまく使って足す値を得る方針も試したが縮まなかった。B、CはAWKで、Cは負け。以降は手付かず。

BはABC258-Gと似ているが、そちらの最短コードと同様の方針で隣接行列を使おうとすると入力がちょっと面倒。その部分が短いAWKで素直に3重ループを回すと縮み、さらに読み込みながら毎回チェックすることでもっと縮んだ。G[$1][$2]やG[$2][$1]をコード中で使用することで、配列G[$1]がインデックス$2を持つといった判定が成立するようにし、k in G[$1]とk in G[$2]を両方満たすようなkを数える。特にfor(k in G[$1])とすることで、実際に判定するのを片方だけにできる。この演算子をコードゴルフで使ったのは初めてかもしれない。全体的にプリミティブなAWKにおいて、これだけ突出して高度な機能を持っていると感じる。

午前7時までは日記を書いていたが、いくらか空白の部分を残したまま明日のコンテストのため布団に移動した。また明日、コンテストが終わってから完成させたい。Multi-Universities Campの間はずっとこれが続きそう。少しハーメルンの更新を読んで午前8時就寝。