11/22(月)

先週は週記を投稿した後しばらくほかの人の日記を読み漁り、布団に入ってから少しなろうを読んで寝た。午前8時半だった。

午後3時起床。ARC129-Aが縮め返されていたのを見つけて一気に目が覚めた。布団の中で唸っていると大幅（-3B）に縮む改善を思いついたので、提出して取り返した。

しばらくラノベを読んでから、今週の定例会に向けた進捗報告スライドを作り始める、前に進捗を作り始めた。先週は本当に何もやっていなくて非常にまずい。思ったよりコードの設計が難しかったので、諦めて正直に何もやっていないと書くことにした。定例会自体は無難に終了。Kaggleのサンタコンペが始まったのでまたチームを組むかという話になったが、前回何も手が動かなかったのがトラウマ気味で腰が引けている。まず自分ひとりで手を動かせたら、チームに入れてもらいに行くつもりだ。

今週はかなり早めに勉強会まで終了したので、午後6時半というとんでもない早朝からあるECRに出ることにした。その前に学食に行こうと思って、自転車ならまあ間に合うかなと思って外に出たら、思いっきり雨が降っていた。学食に行くこと自体諦めそうになったものの、何とか気力を奮い立たせて歩きで向かった。結局3分ほど遅刻して帰宅、即レジって問題を解き始めた。

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

Hackフェーズ前は全完。Aは、マンハッタン距離を上に移動してから右に移動する道のりの長さだと思えば、その経路の中間地点を答えればよいことがわかる。Bは、左右でそれぞれ使える要素の個数をカウントしてみると、 $a\gt b$ の場合 $n,n-1,\dots,1$ しかありえず、そうでない場合は $b\gt \frac n 2\ge a$ が成り立つ必要がある。構築は $n,n-1,\dots,1$ から $a,b$ の位置をswapすればよい。Cは二分探索。Dは結構難しかった。 $a\ge b$ としてみると、値が小さな方に操作するのは $(a,b)\leftrightarrow (a,a-b)$ を行き来するだけで、そこからの派生（値が大きな方に操作する）はどちらも $(a-b,b)$ になってしまうため、無意味。つまり値が大きな方に操作することだけ考えればよくて、この場合ユークリッドの互除法であまりを取る操作を引き算だけで行ったような変化をしていく。逆に、引き算を行う途中で求める値が出現するかは、あまりを見れば判別できる。

Eは貼る枚数を20枚以下で決め打つと、各メッセージに対して貼りだしたとき期待値の分子にどれくらい貢献するかが求まる。これを使って貪欲に取ればよい。21枚以上貼る場合は分子だけ20枚の場合の値を用いれば計算できたので、そちらも求めたが、実は20枚以上貼る場合は $\sum_{m=m_i} k_i$ の平均を取っているのと同じという理由から、21枚以上貼る場合がそもそも存在しないらしかった。答えを構築するときの境界ミスで2WA。Fのsolvedが少なく、しばらく考えてわからなかったのでGに移った。こちらはインデックスに対する係数列を考えれば瞬殺で、どの係数がどれくらい出現するかはimos法で求まる。自由度は係数の重複度の階乗を掛け合わせたものになる。

Fに戻る。最後の状態からさかのぼるのはいい性質が見つからなかった一方、最初の状態から進めるのは、常に最強の装備を組み合わせて最強のものを手に入れるのが最適だと分かった。フィボナッチ数列を考えるとあまり操作回数は大きくならなそうだったのでBFSをしたがTLE。操作回数が同じもののうち、手に入れた最強装備2種類の和が大きなものの上位1万種くらいに絞ってステップを進めるという謎の枝刈りを行ってもTLEだった。ここで、 $N$ と $M$ の値に大きな差があると操作回数が多くなることに気づいた。しかしこの場合は小さいほうがすぐに上限に達するので、どちらかが上限に達した場合の残り回数を前計算しておくことでそのようなケースに対しても高速に処理できるようにした。ずっとWAが出ていて困っていたが、前計算の際にシナジーを考慮するのを忘れていただけだった。8ペナの末何とかACしたが、謎の枝刈りの正当性が全く存在しないのでちょっと怪しい。

ラノベを1冊読了。「信長転生」。まったく肌に合わなかった。なぜなのかがうまく言語化できない。主人公が性欲を積極的に表に出すキャラなのが合わないのかとも考えたが、そこまで問題ではない気もする。テンプレすぎるというのも、受け入れられたラノベがあった覚えがある。そういえば、同じ作者の「貴族転生」もなろうで読もうとして挫折した覚えがあった。そちらの思い出した内容と合わせて考えると、話が軽すぎるのが問題なのではないだろうかという結論に至った。主人公が何かして周囲の人に褒められる、というサイクルを回すのが異常に速い気がする。当然、そこに鬱展開が挟まる余地はない。確かにストレスフリーではあるだろうが、自分には合わなかったということ。特別そういう展開が印象に残っているだけかもしれないが、それはそれで、自分の肌に合わなかった理由としては適当だろう。

7000フォロワーになった。

7000 pic.twitter.com/B7iFSLY2Cl
— こたつがめ (@kotatsugame_t) 2021年11月22日

日曜日のCodeChefの結果が反映され、レートが変動していた。2146→2309(+163)で橙になった。これまで順調に色変してきたが、次回赤というのは不可能だろう。

SnackDown 2021 21st
2146 -> 2309 (+163) highest
橙 pic.twitter.com/eCZ9tapbMA
— こたつがめ (@kotatsugame_t) 2021年11月22日

またラノベを1冊読んだ。「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」5巻。先ほどの反動か知らないが、かなり面白く感じられた。表面的には変わらず無双ハーレムものではあるのだけれど、突っかかってくるキャラにも背景があって、最終的にはいい奴だったとわかるなど、ちゃんと厚みのある物語になっている。また注意深く読んでみれば、登場するいろんな国家における物事の考え方の違いを丁寧に表現していて、主人公はそれを受け入れつつも自分の軸はブレさせずに動いている、ということがわかる。

TCB41の商品でアマギフが送られてきた。先週、返信期限を過ぎたメールを発掘してしまったコンテストのものだ。向こうでよしなにしてくれたらしい。感謝。

TCB41のメールが迷惑メールに入っているのを見つけてびっくりした。こちらは返信期限が11/12だったので、もう手遅れ。
週記（2021/11/15-2021/11/21） - kotatsugameの日記

朝方日記を書いて布団に入り、Pixiv小説を読んでいる間に寝落ちした。午前7時くらいだった。

11/23(火)

午後2時くらいに目を覚ます。購買に行こうと思ったが、今日は祝日で閉まっているということに気づいてやめる。ぼんやりとスマホを弄っているうちに時間が経過し、インターンの予定が近づいてきたので、午後4時くらいに布団から出た。昨日のECRはHackフェーズが終了し、全完が保たれていた。

食事してからミーティング。先週火曜日の日記で言及したように、ヒアリング先の業務を自分でもやってみるということになったので、その研修だった。一応他の研修の録画だったり資料が共有されてはいたのだが、わざわざ時間を割いて説明していただけることになって感謝。実際聞いているとかなり複雑な作業だったので、画面共有で作業の流れを見つつ質問などできたのは助かった。2時間半ほどかけて一通りの説明が行われ、あとは実際にやってみてのお楽しみというところらしい。この業務は、僕が普段やっているコーディングとは違って明確に納期が決まっている作業なので、ちゃんと稼働できる時間を把握して作業が割り振られることになる。週に最低限保証できるだろう稼働時間を見繕って向こうに伝えた。自分の時間はかなり有り余っているはずだが、自分が毎日何時間も作業できる体質ではないということが分かってきたので、伝えた稼働時間はかなり少なくなってしまった。

ハーメルンを1作読んだ。「これ以上龍気活性してしまうと、あたしはバルファルクになってしまう」。僕のヒーローアカデミア世界にモンスターハンターの（今のところ）天彗龍バルファルクの能力だけが持ち込まれたクロスオーバー。途中でエタっている。実はヒロアカにはほぼ初めて触れた。一応個性という能力があることや、やたら強いオールマイトというヒーローがいることくらいは知っていたが、ストーリーを全く知らないので、目新しく読めた。あとがきで作者が進学校イキりをしていて面白い。

syosetu.org

別のハーメルンを読み始めたが、途中でCGR17に出た。

Dashboard - Codeforces Global Round 17 - Codeforces

Aはよ……くない。 $N=M=1$ のとき、理論的には全く質問をせず特定することができる。 $k=0$ が許容されるのかが問題文からは読み取れなかったので、どうするか非常に迷ったが、statusを見るとめちゃくちゃWAが出ていたので、おそらく $k=0$ がコーナーケースとなっているのだろうと思って出したら通った。これをCGRのA問題に置いた人は垢BANされても文句は言えない。Bはちょっと悩んだ。回文の条件を確認していって、最初に条件が満たされなくなった値のペアは、そのどちらかを削除しなければならない。つまり削除する値の候補が2通りに絞られて、あとはそれぞれ試して、チェックはその値を全部削除したときのことを考えればよい。Cもけっこう悩んだが、選ぶ人数を決め打つとそれぞれの $(a_i,b_i)$ が満たす必要のある条件がわかり、その条件を満たすものを先頭から貪欲に取ってよいため、二分探索できる。1secで $n\log n$ を出すのは少し躊躇したが、問題なく通った。

Dは難しい。まず奇数を1つ以上選べば必ず構築可能である。では偶数のみの場合は、と考えると、4で割ったあまりで分類することでサンプル1が合う。しかしサンプル2は合わない。さらによくよく考えてみると、どうやら値を割り切れる最大の2べきの値で分類しなければならないようだった。これに気付くのに非常に時間がかかり、ACしたときにはコンテスト開始から1時間が経過していた。Eは、任意の3要素 $a\le b\le c$ が $a+c\ge 2b$ を満たす必要があるらしい。このもとで貪欲にとっていいようだったので、 $a=a_i$ と $b=a_{i+1}$ を選んで、あとは $a_j\ge 2b-a$ を満たすような最小の $j$ を選んで $b\leftarrow a_j$ としていけばよさそう。 $a=b$ のとき以外は値が2べきオーダーで大きくなっていくようだったので、先頭要素の重複だけは別でカウントしておけば全探索できないこともなさそう。 $j$ を選ぶ部分でlogがつくので、 $O(n(\log n)^2)$ になってしまうが、どうしようもなかったのでそのまま提出したら通った。相変わらず1secとTL設定が攻めている。priority_queueのlogにしたのだが、lower_boundとどちらが速かったのだろうか。

この時点で-100近いレート変動が予測されていて絶望気味。Fに崖ができていたので、何とか解きたいと思って気合を入れた。結論から先に書けば、残り30分で解法が完全に分かったものの、実装ができずに通せなかった。重み2のパスを重み1のパス2本に変換してから戻す、という考察に執着していたようにも感じられる。

まず自明な上界として、重さ1の辺が奇数本出ている頂点しかOddyseyになれない。逆にそのような頂点は全部Oddyseyになれる、ということを、実際に構築することで示す。まず重み1の辺を、「サイクル」と「奇数次の頂点同士のパス」に分解する。サイクルはぐるっと一周向き付けたら放置で良い。パスのほうは、とりあえず適当に向き付けておく。次に重み2の辺を考える。その辺が結ぶ頂点のうち少なくとも片方がOddyseyにならない場合、最後に適当に向きづけてよい。両方がOddyseyの場合が問題だが、これもうまくできるということを以下で述べる。

そのような辺だけを抜き出して、また「サイクル」と「奇数次の頂点同士のパス」に分解する。サイクルは先ほどと同様無視。今作ったパスは、重み1の辺からなるパスたちの先頭か末尾に属する頂点と、同じく先頭か末尾に属する頂点を結ぶパスとなる。実は、重み1の辺からなるパスを適当にひっくり返すことによって、これを重み1の辺からなるパスたちの先頭に属する頂点と末尾に属する頂点を結ぶパスにできる。といっても簡単で、奇数次の頂点は偶数個しかないので、適当にひっくり返していても最終的には矛盾せず収まるのである。

そのようにすると、重み2の辺からなるパスは、末尾から先頭に向けて向きづけることでOddyseyという状態を崩さずすべて向きづけることができるようになる。あとは最後に残った辺を向きづけて終わり。実装はかなり面倒。サイクルとパスに分解するのがまずとんでもなく面倒で、そのあとひっくり返すのも、影響が伝播していくのが微妙に面倒。コンテスト終了後もコーディングを続け、3ペナを出して40分後に通った。5000B近くのコードになった。WAを突破するためにテストケースを見てしまったので、本番ではEまでがうまくいき、考察がすんなり済んだとしても通せなかっただろう。ちなみに考察に間違いはなく、向きの取り扱いミスとか条件の書き間違いだった。

自分はまずdfsでパスに属する辺を検出し、それらだけからなるグラフを適当に突き進んでパスに分解した後、残りのグラフでこれまた適当に突き進むことでサイクルに分解した。これは手数が多くて絶妙に面倒。heno239氏は以下の方法で、まずサイクルを取り除いた後パスに分解したらしい。こちらのほうが手数が少ないかと思ったが、あんまり変わらない気がしてきた。そういえば僕の解法は完全に線形時間を達成している。辺削除を辺番号とフラグで行うのは苦痛の極みだったが、その甲斐あって実行時間は結構短かった。

適当に辺を伸ばしていって、
・サイクルができた
→サイクルを全部消す
・これ以上辺を伸ばせない
→最後に追加した辺を「サイクルに含まれない」と確定して消す
とすると、一見O(NM)に見えるけど各辺について定数回しか見てないのでOK
— heno239 (@heno_code) 2021年11月23日

結局5完遅解き、130位でレートは-89する予測。伝説は遠い。

夜はまたハーメルンを読んでいたが、いい加減切り上げ、日記を書いて布団に入った。さらに少し読み進めて就寝。午前7時半だった。

11/24(水)

午後3時半起床。

昨日から読んでいたハーメルンの最新話まで読了。「蛇王龍、海賊になる。」。

syosetu.org

ワンピースとのクロスオーバーで古龍が海賊をするのは非常に良い設定だった。よく知らない古龍が大量に仲間として出てきてパワーバランスがガタガタに崩れているのも許容できる。ただ、原作介入の結果ルフィ一味が崩壊気味になったのが受け入れられず、辛かった。タグの「アンチ・ヘイト」というのは、こういうことなのだ。これまであまり気にしていなかった（念のためという理由でつけている人が多い？）が、受け入れられるものとそうでないものがある。

家を出て閉店間際の購買に駆け込み、注文していたラノベを2冊受け取った。そのまま学食の夜の部の開店を待ち、入店。一昨日学食に行った際、「納豆はカウンターで注文してください」という張り紙があったのを覚えていて、夜も納豆が食えるのか！とわくわくしながらレジに進んだ。ここで重大な勘違い、レジとカウンターは別の場所を表す言葉であった。また焦っていて、今日も張り紙があったかどうかを現時点で覚えていない。同じ位置に何かが貼ってあったのは確認したはずだが、あまり自信がない。

レジに進んで意気揚々と「納豆をください」と発言。レジ担当の方もよくわからないまま、とりあえず納豆を含めて会計を済ませた。ここで僕が納豆を持っていないことに気づいたらしい。僕もよくわかっていなかったので、「言えば納豆がもらえるはずでは……？」などモゴモゴ言っていた。それでレジ担当の方がカウンターに確認したところ、今日は納豆がないらしい。返金処理になったのだが、ミールカードから払ったのにプリペイドカードに返金ぶんがチャージされ、よかったのかちょっと謎。

さて、以上のことは開店直後のレジで行われた。そのときレジは1台しか稼働しておらず、ふと後ろを振り返ると学食の入り口までレジ待ちの列ができていた。非常に申し訳ない思いをした。納豆がないので白ご飯を噛みしめながら振り返ってみるに、やはりレジとカウンターを混同していたのが混乱の原因だったのだろう。深く反省。帰り際に一言謝ろうと思ったのだが、新人さんにレジ打ちの研修をされていたようだったので声をかけるタイミングをつかめず、すごすご帰ってしまった。人の顔を見ないように過ごしているので、服装や位置で認識するしかなく、日が変わってしまえばもう誰だったかも定かではない。二度と謝ることができないままになってしまった。

昨日のCGRのレート更新が来ていて、予定通り2990→2901(-89)。

受け取ってきたラノベを読んでいたら、いつの間にかJOI一次予選（第3回）の過去問が公開されていた。提出記録を見るに、公開から11分ほど遅れて見つけたらしい。今回も例のごとく、パソコンやスマホでURLを開いておいて、定期的に公開されていないか確認していたのだった。しかし結局今回見つけたきっかけはatgolferの更新だった。

URL自体は推測できるので、先週日曜日からずっとスマホとパソコンの両方で以下のページを開いており、起きている間は数時間に一度リロードしていたのだった。
週記（2021/10/18-2021/10/24） - kotatsugameの日記

JOI 2021/2022 一次予選 (第3回) 過去問 - AtCoder

急いでコードゴルフした。A問題はdcの自明な5Bで、負け。ただBCDは今のところ最短を取れている。Bは負の数の取り扱いと切り上げ除算がそこそこ面倒で、非自明に感じられる20Bのdcコードが最短。CはPerlかと思ったがVimが予想外に短くなった。 $S$ の末尾に"WR"をつけ、先頭から $K$ 個目の'R'の上にカーソルを移動させる。これはfRを適切に繰り返せばよい。この状態で1文字右に移動すると、元の $S$ に'R'が $K$ 個存在したならカーソルは'W'の上に移動し、 $K-1$ 個しか存在しなかったならそのまま'R'の上に留まることになる。あとはカーソル下の文字のみを出力すればよい。Dはかなり自明なPerlコードから縮まなかった。

CodeChefのドメイン名の有効期限が切れていた。今日の夜からコンテストがあるようだが、大丈夫だろうか。正直面白がる気持ちしかない。

え、codechefさん！？ pic.twitter.com/5bwHwY30sv
— (nは自然数) (@n_vip) 2021年11月24日

ホスフィンに誘われて、CoRe Challenge 2022というコンテストにチームを組んで出ることになった。マラソンも得意ではないし、そもそもドメイン知識がないとマラソンにすらできない可能性がある。何とか頑張りたいが、どうなるだろうか。

本研究領域では「The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022)」というプログラミング競技会を開催します．https://t.co/EsIG6QTM6L

皆様のご参加をお待ちしております．また，どなたでもご参加頂けますので，ご興味のありそうな方へ情報拡散して頂ければ幸いです．
— 組合せ遷移＠学術変革領域研究(B) (@comb_reconf) 2021年11月24日

今週金曜提出のレポートがあるので、講義動画の視聴を始めた。Pythonで数値計算をする講義で、どうせしばらくPythonの初歩的な内容だろうと思っていたら、いつの間にかそれっぽいことが始まっていた。しばらく見ていて、先生が「 $\frac{n(n-1)}2$ 回の掛け算をする」と言いながらi=1..nに対して0.9**iをしていたのが気になった。べき乗は単なるループで計算されるのだろうか？

Pythonの内部実装を調べることにした。どうやら最も一般的なものがCPythonであり、GitHubでコードを見ることができるようだ。単純にpowerで検索して出てくるコードから辿ると、謎の構造体のメンバ変数tp_as_numberが関数の配列になっているようで、そこからべき乗を実装している関数を取り出して呼び出しているらしい。しばらく構造体のほうから攻めていたが、検索をかけると大量に引っかかって心が折れそうになった。tp_as_numberで検索してみるとそこそこうまくいって、何とかそれらしき実装にたどり着けた。整数型と浮動小数点数型の2種類の実装があった。

cpython/longobject.c at 345ba3f080c140dee3102f472bc166c2db191bcc · python/cpython · GitHub

整数型は絶妙な高速化が絡み合っていて読み解きづらいが、おそらく二分累乗法をしているだろうというコードが上のリンク先で読み取れる。

cpython/floatobject.c at 345ba3f080c140dee3102f472bc166c2db191bcc · python/cpython · GitHub

一方、浮動小数点数型は簡単で、いくつかの場合分けを取り除いた後はpow関数に投げている。これは別の行で定義されているということもなさそうだから、C言語由来の関数と見て間違いないだろう。C言語のpowの実装を調べるまではさすがにやらなかったが、順当に考えればexpとlogを使うはずで、これはどちらもテイラー展開で実装されていることが期待できる。0.9**iの計算にはこちらが使われるだろう。つまり、実際には先生は $O(n)$ 回の掛け算しか行っていなかったのだ。

このことを指摘しようかと思ったが、そもそも数回前の講義に今更何を難癖付けるんだ、と自省して、取りやめた。

午後11時半からCodeChefの野良コンテスト。しかし開始したはずなのに問題がない。しばらくTLで騒いでいるうちに1時間延期された。ラノベを読みながら待って午前0時半からまた参加しようとしたところ、明日に延期というメッセージが表示されていた。明日はCFのコンテストがあるので、もう出ないかな……。メッセージを読むと、どうやら夜にドメイン名の有効期限が切れた影響がまだ残っているから、ということらしい。

「公女殿下の家庭教師」10巻を読了。この巻は休憩の巻という感じで、ストーリー的にはあんまり進んだ感じがしない。主人公アレンとヒロインリディヤの二人がずっと一緒に行動していて、それ以外のキャラとの絡みもほぼない感じだった。あとがきにもリディヤがアレンを独り占めする巻と書いてあって納得。量こそ少なかったがバトルシーンもあり、アレンとリディヤのタッグが非常にいい感じだった。

CGR17-Fの公式解説を読んだ。重みが等しい2辺 $(u,v)$ 、 $(v,w)$ を、1本の辺 $(u,w)$ に組み替えるということを繰り返すと、最終的に各連結成分が重みが交互に現れるパスまたはサイクルになって、それらを適当に向き付けると関係する頂点が全部Oddyseyになる。あとは組み替えた辺を戻せばOK、ということらしい。かなり頭が良い。

「サベージファングお嬢様」2巻を読了。面白かった。1巻の途中から学園生活がスタートして、この巻では初めからずっと学園が舞台になった。新たに登場したキャラクターとの交流がメインで、ストーリー上の敵組織も今回は終盤に攻めてくるだけだったが、一方バトルシーンでは主人公の新たな能力が発揮されて少し成長した感じがある。と、表面的な内容はそんな感じで言葉にしてみての印象は薄いが、読後感が非常に良かった。バトルの決着の爽快感はあるものの、それ以外で一体何がそんなに心地よかったのか自分でもよくわからない。とにかく面白いと感じたことだけは確かだ。

12月発売のラノベをメインに23冊予約した。「時々ボソッとロシア語でデレる隣のアーリャさん」3巻が12月の頭に発売されるが、それだけ予約受付が終了していた。残念。かなり快調に売れているのだろう。月が変わったどこかのタイミングでリアル書店に買いに行くことにしたい。

布団に入って少しなろうの更新を確認し、午前7時就寝。

11/25(木)

午後1時ちょっと前に起床。今日は少し余裕をもって4年ゼミのZoomに接続できた。今日のゼミは特に発表もなく、のんびりと聞きながらラノベを読んでいた。

「ネトゲの嫁が人気アイドルだった」2巻を読了。1巻の印象があまりよくなく身構えて読んでいた。最も受け入れられなかったヤンデレ気味のヒロインについては、慣れたのかあまり気にならなかった。これまた1巻の感想を受けての見方だが、2巻も主人公とヒロインの関係を深めることをメインに、ネトゲやアイドル要素はほぼなかったように感じられた。まあそれは分かりきっていたこと。この巻では主に主人公の内面を掘り下げていて、案外こちらも闇が深くてびっくりした。

人気アイドルだとかネトゲの要素を目的としていたのに、実際にはヒロインの性質やヒロインと主人公の関わり（のみ）を掘り下げるような内容だったからだろう。あとはヒロインがヤンデレなのもあまり受け入れられない。
週記（2021/06/21-2021/06/27） - kotatsugameの日記

次に「神様の罠」を読了。しばらく前に半分くらい読んで放置していた短編集だった。どれも非常に面白かった。以下短編ごとに感想を書くため、ネタバレ注意。

「夫の余命」：呑気に読んでいたら叙述トリックでびっくりした。これでこの本に対する緊張感のようなものが生まれた。帯に「二度読み必至」と書かれていて、実際この短編は本当に二度読みすることになった。

「崖の下」：米澤穂信氏の手になる短編。これを目的に購入した。ずっとつららだろうと思いながら読んでいたので、そこを外されてまんまと引っかかったなという感じ。

「投了図」：序盤からかなり不穏で、実際その予想は当たったのだが、それでも救いのある結末でよかった。

「孤独な容疑者」：普通のミステリだなあと思いつつ、アリバイ崩しの伏線が全然ないように思えたのでどうするのか見守っていたら、意表を突かれた。

「推理研VSパズル研」：題材となっている論理パズルは、以前レポートで出題された以下のものに似ている。「しばらくして」という曖昧な記述が、ちゃんと1日単位になっていて、より厳密になっていたように感じられた。それだけなら有名問題を紹介しているだけの短編だが、そこから論理パズルの状況としてあり得るストーリーを考えるという試みはかなり興味深かった。ちゃんとそれっぽいものが完成していて感動。

「3人の死刑囚がいる。3つの青い帽子と2つの赤い帽子が用意され、看守が3人にランダムにかぶせた。自分以外の死刑囚がかぶる帽子は見えている。自分の帽子が青いと確信したならば逃げてよいが、このとき実際にかぶっている帽子が赤かったら射殺される。しばらくして、3人の死刑囚は一斉に逃げ出した。なぜ3人は自分の帽子が青いと確信できたか？」
週記（2021/08/02-2021/08/08） - kotatsugameの日記

「2020年のロマンス詐欺」：途中主人公が騙されて犯罪の片棒を担がされそうになり、非常につらい思いをした。最終的にはハッピーエンドになったが、ギリギリ助かったという感じで読後もちょっとモヤモヤしていた。

学食に行こうと部屋を出たら上のほうから音が聞こえ、なんだと見上げたら花火が見えた。帰りにATMで通帳に記帳したら、インターン先から9月分の給料が振り込まれていたのが確認できて嬉しくなった。残高が思ったより多かったのを目にして感づいてはいたが、やはり通帳の一行として自分の稼いだ金銭が記録されていると別格の味わいがある。

眠気に耐えられず午後8時から午後11時まで昼寝した。起きてからCF #756 div.3に出た。

Dashboard - Codeforces Round #756 (Div. 3) - Codeforces

Aはよい。Bは自明な上限が $\min(a,b,(a+b)/4)$ で、どうせ達成可能だろうと思って出したら通った。後から考えてみれば、その上限についての帰納法で示せる。Cは操作の最後に消す値が必ず $n$ で、冷静になると $n$ と比較し続けることで残りの順序はどうとでもできる。Dは距離を $0\dots n-1$ としてよい。E1は多始点BFSで $x_i$ からの距離の最小値を求める。頂点 $1$ からの距離がそれより小さい頂点だけを通ってしか移動できない。E2はすぐにはわからなかったので、順位表でより解かれていたFに進んだ。Fはセグ木上のにぶたん。

E2に戻る。根を頂点 $1$ として、ある頂点 $u$ の親にはたどり着けるけれど $u$ にはたどり着けない、というような頂点を考えれば、 $u$ にたどり着けなくするために必要な頂点 $x$ はそのほかの頂点に対しては無意味ということがわかる。なので $x$ の代わりにそのような $u$ を数えればよくて、再度多始点BFSをしておけばよい。Gはなかなか難しい。盤面を45度時計回りに回転させると、ロボットの移動は下か左に1マス動くことになる。こうすると貪欲ができて、できるだけロボットが盤面の右にいるように移動させればよい。コンテスト後に知ったが、これはLongest Decreasing Subsequenceに等しい。実際LDSに含まれる飴は1回の操作で1個しか取れず、逆にLDS回ロボットを操作しても取れないなら、それらの経路からうまく飴を選びだしてより長いLDSを構築できてしまうようだ。

Gにかなり手間取ったがそこまでが結構速かったので5位。Hackに耐えることを願う。

その後、金曜提出のレポートにようやく着手した。全然集中できなくて結構頻繁にラノベを読んでいたが、ちまちま書き進めて何とか午前6時半に完成した。今回の課題は、常微分方程式を一つPythonによる数値計算で解いて、結果に対して何らかの考察を加えよというもの。常微分方程式なぞほとんど知らないし……ということで、オリジナリティ重視で勝手に差分方程式を考察することにした。イロレーティングというのは実質差分方程式ではないだろうか。

イロレーティングを扱うというネタは決まったが、中身をよく考えないまま適当にコードを書いてビジュアライズして、と繰り返していたら、何が言いたいのかよくわからないレポートが出来上がってしまった。いうほど差分方程式っぽさも感じられないコードになっている。提出した後、ふと変数名の英語が間違っていることに気づいた。historyの複数形はhistoriesであって、historysではない。そもそもhistoryを複数形にする理由もなかったので、そこを修正して再提出したりもした。

少し日記を書いて布団に入り、ハーメルンを読んでいたら寝落ちした。午前11時だった。

11/26(金)

午後6時半起床。サークルに行けなかった。

しばらくラノベを読んで、午後8時過ぎからCF #757 div.2。10分こどふぉったのでyukicoderと被ったかと思っていたが、どうやらまだ5分余裕があったらしい。5完47位だった。

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

ABはよい。Cはとりあえず1例作ればよさそう。各インデックスに対してそれを含む区間のbitwise OR値すべてのbitwise ANDを計算すれば条件に矛盾しない中で最も多くのbitを立てることができて、しかも少なくとも1例存在するという条件からそれらは入力に適する。遅延セグメント木で区間更新したが、最後に答えを計算するとき、式変形の過程で「あるbitが立っている要素数」という情報が消えることに気づいた。コンテスト中はそのまま書き上げたが、bayashikoさんは今の発見を用いて解いたそうだ。つまり、適する数列であるbitが立っている要素が存在するかどうかさえ分かればよく、これは入力のbitwise OR値すべてのbitwise ORを見れば判別できたらしい。かなり頭が良い。

bitごとに独立に考えて、XORが1になるということは1が奇数個あるということなので、数列中に1がk個あるとしてkから奇数個取る組み合わせは2^kの丁度半分であることを踏まえると結局1が1個以上あるなら2^(N-1)回1が出現することになり、1が1個以上あるかどうかは全部のORを取れば分かる　おわり
— bayashiko (@bayashiko_kpr) 2021年11月26日

D1はdp。各 $1\le g\le 5\times 10^6$ に対して、 $g$ で割り切れる $a_i$ の個数 $cnt_g$ を数えておく。数列の先頭に $cnt_g$ 個並べておいて、そのうちいくつかを選べばさらに $\gcd$ が大きくなるだろうが、それをdpで計算する。具体的には $dp_g=\max_{g\mid h}dp_h+g\times(cnt_g-cnt_h)$ となる。D2はかなり悩んだが実はD1と同様のdpでよい。 $cnt_g$ の計算には、素数をふるっておいて素因数分解→dfsで約数全列挙、とすると速くなりそう。dpの遷移は、実は素数 $p$ に対して $h=gp$ となる場合しか考えなくてよいため、それだけ遷移すると全体で10⁸回未満となり、十分高速になるようだった。コンテスト後に試したところ、 $cnt_g$ の計算のために $\sqrt{a_i}$ かけて約数全列挙しても実行時間は大して変わらなかった。

Eは解けなかった。グラフが傾き1と0をつなげた形になるため、これをどうにか管理するものと思っていた。クエリ平方分割をすることにして、 $B$ 回に一回グラフの傾き0の地点とその値を再計算し、実際に値を取得するときは二分探索でグラフのどこの地点にいるかを探し、残り $B$ 回に満たない分は愚直に計算、とした。14ケース目のTLEが取れず、コンテスト後にmapだった部分をvectorに変えるとそこは突破したが、26ケース目でやはり詰まってしまった。バケットサイズガチャも効果なし。

yukicoder 325に出た。全完、writerとtesterを除いて3位。

yukicoder contest 325 - yukicoder

Aはよい。Bは端を通り過ぎてしまい1WA。Cは面倒なdp。Dは $A_i$ と $A_{i+1}$ の間ごとに、左右どちらにどれだけ寄せるかを全探索。Eは適当にパターンマッチングした結果失敗しまくった。 $B_i$ が小さい順に貪欲に揃えることを考えてよくて、 $A_j\le B_i\le B_j$ が満たされるような $j$ のみの区間から取ってくることができる。区間の管理はインデックスをsetで管理し、値の存在判定はrangefreqというライブラリを使った。セグメント木のノードにソート済み列を乗せるやつだ。

Fはよくわからないがうまくいった。全方位木dp。まず最初に、データ構造をマージする一般的なテクで、各XOR値に対して根からの経路途中にその値が出現するような頂点数を数えておく。これは子らに対して再帰的に計算し、mapをマージした後、最後に根から自分までのXORに対応する値XOR[u]と部分木のサイズch[u]を使い、map[XOR[u]]=ch[u]と書き換えれば求まる。あとは求めたデータを全方位木dpで子に渡すときにきちんと更新する方法を考えればよい。結構苦労してガチャガチャやっていた。まず最初に、先ほどch[u]に書き換えてしまった値を元に戻す。これは元の値との差分をメモして、逆に引けばよい。さらに子vに渡すときの値はmap[XOR[u]]だけ正しい値に変更すればよく、vでも元に戻す作業が発生することを考えれば、今のところはvにおけるN-ch[v]とv以下に対して計算した時のmap[XOR[u]]を足し合わせたものにするのがよい。後者は1回目のdfsのときにメモしておけばよい。

「僕らのセカイはフィクションで」を読了。非常に面白かった。珍しく単巻完結っぽい感じがする。帯に「作者のチート知識で無双する」など書いてあるが、これはあまり本筋を捉えているとは言えない。ネタバレになるが、このラノベは作中作の作中作とかいう複雑な概念を扱っていて、読んでいるうちにその階層が逆転したりするのでかなり振り回された。総じてあらすじなどから事前に想像していた内容とは全然違っていた。ヒロインの小さな行動が最終的に壮大な話につながって、なるほどこれがセカイ系、という印象。また作者の夏海公司さんは「なれる！SE」が有名で、本人も前職がシステムエンジニアだったらしく、ところどころIT用語が出てくるのも面白かった。

朝方はずっと日記を書いていた。午前7時くらいに布団に入り、ハーメルンを2時間くらい読んで午前9時就寝。

11/27(土)

途中弁当を受け取りに一瞬だけ起きたが、そのままずるずるとスマホを触り続けるようなこともなく、すぐに二度寝に成功した。午後8時起床。食事して午後9時からABC229。

NEC Programming Contest 2021(AtCoder Beginner Contest 229) - AtCoder

Aから難しい。よくよく制約を読むと、縦または横に2マスつながっているとき、またそのときのみYesになるらしい。これをsedで書いて、1回目の提出の後すぐ/#\n.#\|#.\n#/が/#..#/とまとめられることに気づいて再度提出した。Bはよくわからないので適当にC++。CはRubyで出したが、サンプル1だけ試して出したらサンプル2で落ちてしまった。落ち着いてみると一体何を考えているのかわからないコードになっていて、赤面しながら修正してAC。またC++に戻って、Dは尺取り、Eは逆順に見てUF、Fは一周して最後に閉じるdp。

GはどのYに寄せるかを全探索しようとした。それを一つ固定したとき、残りのYを寄せるためにかかる手数を1文字ずつ求めて、何手かかるYまで寄せられるかを二分探索するとうまくいきそう。 $a$ 手かかるYまで寄せられるなら、残った操作回数を $a+1$ で割ることで、 $a+1$ 手かかるYをどれだけ寄せられるかが求まるというもの。しかし詳細を詰めずに実装に移った結果、かなり迷走して非常に時間を食ってしまった。残りのYを寄せるためにかかる手数はいちいち更新していられないので、頻度分布と総和をBITで持って、適切なオフセットを引き算することになる。最初うっかり手数ではなくインデックスを管理してしまい、それでサンプルは合うものだからデバッグ出力を睨みつけて手計算と照合する羽目になった。解説はかなり頭がよい。

それでもHには40分以上残せたが、何もわからず。とりあえず行ごとに分解して、非不偏ゲームなのがつらいが、1手ごとに黒と白をswapすれば不偏ゲームじゃないか？とか考えていた。これでgrundy数を計算して、全然サンプルが合わないことを確かめて絶望。7完遅解きで箸にも棒にも掛からない順位になった。

コンテスト後に急いでC問題までコードゴルフして、午後11時からCodeChef。今日はNovember Lunchtime 2021。

https://www.codechef.com/LTIME102A

SUBJUMPは、図を描いてみると、 $i$ から $j$ まで飛んだ時 $A_{i+1\dots j}=\mbox{元の}A_i$ とし、最終的な $\sum A_i$ がコストとなるような式だとわかる。よって累積最小値を管理して埋めていけばよい。PERPAIRはまず適当に式を立ててWolframAlphaに投げた。全然帰ってこないので改めて考え、よさげな式をひねり出すことに成功した。 $j$ と $i\lt j-K$ を固定する。まず先頭 $j$ 要素の最大値が $j$ 番目に来る確率は $\frac 1 j$ であり、さらにその上2番目に大きな値が $i$ 番目に来る確率は $\frac 1{j(j-1)}$ である。今 $i$ には自由度 $j-K-1$ があるため、結局 $N!\times\sum_{j=K+2}^N \frac{j-K-1}{j(j-1)}$ が答えになる。シグマの中身を部分分数分解すると分母が定数になって、これもシグマの外に出せば残りは単なる逆数の和になり、累積和を前計算すれば求まる。逆数を10⁷回求める必要があったので、全体で線形時間で求められる式を使った。

MNMXROTはちょっと難しかった。コンテスト中の考察を整理していたら、詰め切れていなかったところを見つけたが、文字列の周期に関する性質を考えると行間を埋めることができた。 $maxb$ や $minw$ を決め打つことを考えると、 $i$ をBに、 $j$ をWに割り振れる条件が気になる。 $d=|i-j|$ として、文字列の $k,k+d,k+2d,\dots,k+(N-1)d$ 番目が全部同じ文字だった場合のみ割り振れなさそう。結局 $d\leftarrow\gcd(N,d)$ で考えているのと同じで、これで調べる必要のある $d$ が $N$ の約数の個数通りになった。毎回 $O(N)$ かけても間に合うようだ。ただ、まだ $i,j$ を探索する必要が残っている。割り振れない $d\mid N$ が存在して $i\equiv j\pmod d$ となるとまずい。コンテスト中はここで、その割り振れない $d$ に着目した。ある $N$ の約数 $d$ であって、 $d$ では割り振れず、 $h\mid d$ なるすべての $h$ で割り振れるようなものを考える。 $d=N$ の場合割り振れず、 $d=1$ の場合割り振れるので、そのような $d$ は必ず一つ以上存在する。 $i,j$ として $i\not\equiv j\pmod d$ なるものを選べば、実は必ず適している。

ここで、なぜ適していると言えるかに文字列の周期が関係してくる。実は割り振れない $d$ というのは文字列の周期の一つになっている。しかも、そのような周期のうち最小のものは、そのほかの周期の約数になっているから、先ほど $d$ の条件として書いた「 $h\mid d$ なるすべての $h$ で割り振れる」を満たすような $d$ は実はただ一つしか存在しない。その $d$ によって $i\not\equiv j\pmod d$ となれば、そのほかの割り振れない $h\mid N$ はすべて $d\mid h$ も満たすので、 $i\not\equiv j\pmod h$ が従うというわけだった。

MINFUNDは結構すぐに見えた。グラフ全体は最終的に連結になるので、新たに張る辺の本数は一定である。まず二辺連結成分分解して、二つのcityを繋ぐ唯一の辺としてすでに存在する橋を使ったか使ってないかを持ちつつ、片方のcityの大きさに関する部分和dpをbitsetで行う。分解してできた木ごとに含まれる頂点数を数えて、橋を使わないならその頂点全部を含めるか含めないかの遷移があり、橋を使うならそれで木を二つに分けて、どちらか一方を含める遷移がある。最終的に、橋を使ったか使ってないかに関わらず、 $\frac N 2$ に最も近づいた部分和が片方のcityの大きさになる。コンテスト後にbitsetの話からCodeChefのメモリ制限の話になって、問題ページに書いてないのでさすがインドと言っていたところ、LayCurseさんに1.5GB制限らしいというのを教えてもらった。思ったより大きかった。

今もそうかは自信がないですがhttps://t.co/5kCYyvCteL
のCubeが使われていてML=1536MBだと思います．
— laycrs (@laycrs) 2021年11月27日

CHASEはかなり難しかった。部分点1は直線グラフで、2点から両端にそれぞれ $\left\lfloor\frac{K-1}{2}\right\rfloor$ だけ進めそう。部分点2は2点の距離+1が答え。部分点3から考察する必要がある。自分は結構後まで気づかなかったが、まず $K\le 2$ の場合は2点の距離+1が答えになるらしい。 $K\ge 3$ の場合を考えると、次数3以上の頂点には必ずたどり着けることがわかる。またクエリで与えられる2点も次数3以上と見なしてよい。その他は、次数3以上の頂点を繋ぐ頂点と、次数3の頂点から距離 $\left\lfloor\frac{K-1}{2}\right\rfloor$ 以下にある点も到達可能。ここまで考察すると、毎回dfsする $O(NQ)$ が書ける。

最後に満点解法。とりあえず直線グラフの場合を取り除き、また $K\ge 3$ とする。次数3の頂点には必ずたどり着けるので、そのような頂点のうち一つ（直線グラフではないので必ず存在する）を根として、他の次数3の頂点とその間の頂点たちに到達可能のマークをつけておく。すると、残ったグラフは次数3の頂点から生えるパスの集合になる。それぞれ親となる次数3の頂点からの距離をメモしておく。このもとで、 $K$ の昇順にクエリを処理する。まずメモした距離が $k:=\left\lfloor\frac{K-1}{2}\right\rfloor$ 以下の頂点は新たに到達可能となる。クエリで与えられた点に距離がマークされていた場合、それが含まれるパスの長さを $L$ 、クエリの点にメモされた距離を $x$ とすると、そのパスでは新たに距離 $\min(x+k,L)$ 以下の頂点がすべて到達可能になる。今そのうち $k$ までの頂点がすでに到達可能とマークされているので、増分は $\max(\min(x+k,L)-k,0)$ である。これをクエリの2点それぞれで計算するが、2点が同じパスに乗っている場合があるので、その時は $x$ として大きな方のみを計算することにする。増分の計算が壊れていたが、何とか修正できてギリギリで通せた。

全完9位でレートは2309→2463(+154)。いい感じ。

ABC229のコードゴルフに戻る。Aはコンテスト中の二度目の提出が最短になっている。Bはdcで、一度取られたが取り返せた。なかなかシンプルなコードになって気持ちがいい。Cはコンテスト中に出したPerlコードの、変数の値の書き換えを防いでいるところで更新があって1B縮められた。DはPerlで尺取り。尺取りの幅の最大値を求めるとき、右端でループして左端はインクリメントするかしないかだけでよい、というテクがかなり好き。左端のループが消えるので相当短くなる。もちろん途中で持っている区間が条件を満たさなくなってしまうが、最大値を更新するためには左端をインクリメントしない必要があって、このときちゃんと持っている区間は条件を満たしている。EもPerl。残りは手付かず。

日記を書いて午前7時半ごろに布団に入り、満を持してハーメルンを読み始めてしまった。

1作読了。「僕のヒーローアカデミア　それは古龍の王たらん」。特定の古龍の能力というよりは、いろんな古龍の能力が登場していたらしい。よく知らないので気づくのが遅れてしまった。途中から一気に不穏になって、今は主人公がなんだか似非サイコパスっぽくなって作中で暴れまわっている。あまり面白くなかった。

僕のヒーローアカデミアそれは古龍の王たらん - ハーメルン

もう1作、ヒロアカ世界で古龍の個性を持った主人公という似たような設定のハーメルンを読んでみたら、こちらはかなり面白くて、うっかり午前11時半くらいまで読んでいた。明日はコンテストが目白押しだが、もう睡眠時間が確保できない。急いで寝た。

11/28(日)

午後4時半に無理やり起きる。食事して午後5時からOpenCup。今日はANFCJKEGHの9完。

Aから順に読み始めた。さっそくAがそれっぽい貪欲で解けそうで、証明を考えつつ順位表をチラチラ見ているとどんどん通され始めたので、ようやく解法に自信をもって書き始めた。実は証明もほとんど完成していた。解を適当に組み替えることで貪欲に選んだ場合と一致させられることを示す、という方針だった。最近似たような問題を見たのを覚えていた。次にNが他の2人によって通された。ソートする比較関数でガチャを回すやつで、チームメイトによって証明がつけられていてなるほどなあとなった。順位表を見るとFが通されていたので読む。これはすぐ解けた。戦法が2種類あって、どちらにどれだけ操作回数を割り振るかを全探索すると、あとは貪欲でいいので差分更新ができる。

その後Cを考え、2以上の要素の個数がかなり少ないことを考察してからちょっとパソコンを借りて実験を回した。要素がすべて2以上の整数であるような配列であって、総積引く総和が $2\times 10^5$ 以下になるようなものを探索。5e8個くらいあるようで普通に配列を全探索すると間に合わないが、出現する値の頻度分布なら全探索できそうだった。改めて実験はしなかったので、書き上げて実行するとめちゃくちゃ時間がかかったのを見て血の気が引いたが、1か所オーバーフローでループのbreakがうまくいっていなかったのを直したら爆速になり、通った。Cを書き始めるちょっと前からJが挑戦されていて、数回のWAの末に通っていた。

Kは最初に消すことになる最小の頂点番号を持つ葉の親を仮の根とするのがうまい手で、その親が葉になるまで部分木を貪欲に消した後は、残った部分木も消すか、グラフ全体を再度再帰的に解くかの2通りになる。最初WAが出て、dfsが正しく回っていないバグを直したら、直線グラフのケースで $O(n)$ 回グラフ全体のdfsをすることになって困っていた。しかしdfsの根は1つずつしかずれないので、再計算する必要がないことに気づいて難を逃れた。最悪ケースは直線グラフで、手元では1.3secくらいかかっていたが、ジャッジは0.6secくらいで爆速だった。次にEが燃やす埋めるっぽいという話になって、自分ではどう弄っても条件がうまく表現できなかったが、頭の良いライブラリを見つけてきてそれに投げてみればいいんじゃないか？と言い残し、しばらくHを考えているうちにいつの間にか通っていた。実際にどのくらいライブラリに頼ったのかは不明。

koyumeishi.hatenablog.com

Gは、Hの考察を交代して行ったチームメイトが瞬殺していた。Hは全然わからないので、考察メモに残されていた $O(n^{2.5})$ を通りそうだと強固に主張して書き始めてもらった。このあたりで4時間が経過し、ARCに移動した。

僕がARCに逃亡した後の話。結局Hは先ほどの計算量の元になったコードで通ったらしい。ジャッジが爆速だったのではなく、計算量の評価が違っていたようだ。2乗の木dpで配列を $K$ 番目までで打ち切ると、計算量が $O(NK)$ になるという話を聞いた。全然納得できなかったので調べてみたら、すぐに見覚えのあるブログ記事が見つかった。やはりこういうものを読むだけ読んでも問題を解かないと本番で役に立たないようだ。

木と計算量前編〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

午後9時からARC130。4完29位。崖が大きい。

AtCoder Regular Contest 130 - AtCoder

Aは削除した文字が等しくなる場合の数と誤読してサンプルも試さず提出し、WA。冷静になると連続する同じ文字たちから2文字選ぶ場合の数になる。コードゴルフしやすそうな見た目をしていたので5分くらい粘着していたが、思ったより短くならなかった。Bは操作を逆順に見る典型で、それどころか問題設定からかなり見覚えがある。Cは繰り上がりの回数を最大化すればよいらしい。繰り上がりする桁は下に詰めることができて、そうすると考えることが単純になる。まず1桁目で繰り上がりを起こして、以降桁同士の和が9を超えられる限りそれを並べていけばよい。並べるのは小さい値から貪欲に行えばよいが、1桁目はどうするのが最適か全然わからない。しかしこれだけは全探索できる。かなり考察がスムーズに行って、ここでいったん順位表を見るとかなり上のほうにいてびっくり。

Dを解く。頂点の大小関係で辺を張ると、二部グラフであって片方からもう片方にしか辺が張られないようなDAGになる。これのトポロジカルソート順を数え上げられないか考えていたが、うまくいかない。もう一度問題に立ち戻ってみると、グラフが木であるという条件を使えていないことに気づいた。これを生かそうとすると木dpが思い浮かんで、自然な流れで2乗の木dpを考えてみようという気になった。つまり、サイズ $c_l$ と $c_r$ の部分木があって、それらに値を割り振って部分木の根の値が小さいほうから $l$ 番目と $r$ 番目になった場合の数から、マージして部分木の根のうち大きな方が $k$ 番目に来る場合の数を求めたい。もともとサイズ $c_r$ の部分木の根だったもののほうが値が大きくなった場合を考える。このとき、 $l+i\le c_l$ なる $i$ に対して $k=l+r+i$ の場合の係数が $\binom{l+r+i-1}{r-1}\times\binom{(c_l-l-i)+(c_r-r)}{c_r-r}$ と求まる。これは $l'=l+i$ と置けば、 $1\le l\le l'$ を満たすような $l$ すべてに対して係数が等しくなるため、累積和を求めておけば各 $l',r$ に対して定数時間で求められる。部分木を入れ替えたものも同様に計算できて、これで2乗の木dpのマージ部分が書けた。実装は、辺が $\lt$ と $\gt$ のどちらに対応するかでコードを変えるのが面倒だったため、毎回列をreverseして片方のタイプの辺だけ考えつつ、最後に答えを2倍することにした。かなり単純になってくれて気持ちがよかった。また順位表を見ると、相変わらず上のほうにいた。

Eに1時間ちょっと残せたが、実装が終わったのすらギリギリで、しかも全然合わなかった。これについては今日の日記の最後に書く。コードゴルフはA問題のみ、コンテスト中に書いたものが最短になっている。

午後11時半からCF combined。疲れているのか頭がふわふわしていた。

Dashboard - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

Aは $i\lt j$ を幻視してdpを書き、サンプルが合わなくて誤読に気づいた。誤読しなければ簡単。Bは"abc"が重ならないので、長さ3の部分文字列を全部見ればよい。更新するときは関係する高々3つの部分文字列をチェックする。"abc"を"ABC"と大文字にしていて、サンプルが合わずしばらく困っていた。Cは後ろから見て、2以上の要素の出現を直近2回分、インデックス $i$ について $i\bmod e$ ごとに保存しておけばよい。素数判定も必要になる。DはUFをマージしていくと目的の達成に使わない辺の本数がわかるので、毎回それを使ってできるだけ大きな集合を作ればよい。ここまで考察すれば、制約が小さいので、集合のサイズを毎回全部取得してソートして足すのが間に合う。

Eは難しかった。まずクエリなしの場合を考えると、一番左の'a'と一番右の'c'の間に'b'が存在しないようにするとわかる。先頭からどこまでは'a'を消して、末尾からどこまでは'c'を消して、と考えると、結局ある $i\le j$ が存在して $[0,i)$ に'a'が存在せず、 $[i,j)$ に'b'が存在せず、 $[j,n)$ に'c'が存在しないようにできればよい。実はより一般に、ある文字列 $S$ が文字列 $T$ を（連続するとは限らない）部分列に持たないためには、文字列 $S$ の $|T|$ 個の（連続する）部分文字列への分割であって、 $i$ 番目の部分文字列が $T_i$ を含まないようなものが存在すればよいらしい。 $\Leftarrow$ は、区間を固定して先頭から当てはめようとしてみれば、不可能なことがわかるので示せる。 $\Rightarrow$ は、 $T_1$ を含まない区間を先頭から貪欲に取ると、~~残りの文字列が $T[1:$ ]を部分文字列に持ってはいけないので、~~帰納法が回る。

2021/11/29追記： $\Rightarrow$ は嘘だった。反例として $S=01$ 、 $T=00$ がある。実は文字列 $T$ の隣り合う文字が異なれば正しいらしい。これは、打消し線の下の事実が正しく成り立つことからもわかるし、区間への分割を貪欲法で行うのが最適という観察から、それで分割できなかった場合のことを考えると、対偶を示すこともできる。

(S, T) = (01, 00) で成立しますか？
— 熨斗袋 (@noshi91) 2021年11月29日

貪欲が明らかに最適です
貪欲で取り切れなかった場合を考えてみましょう
一個先の最初の文字はかならずパターン文字列の次の文字です
しかも隣り合ったやつは違うので分割区間は空にはなりえません
— のいみ (@noimi_kyopro) 2021年11月29日

今、 $A_i$ を、 $[0,i)$ の'a'の個数引く'b'の個数とし、 $B_i$ を $[0,i)$ の'b'の個数引く'c'の個数とし、文字列中の'c'の個数を $cnt_c$ とすると、最小コストは $\min_{i\le j}A_i+B_j+cnt_c$ になる。 $C_i=A_i+\min_{i\le j}B_j$ とおくと、 $\{B_i\}$ と $\{C_i\}$ がそれぞれ区間ADD区間MINの遅延セグメント木で取り扱える。 $i$ 番目の変更を考える。 $\{A_i\}$ への影響は常に数列の右端までの区間ADDになり、直接 $\{C_i\}$ に書き込めばよい。 $\{B_i\}$ への影響は $\pm 1$ ごとに分解して考える必要がある。まず更新前の値で $x=\min_{i\le j}B_j$ を計算して、 $+1$ の場合は $x\lt\min_{l\le j\lt i}B_j$ なる最小の $l$ に対し $C[l:$ ]に1加算、 $-1$ の場合は先ほどの $x$ が $x-1$ になって $C[l:$ ]から1減算、とする。その後 $B[i:$ ]に変更分を足して、分解した $\pm 1$ がまだ残っていればそれを処理する、という流れになる。 $l$ の探索はセグメント木上の二分探索で行った。

Fは解けなかった。右端を固定して左端を動かしたとき、stackを使って最大値・最小値それぞれについてどの値がどのくらいの区間で出現するかを計算できる。これを60種類のpopcntそれぞれについて遅延セグメント木の区間加算で表現して、最小値と最大値両方が同じpopcnt数の場所の数、つまり遅延セグメント木で $2$ が入っている場所の個数を求めたい。これはその遅延セグメント木によって全体の総和と奇数（つまり $1$ ）の個数を取得し、引き算して2で割ることで求まる。計算量は $O(n(\log n+\log \max a_i))$ だが、全然通らなかった。まず遅延セグメント木を60本持つとMLEして、1本持って60回のループ中で使いまわす形にするとTLEした。区間をsetで管理してみたが、これはそもそも被っている区間を求めるときの計算量の保証ができない。しかしコンテスト終了ギリギリだったので、書き上げてええいままよと出してみたら、一応これまでより2ケースだけ進んだところでTLEしていた。

129位で2901→2837(-64)。あっという間に見覚えのあるレートに落ちてきてしまった。つらい。また大当たりを引くまでは雌伏の時、というよりは、大当たりを引きたかったら精進をしなければならない。漫然とコンテストに出ているだけでは強くなれないが、今はコンテストに出るのが楽しすぎてupsolveを放り出している。

ARC-E問題を解いた。頑張って何も見ず96/99まで通ったが、最後はTLでテストケースを見てしまった。

E で虐殺していたケースの1つ↓
5 7
5 1 3 5 3 5 4
— てんぷら (@tempura_cpp) 2021年11月28日

$i_1$ で $I$ を分割する。分割された区間のうち今見ているものを $[l,r)$ とする。直前の $i_{l-1}=i_1$ に対する操作で値が $x$ になっていた場合、 $[l,r)$ で操作された値は $x$ に確定するか、 $\{x,x+1\}$ のどちらか未確定になるか、 $x+1$ に確定する。これらはこの順番で区間に並ぶことになる。それぞれどれに確定したかを持って次の区間に進むとする。

まず簡単なものから、 $i_{[l,r)}$ に同じ値が3回以上出現してはいけない。 $i_a$ と $i_b$ で2回出現した場合、 $i_{[l,a]}$ による操作では $x$ になることが確定し、 $i_{[b,r)}$ による操作では $x+1$ になることが確定する。また、直前の区間で $x-1$ や $x$ に確定した値を操作する場合も確定する。さらに、直前の区間で未確定だった値も、今確定した影響で確定する可能性がある。この「未確定だった値が確定する」のがややこしくて、例えば $\{x-1,x\}$ から $x-1$ に確定した場合、区間でそれより前に並んでいたものも一斉に $x-1$ に確定する。 $x$ に確定した場合は、それより後ろが確定する。これで確定した値たちについても先ほどのチェックをもう一回しなければならない。書いていて気付いたが、このループは2回以上繰り返される可能性がある。自分のACコードでは1回しかチェックしていない。

また、前の区間で操作された値が今見ている区間で操作されない場合もカバーする必要がある。これは、以降さらに $i_1$ に操作するか、つまり $r\lt N$ であるかどうかによっても処理が変わる。どちらにせよ $x$ に確定した値はそのままでよく、 $x-1$ に確定した値は $r\lt N$ なら即座に-1を出力、そうでなくとも最後に $x+1$ に確定した値が存在すればこれまた-1を出力することになる。 $\{x-1,x\}$ で未確定の値については基本的に $x$ に揃えることになるが、先ほど述べた判定を回避して $x-1$ のまま生き永らえることが可能ならば、 $x-1$ に揃えることになる。