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時に投稿した。

kotatsugame.hatenablog.com

「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回目に出た。

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

今日はチームとして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を使っている最短コードを探し、縮めておいた。

atcoder.jp

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

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

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$ をソートするとマスは対角線っぽい感じに分けられる。ここまで整理すれば、あとはたくさん通されているのだから簡単な判定方法があるものだと思って、例えば先手勝ちマスと後手勝ちマスの個数を比較したりしてみたものの、通るわけもなく。そのままコンテスト終了。