kotatsugameの日記

全編通して組み合わせ的な解釈のみでゴリ押している。具体的には $\sum_P c(P)^k$ 、Touchard's congruence、 $|P_{k,n}|=S(n+k,n)$ がそういう解釈を頑張ったところ。一つ目は先週の時点で分かっていたためすぐ書けたものの、残り二つには多くの時間を費やすことになった。二つ目は記事を書いている途中で読んでいた論文から思いつき、説明をまとめるのに苦労した。三つ目は論文を写してきただけだが、読解しながら書いたためこれも大変だった。何とか完成してくれてうれしい。

午後0時半就寝。

08/03(水)

午後7時くらいに目を覚まして1時間くらい教科書を読んでいた記憶がある。また寝て、次に午後10時起床。

布団の中で教科書を読み進めていたが、ちゃんと前のページを読み返したりしないと意味の取れない記述が出てきたので起き上がった。これが日付が変わる前のこと。そこからハーメルンに意識を奪われたりYouTubeを見たりしつつじりじり教科書を読み進めた。

午前4時までかけて一段落するところまで読み終えた後、それを発表資料にまとめることは諦めて、先週の資料を読み返して記憶を復元する作業を行った。明日は午前中にもセミナーがあるので早く寝なければならない。午前中は先週の資料を発表して、間の時間で教科書の先ほど読んだところをまとめ午後からのセミナーに備えようという心積もりだ。

読み返し終わったのが午前5時過ぎで、その後すぐ就寝。

今日見ていた動画はこれ↓。やはり社築さんは見ていて安心感がある。ずっとレバガチャを擦られ続けていて面白かった。十数年前にやったきりと言っておきながらちゃんと上手いのはすごい。いくら相手が初見だといってもこんなに差がつくのだなとびっくりした。

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

08/04(木)

午前8時半起床。TCO Finals進出決定のメールが届いていた。

Hello,

Congratulations! You are a TCO22 Algorithm Finalist! 🎉
— こたつがめ (@kotatsugame_t) 2022年8月3日

今のところオンサイトで開催予定らしい。アメリカ旅行である。こうなってみると、今年度の初めに身分証明書としてしか使う予定のないパスポートを頑張って更新しておいたのはかなり偉かった。ただ、英会話が怖い。一応海外に行った経験が2回あるのだが、それぞれ同じ日本人旅行者と常に一緒に行動したり、日本語を話せる通訳の方がついてくれたりしたので、自分から英語を話す機会というのはほとんどなかったのだ。

そろそろ期限が切れるパスポートを更新しなければならない。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

食事してセミナーに向け出発。ちゃんと時間通り二人揃ったのだが、肝心の先生が来ない。うっすら忘れておられるんだろうなということはわかっていたが、昨日やり残した発表資料のまとめが終わっていないため何食わぬ顔でしばらく準備を続けていた。1時間程度したところで、確認のメールも送らないのはさすがにまずいということに気づき、送信。ちょっと遅すぎた気もする。

すぐ返信が来て、しばらくしてご本人も無事到着され、1時間程度セミナーをした。前回ちょっとした課題が出されていたのでまずそれの解答を確認。関連する話題でひとしきり話していたら、結局午前中は発表せずに終了した。

昼食を摂り、午後はまず講義から。木曜3限、数理論理学特論はこれが初めての出席となる。そして最終回。なのに眠気に負け、中盤は結構大胆に目を閉じていた。最後にレポート課題の説明がされたのだが、これは今日初めて顔を見せた僕も提出してよいのだろうか。ちなみに内容は、この講義に関係する論文を1本以上読んでサーベイせよというものなので、最悪講義の中身を知らなくても書けないことはないはず。

本当は数理論理学特論という僕の指導教員の先生が担当されている講義も取っていたのだが、これは一度も出席できていないためほぼ放棄している。
週記（2022/07/11-2022/07/17） - kotatsugameの日記

そしてセミナーの午後の部へ。先週用意した分のみで終わるかなと思っていたら、準備の時に行間を丁寧に書きすぎたらしくA4 6ページ分を1時間で発表し終えてしまった。今後はこれを参考に時間配分を考えて資料を用意するようにしたい。では今日用意した分まで踏み込んだかというとそうでもなくて、残り1時間は先生の指摘により、今日話した内容の具体例をいろいろ確認していた。一般マッチングに関する強めの主張（Diestel、Theorem 2.2.3）を示したのだが、実際のグラフでどんな風に実現されるか見たいとのこと。簡単なグラフをいろいろ書いて確かめていた。

夕食を摂り午後7時前に帰宅。山道を原付で走っていたところ、ガードレールの外側を歩いている歩行者がいて心底びっくりした。ちょうど道路も混雑しているからあまり大きく避けることもできない。どうやら二人連れらしく、ガードレールを挟んで会話しながら歩いていたようだ。歩道が狭いのはわかるが、ちょうど急カーブの内側なんだから轢かれても文句は言えないぞと思った。

疲れからかなりの時間TLを眺めて過ごした。三項演算子が話題になっていたので、ちょっとした言語仕様クイズを行った。どんな言語でも〇〇、ということを示すのは悪魔の証明なので、AtCoderで使える言語のみと絞り込んだとしてもとても言い切れるものではないから、メタ読みで「どちらでもない」が答えだとわかりそう。

a?b:c?d:eは（AtCoderで使える言語のみを考えたとき）
— こたつがめ (@kotatsugame_t) 2022年8月4日

(a?b:c)?d:e：PHP
a?b:(c?d:e)：C++などほとんどの言語
ということで正解は「どちらでもない」です
— こたつがめ (@kotatsugame_t) 2022年8月4日

PHPのこの仕様はかなり特徴的なので、最後にPHPを書いてから数年経った今も覚えていた。誰も得しない。後日引用RTで指摘されたことだが、PHP8.0からはこのような書き方のとき括弧を入れないとエラーになるらしい。ちゃんと「AtCoderで使える言語のみ」という注意書きを書いておいて助かった。

a?b:c?d:e は今のPHPではエラーになるはず……と思ったけど、AtCoderに入っているPHPは7.4.4だった😇
【PHP8.0】PHPの三項演算子が他言語の実装に一歩近付く - Qiitahttps://t.co/3dg8clBlBJ https://t.co/4zBGINAsyC
— kusanoさん@がんばらない (@kusano_k) 2022年8月5日

しばらくTCO Finalsのための書類を作成していた。一つ二つ完成したところで午後11時半からECR133に出た。

Aは $n\bmod 3$ で分類。 $n=1$ だけ2手かかることに注意。Bはfixednessを毎回1以上減らさなければならず、特に最初はちょうど2減らすことになる。逆に、 $i\rightarrow i+1$ において $i$ 番目と $i+1$ 番目をswapすることでこれが達成できるため、最適。

Cはかなり時間がかかった。しばらくジグザグ上下しながら進んだ後、右にまっすぐ行って行を変え左にまっすぐ帰ってくるという方法しかないことはすぐわかる。しかしこれを計算するのが難しい。途中で足止めされる場合はその分最初に待っておけばよいので、最後から $k$ 番目にマス $(i,j)$ を通るとすれば、だいたい $a_{i,j}+k-1$ の $\max$ を求めることになる。まっすぐ行く部分を行き帰りに分解し、右から累積的に前計算しておいて、ジグザグの部分を愚直にシミュレートした。

サンプルを試すとちょっとずれていた。 $a_{i,j}$ というのはそこに入れるようになる時刻であって、実際に入った状態になれるのは $a_{i,j}+1$ からだった。これも正確には正しくなく、 $a_{i,j}=0$ の場合は時刻 $0$ から入った状態になれる。このことを $a_{i,j}+k-1$ という式に反映すると何とかサンプルが合い、通った。

Dはdp。 $k,k+1,\dots$ と順に試すと、 $k+O(\sqrt n)$ くらいでゴールに到達していない点が存在しなくなる。よってその間を毎回 $O(n)$ かけてdpし、 $O(n\sqrt n)$ 。余りを取るのではなく $\bmod$ を引き算したりして高速化しておいたら200ms程度で通った。最初はdp配列をin-placeに書き換えるだけで答えが求まると思っていたのに、後からちゃんと答えの配列に退避しておかなければならないことに気づいたため、コードへの反映が足りず1WA。

Eはセグメント木を考えるとそれぞれの深さで子をswapするかどうかの違いになる。深さ $0\le k\le n$ のノードは $2^k$ 個あり、それぞれそのノードより下のswap方法が $2^{n-k}$ 通りあるため、合わせると各深さで $2^n$ 種類の状態がある。これらをあらかじめ計算しておけばよい。ノードにいつもの部分列の和を最大化するモノイドを乗せる。

Fはつい先日解説記事を書いたのと同様のテクニックで解ける。取り出したボールたちから奇数が書かれたボールを選ぶのを $k$ 回行うとして、その時選んだボールの種類数を $l$ とすると、場合の数は $S(k,l){}_n\mathrm{P}_l\lfloor m/2\rfloor^l m^{n-l}$ となる。これの和を $1\le l\le \min(n,k)$ で求めればよい。 $n$ が大きいので ${}_n\mathrm{P}_l$ はその場で計算しなければならず、またこの時点ですでに $O(tk)$ なのでうっかりループ内で割り算をしないように気を付ける。焦ってcombinationライブラリを貼ったりと実装に手間取るも無事AC。

1時間弱で全完して8位。Fでは考察がすぐ終わったのに実装で時間を溶かしてしまい、残念。

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

08/05(金)

午前10時くらいに起きていた記憶がある。しばらくTLを見てからまた寝たはず。

午後2時起床。1時間ほどインターン関連の作業をし、その成果を持って午後3時からミーティングを行った。今日も2時間弱。作業時間の倍も何をミーティングしていたのかというと、今日はコードを少し書き換えてプルリクを出す流れを画面共有しつつ行った。

この長期インターンを始めて早一年、ここに来て初めていかにもインターンらしいことをした。しかしこちらも素人ではないのだから、手取り足取り教えて頂くのは申し訳ない。進捗を産むことで一人でも大丈夫であると表明したい。

日曜日のDDCC本戦とその直後の帰省のため、新幹線の切符を買っておく必要がある。特に前者は交通費が出るため指定席で行くつもりだ。どの列車に乗るのかも含め、しっかり調べて紙にまとめてからみどりの窓口に向かうため家を出発した。

ちょうど花火大会直前らしく、川内キャンパス周辺は大混雑していた。駅から出る人並みに逆らって歩くのは仄暗い気持ちよさがある。つまり、逆張り精神のことだ。

みどりの窓口は外に列が少しはみ出すくらいの混雑で、30分程度並んで購入に成功した。DDCCの分は普通の切符に学割を効かせるより週末パスというものを買うほうが安くなるらしいが、もし何かの間違いで終電に間に合わなかった場合使えなくなるとのこと、どうせ交通費が出るのだからと安全側に倒して学割で購入した。

少し本屋に寄った後つけ麺を食べてゲーセンへ。今日は14+で新規AJを二つ出した。

folern AJ pic.twitter.com/6tz99jt4He
— こたつがめ (@kotatsugame_t) 2022年8月5日

folern。フリック周辺で抜けまくって大変だった。フリック階段には速度が2種類あるので速い方は思い切り速く擦るというのと、その近辺の分割タップがどこで分かれているのかしっかり見ることを意識したら多少改善したように思う。

Evans ULT AJ！！！ラスクレで決めた！ pic.twitter.com/8W9mMm1hz1
— こたつがめ (@kotatsugame_t) 2022年8月5日

追加されたときにラストがどうしても通らないので諦めたのだった。今日プレイしてみると、序盤のホールドで1アタ出したものの以降AJで通ったため、狙うことに。それも含め1アタを4回出したが、なんとか閉店直前のクレで出た。ただ99AJ精度が出ていたのにこの回だけやたら赤が出て残念。

帰宅してしばらくハーメルンを読んでいた。「アラサーがVTuberになった話。」の書籍化についての情報が出ていた。9月末発売らしい。楽しみ。

【お知らせ】
ファミ通文庫様(B6判)より拙作『アラサーがVtuberになった話。』が『アラサーがVTuberになった話。』と改題し9月30日発売予定です。
イラスト担当はカラスBTK先生（@BTKcyber）です。
旧題『アラサーがVtuberになった話。』
↓
新題『アラサーがVTuberになった話。』#アラサーV
— とくめい@アラサーV9月30日発売予定 (@hameln_tokumei) 2022年8月5日

チュウニズムの「やってやろうじゃねえかよ　この野郎！」という称号について調べていて、元ネタとなった動画を見た。念のため、この元ネタにもさらにテレビ番組由来の元ネタがあるということに触れておく。動画は面白かった。この方が作曲された他の曲のPVと同じノリの中に混ぜられた、綺麗な例のアレという感じがする。

www.nicovideo.jp

午前1時から3時間でDMOJのYet Another Contest 4に参加した。これについては終了が火曜日なので、詳細な内容は来週の週記に書く。コンテスト終了後しばらく復習して、午前6時半に就寝。

Yet Another Contest 4 - DMOJ: Modern Online Judge

08/06(土)

午後0時半起床。食事して午後1時からMulti-Universities Camp 6回目に出た。

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

チームとしてMBJGAHICの8完、8位。自分はJGHCを解いた。うちJGは簡単枠。

H。FAだった。 $0$ 段目から $n$ 段目（ $n\le 10^9$ ）まで階段を上る問題。一気に $k$ 段上るとスコアが $k^2$ 得られるが、壊れている段が $m$ 段（ $m\le 2\times 10^6$ ）あってそこには立ち入れない上、壊れている段を一度に $S$ 段より多く飛び越えるような上り方ではスコアが得られない。すべての上り方について得られるスコアの総和を求める。

壊れている段を抜いた時の連結成分に分け、 $x\in I$ から $y\in J$ に一気に上がるときのスコア $(y-x)^2$ がどれくらい加算されるか見る。 $0$ 段目から $x$ 段目に行く場合の数は、 $x=0$ の場合を除いて $2^{x-1-c_I}$ と書ける。ここで $c_I$ は $x\in I$ より下にある壊れた段の数。 $I$ 全体で共通なのでこう表記している。逆も同様で、 $y$ 段目から $n$ 段目に行く場合の数は $y=n$ の場合を除いて $2^{n-y-1-(m-c_J)}$ である。まとめると $(y-x)^2 2^{x-1-c_I}2^{n-y-1-(m-c_J)}$ 。

展開すると、 $c_I$ 、 $c_J$ に関する定数を除いて $x^i 2^x$ 、 $y^i 2^{-y}$ （ $i=0,1,2$ ）を掛け合わせた式になる。あとは線形性により、 $I$ 全体どころか様々な連結成分について同時に足せる。それぞれが和を閉じた形で表せるので、Wolfram|Alphaに投げて式を写してきた。 $0$ 段目や $n$ 段目も少しずらして同様に扱える。また同じ連結成分内で移動するケースは別に足す。実装して出すとTLEしたが、写してきた式で $2$ のべき乗やその逆元を何度も計算していたので、少しまとめたら通った。

Cは、 $n$ 頂点 $m$ 辺（ $n\le 16$ 、 $m\le 100$ ）の重み付きグラフが与えられるので、辺の部分集合すべてについて最小重み全域森を考え、重みの和を出力せよというもの。辺をソートすれば、各辺 $uv$ についてそれより前の辺だけ見たとき $u$ と $v$ が連結にならないような部分集合の数を求める問題になる。包除原理などで頑張ろうとしたが式が生えず、チームメイトにHELPを求めたら、ABC213-Gの逆だと言われた。公式解説にある $O(3^n)$ では $m$ 回やると間に合わないものの、別解の $O(n^2 2^n)$ なら間に合いそう。速い提出を拾ってきて通した。

G - Connectivity 2

日記を書いて午後9時からABC263。

LINE Verda Programming Contest（AtCoder Beginner Contest 263） - AtCoder

Aから少し面倒で、以降もずっとC++で書いていた。Aはいちいちカウントして、ちょうど3回出現した要素とちょうど2回出現した要素の存在を判定。Bは根から各人の深さを求めた。Cはdfs。Dは置き換える区間が被らないとしてよい。prefixとsuffixでそれぞれ最適な値を求めるdpを行い、中間を全探索した。Eは後ろから期待値dp。

Fは、人 $2i-1$ と人 $2i$ が対戦するとき、新しい $C$ を $C_j=\max(C_{2i-1,j}+C_{2i,0},C_{2i-1,0}+C_{2i,j})$ とすることで、この対戦の勝者がこれを含め $j$ 試合勝ったときの最大値を表現できる。ここで $C_{\ast,0}=0$ としておく。例えば人 $2i-1$ が勝ったと決め打ち、 $C_{2i-1,j}\leftarrow C_j$ と書き換えることで、以降同様にすべての場合を考慮しつつ計算できる。

Gはちょっと難しかった。基本的に偶数と奇数をペアにするしかないので、ほとんど二部マッチングだと思えて最大流で解ける。ただし $A=1$ の場合が困る。そこで、 $A=1$ とペアにする場合だけコストが $1$ かかることにして、この最小費用流をACLのslope関数を使って解いた。すると $A=1$ をどれくらい使うかが全探索できる。余った分を $1+1$ でペアにした。

Exは解けず。2直線の交点を式で表してみたものの綺麗な形には全然ならなかった。残り時間はコードゴルフをしていた。7完最速で12位。

コードゴルフ。AはRakuで重複要素をカウントし、その積が $6$ になるか調べた。BはAWKかと思ったがdcで頑張ると縮んだ。Cはcombinationを生成する関数・メソッドがあるならそれを使うのが短い。RubyをVimで書いたものよりRakuのほうが短くなった。DはPerl。以降は手付かず。

午後11時半からCF #812 div.2。

Dashboard - Codeforces Round #812 (Div. 2) - Codeforces

A問題は軸上4方向にそれぞれ行ってそれぞれ帰ってくるのを繰り返せばよい。

Bはソートしたものを $b$ とするのが最適で、 $f(a)\le f(b)$ を判定する。 $f$ の実装はセグメント木など使おうとしたがちょっと実装に詰まった。最終的には、大きい値から順にマークをしていきつつ、その値に $1$ から隣二つのうちマークされているものの個数を引いたものを掛け、答えに加えた。

Cは常に可能。 $n-1$ 以上で最小の平方数を $x$ だとすると、 $x-(n-1)\dots n-1$ に $n-1\dots x-(n-1)$ を加えることで、問題を $n\leftarrow x-(n-1)-1$ に書き換えられる。 $n-1\le x$ なので $x-(n-1)\ge 0$ となり、このような操作がいつでもできる。

Dは4人が1人になる過程を2回のクエリで特定できる。1人目と3人目を聞くことで上手く分離できるようだ。最初ランダムに聞いて平均回数を抑えることを考えており、決定的に解けることに気づくのに時間がかかった。またこれだけの改善でクエリ回数制限を満たせることも計算して初めて気づいた。

Eは面白い。 $A_{i,j}$ と $A_{j,i}$ をswapするかどうかしか決められず、特にswapされることと、 $k=i$ なる操作と $k=j$ なる操作を合わせて奇数回行ったということが同値になる。そこで、 $k=1$ での操作回数を固定し（固定した値の偶奇には興味がないことに注意）、 $k=2\dots n$ について操作回数の偶奇が $k=1$ と一致するかどうかを決めていくことにした。辞書順なので先頭から貪欲でよく、偶奇がこれまでの決定と矛盾するかどうかは二部グラフ判定をUFで行うのと同様にして判定できる。つまり、頂点を倍化し、 $i-i'$ と $j-j'$ を繋ぐか $i-j'$ と $j-i'$ を繋ぐというのを繰り返せばよい。 $i$ と $i'$ や $j$ と $j'$ が連結になってしまうと矛盾するので、その場合は諦める。

Fは難しい。まず $a$ 、 $b=b_{\ast,n}$ を0-indexedにし、さらに $a$ をreverseしておく。この元で $b_j=\bigoplus_{i{\rm AND}j=0}a_i$ と書ける。実はどんな $n$ についても、この情報が $j=0\dots n-1$ についてわかっていれば $a$ を復元できるらしい。 $n=1$ なら自明。 $n\ge 2$ のとき、 $2^t\lt n$ となるような最大の整数 $t$ を取って、 $0\dots 2^t-1$ と $2^t\dots n-1$ に分割する。それぞれ $n\leftarrow 2^t$ 、 $n\leftarrow n-2^t$ として再帰していく。

まず $n\leftarrow n-2^t$ について。ちょうど $t$ 桁目のbitが立っている数だけの影響が知りたいが、これは新しい $b'$ を $b'_j=b_{j+2^t}\oplus b_j$ と定めることで計算できる。その結果を高速ゼータ変換して適切にXORすることで、以前の $b$ 全体から $a_{2^t\dots n-1}$ の影響を取り除くことができ、 $n\leftarrow 2^t$ の場合が計算できるようになる。計算量は $O(n(\log n)^2)$ くらいだろうか。200msちょっとで通った。

午前1時5分からTCO22 Regionals Algorithm Competition。いわゆるWildcard。CFと被っていたので直前まで出るかどうか迷っており、Fを考察している間にとりあえずレジだけ済ませていた。その後Fが通ったのが開始3分前くらいでかなり興奮した。そのままコンテスト突入。

コンテスト参照のためのURLはまだわからないため貼れない。

08/13追記：https://community.topcoder.com/stat?c=round_overview&er=5&rd=19337

combinedだからか4問構成だった。まず150点問題、ONACircle。これは自明。検索する文字列が円環より長いケースに注意するだけか。

次に400点問題、OverlappingRectangles。縦 $1$ 、横 $i$ の長方形を $i=1\dots n$ で重ねることで $n(n-1)/2$ 個のペアが作れる。 $n$ を最大化し、それでも $P$ が残っている場合、 $P'=P-n(n-1)/2\lt n$ だから、横 $P'$ の長方形を配置して残りのペアを作れる。あとは適当にバラバラに配置。この構築自体はすぐ思い浮かんで実装まで終わらせることができた。しかし何を考えたか手元でチェッカーを書いてしまい、それの実装と実行に時間を取られ、提出した時には40位くらいに位置していた。絶望。

700点問題、DominatedSubstrings。セグ木上の二分探索を使うと、各文字から左右にどれだけの長さの範囲でdominateできるか求まる。この情報を使い、左端の文字を全探索しつつその文字までdominateできる右端の文字の集合を管理することで、毎回可能な最も遠い右端の文字が求まる。ここから直接答えを出せる。簡単なのに焦って考察がまとまらず、また実装も少し手間取った。

1000点問題は解けず。memberに含まれる人のみをbitDPし、残りは単に人数で管理することで、計算ステップ数が最大 $((4^{10}-3^{10})\times 41+3^{10}\times 41^2)\times 50$ くらいになるコードを書いた。しかし当然間に合わず、高速化する間もなく時間切れ。

チャレンジフェーズも何もせず、今のところ22位になっている。なんとシステスは来週のイベント中に行われるらしい。なので上でコンテストURLが貼れなかったわけだ。3完のつもりで書いたコメントにも間違いがあるかもしれない。

明日オンサイトがあるのに睡眠時間を削った上でレートを暴落させ、さらにそのわかりきった結果が出るのを待って焦らされているのは無様以外の何物でもない。先ほどのCFがシステスを終え全完3位になったのを確認し、寝た。午前3時半だった。

08/07(日)

午前8時起床。眠すぎる。熱を測ったら平熱だった。ゆったり準備して出発し、仙台駅には午前9時頃到着。立ち食い蕎麦屋でカレーを食べ、新幹線に乗り込んだ。DDCC2022のため東京に向かう。

以降解散するまでのことは参加記に書く予定である。最近日記すら全然間に合っていなくてまだ1文字も書けていないが、無事投稿出来たらリンクを貼ろう。これはつまり、日曜日の日記を丸々後回しにしたのと同じことである。

午後11時過ぎ仙台に到着し、そのまま帰宅。以降しばらく日記を書いていたが、全然集中できず1時間くらいはYouTubeを見ていたはず。

午前3時に布団に入り、しばらくラノベを読んで午前4時就寝。

2022-08-03

"蔚来杯"2022牛客暑期多校训练营3 I Ice Drinking

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

注（検索用）：Multi-Universities Campとか、TwitterではNowCoderとか呼ばれている中国の合宿の問題です。

問題概要

長さ $n$ の順列 $P=(P_1,P_2,\dots,P_n)$ に対し、 $c(P)$ を $P_i=i$ なる $i$ （ $1\le i\le n$ ）の個数として定めます。 $P$ をランダムに決めたときの $c(P)^k$ の期待値を $\bmod 862118861$ で求めてください。

$1\le n\le 10^{18}$
$0\le k\le n+5\times 10^3$

解法

準備

まず $k=0$ の場合は自明なので除きます。また素因数分解すると $862118861=857\times 997\times 1009$ なので、素数 $p\approx 10^3$ について $\bmod p$ で求めることができれば、中国剰余定理より答えが求まります。以降はこれらのことを前提にして解きます。

$\displaystyle\sum_P c(P)^k$ を求める

解説スライドによれば、 $c(P)$ を固定して完全順列の式を使い式変形を頑張る方法もあるようですが、ここでは組み合わせ的解釈から導くことにします。

$c(P)$ を ${}_{c(P)}\mathrm{C}_1$ だと思うことにします。これはつまり、 $P_i=i$ であるような $i$ を一つ選ぶ場合の数です。今 $c(P)^k$ を求めているのですから、一つ取り出す操作を $k$ 回繰り返す方法を数え上げればよいです。このとき取り出す順番を考慮していることに注意します。

さて、 $k$ 個取り出した $i$ たちは当然大量に重複しますが、この重複を除いたものが $m$ 種類（ただし $1\le m\le\min(n,k)$ ）だったとします。この $m$ を固定してみます。

まず、 $m$ 種類がどのように分布するかを考えます。 $k$ 回の操作をそれぞれ区別される玉、 $m$ 種類の $i$ を区別しない箱だと思えば、求める分布の数はそれぞれの箱に1個以上の玉を入れる場合の数ですから、写像12相によれば $S(k,m)$ となります。ここで $S$ は第2種スターリング数です。

次に、それを達成できる順列 $P$ がどれくらいあるか考えます。 $1$ から $n$ のうち $m$ 種類の箱として使うものを決めるのが、どの箱にどの数字を対応させるかまで含めて ${}_n\mathrm{P}_m$ 通りになります。先ほど箱を区別しなかった分、ここで区別する必要がありました。選んだ $m$ 個の値は位置まで決定しており、残りは自由ですから $(n-m)!$ 通りで、掛け合わせると ${}_n\mathrm{P}_m\times(n-m)!=n!$ になります。

順列としての重複を考える必要はありません。なぜなら今の考察は、最初「すべての順列について」「 $m$ 種類の取り方すべてについて」の順で考えていたものを、逆順で表現しなおしただけだからです。

よって $\sum_P c(P)^k=\sum_{m=1}^{\min(n,k)}S(k,m)n!$ であることがわかりました。

ベル数による書きなおし

今は期待値を求めているので、先ほど求めた式の両辺を $n!$ で割ります。また $k\lt m$ のとき $S(k,m)=0$ であるため、 $\min(n,k)$ の部分を $n$ に書き換えることができます。これにより、求める値を $\sum_{m=1}^n S(k,m)$ と表せました。

ところで、 $S(k,m)$ を $m=1\dots k$ で足し合わせたものはベル数 $B_k$ です。よって $\sum_{m=1}^n S(k,m)=B_k-\sum_{m=n+1}^k S(k,m)$ と書けます。特に $k\le n$ の場合は、 $B_k$ さえ求まればよいことになります。

Touchard's congruence

巨大な $k$ に対して $B_k$ 、正確には $B_k\bmod p$ を求める必要があります。ここで素数 $p$ が十分小さいことを利用します。

Touchard's congruenceと呼ばれる合同式が存在します。非負整数 $n$ 、素数 $p$ について $B_{n+p}\equiv B_n+B_{n+1}\pmod p$ という式ですが、これについても組み合わせ的な解釈を説明します。

まず、ベル数 $B_n$ とは、 $n$ 個の区別できる玉をいくつかの箱に分ける方法でした。ここで $B_{n+p}$ を、 $B_n$ において得られた分け方にさらに $p$ 個の玉を追加したものとして捉えます。追加の際に箱を増やしても構いません。

いったん $n$ 個の分け方を固定しましょう。ここに $p$ 個の玉、説明のため $0,1,\dots,p-1$ と番号を付けますが、これを追加し、得られた $n+p$ 個の玉の分け方を集めた集合を $A$ とします。最初に定めた $n$ 個の分け方が異なれば当然そこから得られる $A$ の要素もすべて異なりますから、 $|A|\bmod p$ を考えてうまく足し合わせることで $B_{n+p}\bmod p$ が得られます。

任意の $a\in A$ について、 $a$ における玉 $0,1,\dots,p-2,p-1$ を一斉に $1,2,\dots,p-1,0$ に置き換えたものもまた $A$ の要素になっています。これを $f(a)$ とします。つまり、 $f$ は $A\rightarrow A$ の写像を与えます。また明らかに $f^p=\mathrm{id}_A$ です。

$A$ を、 $f$ を複数回適用することによって互いに移り変わる要素たちに分割します。巡回群 $\langle f\rangle$ による $A$ への作用の軌道を考えているとも言えますが、以降特に群の性質は使っていません。分割後の各部分集合のサイズを見ましょう。

$a\in A$ であって $f(a)\ne a$ であるようなものを取ります。 $f(a)\ne a$ と、 $p$ が素数で $f^p(a)=a$ が成り立つということから、 $a,f(a),f^2(a),\dots,f^{p-1}(a)$ がすべて異なると言えます。よって分割後の部分集合で $a$ が含まれるもののサイズはちょうど $p$ だとわかりました。今は $|A|\bmod p$ を考えているので、この部分集合は $A$ の要素としては無視してよいです。

結局、 $f(a)=a$ なる $a\in A$ を数える問題に帰着されました。ではこの $a$ はどんな構造をしているのでしょう。以下、 $a\in A$ を $f(a)=a$ を満たすものとして固定します。

玉 $i$ が入っていた箱に同時に入っていた玉 $0,1,\dots,p-1$ の数を数え、 $c_a(i)$ とします。例えば玉 $0$ に注目すると、 $c_a(0)$ 個の玉が $f$ によって置き換えられ、 $f(a)$ のほうで数えると $c_{f(a)}(1)$ 個になることから、 $c_a(0)=c_{f(a)}(1)$ が成り立ちます。ここで $f(a)=a$ より $c_a(0)=c_a(1)$ です。同様の議論で $c_a(i)$ がすべて等しいことが言えました。つまり $p$ 個の玉が同じ数ずつに分けられてそれぞれ箱に入っていることになりますが、 $p$ は素数ですから、その分け方は「 $1$ 個ずつ」または「 $p$ 個ずつ」です。

$1$ 個ずつ分ける場合

当然ながら、すでに分けられていた $n$ 個のどれかと一緒に入ってしまうと $f(a)=a$ が成り立たなくなるので、それぞれについて新しい箱を用意する $1$ 通りしかありません。これを $n$ 個の分け方である $B_n$ 倍するのですから、 $B_{n+p}$ に対する寄与も $B_n$ となります。

$p$ 個ずつ分ける場合

どの箱に入れても常に $f(a)=a$ となります。ここで $p$ 個をまとめて1個の玉だと思うことで、 $n$ 個の玉を分ける方法と合わせ、 $B_{n+p}$ には $B_{n+1}$ だけ寄与します。

以上より $B_{n+p}\equiv B_n+B_{n+1}\pmod p$ が言えました。ここまでの議論は参考文献[1]のLemma 3.1の証明に着想を得たものです。

また、より一般化した合同式として、非負整数 $m$ について $B_{n+p^m}\equiv mB_n+B_{n+1}\pmod p$ が成り立ちますが、これについては帰納法で簡単に示すことができます。以下 $p$ を法とします。

$\displaystyle\begin{eqnarray}B_{n+p^{l+1}}&\equiv&lB_{n+p^{l+1}-p^l}+B_{n+p^{l+1}-p^l+1}\\ &\equiv&l^2B_{n+p^{l+1}-2\times p^l}+2lB_{n+p^{l+1}-2\times p^l+1}+B_{n+p^{l+1}-2\times p^l+2}\\ &\vdots&\\ &\equiv&\sum_{i=0}^p {}_p\mathrm{C}_i l^{p-i}B_{n+p^{l+1}-p\times p^l+i}\\ &\equiv&l^p B_n+B_{n+p}\equiv lB_n+B_{n+p}\equiv(l+1)B_n+B_{n+1}\end{eqnarray}$

ただし最後の行への変形で、 $0\lt i\lt p$ に対して ${}_p\mathrm{C}_i\equiv 0$ であること、フェルマーの小定理より $l^p\equiv l$ であることを用いました。

この等式を使うことで、巨大な $k$ に対しても十分高速に $B_k\bmod p$ を求めることができます。

$S(k,m)$ を求める

さて、残るは $\sum_{m=n+1}^k S(k,m)$ です。ここに $k\le n+5\times 10^3$ という制約が効いてきます。つまり、改めて $m\leftarrow k-m$ と置きなおして、 $0\le m\lt k-n\le 5\times 10^3$ に対して $S(k,k-m)$ をそれぞれ高速に求められれば良いのです。 $m=0$ は自明なので取り除いておきます。

ところで、第2種オイラー数というものが存在します。これに関する日本語の文献はほとんどなく、英語で「Eulerian numbers of the second kind」などと検索する必要があります。三角かっこで2重にくくる表記が一般的ですが、ここでは第2種スターリング数（と参考文献[2]）に合わせて $B(n,k)$ で表記します。

この値の組み合わせ的な解釈を述べます。まず、 $1,1,2,2,\dots,n,n$ を並べ替えた数列であって、「任意の $i$ について $i$ と $i$ の間に出現する数はすべて $i$ より大きい」という条件を満たすものを、 $n$ 次のStirling permutationと呼びます。 $B(n,k)$ とは、 $n$ 次のStirling permutation $a=(a_1,a_2,\dots,a_{2n})$ であって、「 $a_j\lt a_{j+1}$ を満たす $j$ （ $1\le j\lt 2n$ ）がちょうど $k$ 個ある」という条件を満たすものの数です。

具体例など詳しくはWikipediaを参照してください。 $a_0=0$ だと思う定義も存在し、文献によっては $k$ が少しずれていました。また左右が逆のものもあります。

このような数を突如導入した理由は2点、まず単純な漸化式が存在し小さい範囲の値を高速に求められるから、次に $m\ge 1$ に対し $S(k,k-m)=\sum_{i=0}^{m-1}B(m,i){}_{k+m-i-1}\mathrm{C}_{2m}$ が成り立つからです。

前者によって $B(m,i)$ を前計算しておけば、後者によって $S(k,k-m)\bmod p$ を高速に求めることができます。 $p$ が小さい今回であればリュカの定理により $O(m\log m)$ が達成でき、 $p$ が大きければ二項係数を徐々に更新することで $O(m\log p)$ が達成できます。

参考までに、 $p$ が小さいときは一般のスターリング数を高速に求めることができるそうです。大きな $p$ について $S(k,k-m)\bmod p$ を高速に求めたくなる機会は今後訪れるのでしょうか。

maspypy.com

第2種オイラー数の漸化式

$B(n,k)=(2n-k-1)B(n-1,k-1)+(k+1)B(n-1,k)$ というものです。ただし $k\lt 0$ または $n\le k$ の場合 $B(n,k)=0$ としておきます。 $n\le k$ の場合に $B(n,k)$ となることは、以下の漸化式の導出により確かめることができます。

この漸化式はdpだと思うことで簡単に導けます。最初に $n=0$ の場合、条件を満たすただ一つの数列 $(1,1)$ を見て $B(1,0)=1$ と定めることができます。以降 $n\ge 2$ とします。

$n-1$ 次のStirling permutationに $n$ を二つ挿入する方法を考えます。条件より $n$ と $n$ の間に出現する数はすべて $n$ より大きい必要があるので、特に今、二つの $n$ は隣接している必要があります。挿入できる位置は両端を含めて $2(n-1)+1=2n-1$ 箇所あります。

まず、 $B(n-1,k-1)$ でカウントされる並べ方について考えます。 $n$ を挿入することで $a_j\lt a_{j+1}$ なる $j$ を一つ増やす必要がありますから、すでにそうなっている $j$ の後ろに挿入してはいけません。そのような位置は $k-1$ 箇所あります。さらに左端に入れるとその左の項が存在しないため、これもまた意図に沿いません。以上より挿入できる位置は $2n-1-(k-1)-1=2n-k-1$ 箇所なので、場合の数として $B(n,k)$ に対し $(2n-k-1)B(n-1,k-1)$ だけ寄与します。

次に $B(n-1,k)$ について考えます。今度は逆で、先ほど挿入できなかった箇所にしか挿入できません。 $a_j\lt a_{j+1}$ なる $j$ は今回 $k$ 個ありますから、その $k$ 箇所と左端を合わせて $(k+1)B(n-1,k)$ だけ寄与します。

二つを合わせることで先の漸化式が得られました。

$\displaystyle S(k,k-m)=\sum_{i=0}^{m-1}B(m,i){}_{k+m-i-1}\mathrm{C}_{2m}$ について

探したらこれにも組み合わせ的な解釈がありました。参考文献[2]のTheorem 2.3を用いるものです。ちなみにこれが、先ほど言及した左右が逆になっているものです。以下、文献と左右が逆になった状態のまま進めます。

まず、 $P_{k,n}$ を、 $k$ 次のStirling permutationに対し、その項の間または両端に合計 $n$ 本仕切りを入れたものの集合とします。ただしこの時、数列の「左端」「 $a_j\lt a_{j+1}$ なる $j$ の直後」には必ず1本以上仕切りが入っているものとします。

例えば $k=3$ 、 $n=4$ とし、仕切りを $/$ で表せば、 $/3/31/221/$ のようになります。

実はそのような仕切りの入った数列と $n+k$ 個の玉を $n$ 個の区別できない箱に入れる方法が一対一対応しており、したがって $|P_{k,n}|=S(n+k,n)$ が成り立ちます。

先に、ここから上の式を導いておきましょう。 $S(k,k-m)=|P_{m,k-m}|$ となるので、 $m$ 次のStirling permutationに対し、条件を満たしつつ $k-m$ 本の仕切りを入れる方法を数え上げればよいです。

「 $a_j\lt a_{j+1}$ なる $j$ 」が $i$ （ただし $0\le i\lt m$ かつ $i\lt k-m$ ）個あったとすると、そのような数列は $B(m,i)$ 通り存在し、左端と合わせすでに $i+1$ 本の仕切りの位置が確定しています。

残り $k-m-i-1$ 本の仕切りを入れる位置を $2m+1$ 箇所から選びます。これは重複組み合わせによって ${}_{2m+1}\mathrm{H}_{k-m-i-1}$ と書け、二項係数に直すと ${}_{(2m+1)+(k-m-i-1)-1}\mathrm{C}_{k-m-i-1}={}_{k+m-i-1}\mathrm{C}_{2m}$ となります。ここまで変形すると、先ほどの $i\lt k-m$ の制限を外してよくなります。仕切りが足りない場合を考慮していましたが、そのような場合 $k+m-i-1\lt 2m$ から ${}_{k+m-i-1}\mathrm{C}_{2m}=0$ となるからです。

まとめると $S(k,k-m)=\sum_{i=0}^{m-1}B(m,i){}_{k+m-i-1}\mathrm{C}_{2m}$ となり、見事求める式が得られました。

$\displaystyle|P_{k,n}|=S(n+k,n)$ について

参考文献[2]では一方をもう一方に変換する方法を事細かく説明していました。これを引き写してくるのはさすがに面倒なので、具体例を見た後大まかな説明を試みます。

基本的には仕切り一つが箱一つ＋玉一つに対応します。玉が二つ以上入っている箱については数列の同じ値を持つ要素二つを対応させます。先ほど挙げた例 $/3/31/221/$ を変換してみましょう。これは $n+k=7$ 、 $n=4$ より、ラベル $1,2,\dots,7$ を $4$ 個の集合に分割する方法の一つと対応しているはずです。

まず、 $/3/31/221/$ を、 $/3/31/221/\rightarrow/1/221/\rightarrow/1/1/\rightarrow//$ と分解していきます。同じ値を持つ要素二つとその間の仕切りすべてを削除するのを繰り返しますが、このとき削除した要素のすぐ左には必ず別の仕切りが存在します。このことは、 $P_{k,n}$ の定義で設けた仕切りの位置の制約から言えます。

削除されたのと逆順にラベルを振っていきます。まず最初の仕切りが二つで $/_2/_1\leftrightarrow\{1\},\{2\}$ となります。右から左の順でラベルが付いているのは、参考文献と第2種オイラー数の定義が逆だからです。次に、 $2$ に対応した仕切りのすぐ右の要素を削除しましたから、それをラベル $3$ として $\{2\}$ に追加します。 $/_21_3/_41/_1\leftrightarrow\{1\},\{2,3\},\{4\}$ です。

以下同様に $/_21_3/_42_521/_1\leftrightarrow\{1\},\{2,3\},\{4,5\}$ 、 $/_23_6/_731_3/_42_521/_1\leftrightarrow\{1\},\{2,3,6\},\{4,5\},\{7\}$ と更新されていき、無事 $1,2,\dots,7$ を $4$ 個の集合に分割できました。どう表示したとしても見にくいので勘弁してください。

さて、分割を数列に戻しましょう。それぞれの集合のうち最小のラベルを仕切りに変換し、残りを倍にコピーして降順に並べると、 $/_1,/_26633,/_455,/_7$ となります。これを適切にマージします。具体的には、仕切りがもともと対応していたラベルを昇順に見て、それより $1$ 小さいラベルが出現する最も右の位置のすぐ左に塊ごと挿入します。 $/_1\rightarrow/_26633/_1\rightarrow/_2663/_4553/_1\rightarrow/_26/_763/_4553/_1$ となりました。番号を順序を保って振りなおせば $/3/31/221/$ が得られます。

これはいったい何だったんでしょうか。数列の要素との入れ子関係によってラベルの番号を管理しているのは明らかです。このとき、すでに決まった集合の構造が失われないように要素を二つずつ使っていたのでしょう。

つまり、すべての仕切りについて、一つ右にある要素を見るのと同じ要素の次の出現位置に飛ぶのを交互に繰り返せば、スタート地点の仕切りと同じ集合に入っていたラベルが列挙できるのです。特に要素のラベルは単調減少に並ぶようにしましたが、これは仕切りの位置の制約から、 $a_j\lt a_{j+1}$ となる場合その間に別の仕切りが必要であることに対応しています。これによって一意性が担保されています。

今説明した両方向の変換が、それぞれ互いの逆変換になっていることも、この理由付けから納得できそうです。僕が納得した気になったので終わります。

実装例

ACLからmodintを、手持ちのライブラリから $\bmod 862118861$ の解を復元するのにgarnerのアルゴリズムを使っています。

#include<iostream>
#include<atcoder/modint>
using namespace std;
#include"math/garner.cpp"
template<int p>
struct A{
    using mint=atcoder::static_modint<p>;
    mint C[p][p],Bell[p],B[5000][5000];
    A()
    {
        for(int i=0;i<p;i++)for(int j=0;j<p;j++)C[i][j]=0;
        C[0][0]=1;
        for(int i=1;i<p;i++)
        {
            C[i][0]=1;
            for(int j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
        Bell[0]=1;
        for(int i=1;i<p;i++)
        {
            Bell[i]=0;
            for(int j=1;j<=i;j++)Bell[i]+=C[i-1][j-1]*Bell[j-1];
        }
        for(int i=0;i<5000;i++)for(int j=0;j<5000;j++)B[i][j]=0;
        B[0][0]=1;
        for(int i=1;i<5000;i++)
        {
            B[i][0]=B[i-1][0];
            for(int j=1;j<i;j++)
            {
                B[i][j]=(2*i-j-1)*B[i-1][j-1]+(j+1)*B[i-1][j];
            }
        }
    }
    mint bell(long long k)
    {
        int m=0;
        long long q=1;
        while(q<=k/p)m++,q*=p;
        vector<mint>now;
        now.push_back(1);
        for(;m>=1;m--,q/=p)
        {
            int t=k/q;
            k%=q;
            vector<mint>F(t+1);
            mint coef=1;
            for(int i=t;i>=0;i--)
            {
                F[i]=coef*C[t][i];
                coef*=m;
            }
            vector<mint>nxt(now.size()+F.size()-1);
            for(int i=0;i<now.size();i++)for(int j=0;j<F.size();j++)nxt[i+j]+=now[i]*F[j];
            while(nxt.size()>p)
            {
                mint tmp=nxt.back();
                nxt.pop_back();
                nxt[nxt.size()-p]+=tmp;
                nxt[nxt.size()-p+1]+=tmp;
            }
            now=nxt;
        }
        mint ret=0;
        for(int i=0;i<now.size();i++)
        {
            int id=i+k;
            if(id<p)ret+=Bell[id]*now[i];
            else ret+=(Bell[id-p]+Bell[id-p+1])*now[i];
        }
        return ret;
    }
    mint combination(long long n,long long k)
    {
        if(n<k)return 0;
        mint ret=1;
        while(k>0)
        {
            ret*=C[n%p][k%p];
            n/=p;
            k/=p;
        }
        return ret;
    }
    mint S2(long long k,long long m)
    {
        m=k-m;
        if(m==0)return 1;
        //S2(k,k-m)
        mint ret=0;
        for(int i=0;i<m;i++)ret+=B[m][i]*combination(k+m-i-1,2*m);
        return ret;
    }
    int solve(long long n,long long k)
    {
        if(k==0)return 1;
        mint ans=bell(k);
        for(long long m=n+1;m<=k;m++)ans-=S2(k,m);
        return ans.val();
    }
};
int main()
{
    long long n,k;
    cin>>n>>k;
    vector<long long>x(3),m(3);
    x[0]=A<857>().solve(n,k);m[0]=857;
    x[1]=A<997>().solve(n,k);m[1]=997;
    x[2]=A<1009>().solve(n,k);m[2]=1009;
    cout<<garner(x,m)<<endl;
}

参考文献

[1]：Greg Hurst, Andrew Schultz、2009、[0906.0696] An elementary (number theory) proof of Touchard's congruence

[2]：Ira Gessel, Richard P Stanley、1976、Stirling polynomials - ScienceDirect

2022-08-01

週記（2022/07/25-2022/07/31）

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$ にセットしなければならないということで、逆に開区間になったと思うとより自然さが増したと感じられる。

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

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

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

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

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

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

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を引退される黛灰さんの生前葬配信を見ていた。

https://twitter.com/mayuzumi_X

黛灰さんは、時折切り抜きで姿を目にするだけで特別追っていたわけではない。しかし有名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アカウントに鍵がかけられており、僕はフォローしていなかったため実際に目にできてはいないのだが、最後のツイートも配信画面と同じ文面だったらしい。

一方、綺麗でない終わり方のことも考えていた。具体的には炎上による引退、もっと言えば潤羽るしあさんのことである。当時僕はまだ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時就寝。

2022-07-25

週記（2022/07/18-2022/07/24）

07/18(月)

数回目覚ましをやり過ごした後、午後0時半起床。ギリギリまで寝ていると寝坊する可能性があった。シャワーを浴びて午後1時からMulti-Universities Camp。

まずこのCampについて少しばかり説明しておきたい。一つ目、このCampは計10個のコンテストから構成されていて、毎週月曜日と土曜日の午後1時から5hで開催される。今日が初回なので最終回は08/20となる。二つ目、3人以内のチームを組んで出場する。そして三つ目、これが僕にとって一番驚きだったことなのだが、このコンテストは基本的に有料である。

じゃあなんで参加しているのかというと、CodeforcesのDMで無料参加の招待が来たからだ。レートが高いほうから順に送られているという噂を聞いたが、確認すると僕のところには昨年も来ていて、当時のレートが2400程度だったことを考えればかなり手当たり次第と感じられる。昨年はよくわからんコンテストには興味ないねと思ってスルーしたものの、なんだかOpenCupに参加している人はこちらにも結構参加するようで、その中でチームも組むらしいのでホイホイ参加を決めた。僕が入ったチームはOpenCupのものとは少し変わっている。

有料コンテストの内容を公開するのには注意が必要。これに関しては招待を送ってきた運営の人に確認を取って、「ブログに問題文の要約と解説を書いて良い」という返答を貰っている。

- Can I write commentary of Camp's problems with summarized statement on my blog?
- yes
問題概要すら載せていいらしいです
— こたつがめ (@kotatsugame_t) 2022年7月21日

ただ、問題文そのものが公開されるのかはよくわからない。自分が後から読み返して辿れるように以下にコンテストリンクを貼っておくが、ここから見るには少なくともログインが必要である。

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

チームとしてGAIHEDBCJの9完。僕はGEBJを書いた。

Gは簡単枠。次にHを見て、計算量がダメダメな解法で解けたと主張し直後に間違いに気づくなどしたが、その時にはチームメイトが正しく解けていてスルッと通していた。改めてコードを見ると畳み込みなど使っていて、これを一瞬で詰め切ったのには素直に脱帽。

Eはちょっと面白かった。二つの根付き木が与えられ、その「Longest Common Subsequence」みたいなものを求める問題。木dpの配列が2次元となり、それぞれの木でどの部分木を見ているかが状態になる。問題は、今見ている頂点をマッチさせたとき、子からどのように遷移するのかということ。どの子とどの子が対応するかわからないのだ。実はここに最大重み二部マッチングが使える。うしさんのライブラリからハンガリアン法を拝借してきて通した。

Bは大変。数字からなる長さ $n$ の文字列が与えられて、長さが等しい部分文字列のペア $(s,t)$ であって数として見たとき $s+1=t$ となるようなものを数え上げる問題。ただしleading-zeroは許される。とりあえず $s$ の最下位桁 $s\bmod 10$ が $9$ でない場合を考えると、 $(s\bmod 10)+1=(t\bmod 10)$ かつ $s/10=t/10$ だから、与えられた文字列を反転させてSA＋LCPを使えば解けそう。以下、与えられた文字列を反転したとして説明する。

求めたSAを順と逆順に2回見ることでペアの抜け漏れをなくす。 $s/10=t/10$ を判定しているのだから、見ている接尾辞は $s/10$ に、その一つ前の文字が $s\bmod 10$ に対応する。以降、接尾辞を一つ前の文字と組にして $s=(s/10,s\bmod 10)$ だと思うことにする。これまで見た接尾辞のうち $t=(t/10,t\bmod 10)$ については、 $(s\bmod 10)+1=(t\bmod 10)$ だったなら ${\rm LCP}(s/10,t/10)+1$ だけ答えに寄与する。LCPは常に減っていくためstackに入れて管理できる。更新の際、上からいくつか取り出しマージして戻すということ。このstackを10本用意し、 $t\bmod 10$ に応じて入れる場所を変えれば前者の条件を考慮できる。寄与の和はstackごとに差分更新しておく。

さて、最下位桁が $9$ の場合はどうなるだろうか。 $+1$ した時の繰り上がりを考えると、文字列長として $|s|=|t|=|s+1|$ なので、結局どこかに $9$ でない桁が出現しなければならない。なのでそこを改めて最下位桁、先ほどでいう $s\bmod 10$ だと思い直す。その左に続く $9$ の個数を $c_s$ とし、同様に繰り上がりが止まった位置という意味での $t\bmod 10$ を見てその左に続く $0$ の個数を $c_t$ として、寄与が $\min(c_s,c_t)+1$ 倍になるとわかる。これは困った。

実はある程度愚直にやってよい。 $t\bmod 10$ としては $1$ 以上しか考えなくてよく、それだけ見たとき、与えられた文字列における $0$ の連結成分と $c_t\gt 0$ なる $t$ はほとんど一対一対応する。特に $\sum_t c_t$ は元の文字列の長さ $n$ を超えないため、種類数が $O(\sqrt n)$ になる。

先ほどはstackごとに寄与を差分更新していたが、これを区間SUMのセグメント木に置き換え、ペア $({\rm LCP},(c_t+1)\times{\rm LCP})$ をインデックス $c_t$ に足しておく。取得時はインデックス $c_s$ の左右で値の取り扱いを変え、答えに足すことで寄与の $\min(c_s,c_t)+1$ 倍が再現できる。またstackの要素それぞれにmapを用意して $c_t$ の分布を持つと、このサイズが $O(\sqrt n)$ なので、マージもセグメント木の書き換えも愚直にやって良さそう。さすがにこの通りの計算量だとまずいのだが、そんな極端な最悪ケースはないだろうと投げ、実際 $n\le 4\times 10^5$ なのに1sec程度で通った。

Jもまあまあ大変。有向グラフがあって、入次数1の頂点があったらその入ってくる辺を使って2頂点を縮約する、ということを繰り返したい。この結果発生した多重辺は消し、自己ループは残す。縮約をUFで行うことを考えていたが、多重辺を消すのは結局愚直に行う必要がありそう。と思っていたらマージテクでできることに気づいた。

2頂点をマージするとき、次数が小さいほうの頂点についてそこに入る辺・そこから出る辺を全部見て、新しい頂点番号に書き換えることを繰り返せばよい。常に正しい頂点番号が得られることになってかなり見通しが良くなった。実装はsetだとTLEしたのでunordered_setを使う。自己ループの処理で何回かWAを出した。すでにある自己ループを縮約先の頂点に移動するのに失敗していた。

チームとして出来がいいし、個人的にもなかなか満足のいくセットだった。Bの重めの実装を一発で通したことと、Jを数回のWAにめげず通したこと。このサイトはAC時に効果音が鳴るようで、最初はただ面白がってしかいなかったのだが、Jを苦労して通したときに聞いてみるとかなり達成感があった。

食事して日記を書き始めた。

途中でTLを見ると、東方ダンマクカグラというスマホ音ゲーがサービス終了するお知らせが流れてきていた。驚き。プレイヤー数が多い部類の音ゲーだと思っていたし、そもそも運営の熱意が強いという印象があって、ちょっとやそっとでは終わらせないだろうと考えていた。

動画では、このままサービスを続けようとするとクオリティを落とさざるを得ないため終了の判断をした、と言っていた。東方Projectというコンテンツに向ける熱意があるからこそ、それを構成する一つの要素として晩節を汚したくないということか。なかなか誠実な態度であるように思える。プレイヤーとしてはたまったものではないのかもしれないが。

【大切なお知らせ】
2022年7月18日20時より配信中のダンカグ通信最終回にて「東方ダンマクカグラ」のサービス終了をお知らせしました。
この後、20時30分にもゲーム内お知らせが更新されますので、そちらもご確認ください。https://t.co/qN3GhzKOsa #ダンカグ
— 東方ダンマクカグラ◆好評配信中 (@danmakuJP) 2022年7月18日

午後11時半からCF #809 div.2。週記はギリギリで完成し、投稿することができた。

Dashboard - Codeforces Round #809 (Div. 2) - Codeforces

Aは $a$ の頻度配列を求め、これをデクリメントしつつ文字列の先頭から順にAにできるならしていった。Bは見た目はいかついものの整理すると簡単。サンプルを見つつよくよく考えると、二つのブロックはそのインデックスの偶奇が異なるとき、またその時に限り縦に並べることができる。あとは書かれている数字ごとにブロックのインデックスを集めてdp。

Cは $n$ が奇数ならどのビルがcoolになるか定まり、互いに干渉しないため、それぞれ計算。偶数の時も互いに干渉しないのは一緒で、どこかに1か所だけcoolでないビルが2連続する箇所があるのでそれを全探索すればよい。左と右から前計算しておけば必要な階数が直ちに求まる。インデックスの範囲や偶奇にかなり気を使って実装した。

D1D2はよくわからない。似たような $\max-\min$ を求める問題は最近CF #804 div.2で見たため、同様の方針で最小値または最大値を決め打ってみる。いろいろ組み合わせを考えた結果、最小値を決め打ってどんどん大きくするのがよさそうだった。

https://codeforces.com/contest/1699/problem/E

初期状態はすべて $p_i=K$ である。これが最小値 $L=0$ に対応し、そこから $L=1\dots a_1$ の順で、 $L\le\left\lfloor\frac{a_i}{p_i}\right\rfloor$ をギリギリ満たすように $p_i$ を決めていく。そのような $p_i$ としては $\left\lfloor\frac{a_i}L\right\rfloor$ が上限で、最適。これと $K$ の $\min$ を $p_i$ として最大値を更新した後、次に更新するタイミングとして $L=\left\lfloor\frac{a_i}{p_i}\right\rfloor+1$ を記録しておく。

どのインデックスについて更新しなければならないか取得するため優先度付きキューを使った。キューへのpushが $O(\sum_i\sqrt{a_i})$ 回行われるが、キューのサイズは常に $N$ である。しかしさすがに怖いので、念のため最初に $a$ をuniqueしておいた。実装してとりあえずD1が通り、試しにそのままD2にも提出すると3700ms強で通った。メモリは3MBも使っておらず余裕だったようだ。手元でも試し、思いついた中での最悪ケースが3800ms程度だったのを確認して、安心して次に進んだ。

Eは簡単。最初、見た目から並列二分探索だと思ったものの、区間の点が連結であるかを高速に判定できなかった。これをどうにかする方法を考えていたらもはや二分探索する必要もなくなった。マージテクで連結成分の点をすべて管理すると、マージの際に小さいほうの集合を全部見ることになる。このとき見た点について左右と新しく連結になるか判定し、そうであったらその「点と点の間」に使った辺のインデックスを記録する。クエリへの回答は、区間内の「点と点の間」をすべて見て、記録されたインデックスの最大値を答えればよい。RMQである。記録したインデックスを上書きしてしまい1WA。

1時間弱で全完。システスも全部通って順位は変わらず9位だった。Dは、各 $a_i$ に対して $O(\sqrt{a_i})$ 個の $L$ を考えなければならないのはどうしようもない。ただし最初に $a_i$ を固定し、必要な $L$ を全部見て対応する $\left\lfloor\frac{a_i}{p_i}\right\rfloor$ を記録しておくと、最大値が記録を全部まとめた上での $L=0$ からの累積 $\max$ で書けるようになる。これで優先度付きキューの $\log$ が落ちる。

疲れ果ててしばらくネットサーフィンをした後、昨日のJuly LunchtimeのINVRETをもう少し考えていた。マージソートを書いて85点を獲得したところから。1要素の列をソートするとき番兵まで置いているのは明らかに無駄なので、ここを何とかする。まず2要素のソートを分割せず直接処理することで通る部分点が一つ増えた。

次に3要素のソートも書き下してみる。転倒数を数えるのに必要な比較を3回行うと、その結果の組み合わせは当然異なる。これをうまく組み合わせることで、要素の並び方 $3!$ 通りそれぞれに対してソートした後どの位置にどのインデックスが来るかという値を生成。紙に書いて気合いで求め、実装。提出するともう一つ通る部分点が増え、ついに98点となった。コンテスト中のtouristと並んだことになる。

https://www.codechef.com/viewsolution/69305522

4要素のソートも展開しようと思ったものの、あまりの複雑さに絶望。眠気もあって布団に倒れこんだ。午前5時就寝。

07/19(火)

正午起床。ゲーム理論の課題が投稿されていた。もう勘弁してほしい。

Slackのフリープランの利用上限が変わるらしい。アクセスできるメッセージの制限が、直近10⁴件までではなく過去90日間のものまでになるようだ。昔のICPCチームのやり取りが消えたりするのはちょっと残念。ただ、冷静に考えると消えて困るようなメッセージもあまりない。

Slack 初の料金改定とフリープランの内容変更のお知らせ | Slack

ゴミを出した後、しばらく読んでいなかったカクヨムの更新をひとしきり追ってから午後4時に再度就寝。午後9時にまた起床し、今度はずっとなろうを読んでいた。

祝日の影響で明日にずれていたインターン先勉強会は自分が発表者である。その準備をしなければならないのになかなか手が出ない。シャワーを浴びたりして、もうほかにやることがなくなってから満を持してスライド作成を開始。午前6時だった。

一度書き始めると興が乗り、午前11時半までかけて一息に完成させた。まあ、そもそも自分で興味が持てない内容は勉強会で発表するべきではない。

布団に入ってみると起きるまで最大6時間あって結構余裕だなという感じがしてきた。しばらくなろうを読んで午後1時半就寝。

07/20(水)

午後5時半起床。全然余裕ではなかった。かなり眠気が強い。

すぐさまインターン先定例会へ。今週の進捗は勉強会スライドを作っていただけ。話すことがあるだけマシという感じもする。勉強会は発表30分、質疑応答30分だった。準備した内容が薄く、30分で説明し終えてしまいちょっと焦ったのだが、思いがけず質問やコメントが結構来て最終的にはそれなりの時間となった。終了後にスライドを公開した。ここにもリンクを貼っておく。

勉強会0720.pdf - Google ドライブ

内容はNumPy、というかそれが呼び出しているBLASという線形代数ライブラリにおける行列積の実装について。ABC258-Gの最短コードでは $3000\times 3000$ のサイズの行列積を計算しており、これが間に合っているのがなぜかを解明しようとした。結局はアセンブリ言語をバリバリ書いたりキャッシュヒットに気を使ったりして頑張っているという結論になった。

また実装を追っているうちに発覚した高速化・低速化のポイントも書いておいた。こちらのほうが興味を持たれやすいのではないか。まず、 $G\times G$ より $G\times G^T$ のほうが高速になる。まあそれはそうで、 $G\times G^T$ は対称行列だから半分しか計算しなくてよいのだ。転置行列を掛けるという操作は線形代数においてかなり出現頻度が高いらしく、専用のルーチンがBLASにも用意されている。

一方低速化としては、NumPyで作った行列の型をintにすると極端に遅くなることを書いた。コードゴルフしているとき、intのほうが短いからとそう書いただけなのに突然通らなくなって苦労した部分。理由はBLASがfloat・doubleとその複素数型にしか対応していないからで、intに限らずその四つ以外の型を使うと、何の工夫もなくごく普通にループを回して計算するコードが走ってしまう。

食事してからTCB49に出た。今日スタート。睡眠時間的な意味では万全ではないものの、やれる日にやっておく必要がある。期間は今週日曜日までなので、ここに感想を書いておく。

https://techful-programming.com/user/event/3013

5問目はbitで使える文字を管理する。 $Q$ 個の条件をまとめて伝播させることで調和級数の $O(N\log N)$ になる。

6問目はちょっと面倒。外側の括弧と長さを指定してメモ化再帰を書こうとしたが、重複を省くのが思ったより面倒なことに気づき、開き括弧の位置を全探索する方針に切り替えた。 $\pm 1$ に置き換えた後の累積和が $0$ になる位置で文字列を分割し、それぞれで考えてよい。外側の括弧だけ決め打つとそこから何レベル内側かで括弧の種類が決定するため、あらかじめどのレベルにどんな種類の括弧が指定されているか求めておいてチェックした。閉じ括弧が属するレベルはデクリメント後の累積和の変数が表すことになるのに、デクリメント前の変数を使って処理を行ってしまい1WA。-12pt。サンプルが弱すぎる……。

7問目は挿入dp。8問目は $1\le g\le N$ に対して $l\le \forall i\le r.\;g\mid P_i$ を満たすような $(l,r,P)$ の組を数え、除原理で条件を $\gcd(P_l,\dots,P_r)=g$ に直して、係数を掛けつつ和を取ればよい。一番最初の数え上げについては $k=r-l+1$ とおくと $1\le k\le N/g$ となるため、 $k$ を全探索できる。あとは典型的な組み合わせ計算。

9問目と10問目は問題文が同じというなかなか面白い趣向だった。10問目を開いたときはミスを疑ったものだ。まず、ともに $K$ 以上の場合の数から $K+1$ 以上の場合の数を引けば答えになる。以降「最小値が $K$ 以上」の場合について解を求める方法を説明する。ここから制約によって解法が異なり、まず9問目は直前に建設した街までの距離を持つdpが行列累乗で高速化できる。

10問目は $2\times 10^5\le K$ という普段とは逆向きの不等号の制約から $N/K$ が小さいことに注目し、建設する街の数 $c$ を全探索する。 $2\le c\le\frac{N-1}K+1$ であり、最初に $c-1$ 個の隙間に距離 $K$ を割り振った後、街の間と両端の計 $c+1$ 個の区間で残りの距離 $N-1-(c-1)K$ を分け合うことになる。combinationで書けば $\binom{N-1-(c-1)K+c}{c}$ 。どうやって計算するんだと思ったが、丁寧に確認すると $c\le\frac{10^9-1}{2\times 10^5}+1\lt \frac{10^4}{2}+1$ なので、毎回 $O(c)$ かけて計算しても問題ない。

テーマが数え上げと聞いて身構えたものの、かなり簡単だった印象。なのに5問目のせいで理論値を逃してしまい非常に悔しい思いをしている。WAだけではなく回答時間的にもちょっと間に合っていない。目標回答時間の30%で通せばタイムボーナスが理論値となるが、この問題だとボーダーが $40\times 0.3=12$ 分で、最初のWAだった提出すらそれより少し遅かったのだ。ともかく、結果は理論値-12pt。5問目以外に時間のかかった問題もなく、合計時間は50分弱だった。

日記を書き始めた。月曜日のINVRETと格闘していた部分を書いているときに、ふとtouristの98点が何をしていたのか気になった。見ると、マージソートという方針は同じでも操作回数の減らし方が僕と異なっており、二つのコードのいいとこどりをすることで見事満点を達成することができた。touristは2要素3要素のソートを特別扱いしていない。

https://www.codechef.com/viewsolution/69476366

まず、ソートした要素を改めてcomposeすることでメモリ上の位置を連続させていた部分。 $F_l$ と $F_r$ を比較しているとき、 $(F_l\lt F_r)\times l+(F_r\lt F_l)\times r$ を求めてcomposeするインデックスに使っていたが、ここは $(F_l\lt F_r)\times F_l+(F_r\lt F_l)\times F_r$ として直接値を求めたほうが良いようだ。なんとなれば、composeしていた部分で最後の $+$ を行うことで、改めて要素をコピーする必要がなくなり操作回数を1減らすことができるから。

この部分は何回も実行されるためかなり効いた。しかし満点を取るにはあと682回操作回数を減らす必要があった。上のアイディアは自分では考えもしなかったので、ほかに使えるところがあるのではないかと捜したところ、2要素のソートを直接処理している部分でも操作回数を1減らすことに成功した。小さい方の要素はインデックスを求めてcomposeするが、大きい方の要素はそうではなく、二つの要素の和から小さい方の要素を引くことで求めるのが良い。これで $N=7000$ のときの操作回数が999045回となり、満点。

ちなみに、ここから3要素のソートの特別扱いをなくしただけでも満点は取れなくなるようだ。大変な問題である。

昨日投稿されていたゲーム理論の課題を終わらせた。今度こそ最終回。課題の内容は、演習問題を解かされるのではなく講義の感想を書けというもので、大学院にもなってそれはどうなんだと思った。ただ、自分が人に何か説明する立場になったとして考えると、フィードバックは欲しくなるだろうから、こうやって強制的に書かせるのは分からない話でもない。見た瞬間反射的に課題がつまらないとか書こうとしたものの、そういう攻撃的な態度を改め、適当に無難なことを書いておいた。

布団に入って2時間ほどなろうの更新を読み、午前5時就寝。

07/21(木)

午前11時半起床。しばらく布団に転がっていたが、二度寝するのはやめて起き上がった。シャワーを浴びて、学食で食事し、購買で予約していたラノベを買っていったん帰宅。

セミナーに向け出発するまで30分ほど時間があったので、机の上の積読を整理した。なんとなく気分を変えたくて本の角度をバラバラにして積んでいたのだが、一部分だけ上から数か月プレスされ続けた結果表紙が曲がってしまった本があり、罪悪感に苛まれた。本棚には入りきらないので、整理したといってもまたいくらか机に出しておく必要がある。今回はちゃんと揃えて積み重ねた。これから気を付けたい。

pic.twitter.com/fL3hB5Ri6w
— こたつがめ (@kotatsugame_t) 2022年5月26日

再度外出。大学に向かいセミナーに参加した。今日は午後6時半くらいまでやっていた。僕ではなくもう一人の発表。2週間前に以下のようなことがあり、彼の発表方法に口出ししたのだから見届ける義務があると思って、今日はそのあたりのことにも注意して聞いていた、つもり。しかし、何かが変わったことを発見したはずなのに、発表後に伝えようとしたら忘れてしまっていた。少なくとも僕が思う良いやり方に近づいているはず。実のところ、それが本当に良いのかはわからないのだが。

先生が帰った後黒板発表の方法について少し話していた。
週記（2022/07/04-2022/07/10） - kotatsugameの日記

食事して帰宅。Multi-Universities Campの問題をこの日記に書くのが良いのか気になったため、CodeforcesのDMで運営の方と連絡を取った。結果は月曜日の日記の冒頭に書いた通り。

いい加減ICPC国内予選の参加記を書こうと思って、夜はずっとそれに取り組んでいた。もう2週間も前のことになる。しかしコンテスト時間のほとんどはE問題に苦しんでいただけなので特に詳しく描写する必要もなく、残りの部分の出来事を記憶と順位表から復元するのはそう難しいことではなかった。

午後11時半からはECR132に出た。

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

Aはどう書いたらいいかパッと思いつかなかった。今持っている鍵で開けられる扉を全部開けるという操作を3回繰り返し、すべての鍵が手に入れられるかチェックした。Bは左右に累積和を取っておく。

Cは?に埋める(と)の数が決まるので、まず(を優先的に使ってみる。これで正しい括弧列にならないなら1通りも作れない。作れるなら、今度は?に埋めた(と)を一つずつ選んでswapしたとき、正しい括弧列のままでいられることがあるかを調べる。swapする(を全探索すると)は最も近いものを選ぶのが最適。括弧を $\pm 1$ に置き換えたときの累積和は、swapによって選んだ(と)の間が $-2$ されるから、その部分の値が最初の状態で常に $2$ 以上だったかを見れば、swap後も正しい括弧列であるかを判定できる。区間MINをpriority_queueで管理した。スライド最小値でもよかったか。

Dはまず $k\mid(x_s-x_f),(y_s-y_f)$ である必要がある。列を移動する際は行番号をできるだけ大きくしておくのがよいから、行 $n-((n-x_s)\bmod k)$ を使って移動することになる。 $y_s$ と $y_f$ の間の列であってこの行までブロックされているものがないかチェック。区間MAXを取得すればよい。

Eはマージテクで木dp。中途半端なパスの重みを更新するため、set全体の要素にある値をXORしたくなる。つまり全体にXORされた値というのを別途管理することになるので、それの処理に気を付けながらマージしていく。もう十数回書いたはずなのでさすがに慣れてきたのか、ここでは特に詰まらなかった。同じ子から来たパスを2本繋げないため、マージの際は重み $0$ のパスを探し終えてから要素を移す必要があることに注意。

Fはdp。文字列 $s$ と $0\le i\le k$ に対し、 $s$ をprefixに持つ文字列だけ考えたとき、条件を満たす多重集合の最大サイズがちょうど $i$ になるような $c$ の決め方を求める。対称性から実は $s$ の長さにしか興味がないことがわかるので、計算できそうな状態数になる。これを $dp_{|s|,i}$ とおこう。

$|s|=n$ のとき、最大サイズは $c_s$ と一致する。よって $0\le i\le k$ に対し $dp_{n,i}=1$ である。 $|s|\lt n$ のとき、 $dp_{|s0|,\ast}$ と $dp_{|s1|,\ast}$ の畳み込みによって $dp_{|s|,\ast}'$ が求まる。ここから $0\le c_s\le k$ を決めるごとに、 $0\le i\le 2k$ について $dp_{|s|,i}'$ は $dp_{|s|,\min(c_s,i)}$ に寄与することになる。適当に実験すると累積和とちょっとした係数によって書けることが分かった。最後に長さ $k+1$ にresizeする。

$dp_{1,\ast}$ が求まったら、それを $s=0,1$ の分と見て畳み込む。空文字列 $\varepsilon$ に対する $c_{\varepsilon}$ は存在しないので、先ほどのような後処理はせず、得られた列の $f$ 番目を出力すればよい。

全完4位。Cで結構詰まったのが苦しい。実は(を全探索する必要はなかったようだ。?に埋めた括弧は前からいくつかが(、残りが)となっているため、括弧の種類が切り替わる直前と直後のペアをswapするのが最適。確かにCで区間MINを要求されるのは何かがおかしいなという気がしたのだった。

参加記の残りを書き上げ、午前4時に投稿した。

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

「kotatsugameに質問」の更新作業にもさすがにそろそろ手を付けるべき。というわけで、ここから2時間くらいは新しい質問への回答を作成していた。記事公開直後に投稿されたものは2か月以上も回答をお待たせしていることになり、申し訳ない。

午前6時半就寝。

07/22(金)

午後1時の直前に起床。すぐミーティング……と思ったら午後3時からだった。時間を勘違いしていたらしい。

空いた時間で二度寝するのではなく、大学生協に行った。昼食を摂って午後2時、そこから床屋に入店。「1時間くらいで終わりますか？」と聞いて肯定され、実際1時間もかからず終了したのだが、午後2時から1時間後というのは当然午後3時であって、つまるところ、もうミーティング開始には間に合わない。遅れる旨を先方に伝えたら30分ずらしていただけたので、購買で予約していたラノベを買いつつ帰宅した。

家にたどり着いてシャワーを浴び、午後5時半までミーティング。かなり盛りだくさんの内容だった。一応議事録っぽいものはあるものの、こういうのは個人的にもメモを取っておかないとまずそう。心がけたい。

DDCC本戦に参加するにあたってアンケートが来ていたので回答。その後家を出てゲーセンに向かった。今日はほとんど新曲埋め。ULTが7譜面追加されていたので、14以下はAJ、14+はSSSまで詰めた。さらに以前詰め切れなかった14+のSSSを出した。

幾望の月 ULT AJ
フリックの速度思ったより速かった pic.twitter.com/cAHg5POVOP
— こたつがめ (@kotatsugame_t) 2022年7月22日

精度が取れない。MASも99AJを出すのにかなり苦労した記憶がある。これでも最初のころから赤は20くらい減った。終盤はある程度どついても通るが、それよりもフリックの近くに赤タップがあるところで頻繁にATTACKを出してしまっていた。

14+のULT埋めた pic.twitter.com/CzAvCAeKIq
— こたつがめ (@kotatsugame_t) 2022年7月22日

どれも大変な譜面だったがある程度サッと出てくれた。その分もったいないミスが残っていてちょっと残念。

「患部で止まってすぐ溶ける……」は終盤の謎リズムの両手トリルがすべて。セリフ合わせという話を聞いたがよくわからない。譜面製作者にはいったい何が聞こえているのか。

「Gustav Battle」は忙しいうえエアーで譜面がよく見えず、嫌い。うまく認識できていないのになぜか通ったという配置が多いので、これ以上連奏したら押せなくなってどんどんスコアが下がっていっただろう。早めに出せてよかった。

「Gate of Fate」もすぐ出た。これが一番残念で、やたら速い配置がある1か所でドバっと出してしまった。ラストの蟹は何もわからないままスライダーを撫でていたらAJ通過した。これも時間をかけると泥沼にはまり込むタイプの譜面に見える。

Re：End of a Dream SSS
14+全鳥奪還 pic.twitter.com/JiEg6bLnPD
— こたつがめ (@kotatsugame_t) 2022年7月22日

ちゃんと運指を組んだらすぐ出て、14+の全鳥を奪還できた。以下のツイートに二つばかり紹介した他、ところどころ擦っている。適当に考えたあまり丁寧ではない擦り方だったが、案外通ってくれて楽だった。たまたまだろうか。

運指（左のは昔nullさんが言ってたやつ） pic.twitter.com/E1sp87cMSx
— こたつがめ (@kotatsugame_t) 2022年7月22日

GiGO仙台にいたのだが、午後11時を回ってすぐに閉店してしまった。新たにプレイを始められる時刻の制限が以前より早められた気がする。ラスクレで上のSSSを出したとはいえまだ微妙にやり足りなかったので、スーパーノバに向かった。こちらは午後11時45分まで新しくプレイ開始できるため、さらに2クレばかり遊んだ。

油そばを食べて午前1時前に帰宅。シャワーを浴びた後は疲れ果ててしばらくYouTubeを眺めていた。少し日記を書いて午前4時就寝。

07/23(土)

午前8時半に目を覚ました。二度寝したいので眠気を待とうと思いつつラノベを開いたら、途中で止められなくてそのまま読了してしまった。

「紅蓮戦記」。かなり面白かった。魔法がある世界で戦争する話。魔法を組み込んだ戦術だったり軍の構成だったりが緻密に描かれており、そういうところからはリアルさを感じる一方で、主人公だけがあまりにも圧倒的に強かったのが好みだった。そのあたりもリアルだと辛いから。魔法＋戦争と聞くと幼女戦記が思い浮かぶが、あちらも主人公はチート持ちだったのである。あとがきに、異世界の話だから固有名詞以外に英語を使わないようにしたと書いてあってびっくりした。まったく違和感なかった。

敵軍に完全包囲された中から脱出する、とあらすじにも帯にも盛んに書かれていたものの、それがこの巻のメインかと言われるとあまりそうでもない印象。とにかく強いため局地的には勝ち続けているし、いざ包囲されて脱出する際も、その手法ではなく脱出後にどう行動するかが注目されていた。

結局眠れなかったことになる。布団から出て少し準備し、午後1時からMulti-Universities Campの2回目に出た。

今日はチームとしてGKDELIHCJFAの11完。僕はGLIHを書いた。

Gは順列を並べ替えてLISとLDSのうち大きいほうを最小化せよという問題。細かいところに自信がなかったものの、無事ARC091-Eがほとんど強化版の構築問題になっていることを発見し、解説を見つつコピペして解いた。最初は自分の提出を使っていたのだが、サンプルにすら正しい答えが出せなかったため、提出日時が最も早かったコードに切り替えた。writer解だと思っていたらFAの人のコードだったらしい。

E - LISDL

そこそこ通されていたEが考えても解けなかった。数え上げが得意そうな人にHELPを要請したら一瞬で解かれていた。つい先週のABC260-Exの部分問題だったらしい。その後Jに進んだ。データを最小二乗法で1次関数にフィッティングしたときの二乗誤差の和を出力せよという問題。しばらく式変形していたら別の人も合流してきて、結局式をガチャガチャやるだけだったので任せてほかの問題に進んだ。

LIHはまあやるだけ。Lはメモリ制約が厳しい問題でちょっとビビっていた。入力すら全部持てないほどだが、特に難しいことをせずとも入力を読み込みながら処理できるため全く問題なし。

Cは謎のWAで苦しんでいたようだが、いつの間にかリジャッジがかかって通っていた。かわいそう。Jは式変形は正しいのに誤差が厳しい問題だったらしく、10WAののちPyPyの多倍長整数を持ち出して解いていた。かなり苦しそうだった。

Aを考えていたらFがいつの間にか通されていて、ちょうどそのあたりでAがMongeやらAlienやらの関連だと分かったがこの実装も別の人に押し付けた。AlienDPにはいい思い出がない。最後に残ったBを考えて、頑張れば解けるけどどう見ても間に合いそうにないし頑張りたくないなあと思っていたらコンテスト終了。

今日は簡単な問題が多かった。4問も実装して満足という気持ちだったのに、よく見たら自明しか解いていない。途中で別の人に任せてしまったJは実はとんでもない問題だったので、ちょっと申し訳なさがある。

信じられないくらい眠いので午後6時半から仮眠することにした。2時間程度で無事起床し、午後9時からABC261。

AtCoder Beginner Contest 261 - AtCoder

今日も全部C++。そんなすぐに短くなる問題もなかったように思えたので、一切コードゴルフのことを考えず駆け抜けた。Cまでは特に言うことなし。Dはdp。Eは桁ごとに最初が $0$ の場合と $1$ の場合を計算しておけばよい。Fは感覚的に、大小関係に加えて色が異なるという条件を入れた場合の転倒数だと思ったので、普通に計算した転倒数から色ごとに計算した転倒数を引いた。BITのゼロクリアは毎回やっていると間に合わないので、更新した部分に打ち消すような値を足すことで行う。

Gは大変。各英小文字に対し、それを $T[l:r]$ に一致させるために必要な操作回数を計算した。操作は入れ子になっている可能性があるので、 $(C_i,A_i)$ と $(l,r)$ を全探索するのを、どこの操作回数も更新されなくなるまで繰り返した。 $(C_i,A_i)$ を決めるごとに定数倍が軽い $O(|A_i||T|^3)$ のdpで全 $(l,r)$ について更新できる。これを何回繰り返すのかはよくわからなかったが、 $|A_i|$ が大きなものばかりだとそう何度も操作できないので、全体としては小さくなってくれるはずと信じて出したら通った。

Exはまず頂点を倍化して先手後手に対応させる。出次数が $0$ の頂点では先手後手ともに答えが $0$ になっていて、そこから逆辺をたどり、先手に対応する頂点では到達できたものの $\min$ を、後手に対応する頂点では $\max$ を取る。先手に関してはdijkstraすればよい。後手は出次数をデクリメントして $0$ になったタイミングでキューに入れる。そもそも $0$ にならなかった場合はINFINITYで、キューに入れる必要もない。

初手でとりあえずSCCをしたまま実装してしまい、辺の先が同じ強連結成分かどうか確認していなかったため、うっかり二重に出次数をデクリメントして1WA。ちゃんと確認してACした後、SCCを使わないコードも出しておいた。

全完4位。Gは $(l,r)$ を先に決めると自然と区間dpに思えて、計算量解析ができるようになった。 $O(|T|^4\sum|A|)$ ではあるが定数倍 $\frac 1{24}$ がついているようだ。解説より悪いオーダーなのは、補助的なdp配列を使わず、常にその場で計算しているから。

Exについて、そもそも最初はただのBFSをしようとしていた。上で書いたキューに入れるタイミングはその時と変わっていない。先手に対応する頂点に到達した値の $\min$ が何度も更新されるとまずいなと思ってdijkstraにしたのだが、同時に後手に対応する頂点では到達した値の $\max$ を求める必要があるため、見た目的には上手くいきそうにない。しかし実のところ、出次数が $0$ になるタイミングでしかキューに入らないという理由から壊れないことがわかる。この事実は結構面白かった。

コードゴルフ。Aはdc。なんだかんだ言ってそれなりに短くなった。 $\min$ や $\max$ を計算するとスタックの深さが分からなくなるのが難点。 $L_2$ と $R_2$ を変数に持ち、まず $\min(R_1,R_2)$ を計算する。それをduplicateした後スタックの底から $L_1$ を持ってきて、今度は $\max(L_1,L_2)$ を計算する。この時点でスタックの上から2番目に何があるかはわからないのだが、先ほどduplicateしておいたので3番目は確実に $\min(R_1,R_2)$ になっている。うまいこと2番目をpopして3番目から1番目を引き算。最後の $\max(0,\ast)$ は精度の変数kを使ういつものやつ。

BはまずW→ $1$ 、L→ $-1$ 、D→ $0$ と変換し、転置行列と和を取って全部 $0$ になることを確認するOctaveのコードを書いた。しかしRakuでW↔Lと変換した後転置して一致するか見るほうが短くなった。CはAWK。DはdpをOctaveで書いた。Eは桁をばらしてループを回すコードでACしたので短くなりようがないと思っていたのだが、普通にbit演算で書けたようだ。そこからは縮みそうにない。

FはBITの配列を連想配列にすることで仮想的に長さ $N$ のBITを $N+1$ 本持てる。Rubyだと2000ms前後で通った。Perlはコード的にはかなり縮んだのにどう頑張っても手元で5secかかり絶望。そもそも、上のようにゼロクリアを頑張ることで同じ配列を使いまわしたとしても5secかかっていた。Gは日記を書くときにコードを整理していたら最短になっていた。以降、というかExは手付かず。

午前8時くらいまで日記を書いた後、布団に入ってラノベを読んでいた。3分の2ほど読み進めたあたりで切り上げ、午前10時半就寝。

07/24(日)

午後4時起床。眠すぎる。布団の上でしばらくぼんやりした後起き上がった。

午後5時からOpenCup。今日はGrand Prix of Bytedance。チームとしてEFBIJの5完に終わる、かなり難しめのセットだった。僕はBのみ。

数 $t$ が左の子に $\lfloor t/2\rfloor$ 、右の子に $\lceil t/2\rceil$ を持っているとして作られた二分木がたくさん並んでいる。ただし $1$ 以下の頂点は無視。二分木の列を深さごとの頂点の列だと思い、一つ右の頂点に進む、または左の子と右の子の間となるような位置に降りるということを繰り返して、最大でどれだけの頂点を訪れられるかという問題。

木から出るときの深さを決めたとき、一番深い部分以外は完全二分木なので入る前ににできるだけ降りておいたほうがよい。問題は二番目に深い部分から一番深い部分にどのタイミングで降りれば訪れた頂点数を最大化できるかということ。ここをメモ化再帰で実装すればとりあえず通るなと思い、実際愚直解と同じ値が出力されたため提出。しかしTLEだった。

たまたまその時間他のチームメイトがPCを使っていなかったので、しばらく占有してガチャガチャしていた。メモ化しなくても手動で同じ頂点をまとめながらループで計算を繰り返せばよさそうだということに気づく。 $\lfloor t/2^i\rfloor$ と $\lceil t/2^i\rceil$ という形の頂点しか現れず、この二つから作られる部分木の高さが異なる場合だけ丁寧に計算すればよい。それだけは再帰することになるものの、木ごとに高々1回しか起こらないはずなので間に合いそう。

ところが紙で詰めずに実装を始めてしまいかなり迷走した。そのうちほかの問題を解いたチームメイトにPCが空くのを待たれていたのだが、ちょうどそのときは答えが微妙にずれている真っ最中で、結局PCを使いっぱなしのまま愚直と答えが合うところまで持っていった。提出するとAC。愚直解やTLE解があったおかげでデバッグは楽だったものの、そもそも闇雲にガチャガチャするのはチーム戦では避けるべき。

残り時間はGを考えていた。適当に条件を出したものの先に進まず、コンテスト後に解説を読むと、実は僕が出した条件だけでdfsしても十分少ない状態数しかないということが書かれていた。これはコードを書いてみないとわからない問題。

素因数分解した形をdfsで探索するときに最大の素因数の指数が $1$ か $2$ 以上かで分けて考える、というのは汎用的なテクに見えるため、ここで知れてよかった。 $N$ 以下の数を探索するとして、数 $n$ を持っていたら、まず $N/n$ 以下かつこれまで使ったものよりも大きな素数 $p$ について $np$ を集める。これが上で述べた指数が $1$ の場合。その後、 $np^2\le N$ かつこれまで使ったものよりも大きな素数 $p$ について、 $np,np^2,\dots$ をそれぞれ新しい $n$ として再帰する。また同時に、上で述べた指数が $2$ 以上の場合として、 $np^2,np^3,\dots$ はこのタイミングで集めるべき数となる。再帰してしまうと $np^2\times 1$ は得られなくなるから。

少しコードゴルフ。まずABC261-BはWとLの文字数が同じか判定するだけで通るらしい。OpenCup中の集中が切れたタイミングでチラッとTLを見たら、それを使っている提出が流れてきて、慌てて縮めた。Perl。

また、ABC261-Fが縮められていた。20B近く短くなっていたのだが、これを達成する短縮ポイントの一つでRubyでBITを書くとき汎用的に使えるテクが生み出されていた。BITの配列にアクセスする変数の更新は、アクセスした後でないと書き換えることができない。そのため、これまでは(s+=b[i];i&=i-1)のように二つの式として書いていた。ここをs+=b[i|i&=i-1]とすると縮む。同様に更新時の(b[i]+=1;i+=i&-i)もb[i%i+=i&-i]+=1とできる。

RubyでBITを使っている最短コードを探し、縮めておいた。

Dashboard - Codeforces Round #810 (Div. 1) - Codeforces

午後11時半からCF #810 div.1に出た。

Aはサンプルの図が大ヒント。このように縞模様に塗るしかない。実際に手で同じ色の連結成分を構成してみると、周り2マスが塗られた時点で中心のマスもその色になるということから、図のように一周するしかないことが感じ取れた。念のため縦横を両方探索して、 $\sum_i\left\lfloor\frac{a_i}n\right\rfloor\ge m$ ならOK……とはいかない。幅1の縞模様もダメである。

なので $\left\lfloor\frac{a_i}n\right\rfloor\le 1$ なら和を取るときに弾くのと、横 $m$ マスに詰めたときに幅1だけ塗る色がないようにする必要がある。 $\left\lfloor\frac{a_i}n\right\rfloor\ge 3$ なる $i$ があれば、それを適宜狭めることでうまくいく。弾かれていないすべての $i$ について $\left\lfloor\frac{a_i}n\right\rfloor=2$ かつ $m$ が奇数の場合はどうしようもない。このケースがサンプルにあったのには、かなり優しさを感じた。

Bは誤読してかなり時間を溶かした。考える座標が $1\dots n$ だけだと思って、imos法を2回行って三角形を足すコードを書き上げ、サンプルを試している段階で気づいた。判定部分は $a_j\gt m$ かつ $a_j-m+|x-j|\gt p$ なる $j$ が存在するとアウトで、 $a_j\gt m$ なものだけ抜き出して $a_j-m+(x-j)$ と $a_j-m+(j-x)$ を区間MAXが取得できるデータ構造に乗せ、 $[1,x]$ と $[x,n]$ で取得する値を分けている。

正しい問題を解く。まず判定するべき $j$ としてはどこかの $x$ だけを考えてよい。よって $a_{x_i}$ をすべて求めることができれば、 $x$ を座圧することで上と同様の方法が使える。 $a_{x_i}$ を求めるために折れ線の傾きを管理することにした。傾きが変化する点は $O(N)$ 個しかないため、それと値を取得する点をまとめてイベントソートし、値を更新していく。さっきまでimos法2回で苦しんでいたのが何だったのかと思うくらい簡単に書けた。

この時点で順位が3桁でかなりまずいなという気持ちになった。C問題に進む。これは簡単。 $x,y\lt z$ として $x+y\gt z$ だけ判定、など考える必要もなく、 $x+y-z$ 、 $y+z-x$ 、 $z+x-y$ をほぼ直接管理できる。この値が $1$ 以上なら $1$ としてよく、また $-2$ 以下なら以降どう頑張っても正にはできないため無視することで、それぞれを3状態に圧縮できるからだ。 $a,b,c$ それぞれが $n$ 未満かどうかをチェックする2³状態と合わせても十分少ない状態数の桁dpになる。

順位表を見ると、この時点でDのsolvedがほぼ0である一方Eのsolvedが30以上あったため、そちらに取り組んだ。答えを二分探索すると、ゲームは先手勝ちマスと後手勝ちマスのどちらで終了するかというものになる。 $a$ と $b$ をソートするとマスは対角線っぽい感じに分けられる。ここまで整理すれば、あとはたくさん通されているのだから簡単な判定方法があるものだと思って、例えば先手勝ちマスと後手勝ちマスの個数を比較したりしてみたものの、通るわけもなく。そのままコンテスト終了。

CとEが既出であるとして話題になっていたが、それどころか特にEは過去に出題された問題の剽窃だったらしい。これを理由に今回のdiv.1はUnratedになった。そもそもBでめちゃくちゃ詰まって順当に失敗した回だったから、偶然命拾いしたという感覚。

About div1E (round #810) - Codeforces

TCB49の順位が出ていた。6位。やはりミスが大きかった。

朝までずっと日記を書いていたが終わらない。また明日も昼から5hなので、午前7時を回ったあたりで布団に入り、すぐ就寝。

2022-07-22

ICPC国内予選 2022 参加記

2022/07/08に開催された国内予選にチームAobayama_dropoutで参加しました。模擬国内予選の参加記でも書きましたが、今年のメンバーはha15さん・ホスフィンさん・僕です。

これも模擬国内と同様、ホスフィンさんが確保してくれた大学の演習室から参加しました。

序盤の戦略はホスフィンさんがA、ha15さんがB、僕がCを読むというものでした。以降の問題については、とりあえず皆で考え、解けたら誰か一人に実装を任せて残りは先に進むというような形にできればなと思っていました。以下に見るように、今日はそれどころではなかったのですが……。

問題文：https://icpc.iisf.or.jp/past-icpc/domestic2022/contest/all_ja.html

今年は特にネットワークに問題もなく、時間通り始まって問題文もすぐ読むことができました。

C問題

能力の増分は、 $k$ 日連続すれば $\pm k^2$ となるように定められています。特に、練習計画においては練習日と休憩日がそれぞれどれだけ連続しているかにだけ興味があって、その順番は特に関係ありません。

練習日の連結成分が $1\le i\le n$ 個ある場合、休憩日の連結成分は $j=i-1,i,i+1$ 個のどれかなので、この組を全探索できます。中途半端に偏らせる必要はなさそうなので、練習日と休憩日のどちらかは連結成分を一つだけできる限り大きくし、もう一方は全体にまんべんなく割り振るのがよいでしょう。

連結成分が二つだとして、両方の戦略で能力の増分（の絶対値）がどれくらいになるか比較したところ、前者のほうが大きくなるようでした。よって、練習日はほぼ $1$ 連続のところ一つだけ $n-i+1$ 連続することになり、休憩日は基本 $\lfloor m/j\rfloor$ 連続、うち $m\bmod j$ 個は $+1$ となります。

これを実装します。 $n=0$ または $m=0$ の場合を先に処理しておき、 $j$ が $1\le j\le m$ を満たすように全探索して、上の戦略を用いた時の能力の増分を計算しました。サンプルが合ってそのままAC。7分40秒でFAでした。

D問題

A問題も少し前に通っていました。一方B問題では詰まっているようでしたが、聞いてみると「解けるはずだが実装がよくわからない」ということだったので、僕が読む必要はないと判断し、ホスフィンさんにヘルプに入ってもらうことにして一人だけ先に進みました。

D問題を読みます。結局マージソートをしているため、列の一部を切り出す度にそこまででちゃんと望む順番に入場できているか判定してよいことがわかります。つまり、まだ分割していない部分の影響で順序が入れ替わることはないということです。ここで分割位置と分割回数を持つdpが思い浮かんだので、実際に書けるかどうか考えてみました。

今、インデックス $i$ の前までを $j$ 本の列に分割できているとしましょう。まず、新しく列 $s_{[i,i')}$ を追加したとき、ちゃんと望む順番の入場順になるかどうかですが、すでに「 $s_{[0,i)}$ を $t$ における順番に並び替えたもの」があったところに $s_{[i,i')}$ をマージしたとき、「 $s_{[0,i')}$ を $t$ における順番に並び替えたもの」が得られるか判定すればよいことになります。 $s_{[0,i)}$ と $s_{[i,i')}$ の値たちをいくらか大小比較すればできそうです。

またそのような、言わば「 $i$ の遷移先となれる $i'$ 」は、 $i+1$ を左端とした区間をなすこともわかります。つまり遷移が区間加算で書けるため、dpと同時にimos法を行うことで十分高速に計算できます。

大体解けた気持ちになりました。B問題は念のため二人で実装しているらしく、また上の考察は細かいところまで詰められていなかったので、人に投げるのをやめ、自分で書きながら考えてみることにしました。

$t$ の逆順列を $T$ とします。つまり $t_{T_i}=i$ です。インデックス $i$ を見ている瞬間、セグメント木には各 $k\in s_{[0,i)}$ について位置 $T_k$ に値 $k$ をセットしておきます。今、新たに列 $s_{[i,i+1)}$ を追加したとすれば、マージ後に $s_i$ が $T_{s_i}$ の位置に来るためにはセグメント木の区間 $[0,T_{s_i})$ に $s_i$ より大きな値がセットされていてはいけません。これは区間MAXを計算することで判定できます。

同様に、 $s_{[i,i+2)}$ を考えているとき、先ほどの条件に加えてセグメント木の区間 $[T_{s_i},T_{s_{i+1}})$ に $s_{i+1}$ より大きな値がセットされていないことをチェックする必要があります。また当然ながら $T_{s_i}\lt T_{s_{i+1}}$ も必要です。このようなチェックを繰り返して追加できる限界を求め、それを用いて区間更新しました。

サンプルが合いません。しばらく考えて、 $T_{s_i}$ より後ろに $s_i$ より小さな要素がある場合もまずいことに気づきました。ただし $s_i$ 追加時点で列の先頭にいなければ大丈夫です。しかしこれは、判定が列の分割方法に左右されてしまうことを意味します。つまりこのままではdpができません。

一瞬目の前が真っ暗になりましたが、チェックのタイミングを変えることで一命を取りとめました。つまり、 $s_i$ を追加できない原因を探すのではなく、 $s_i$ がほかの何かの「追加できない原因」にならないか判定すればよいのです。 $s_i$ が列の先頭にいるのは $[0,T_{s_i})$ の間ですから、その区間で、 $s_{[0,i)}$ にまだ出現していない値であって、 $s_i$ より大きなものがないかチェックすることになります。

同様のチェックは $s_{i+1}$ について $[T_{s_i},T_{s_{i+1}})$ を見るという風に全体で行うことになります。区間MAXを計算するセグメント木をもう一本生やして、こちらはまだ出現していない値をセットしておきました。条件を追加してもう一度サンプルを試すと今度こそ合い、提出してAC。28分57秒で、今度もFAでした。

E問題

2問もFAだったということでひとしきり踊り狂っていました。B問題は実装が佳境に入り、もう問題なさそうなのでE問題を考え始めました。

この問題は非常に難しかったです。まず初手でこれっぽいと思える方針がありませんでした。一応、フローらしさが感じられないこともなかったので、かなり長い間その考察と像の条件を絞っていく考察を交互に進めていました。結局フローではなかったのですが。

1時間くらい経過して、その時点で得られていた考察は、端の交差点に関するものだけでした。まず、調査員が帰還した道路は、最初が+で最後が-であることが確定します。逆にこのどちらかを満たさないように置けば、調査員が絶対に帰還できないようにできます。

これを念頭に置いて、例えば $A_1=0$ の場合を考えます。このとき一番北の道路はほとんど自由に決めてよいですから、各 $j$ について $B_j=1$ なら+を、 $B_j=0$ なら-を置くのが最適です。 $A_1=1$ の場合も $B_j=1$ なら+と決定しますから、 $B_j=0$ である道路だけから $m/2$ 個選んで-にすることになります。この選び方は東から貪欲に取るのがよいでしょう。 $A_n$ の値を見れば、ほとんど同様のことが一番南の道路に対しても行えます。

ここからが一つ目のポイントでした。 $B_j=0$ である道路のみを考えます。 $A_1=0$ または $A_n=0$ なら、最初に-を置かれたり最後に+を置かれたりして、すでに調査員が帰還できないと決まっています。では $A_1=A_n=1$ ならどうでしょう。一番北の道路では東から $m/2$ 本に-が、一番南の道路では西から $m/2$ 本に+が置かれています。すると、 $B_j=0$ である道路は当然 $m$ 本以下ですから、これまた $A_1$ と $A_n$ のどちらかで調査員が帰還できないと決まっていることがわかりました。

結局、端に関する考察だけで $B_j=0$ は達成できています。同様のことを $B$ でも行いますから、残りは $(n-2)\times(m-2)$ 個の交差点で $A_i=1$ と $B_j=1$ を無事帰還させることさえ考えればよいことになりました。

ここで二つ目のポイントです。 $(n-2)\times(m-2)$ を市松模様に埋めれば、最初が+で最後が-なら必ず帰還できるようになります。これに気付いたときはかなり大きな衝撃を受け、思わず手を打ち鳴らしてしまいました。

実装に取り掛かります。 $A_1$ と $A_n$ を見て端を埋めるコードを書き、それをコピペして $B$ 向けに修正しました。この部分は明らかに、 $A$ と $B$ を交換して同じコードを再利用したほうが良かったです。端を埋め、中を市松模様で埋めた後、四隅が矛盾している場合に備えて実際に各道路をチェックし、出力しました。それなりに苦労してサンプルを合わせ、いざ提出。しかしWAでした。

最後にチェックしているのですから、答えがYesのケースは間違っていません。つまり、YesなのにNoと出力しているケースがあるはずです。絶望しながら考察をもう一度辿っていると、 $A_1=0$ や $A_n=0$ の場合の決め方があまりに自由すぎることに気づきました。 $B_j$ の値に応じて決めた結果、うっかり帰還できてしまうケースが考えられます。

これを解決するためには、 $B_j=0$ であるような道路を選んで切り替えればよいです。ですが、これを切り替えたせいで今度、その道路が帰還可能になったりはしないでしょうか？結論から言えば、そのような $j$ があるならそもそも出力がNoとなります。場合分けで確かめられますが、実はこの事実は今気づいたことで、本番では適当な場合分けにより、 $B_j=0$ であって一番東または西の道路を選んで切り替えていました。こうするとそこも帰還可能にならないことが言えます。

しかし、今度はそのような道路を切り替えたことで四隅が矛盾する可能性があります。そこで、まず四隅を2⁴通り全探索し、それ以外の部分を上のように決めたり切り替えたりする対象にすることにしました。コピペの結果実装が肥大化していて、苦しい書き換え作業になりましたが、何とか実装し切ってサンプルを合わせました。

先ほどWAを出したテストケースに対する出力がどのように変わったかチェックします。YesとNoの行だけを抜き出してdiffを取ると、見事に3ケースNoだったものがYesになっていました。これを提出してAC。2時間39分34秒でした。

コンテスト終了

残り時間、と言っても20分しかなかったのですが、その間はF問題のコーディングをしていました。

さすがにE問題だけに2時間以上没頭できていたわけではなく、途中で少しF問題を読んでいました。その時点でとりあえずメモ化再帰で答えが出せることはわかっていましたが、それほど高速には思えず、またE問題のほうに注力すべきだと考えて詳しく考えずに戻ったのでした。その考察を引っ張り出しとにかく実装してみることにしましたが、さすがに20分では何もできず、そのままコンテスト終了時刻を迎えました。

結果は5完13位です。学内1位を取って昨年の予選のリベンジこそできたものの、E問題で苦しみすぎて喜ぶ元気はありませんでした。5完したチームではちょうど真ん中の順位を取ってしまっていますから、D問題までのスピードが見る影もありません。上では触れませんでしたが、2問FAの後、B問題も無事通った時点では2位だったのです。

https://icpc.iisf.or.jp/past-icpc/domestic2022/common/guest_standings_ja.php.html

結局僕がCDEを実装してしまっています。しかしそもそも、そのような問題分担について考えられるような出来ではありません。いかなる戦略を取ったとしてもE問題が解けるのは前提になっていて、それが崩れた今回はもう……本当に大変でした。なぜ解けたのかがよくわかりませんが、九死に一生を得たような心持ちです。

まあ、戦略に関して思うところがないわけではありません。E問題に取り掛かった時点では順位表に一切の情報がありませんでしたが、それからしばらくしてE問題とF問題に同程度、むしろF問題のほうが多い瞬間もあったくらいACが出てきたのは把握していました。つまり今回、この二問の難易度にそれほど差がないことは分かっていたのでした。

僕自身はE問題を捨てるような気分になれなかったものの、例えば一人、F問題の考察に回ってもらうのは十分あり得た戦略かと思います。いや、実際にF問題も考えてくれていたのかもしれません。チームメイトが何をしているかは全く把握していませんでした。しかも解法は僕が考えた方針の先にあるものだったため、余計にもったいなさを感じます。これは結果論ではありますが。

E問題を通してからF問題の自分の考察を開陳したのですが、コンテスト後にチームメイトに考えていたことは共有してくれと言われてしまいました。これは全くその通りです。チームメイトが何に取り組んでいるかを把握しようとしなかったのも合わせ、自らワンマンチームにしようとしているようなものなので、意識を変えなければなりません。

2022-07-18

週記（2022/07/11-2022/07/17）

07/11(月)

先週の週記を投稿してから寝るまでの話。

布団に入ってから、先週火曜日に提出した離散数学の課題の模範解答がアップロードされていたことに気づいた。改めて書いておくと、最後の問題が $\mathbb{Z}_{\gt 0}\times\mathbb{Z}_{\gt 0}\rightarrow \mathbb{Z}_{\gt 0};(m,n)\mapsto 2^{f(m)}g(n)$ という全単射を構成せよというものだった。ここで $f(m)=m-1$ と決めておく。

自分は $g$ として素因数分解した後の素数を一つずつずらすような写像を考え、頑張って必要な性質を示した。しかし解答は $g(n)=2n-1$ だった。目から鱗。特に自分の作った $g$ がただ複雑なだけの $\mathbb{Z}_{\gt 0}\rightarrow \mathbb{Z}_{\gt 0}\setminus 2\mathbb{Z}_{\gt 0}$ であるということは、冷静になると当たり前なのだが、見た目からはすぐにはわからないと感じている。

まあ減点はされていなかったのでOK。無事期末レポートを無視しても満点評価が得られることになった。午前9時就寝。

午後1時起床。直後からインターン先のミーティング。僕がしばらく前に適当に書いた実験コードが以来ずっと使われていて、しかし精度を上げるための重要な処理が抜けていたため、これまでの実験結果は参考程度にしかならないということが発覚した。申し訳ないという気持ちももちろんあるが、そもそも使ったことのない処理なので自分では発見できなかっただろうし、それよりもその処理を入れると精度が目に見えて上がったということに興奮している。

少しコードを手直ししたりもして、午後3時前に終了。すぐ購買に行って菓子パンを買い込んだ。

日曜日のCF #805 div.3の順位表を見ると、open hacking phaseが終わって11位になっていた。もともと13位だったのが上がった原因は、上の人の提出が落ちたからではなく、そもそも垢BANされたからに見える。

インターン関連の作業を始めて、その途中から定例会に突入。進捗報告は直前までやっていた作業のことで、○○をどうすればいいかわからないのが現状ですと発表したのに、そのすぐ後でググったら思いっきり出てきてしまった。慌てて進捗を用意しようとしているのがバレバレ。

ちなみにやっていたことは、エクセルファイルのブックをまたぐシートのコピーに関する不具合の修正。コピー後のセルの色がおかしなことになるケースがあって、調べていくうちに、色データがセルの書式というよりはブックに紐づけられた概念であることが発覚した。具体的には、ブックごとに数値→色という変換マップが存在して、セルの書式では変換前の数値で持っているらしい。

シートのコピーを実装したのは、日記によればもう5か月も前になるが、その時点でセルの書式がブックに紐づくものであることは知っていた。書式をブック間でコピーする関数があったのでこれを使えば全部解決と思っていたものの、実は色については数値の形式でコピーされていたようだ。コピー元とコピー先で先に述べた変換マップが異なるケースがあり、色がおかしなことになってしまっていた。正しくコピーするために色をRGB値から指定する方法を探し、見つかっていない状態で進捗報告の発表をしたのに、直後にググったら出てきたということ。

ブックをまたぐシートのコピーの難しさについて。
週記（2022/01/31-2022/02/06） - kotatsugameの日記

勉強会まで終えてから大学の課題に手を付けた。離散数学とハードウエア基礎は今期の講義が終了したようなので、あとはゲーム理論だけ。今日提出なのは第12回の課題で、これは教科書12章に対応している。課題となっているのは教科書の演習問題だが、本文でやったことを数値を変数に置き換えた状態でそのまま写すだけに見える。簡単。

すぐ終わったので、しばらくYouTubeに気を取られてから第13回の課題も終わらせることにした。教科書13章はエピローグみたいな位置付けなので何をやるのかと思ったら、なぜかまだ12章をやっていた。どうやら前後半に分けていたらしい。別に分量もそう多くないはずだが……。ともかく今度も演習問題で、こちらは図を描いたりと多少面倒だった。眠気に耐えつつ日付が変わったくらいで完成。

これで教科書を全部終えたのだから、多分今期の課題は終了だろう。本当は数理論理学特論という僕の指導教員の先生が担当されている講義も取っていたのだが、これは一度も出席できていないためほぼ放棄している。

ゲーム理論もハードウエア基礎も扱っている概念は初見だったものの課題は取り組みやすかった。なぜかというと、ある問題とその未知の解があったとき、解の存在証明ではなくそれを発見するためのアルゴリズムが講義で説明されていたからだと思う。詳しい理論まで理解が及ばずとも書いてある通りに手を動かせば解けてしまうのだから、楽しいかどうかはともかく楽だった。

ラノベの新刊チェックをして20冊ばかり注文した。1巻を買って、積んで、2巻を買い忘れていたラノベの3巻が発売されるようだったので、2巻とともに注文しておいた。自分が当時の新刊チェックで見落としたということが信じがたかったし、また「ある本を自分が買っていないこと」の判定は難しい。買ったラノベのリストはブログ記事にしているものの、ないことを判定しようとすると書き忘れが怖い。本棚をひっくり返しても見つからなくて、やっと買っていないことを納得した。

午前2時過ぎ就寝。

07/12(火)

午前8時起床。今日はゲーセンに行きたいのだが、まだ眠気があるため二度寝もしたい。とりあえず二度寝優先で、眠気を待ちつつラノベを開いた。

1冊読了。「同い年の妹と、二人一人旅」。旅ラノベということで風情があるなあと思って購入したものの、あまり風景描写に興味が持てなかった。そもそも旅に興味がないのかとも思ったが、例えば2chの旅スレまとめを読んだこともあるので、それを文章とイラストだけで表現するのが肌に合わなかったのだろうか。写真を見てなんぼという気持ちがある。

別のラノベを開いたりYouTubeを眺めたりしてから午後1時になってようやく二度寝。その後午後3時くらいに目覚ましをかけていたはずが起きられず、午後5時前にようやく目を覚ました。すぐ準備して家を出る。今日は夜遅くになると雨が降るらしいので、地下鉄を使った。

まず食事。つけ麺屋。連れだって訪れた客を並んで座らせるため、という店の都合で席を移動したところ、海苔をサービスしてもらった。

ヒルベルトの無限ラーメン屋は人が一人来るたびに無限人が席を移動するためサービスの海苔が無限枚必要らしいです
— こたつがめ (@kotatsugame_t) 2022年7月12日

いざゲーセン。今日は新曲だけ。14+が3曲通常開放されたので詰めて、SSS、AJを一つずつ出した。もう一つ、「Re：End of a Dream」はまだSS+。14+の全鳥が剥奪されてしまった。

脳天直撃 SSS
ラストのトリルの速さを分かっておらず無事SSS+割って涙 pic.twitter.com/ZkqhG7gO3b
— こたつがめ (@kotatsugame_t) 2022年7月12日

数回で出た。BPMが遅いので案外押せた。ラストのトリルがどれくらいの速さか分かっておらず、そこで確か0-2出したはず。もったいないのでSSS+を狙おうとしたものの、以降SSSすら出なくてびっくりした。どうやら数回で出たのは運がよかっただけらしい。

色彩過剰のダイアリーミュージック AJ pic.twitter.com/vTCvKsHKnD
— こたつがめ (@kotatsugame_t) 2022年7月12日

以下のツイートにある2枚目の画像（51、52小節目）は黄タップを無視し赤タップを両手で取るだけでよいということを聞いていたのに、配置を覚える前にそこ以外全部揃ってしまった。しかしAJが狙えるということが分かったため、頑張ってみた。

ここで全部出た pic.twitter.com/GNfbUaetj4
— こたつがめ (@kotatsugame_t) 2022年7月12日

実際に両手で取ろうとするとたまに抜けるので、TLで助けを求めたところ、左手小指をスライダーに固定しておくと抜けないと聞いた。どうやらトリルに合わせて小指がズレて、黄タップを擦っているのと同じ判定になるらしい。これで結構安定した。

プレイするうちに中盤がボロボロ崩れてきてもう大変。ついにラストの配置にも癖がつき始めた頃合いで出た。最高精度でラッキー。この時のラストは緊張もあってリズムが完全に頭から抜け落ち、本当にギリギリで押せていた感じだった。

午後11時前に離脱。予報通り雨が降っている、どころか土砂降りだった。急いで帰宅してシャワーを浴びたら、午後11時半からのCF #806 div.4にギリギリ間に合った。

Dashboard - Codeforces Round #806 (Div. 4) - Codeforces

Aは条件式を頑張って書いた。最初に大文字あるいは小文字に揃えた場合とどちらが速く書けたかは微妙なところに思える。Bはやるだけ。Cはサンプルを見て題意を把握した。Dは前半の文字列長を全探索。存在判定はsetの定数倍がちょっと怖かったのでソートしておいて二分探索した。Eは回転させて一致するマスを列挙し、0と1のどちらに揃えるか決める。すでに見たマスにフラグを立てておけばどこをスキップするか考えなくてよいし、中心だけ特別扱いする必要もない。Fは $a_i\lt i$ なる $i$ だけ集めたあと、それらの中で $i\lt a_j$ を満たす $(i,j)$ を数える。 $j$ ごとに二分探索した。

Gは30回badな鍵を使った段階で得られるコインがなくなってしまうため、それ以上の回数を同一視してよい。よってbadな鍵を使った回数を持つdpが可能。上限を20回にしていて1WA、気づいた後余裕を持って40回に増やしたところint型に対し最大で幅40の右シフトをすることになり、これは壊れてしまうらしくさらに1WA。特に2WA目は未定義動作っぽかったもののまさか本当にそこで落ちているとは信じられず、出し直してACするまでにかなり時間がかかった。

open hacking phase開始時点で25位。Gのせいで1ページ目から陥落した。残念。

今日は画面とマイク音声を記録していたので、コンテストの残り時間で編集して、終了後に投稿した。パソコンの前に座ったのがコンテスト開始ギリギリだったため、何とかマイクの設定まではできたもののページサイズを変えるのを忘れていてショック。そのうえG問題で詰まりまくってしまったためボツにすることも考えたのだが、無事全完はしているのだし、たまにはへなちょこなのもいいだろうと思って公開した。

#にじさんじアルプススタンド - Twitter Search / Twitter

少し日記を書いた後YouTubeを見ていた。

にじさんじ甲子園という大規模コラボイベントが現在進行中である。参加するVtuberがほかのVtuberをモデルにした野球選手をパワプロで作り、対戦するというものらしい。ここで、モデルにするVtuberを決めるのにドラフト会議という形式を取っている。パワプロには興味がないのだが、ドラフト会議で決定したチームを描くファンアートは非っ常～～～に良かった。すでに存在するコラボユニットが集まったり、これまでなかった組み合わせが生まれたり。ハッシュタグで検索してニヤニヤしている。

布団に入ってから、ハーメルンを読み返したり捜索掲示板を徘徊したりして眠いのに3時間ほど起きていた。午前6時を回って就寝。

07/13(水)

正午、エリアメールの爆音で目覚める。雨がヤバいらしい。

TCO22のR4にStage3とR3で2回進出を決めているのがほかのユーザにバレていた。TopCoderのDiscordに以下のような投稿があった。Stage3の結果はメールで通知されていなかったので、うっかりR3に出てしまうのはしょうがないはず。俺は悪くねえ！まあ、自分がR3開始前にR4に進出したことを知っていたのは日記やTwitterから読み取れてしまうのだが……。

バレてて草 pic.twitter.com/aO3j3b3JCG
— こたつがめ (@kotatsugame_t) 2022年7月13日

ハーメルンで新しい作品を読み始めた。ずっと読み続けていて、午後4時くらいにまた寝た。

午後9時半に再度起床。TLでTCO regionalのメールが届いた人を観測したため意気揚々とメールボックスを開いたものの、自分のところには来ていなかった。迷惑メールもチェックしたが、ない。TopCoderからのメールはいくつか受け取る設定になっているので、単純にお呼ばれしていないということのようだ。残念。もしかして上に書いたズルのせいか？

代わりにと言っては何だが、DDCCの本戦に進出できていた。ちなみに全完は40分弱だった。TLを見る感じこのタイムなら一般枠でも結構余裕だったらしい。

布団でずっとハーメルンを読んでいたが、さすがに明日のセミナーの準備をしないとまずいと思い、午前3時ごろにようやく身を起こした。

まずDDCC本戦に出場するためGoogleフォームを埋めた。会場に向かうためどの駅を使うか選択する項目があって、去年は参加記によれば大森海岸駅だったらしいが、調べると大森駅のほうが新幹線からの乗り換えが少ないようだ。今年はそちらにした。24卒ということで交通費が出るため、指定席に乗ることにして料金を計算。往復で2万3千円ちょっとだった。

シャワーを浴び、食事し、昨日投稿した動画のサムネイルを設定。open hacking phaseを終え、25位から変わらなかったようだ。良い順位ではないため今回は表記していない。

ほかにやることもなくなり逃げ場を失ったため、満を持して教科書を読み始める。午前5時だった。そこから準備を続け、午前10時半に就寝。

07/14(木)

午後2時半ごろ気合いで起床、すぐ出発。いつの間にか駐輪場の工事が始まっていて、原付を停める場所に少し苦労した。

セミナーの発表はいい感じ。ちょっとメモを見る回数が多かったかなと思うが、それ以外はスムーズに進んだ。準備の一部でHallの結婚定理を5通りの方法で示したのだが、これは時間がなくて一つだけ説明するに留まった。5通りも用意したのは教科書に書いてあったということ以上に発表時間が余らないようにするという目的だったので、そういう水増しをしなくてよかったのは良いこと。

二つの集合が一致するのを示す部分で両方向の包含関係を見たのだが、先生の指摘でもうちょっと簡単になることが発覚した。片方の証明が実は同値変形に書き換えられて、結論から仮定へも辿れたということ。この辺りはちょっと意識が行き届いていなかったなと感じる。手を動かしたら示せるので手を動かした、というだけでは発表として物足りない。ただこれも徹底するのは難しいポイントである。

終わってから黒板の写真を撮った。

pic.twitter.com/4XzGVEv7J6
— こたつがめ (@kotatsugame_t) 2022年7月14日

学食で食事して帰宅。降水確率40%でちょっとビクビクしていたが、何とか天気は崩れなかった。

帰宅してからは疲れ果ててPCの前から動けず、ずっとネットサーフィンしたり動画を見たりしていた。

Dashboard - Codeforces Round #807 (Div. 2) - Codeforces

日付が変わってから布団に入り、さらにしばらくスマホでYouTubeを見ていたようだ。午前1時半就寝。

07/15(金)

午前8時起床。ハーメルンを読み続け、正午就寝。次に午後3時起床。

即座にインターンのミーティング開始。以前タスクがないことをメンターの方に伝えておいたのだが、この度別の方の元に手が回らないタスクがあるということで、その方とのミーティングだった。ちょっとしたヒアリングと、大まかなタスクの内容について説明を受けた後、必要なコードを手元で動かす準備をした。新しくライブラリをちょっとばかり入れるだけで動いたのは楽でよかった。

しばらくYouTubeを見てから、ゲーム理論の課題をこなした。月曜日に今期の課題は終了だろうと自信満々に書いたのに、いつの間にか第14回の講義スライドと課題が出ていて目を剥いた。スライド冒頭を見ると教科書11章と書いてあって、なぜ戻っているのかと首を傾げていたが、内容としては教科書に書いてないことをやっているように見える。課題はちょっとした証明で、詳しいことまで理解せずともスライドと同じことを同じようにやればいいため簡単。面倒でもない。

午後7時半から午後10時まで布団に戻って寝ていた。シャワーを浴びて、午後10時半からCF #807 div.2。序盤はサイトが不安定で、B問題から軽量サイトのほうで提出していた。

Aはソートして $\forall i.\;h_i+x\le h_{i+n}$ を判定。Bは左端から動かしていくことで基本的に $\sum_{i=1}^{n-1}a_i$ 回の操作で達成できる。ただし途中に $a_i=0$ なる $i$ があったらそれぞれ1回操作して埋める必要があるので、その分増える。埋める時も端から移動させればそれ以上余計なコストはかからない。

Cは毎回操作を後ろから全部見ることで、求める文字の最初の文字列における位置を求める。このとき各操作ごとに文字列長を求めておく必要があるが、上限が制約にないのでオーバーフローに気を付けなければならない。と思っていたものの、最大でも $n\times 2^c\lt 2^{18}\times 2^{40}=2^{58}$ にしかならないので大丈夫だった。日記のこの部分を書いているときに気づいた。

Dはちょっと時間がかかってしまった。文字列の隣接XORを取ると $01\leftrightarrow 10$ という操作に言い換えられるので、あとは先頭から $1$ の位置を合わせていけばよい。

Eはかなり手間取った。セグ木の区間 $[l,r)$ を表すノードに $r-1$ の個数・ $r-1$ をもう一つ作るために必要な $l-1$ の個数・それ以上 $r-1$ を作るために必要な $l-1$ の個数（ $=2^{r-l}$ ）を持たせることで、ノードのマージが行える。あとはセグ木上の二分探索で答えが求まると思っていたのだが、 $r-1$ の個数がゼロか非ゼロかに単調性がないことに気づいた。追加で答えも持つようにするだけでよかったのに、ここで実装方針を大きく切り替えてしまった。

操作を可能な限り行った後にどの値が残っているかを持つことにした。区間をsetで管理することで効率的に扱える。しかしサンプルを合わせて提出するとREになってしまい、このデバッグに非常に時間がかかった。最終的に小さめのランダムケースでもすぐ再現することに気づいて、それを見ることで何とか直せた。バグの原因はif-else文で処理を切り替える際、条件判定の途中でイテレータを弄るため最初のif文だけ二重になっていて、内側のif文に入らないうえ外側のelse文も実行されない場合があるというものだった。

Fは乱択アルゴリズム。最初にランダムなTF列を用意してクエリを出力する際にXORすることにすれば、以降求める答えもランダムなTF列だと見なしてよい。まず全部Fの場合を聞いて、以降 $W$ 文字ずつ決めていくことにする。bitDPで計算したところ、 $W=4$ のとき平均2.625回のクエリで決定できることが分かった。この時 $n/W\times 2.625\le 1000/4\times 2.625=656.25\lt 675$ なので、ギリギリQLEしないはず。とりあえずプレテストは一発で通った。

DEで詰まったもののFを通して、システス後も全完のまま11位。Fはシステス中に手元で回していたら何十回に1回QLEしてしまうことが分かったが、何とか通ってくれた。実は $W=9$ とするとちょうど6回のクエリで必ず決定できるらしい。そこまで行くとさすがに全探索できない。 $W=4$ だと実行時にbitDPすることで答えを埋め込まずに済んだ。

その後午前10時まで必死に日記を書いていた。今週は月曜日から溜めてしまっていた。そういえばICPC国内予選の参加記も書いていない。何もかもハーメルンが面白すぎるのが悪い。

「黄金の経験値」が書籍化するらしい。

https://ncode.syosetu.com/n0806fu/

【朗報】
黄金の経験値さん、カドカワBOOKSより書籍化が決定した模様
— 原純 (@harajun1001) 2022年7月15日

布団に入って2時間ほどハーメルンを読み、1作読了。「二郎になりました…真君って何？」。

syosetu.org

Fateシリーズの二次創作で完結している。面白かった。主人公は半神半人で5000年近く生きている。良い。古代スタートということで、原作前は主人公が歴史に介入していく感じで自分の好みだった。原作スタート後は急にキャラが増えたりしてちょっと置いて行かれ気味だった。原作を知らないが故の苦労。

大体好みだっただけに、後半の主人公の行動が気になる。何物にも邪魔されないだけの圧倒的な力を持って好き勝手行動しているとされながら、結構ポンポンと人を助ける描写が入るのがあまり好みではなかった。自分の興味関心の向く先以外ではもうちょっと腰が重くなるような性格だと嬉しい、気がする。かと言って自分とその仲間のことだけ考え、周囲の迷惑を顧みないような主人公も気に入らないはず。自分の中の基準が一体どのあたりにあるのかよくわからなくなった。

正午ごろ就寝。

07/16(土)

午後3時半ごろ、生協の冷凍弁当を受け取った。直後からまた入眠することができ、最終的に午後8時に起床。シャワーを浴びたり食事したりして午後9時からARC144に出た。

AtCoder Regular Contest 144 - AtCoder

Aは題意を掴むのに少し時間がかかった。まず $x=\frac{10^N-1}9$ を考えることで $M=2N$ とわかる。このとき $x$ としては2倍したときに繰り上がりしない数であればなんでもよいはず。このあたりでサンプルを確認し、思った通りになっていたので実装、AC。Bは二分探索。最近のARCらしくないド典型だと感じて、見落としていることがあるのではないかとちょっと提出をためらった。

Cは思ったより難しかった。辞書順最小のことを忘れると、 $K+1,\dots,N,1,\dots,K$ という並べ方が一番素直。これでダメならダメだろう。このとき $1$ の位置を見て $(N-K+1)-1=N-K\ge K$ である必要がある。つまり $2K\ge N$ 。さて、 $K=1$ の場合は $2,1,4,3,\dots$ のような形になる。ここから類推すると、最初に数列 $1,\dots,N$ を用意したあと $\frac{N-2K}{2K}$ 回、前から $2K$ 要素を切り出して前半と後半を入れ替えるのが最適になるはずだ。

最後に残った $2K$ 個以上 $4K$ 個未満の要素については、一番初めに作った $K+1,\dots,N,1,\dots,K$ のような並びにしかなれないと思った。これを作って提出したところ、WA。慌てて全探索のプログラムを書き出力を比較してみたところ、 $(N,K)=(7,2)$ で間違っていることが分かった。 $3,4,1,6,7,2,5$ が答えのところ、 $3,4,5,6,7,1,2$ を出力してしまっている。

$1,2,3,4,5,6,7\rightarrow 3,4,1,2,5,6,7\rightarrow 3,4,1,6,7,2,5$ という変換がされていると考えられる。つまり、 $2K$ 要素を切り出すのを $\frac{N}{2K}$ 回行ったあと後ろ $2K$ 個の前半後半をswap。ただしこれも常に行うというわけにはいかなかったので、前から切り出し終わった残りの個数を見て $0$ 個ならそのまま、 $1$ 個以上 $K$ 個未満なら少し巻き戻して最初に提出したのと同じものを作り、 $K$ 個以上のときだけ満を持してswapした。小さいケースを念入りに試してから提出し、無事AC。

Dは難しい。まず、 $f(0)$ と各 $f(2^i)$ を独立に決めたとき、任意の数 $x=\sum_{i\in I}2^i$ （二進法で書いた形）について $f(x)=\sum_{i\in I}f(2^i)-(\#I-1)f(0)$ が成り立ち、かつ問題文にある二つ目の条件が満たされることが分かった。あとは一つ目の条件。常に $f(0)=0$ なら簡単なのになあと思ったが、全然そんなことはない。

$f(x)$ の最大値と最小値を考えたい。ここで、各 $f(2^i)$ を $f(0)$ と比較してみる。 $R=\{0\le i\lt N\mid f(2^i)\gt f(0)\}$ 、 $L=\{0\le i\lt N\mid f(2^i)\lt f(0)\}$ とおいたとき、 $f(x)=\sum_{i\in I}f(2^i)-(\#I-1)f(0)=\sum_{i\in I}(f(2^i)-f(0))+f(0)$ であることから、 $\max f=\sum_{i\in R}(f(2^i)-f(0))+f(0)\le K$ かつ $\min f=\sum_{i\in L}(f(2^i)-f(0))+f(0)\ge 0$ となることがわかる。

簡単のため、 $a_i=f(2^i)-f(0)$ とおこう。元の問題は $f(0)$ と各 $a_i$ を $S_R=\sum_{i\in R}a_i\le K-f(0)$ かつ $S_L=\sum_{i\in L}a_i\ge-f(0)$ を満たすように決めるものと書き直された。

$0\le f(0)\le K$ は全探索できないため、しなくてもよい方法を考える。 $S_L\ge-f(0)\Leftrightarrow-S_L\le f(0)$ と $S_R\le K-f(0)$ を辺々足すことで $S=S_R-S_L\le K$ が得られる。ここで実は $S=\sum_{i=0}^N|a_i|$ となっている。またこのとき $0\le-S_L\le f(0)\le K-S_R\le K$ を満たす $f(0)$ は $K-S+1$ 通りある。これで $f(0)$ を決め打たなくてよい上、 $S_L$ と $S_R$ の区別には興味がなかったことが判明し、 $|a_i|$ とその符号を決める問題に帰着された。

符号を考える前にまず $a_i=0$ の場合を取り除く必要がある。 $a_i\ne 0$ なる $i$ が $0\le n\le N$ 個あったとする。 $a_i=0$ なる $i$ の決め方は $\binom N{N-n}=\binom N n$ 通りであり、それ以外のものについて符号の決め方は $2^n$ 通りある。次に、各 $n\le S\le K$ に対し、 $n$ 個の正整数の列であって和が $S$ となるようなものの場合の数を求める。これは写像12相の一つとなっており、 $n=0$ の場合を取り除けば求める数は $\binom{S-1}{n-1}$ である。さらに $f(0)$ の決め方 $K-S+1$ も掛け合わせる。

まとめて、 $n=0$ の場合を足し、 $K+1+\sum_{n=1}^N2^n\binom N n\sum_{S=n}^K\binom{S-1}{n-1}(K-S+1)$ が答えになると分かった。内側の $\sum$ をWolfram|Alphaに投げると無事閉じた式になったため実装し、AC。 $K$ が大きいのでcombinationは $n$ を増やすごとに比を考えて少しずつ更新していく形にした。コードはかなり短くなった。

Eは解けず。始点と終点が同じで途中に $A_i=-1$ なる頂点 $i$ を通らないような経路をいろいろ求め、それらの差を取って $\gcd$ を計算しまくり、最後に適当な $1\rightarrow N$ の経路とも $\gcd$ を取れば答えになると考えたものの、高速に計算できているわけでもないし答えも全然合っていない。結局4完39位だった。

Dの解法を一所懸命に説明したのに、公式解説とだいたい同じになってしまった。どうやら数え上げ方はほぼ一本道らしい。コンテスト中はその道を探していろんなところを行ったり来たりしたものの、こうやってある程度整理して説明しようとすると自然と収束していく。

コードゴルフ。Aはdc。Dはコンテスト中に求めた式をRubyで求める、コードをVimで作った。Bはシンプルな二分探索のコードがRubyで提出されており、縮みそうにない。他は手付かず。

午後11時半からCF #808 div.1に出た。

Dashboard - Codeforces Round #808 (Div. 1) - Codeforces

Aからちょっと難しかった。コンテスト $1\dots n-1$ のどこかでIQが $0$ になるなら、代わりにコンテスト $n$ で $0$ になるとしても損しない。こうするとコンテスト $n$ 開始時点でIQが少なくとも $1$ である必要があって、特に $2\rightarrow 1$ となる瞬間があったならそれもできるだけ最後に近いコンテストであるとして問題ない。そうやって後ろから見つつ、今見ているコンテストが始まる時点での必要IQを（ $q$ を超えないように）管理すればよい。

Bは謎。1回操作すると $\sum a$ が元の数列における $a_n-a_1$ になると分かった。それらをソートしてランレングス圧縮すると要素数は $O(\sqrt{a_n-a_1})$ 。こうなると同様にして残り $n-2$ 回愚直に操作してもよさそうに見える。これ以降の要素数はうまく見積もれなかったものの、とりあえず常に $O(\sqrt{\max a-\min a})\subset O(\sqrt{a_n-a_1})$ であり、また $\max a-\min a$ が減らなくなったら $a$ はほとんど $0$ になっていることもわかる。 $a_n$ に制約がついているのも使えているため、ある程度自信を持って提出できた。

Cは最小全域木を取って $1\dots n$ のそれぞれを根としたとき、最小全域木に含まれなかった辺であって端点が先祖・子孫の関係にないものがある場合のみアウト。これを判定するため、含まれなかった辺 $(u,v)$ について、その辺のせいでアウトになってしまう頂点にマークすることを考えた。 $uv$ パス上の頂点のみがそうだと思ったものの、サンプル2が合わない。 $uv$ パス上の頂点から別の方向に向かって出ている辺の先の部分木もマークしなければならないことに気づいた。

これは難しいので、逆にアウトにならない頂点にマークした。 $u$ から見て $v$ の方向以外にある頂点と、その $u$ と $v$ を逆にしたもの。木上のimos法で計算することにすれば、基本的には頂点 $u$ と $v$ に $+1$ するだけでよい。 $u$ が $v$ の先祖（あるいはその逆）の場合だけちょっと面倒で、 $u$ から $v$ に向かって1歩進んだ頂点が必要になる。LCAをダブリングで計算するのと同様に求められるため、OK。

Dは解けず。2乗の木dpに見えるもののマージが書けない。左の部分木から頂点が消えるのと同時に右の部分木から頂点が消える場合を処理するのが非常に難しい。とりあえず計算量を考えずに書いてサンプルは合ったものの、そのままでは高速化できない。 $S_1=S_2$ を許して解いてから除原理っぽく計算すればいけそうだと思ったが、具体的な計算方法がわからずコンテスト終了。

システスは全部通って3完39位、レートは2964→2959(-5)。Cまでがそこそこ速かったので助かった、か？ARCと同じ順位だったのは面白い。

午前9時まで日記を書いていた。ちゃんと月～土の部分の校閲まで終わらせることができたので、日曜日に必死になって2万文字読み返す必要はない。2万文字と書いたが、果たして今週の週記はそれだけ肥大化するだろうか？いまここを書いている時点でおよそ1万5千文字であるが、明日はOpenCup＋ABC＋Lunchtimeと盛りだくさんなので1日で5千文字くらいは増えそうな見込み。

明日のコンテスト開始まで、直前の準備を考えても7時間ちょっとの睡眠時間がある。案外余裕だなと思って布団に入ってから新しくなろうを読み始めた。これが面白くてなかなか止まらず、就寝が午後1時半になってしまった。愚か者め。

07/17(日)

コンテスト開始時刻である午後5時の直前まで起きられなかった。当たり前。

なんで布団に入ってからの7時間を4時間なろう3時間睡眠と振り分けてしまったのかがわからない。本当に助けてくれ
— こたつがめ (@kotatsugame_t) 2022年7月17日

すでにフラフラの状態でまずは1戦目、久しぶりのOpenCup。今日はGrand Prix of Seoul。チームでMADHGFJCEKをこの順に解いた。僕はADCの考察・実装とEの実装をした。

Aはbitで状態を持ってBFS。Dは平面に縦横合わせて3本の直線を引き、乗っている点の重みの和を最大化する問題で、座標軸を入れ替えることを考えれば縦3本と縦2本・横1本の場合が解ければよい。このうち前者は自明。後者は横の直線を全探索して、それに乗る点を逐一取り除きつつ上位2要素を持つセグ木で縦線を決める。縦横がちょっとややこしかったが、何とか書き切ってみるとそのまま通った。

Cは平面上の点をクラスタリングするアルゴリズムに関する問題。まず中心を2点決めて、各点を近いほうの中心に対応する集合に入れ、次に各集合におけるX座標・Y座標の中央値を求めて新しい中心にする、ということを繰り返す。最初に決めた2点に応じて何ステップでどんな中心の組に収束するか求めよというもの。実は単純なメモ化再帰でよい。なぜなら、このような分け方は点たちをある直線で分割した形になり、そのような分割のされ方は $O(N^2)$ 通りしかないから。この事実は今年3月のCook-Offで見た。

遷移の種類は高々N2N2個らしい。
週記（2022/02/28-2022/03/06） - kotatsugameの日記

内部で分割し新しい中心を求めるのはnth_elementを使えば $O(N)$ で書けて、合わせて $O(N^3)$ 。TLEしてひっくり返ったもののオーバーフローを見つけて、無事2回目の提出でAC。

Eは面白かった。じゃんけんの手の列があって、勝ち負けを比較関数だと思ってバブルソートする問題。より正確に書けば、1回の操作では隣接する要素を先頭から順に見て、それぞれ前の手が後ろの手に勝つならswapする。この操作を $T$ 回繰り返した後の列を出力する。

最初に1回シミュレートするのがかなり上手い考察方針で、列が分割できることに気付けた。例えば先頭がグー（R）だったとき、グーが追い抜ける手であるチョキ（S）とRSRRRSSRのように交互に出現する部分をその後ろ（パー）から切り離すことができる。

このような列に対して $T$ 回操作した後の状態を考えるのは、ランレングス圧縮して考えると見通しが良い。例えば上の列は $[1,1,3,2,1]$ に変換されて、これに操作を繰り返すと $[1,1,3,2,1]\rightarrow[0,1,3,2,2]\rightarrow[0,1,2,2,3]\rightarrow\dots$ のようになる。かなり綺麗にまとまって、実装は一瞬で完成した。

午後9時前にフェードアウトして食事し、ABC260に出た。

AtCoder Beginner Contest 260 - AtCoder

Aはうまい書き方が思いつかず、結局種類ごとの文字数をカウントして解いた。この問題を含め、今日は全部C++だった。Bは面倒なだけ。Cは $(r,b)\rightarrow(r,b+Xr)\rightarrow(r+b+Xr,(b+Xr)Y)$ という変換を繰り返す。それぞれレベルが $(n,n)$ 、 $(n-1,n)$ 、 $(n-1,n-1)$ に対応している。何か閉じた形で表せるのかと少し考えてみたが、少なくともきれいにはならなかった。

Dは場に見えているカードをsetで管理。それぞれの山はvecterで管理して、カードからvectorが取得できるようにインデックスを記録して……と考えていたが、そういうテクいことをしなくても直下のカードだけ記録しておけばよい。

Eはよい数列の右端 $r$ を全探索し、左端としてありうる最も右の位置を計算。組 $(A_i,B_i)$ に対して $L_i$ を $r\lt A_i$ なら $0$ 、 $A_i\le r\lt B_i$ なら $A_i$ 、 $B_i\le r$ なら $B_i$ と定めたとき、求める位置は $\min_i L_i$ になるので、 $L_i$ をsetで管理しつつ差分更新した。

Fはよく見ると $T$ が小さいので鳩ノ巣原理。このタイプの鳩ノ巣原理は何度も見ている。メモをmapで行ったら $O(T^2)$ 回のアクセスでTLEしてしまい、vectorに十分多く要素を詰め、ソートして重複を探したら通った。後から気づいたが普通に2次元配列でよかった。Gは縦横無尽にimos法を行って全マスに対する答えを求めておく。 $N\times(N+2M)$ の配列が必要になってかなり怖かった。

Exには手も足も出ず。FPSをこねくり回すのだろうなと思っただけ。どうやらみんな解けなかったようで全完は一人しかおらず、Gを通した時点で2位だったのがそのまま保存されて7完3位だった。

少しコードゴルフして午後11時半からCodeChef、July Lunchtime 2022 div.1。もう体力ゼロなのにここから3時間と聞いてそこそこ絶望した。

https://www.codechef.com/LTIME110A

LARGEFAMは簡単。子が少ない人を優先的に使っていけばよい。

STRINGXORはちょっと難しかった。まず $A$ に $1$ がない場合を取り除いておく。 $1$ があるならそれを使って操作を繰り返すことで全部 $1$ にできるので、そこから $B$ を作ることを考えてみる。 $111\rightarrow 110,011$ であるが $111\not\rightarrow 010$ であるということから、 $0$ を作るときはどこかの $11$ に押し付けるようにしなければならないことがわかった。

$B$ に $11$ があればそこに押し付けて変換可能。ない場合も、 $11\rightarrow 00$ を考えると $B$ における $00$ を $11$ だと思ってよいことになるため、 $00$ が代用できる。逆に $00$ も $11$ もないとき、そもそも $B$ は操作を1回以上行った後の列ではない。よってこのときも $A$ に $1$ がない場合と同様、初期状態で $A=B$ か判定すればよい。

BINHAPPは少し手間取った。まず、文字列のbeautyとは $1$ の個数から $0$ の個数を引いたもの（と $0$ の大きいほう）である。実際、分割後の列はそれぞれこの値が正になっているため足すとbeauty以上になり、一方beautyがちょうど $1$ であるような部分文字列を先頭から切り出し続けることで一致させることができる。happinessは連続部分列におけるこの値の最大で、全体・左端・右端・内側の組がモノイドになるためセグ木に乗り、文字列の連結操作が入っても解ける。

しかしここで連結する順番をバラバラにしてよいのに悩まされた。最初はモノイドのop(l,r)を計算するときにop(r,l)も計算して最大値を採用すればよいかと思ったが、これでは自由度が足りないようだ。つまるところ、区間から「左端」だけ使うもの一つ・「右端」だけ使うもの一つ・「全体」を使うものいくつかを選んで足し合わせていると見なせて、すでに左右が埋まった「内側」に新しく「全体」を足す場合なども存在すると気づいた。ただし、一つの文字列だけで完結してしまう「内側」に「全体」を足すことはできない。なので「内側」を2種類持つことにして、何とか3回目の提出でAC。

TREERETは謎。2点 $u,v$ を選んでもう1点と合わせて聞くことで、その点が $uv$ パス上の点か、 $uv$ パスの内側から生えた部分木の点か、 $u$ から見た $v$ の子か、 $v$ から見た $u$ の子かの4状態に分けられる。パス上の点は二分探索で整列させることができる。そこから生えた部分木の点はどこから生えているのかを二分探索できる。よっていくつかの部分木に分割できたので、それぞれで再帰的に解いた。これを提出したらもともとの制約の場合のみQLEして56点だった。

手元の二分木で試すと2000回ほどオーバーしているらしい。やはり3頂点しか聞かないというのは無駄が多そう。少しいじっているうちに別方針を思いついたので、そちらを実装することにした。クエリの答えが $\sum_{s\in S}s$ になるような集合 $S$ を管理する。ある頂点を追加してもしこの条件が満たされなかったら、その頂点は $S$ の頂点たちを結ぶ木の内部の点であるか、もしくはある $s\in S$ の部分木となる。このような $s$ もクエリの答えから特定できる。

こうやって各 $s\in S$ の部分木と $S$ の内側の木に分けられたので、それぞれで再帰する。ただし、内側の頂点が一つしかない場合は、その頂点と $S$ の頂点をそれぞれ結んでよいとわかるため先に処理しておく。実装して同様に二分木で試したところ、最初は先ほどと同様クエリ回数が2000回ほどオーバーしていたものの、頂点をシャッフルすると一気に5000回まで減ったため、提出。満点となった。

あとは部分点のみ。INVRETの部分点1は $i\lt F_i$ なら $2F_i$ を、 $F_i\lt i$ なら $-2F_i$ を答えに足し、最後に $i\ne F_i$ なる $i$ が存在したなら答えをデクリメントする。その時点での答えが $0$ より大かを判定したほうが操作回数は少なかったか。部分点2は全探索で、合計29点。TREEQUERの部分点1は愚直。以上で439点を確保した。

残り時間はより得意そうだったINVRETに注力した。思っていることが書けたと思ったのにバグっていて、チェッカーを書いていないため提出しまくることになってしまい、しかも結局通らなかった。点数は変わらず、最終的に5位で終了。

コンテスト終了後にチェッカーを書いてデバッグしたところ、無事バグが取れた。提出すると85点だった。まあ追加で50分くらいかかっているのでどうしようもなさそう。コンテスト3時間は長いなと思っていたのだが、終わってみると実は全然足りなかったことが分かった。

方針はマージソートで、ソート済の列を最後にまとめてcomposeすることでメモリ上の位置を連続させておくのがよい。さらにその後ろに番兵を設置することで、固定回数のループを回せばマージができるようになる。左右の列の先頭インデックスが $F_l$ と $F_r$ にあるとき $F_{F_l}$ と $F_{F_r}$ を比較し、列 $F$ に $F_l+(F_{F_l}\lt F_{F_r})$ と $F_r+(F_{F_r}\lt F_{F_l})$ を追加して、そのインデックスを新しい $l,r$ にする。

今見たように、操作列を生成するコードでは「ポインタのポインタ」みたいなものを扱うことになり、頭を壊してしまった。バグもこれに関係するもので、ただ1か所「ポインタ」でよいところを「ポインタのポインタ」を扱ってしまっていた。無念。最近DMOJでも制限された操作でプログラムする問題があって、そちらもただ一つのバグのせいでギリギリ満点を逃してしまったことを覚えている。人生そういうのばっかり。認知バイアス。

5位なのでレートは上がった。2697→2765(+68)で、ついに2月に記録した最高値を2だけ更新した。しかし現在CodeChefはレートシステムの転換期らしいので、単にそのおかげにも見える。

ABCのコードゴルフについて。Aの前にそれ以降の話をする。BはRubyのmax_byと集合の引き算で頑張る。Cはdcでループを回して計算。先ほども述べたように、閉じた形にできたとしても短くはならなそう。Dより先は手付かず。

Aはコンテスト中にVimで24Bを達成しホクホクしていたのに、2Bも縮められていた。何もかもが絶妙な噛み合い方をしていて天才的で、逆立ちしても書けないと思う。-1を書く代わりに0を書いて後からデクリメントするというのが大本のアイディアに見える。削除しつつレジスタに入れるのがddからxに縮むうえ、その操作後のカーソルは右に一つ進んでおり、このためlコマンドがいらなくなる。以上が-2Bであった。

https://codeforces.com/contest/1696/problem/G

明日は午後1時からMulti-Universities Campというコンテストがあるため、睡眠時間を確保しようと日記を書かずに布団に滑りこんだ。しかしそこからなろうを2時間ばかり読んでしまった。馬鹿野郎。午前8時前に就寝。

ちなみに今週の週記の文字数だが、書き上げてみると2万文字を余裕で突破した。日曜日はおよそ6千文字だったらしい。

2022-07-11

週記（2022/07/04-2022/07/10）

07/04(月)

午後0時半の目覚ましで意識を取り戻し、眠気と戦って午後1時少し前に布団から脱出。

直後からミーティング。寝ぼけて開口一番の挨拶を「お疲れ様です」ではなく「おはようございます」にしてしまったが、笑って流していただいた。その後は普通に進んでいった。今日はメンターの方ともう一人とのミーティングで、そのもう一人の方が先に退出されてからも最近ご無沙汰していた1on1っぽく追加でいくらか話していた。あまりやることがないのでタスクをくださいということを伝えた。これまでやっていたことが一旦落ち着いており、しかもそこから大きな進展が見込める状態にはまだない。これは僕の問題ではない。午後2時半に終了。

ABC256の総合10位、学生5位の賞金でアマギフが一万円×2届いていた。ここ最近のABCでは結構Exが解けており賞金付きの回も多いため、かなり稼がせてもらっている。ついにギフト券残高が30万を突破した。もともとほとんどネットショッピングをしないため増える一方。

購買に行こうとしたが雨が降っていたため取りやめ、冷凍弁当を食べてからゲーム理論の課題に手を付けた。今週の課題は普段と比べ少し計算量が多かったように感じ、大変だった。先週以下のようなことを書いたが、今週はゲームの一部始終を考察するため、まさに表を埋めるような勢いだった。ゲームの種類が違うため一概には言えないのだが。

今週の課題も簡単で、定義に従って計算するだけ。ただ戦略形ゲームの表を埋めようとしたらこの計算をあと15回繰り返さなければならないので、ちょうどよい難易度の問題がなかったのかなと思ったりした。
週記（2022/06/27-2022/07/03） - kotatsugameの日記

午後4時半からインターン先定例会。今週発表する成果は昼のミーティングと、あとは先週の定例会後に少しだけ考察したのを思い出してそれを入れておいた。細かく書いたらそれなりの分量になってくれて安堵。

勉強会は双対について。いわゆる高度典型だと認識していて、いつか勉強しなければと思いつつずっとスルーしてきた話題。ところがつい最近CGR21-Gで出題されて、ついに自分の手が届く、あるいは届かせなければならないところに出てきた矢先だったため、大変タイムリーな発表だった。内容は軽め。最後に牛ゲーの双対を取って確かに最短路問題になっていることを確認したが、不等式だけ見ればすぐわかるのに双対を取った後だと式の解釈を結構頑張る必要があってかなり大変。その分、最後に綺麗にまとまったのは面白かった。

終わってから先週の週記を完成させにかかる。先週末はコンテストが少なかったため夜中のCFの前に校閲まで終えられるだろうと予想していたのだが、結局土日分に目を通す時間はなかった。いったん投稿し、午後11時半からCF #804 div.2に出た。

Dashboard - Codeforces Round #804 (Div. 2) - Codeforces

Aはまず偶数なら $n/2,n/2,0$ でよい。もしかして奇数ならできないのでは？と思い $(a\oplus b)+(b\oplus c)+(a\oplus c)$ の最下位ビットを確かめてみると、確かに常に $0$ になっていることが分かった。Bは、サンプル1の出力例がかなりそれっぽい構成をしているな……と思いつつ左上から埋めてみると、サンプル1を素直に拡張した模様が表れて拍子抜け。 $n,m$ は偶数なので、これでよいと分かった。

Cは解法はすぐなのに合わせるのになぜか時間がかかった。まず $0$ の位置が決定する。次に $1$ の位置も決定して、同時に $a$ において $0$ と $1$ の間にある $2,3,\dots$ が $b$ でも $0$ と $1$ の間になければならないと決まる。以降同様に、現在見ている区間に入っていない最も小さい数を含むように区間を伸ばして、その時新たに含まれるようになった連続する数たちを区間内のどこかに配置することを繰り返せばよい。

Dは難しかった。まず、ある区間を操作で完全に消せる条件は「長さが偶数かつ最頻値が全体の半分以下」である。証明は帰納法で簡単。 $O(n^2)$ かけることで消せる区間が全列挙できるので、これを使って、残す数を決め打った時最大何個残せるかでdpしたくなる。これは $O(n^3)$ なので間に合わない。残す数が必ず全体の最頻値であると思いそうになるが、サンプルで落ちる。

ここで、すべての数に対して先のdpを同時に計算することを考える。こんなことがなぜ可能かというと、 $a_i$ を見ているとき、これを残す場合は $a_i$ に関係する部分のみ更新すればよいし、ここからスタートする区間を消す場合は直前の要素を残していると考えてよいため、 $a_{i-1}$ （ただし $i=1$ のときは全部）に関係する部分のみ更新すればよいからである。隣接する区間をそれぞれ消せるなら、それらをまとめて消すこともできるのだ。よって $O(n^2)$ 状態のdpでありつつ遷移も合計 $O(n^2)$ になり、間に合う。

Eは解けず。素因数分解したものをmultisetに入れて、先頭から2個ずつ積にしてまたmultisetに戻すことを繰り返せば、分解後としてありうる最小値と最大値の組が全列挙できると思っており、WA。その後これではいけないことに感づき、代わりにそういうものを全部前計算するようにしたところ、MLEした。

ここでコンテスト終了。4完で74位と久しぶりに見るひどい順位を取ってしまった。普通にDすら遅かったのは反省。

とりあえず先週の週記の校閲を済ませ、更新。その後Eを解説を読んでupsolveした。MLEしてしまった前計算だが、各数についてその約数を全探索し、それらで割った数から今見ている数へ遷移してくるようなdpを考えるのは正しかったようだ。ただ、何個に分解したときどうなるかという的外れなことを考えていたので先に進めなかった。

最小値を決め打つことにして $L+1$ から $L$ に緩めたとき、分解後の最大値としてありうる最小値が変化しうるのは $L$ の倍数だけ、というのは結構びっくりした。コンテスト中はそもそも最小値（あるいは最大値）を最初に決め打つことを全然考えなかったため、その先の考察に衝撃を受けるのもやむなし。 $L$ を含むような形に分解しないほうが良いこともあるというのに気づかず、つまり遷移してきたdpの値をminも取らずに直接代入してしまって、2回ほどWAを出した。

少しコードゴルフしてから午前4時半に布団に。ネット小説の更新を確認していたら寝落ちした。午前5時半ごろだった。

07/05(火)

午後5時起床。もっと寝ようかどうしようか迷いながらYouTubeを見ていた。午後6時半に布団から脱出。今日も天気が悪いようなので、学食には行かないことにした。

面白いコードゴルフの更新が流れてきた。素直に感動。以前の最短コードではa b cという文字列をVimで編集してa*_1**5+_1*b>-cにしていた。ところがこの問題、制約に $-10^9\le c\le 10^9$ とあるものの、実は $f(1)=a+b+c\lt 0$ より $c\lt -(a+b)\lt 0$ であり、従ってa*_1**5+_1*b c>0という文字列を作ればcの負号が二項演算子として解釈されて上の式と同等になる。アハ体験。

課題に取り組む。まず離散数学。第11回目のこれが最後の課題になるらしい。課題は各回 $5$ 点満点で評価されており、その和を $a$ 、期末レポートの点数を $b$ としたとき、この講義の成績は $\min(a+\max(a,b),100)$ で定められる。これまで10回の課題を終え、初回提出期限に間に合わず $-2$ 点された以外は満点を保ってきたので、今のところ $a=48$ を確保している。ということで今回 $2$ 点確保すれば期末レポートを前にゴールインできる、が、ギリギリを攻める趣味もないためちゃんと全部解こう。

……と思ったら、最終問題がかなり難しかった。 $\mathbb{Z}_{\gt 0}\times\mathbb{Z}_{\gt 0}$ が加算集合であることを（全単射を構成して）示せという問題。縦横に並べて斜めに辿るものが有名だが、ヒントに $h:\mathbb{Z}_{\gt 0}\times\mathbb{Z}_{\gt 0}\rightarrow\mathbb{Z}_{\gt 0};(m,n)\mapsto 2^{f(m)}g(n)$ という形で構成してみよと書いてあってたまげた。

しばらく考えて、ようやく素因数分解した後の素数を一つずつずらすような写像のことを言っていると気づいた。 $(9,2^3\times 3^2\times 7^1)\mapsto 2^{9-1}\times 3^3\times 5^2\times 11^1$ のような感じ。これを頑張って記述する。言葉で言うだけなら簡単だが書くのはかなり面倒だった。そもそもこういうことをするためにはまず素数を一つずつ全て並べた無限長の列が必要。まあそれはいいのか？一応そのような列の存在も具体的に構成することで示しておいた。

07/21追記：もっと簡単なものがあったらしい。賢しらに無限長の列云々など言い出してしまって恥ずかしい。

解答はg(n)=2n−1g(n)=2n−1だった。目から鱗。特に自分の作ったggがただ複雑なだけのZ>0→Z>0∖2Z>0Z>0→Z>0∖2Z>0であるということは、冷静になると当たり前なのだが、見た目からはすぐにはわからないと感じている。
週記（2022/07/11-2022/07/17） - kotatsugameの日記

主に最終問題のせいで3時間ほどかかった。何とか提出し、次にハードウエア基礎。組み合わせ回路が与えられるので、すべての信号線について単一縮退故障を検出できるような必要最小限の入力パターンを求めよという問題だった。講義スライドでは1本の信号線に対してそこの故障を検出できる入力パターンを列挙していたので、これを11本すべてに対して行うことにした。非常に面倒だった。そもそも入力パターンが2³通りしかないのだから、そちらから攻める方法もありそうなものだが、知らないのでしょうがない。

そのようにして列挙した入力パターンの集合が、11本の信号線それぞれ、0縮退故障と1縮退故障で都合22個ある。2³通りの入力パターンの部分集合であってそれらのどの集合とも共通部分が空にならないようなもののうち、サイズが最小のものを求めよという問題になった。えっ！手で最小頂点被覆問題を！？と思ったが、冷静に確認するとサイズ1の集合がいくつかあったためそれらをまず選び、残りは1パターンでカバーできたので、難しくはなかった。日付が変わる前くらいに提出。

疲れ果ててしばらくTLを眺めてからシャワーを浴び、インターンのコーディングを少し行った。以前書いたコードで、ほぼ等価なものがライブラリで用意されている部分があったので、それに置き換えることで高速化を図ろうとした。しかし実は他の部分の実行時間が支配的すぎたらしく、計測しても全然違いが出なかった。まあコードがシンプルになったのは確かだし、と言い訳してプルリクを作った。

ラノベを読み始めた。途中結構な時間をYouTubeに吸い取られ、午前11時前に1冊読了。「最強魔法師の隠遁計画」15巻。面白かった。帯にこの巻で今進行している話が一段落すると書いてあったので、前半の苦しいシーンもすぐ後で全部解決されると思えば耐えられた。ラノベ読者にはストレス展開に弱い人も多いということをよく知っていらっしゃる。主人公不在の学園が襲撃されるというのは個人的にかなり辛い展開。そもそも主人公が知らないところで状況が悪いほうに傾いていくのが苦手で、特に今回は位置的にも離れており、十中八九主人公は間に合わないんだという絶望感を得つつ読んでいた。そしてヒロインたちがかなり手ひどく痛めつけられる。そういう苦しさがあってこそ終盤の逆襲が輝くわけで、読み終わってみればバトルシーンと学園シーンがいい感じにミックスされた満足のいく巻だった。

学食に行って昼食を摂り、菓子パンを買って帰宅。1時間半ほど日記を書いてから布団に入り、なろうの更新を一つ読んで午後2時前に就寝。

07/06(水)

午後10時半起床。寝る前に買ってきた菓子パンを食べた。写真を投稿したところ、以下のような指摘があった。

これって6本じゃなかった？ https://t.co/NJTu46VM1Q
— しぶやん (@mathematicswim) 2022年7月6日

確かに先週買ったものは6本だった。値段が変わっていないので何も気づかなかった。パッケージをゴミ箱から探し出して確認したところ、6本入りの時は1本あたり86kcalだったのが5本入りでは101kcalになっていたので、1本ごとは大きくなっていたらしい。まあ、さすがに1本分まるまる減量という豪快なことはできないのだろう。

食事 pic.twitter.com/8NHknUrOou
— こたつがめ (@kotatsugame_t) 2022年7月2日

布団でハーメルンを読み始め、午前2時過ぎに1作読了。「遊戯王の世界で遊戯王プレイヤーたちが遊びだしたようです。」。主人公だと思っていた人が早々に管理人と名乗って出番を減らし、以降いろんなキャラがわちゃわちゃし出した。別にフィクサーっぽいムーブをしているわけではないものの、そういう設定も面白いなと思う。

syosetu.org

切り抜きを見た。おどおどしている名取さなさん可愛いね……。ところでこういう話題、見ている側は面白いけれど同時に結構ギリギリのラインで綱渡りしているような感覚も得てしまう。正直怖い。

2022/Teams/List - ICPC OB/OG の会

明日のセミナーは僕は発表しない予定なので、こうやって前日深夜にも拘わらずのんびりしている。とはいえ少しばかり教科書を読み進めておくか、ということでスマホでPDFファイルを開いた。しばらく読んでいたら眠気が来たので逆らわず就寝。おそらく午前4時半ごろだった。

07/07(木)

午前8時半に目を覚ます。あんまり寝た気がしないので二度寝したい。また教科書を読んで眠気を待つことにした。ちょっと気になることが生じたため目をつぶって細かく考えてもいたが、これでも眠れなかった。

ちなみに気になることとは、DiestelのTheorem 2.1.4、任意に定められた全順序たちに対して○○が存在するという命題は半順序ではダメなのかという疑問。半順序でもwell-definedになるように少し定義を変え、改めて証明を一つ一つ確認していたのだが、冷静になると適当に拡張して全順序にすることができるため一瞬で言えてしまった。制約を弱めているのだから当然だった。

正午に布団から出た。チームメンバー・コーチの了承を得てICPCのチーム情報をJAGのページに書き込んだ。Twitterアカウントのリンクの貼り方をミスってしまい絶望したが、リプライで修正方法を教えてもらい一命を取り留めた。

左上の編集ってとこから編集できます
— ⚡すく⚡ (@0214sh7) 2022年7月7日

シャワーを浴びてから少し日記を書き、午後2時半に出発。購買で菓子パンを買い込み、山に登った。

午後3時からセミナー。今日はずっともう一人の発表。やはり2週空くと忘れてしまった定義などがあって、確認したり教科書を見せてもらったりしつつ補っていた。今日は比較的何事もなく終了。先生が帰った後黒板発表の方法について少し話していた。それは彼の発表方法に思うところがあったからなのだが、そもそも自分の発表がどのように見えているのか、また自分が心掛けているつもりのことは本当に実現できているのか、主観ではよくわからないのに人に対して指摘するなどおこがましすぎた。反省。

学食で食事して帰宅。しばらくYouTubeに時間を吸い取られた後、午後8時からTCO22 R3に出た。Parallelでないほうにレジってから、そういえばStage3の結果はどうなったんだと思って見に行くと、いつの間にかページが更新されていてR4進出が確定していた。レジれてしまったものは仕方ないと自分に言い聞かせ、そのまま出場することにした。

https://tco22.topcoder.com/competition/algorithm?tracks%5balgo-tco22%5d=3&tracks%5balgorithm-tabs%5d=4

↑このURL、%5bと%5dはもともと[と]である。そのまま貼るとリンクが壊れてしまうため手動でURLエンコードする必要があり、面倒だった。

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

Easyから難しかった。サンプルの様子を見ると地獄みたいな実装が思い浮かんでしまうが、ぐっと耐えて盤面のサイズが $26\times 26$ であることに思いを馳せる。駒をうまくバラして各列に一つずつしかないようにできれば、あとは文字コードに応じて行を決めることで必ずソートできる。この各列一つというのを頑張る。ある行に注目しているとき、「その行の駒は左から順に $l\dots r$ 列目に配置する」と決め打ち、移動先が左の駒は左から順に移動、右の駒は右から順に移動させればよい。

Medは謎。問題文を読んだだけでは見当もつかないので、とりあえず与えられたファイルを眺めてみる。全部DFS木のファイルと全部MSTのファイルがあって、これはプログラムのチェックのほかに、手軽に2種類の木を比較するためにも使える。DFS木のほうでどのように探索していったか目で追ってみると、結構長い一本道がたくさん発見できた。これはMSTにはない顕著な特徴だ。ということで、DFS木であるかを判定することにした。

方法はもうちょっと考える。DFS木における行き止まりとは、つまりたどり着いたときすでに4近傍が訪れられていたような部屋である。このことからそれらの部屋を訪れた順番が確定して、これを使って枝分かれにおいてどのような順番で探索したかが決定できるのではないかと考えた。しかしこれはかなり面倒そうなので、簡略化を試みる。

行き止まり以外の部屋でも「進まなかった方向」というものがあって、その先の部屋は、今の部屋から先をたどって行った先で訪れたか、あるいは今の部屋にたどり着く前に訪れたか。前者は言い換えれば木における子孫であり、後者は、その部屋から今の部屋に向かって進んできていないことから「訪れたがまだ全方向を探索していない部屋」、つまり今の部屋の先祖であることがわかる。よって壁を挟んで隣接する2部屋について、それらの間には木の先祖・子孫の関係があることが分かった。

別に壁を挟んでいなくとも隣接する2部屋を全部見てよい。これを実装することにした。各頂点についてbitsetで先祖の頂点集合を持つ方針。実行するとサンプル・全部DFS木のファイル・全部MSTのファイルで全問正解したため提出作業に入った。bash スクリプトを書いて一括実行し出力をswitch-case文に成形して、コードにペースト。ファイル11は大きな入力しかなかったようでちょっと時間がかかったが、埋め込みなので問題ない。そういえばこのファイル実行の形式は、入力サイズを抑えられない上疑似乱数で与えることもできない以上仕方のない、苦肉の策だったのだろう。

Hardに30分弱残したものの、一切分からず。チャレンジフェーズではEasyしか落ちないだろうと考えて少し眺めていたところ、Medが大量に落とされてびっくりした。見るとファイル1に対してほとんど'D'を出力しているコードがいくつかあってびっくり。その他Easyもいろいろ落とされていたものの、自分は何もできず終了。

システスではEasyが落ちてしまった。注釈に「同じマスへの移動も許される」とあったため判定をサボって常に移動させていたのだが、この時すでに正しい位置に移動させ終わった駒をもう一度同じマスに移動させてしまうことがあったらしい。そもそも僕がデバッグのために盤面を出力しようとして、クソ真面目にわざわざ文字を入れ替えたりしていたからこういうバグを埋め込んでしまったのだ。残念。

結局Med1完で19位、2848→2854(+6)でhighest。助かった。Medは次数だとか葉の枚数、直径などいろいろな観点が考えられるようで、下手すると小さいケースが全然判定できなくなってしまうらしい。上で言及したファイル1はその小さいケースしかなく、偏った出力をしてしまいがちだったそうだ。

そこのところ、自分がたどり着いた判定方法はかなり本質的。ただしこれも解法ガチャに成功した結果というか、それ以外の判定方法と比較検討したわけではないためただ運がよかっただけという感想になった。一本道で答えにたどり着いてしまい他の判定方法があるとは思っておらず、チャレンジフェーズではMedは落ちないと考えコードを見もしなかったのだ。

しばらくTLを眺めてから日記を書き進め、布団に入って午前1時半に就寝。明日はICPC国内予選。

07/08(金)

午前7時半に目を覚ましてしまった。2時間ほど横たわりながら本を読んでいた。そろそろ二度寝したいと思って本を閉じたのに、そこからハーメルンを読み始めて結局眠気はやってこなかった。

1作読了。「バーチャルなんたらになることになった。」。一口サイズで特に感想はなし。エタっている。

syosetu.org

正午、TLにとんでもないニュース速報が流れてきた。日記に書くかどうか迷ったのだが、その日あったことを記録するという意味でこれに触れないのは嘘だろう。僕くらいの世代の人間は、その政治的立場を抜きにしても、彼の人の言動に多く触れ、また総理大臣であるとの印象を強く残しているはずだ。少なくとも僕はそうだった。だから、このどこか現実感のないニュースを目にして非常に大きな衝撃を受け、その後しばらくTLに流れ続ける関連ツイートや一色に染まっていくトレンドをぼんやり眺めていた。

午後1時頃布団から出て学食で昼食を摂り、帰宅。少し日記を書き進めて、ICPC国内予選参加のため午後3時に家を出発した。

この予選に関しては参加記を書くつもりである。投稿したらここにURLを貼ろう。

07/22追記：投稿した。