02/13(月)

午後4時過ぎ起床。30分近くかけて布団から這い出し、インターン先定例会に参加した。

進捗報告の場で共有されたことだが、自分が書いたコードがデプロイされた先でバグり散らかしていたらしい。すでに原因も特定されており、改めて見てみるとなんで気づかなかったんだと思うような単純なミスで愕然とした。一度正しく動くコードを書いた後、対応できていないケースが将来的に存在し得ることを発見し修正した部分。その修正が十分な範囲に及んでいなかった。

一応手元で書き換える前と後で出力が変化しないことを確かめたはずだから、試すデータが十分でなかったと考えていた。しかし今改めて思い返すと、ここがバグっていたら結構盛大に出力が変わるはずだから、もしかしたらそういうテストを全くしていなかったのかもしれない。目視でチェックしただけでいいやと思ってしまいかねないくらいの、本当に小さな範囲の修正だったのだ。

自分の見える範囲を離れた先でバグったということで、影響範囲が実感できない。だからこのバグが及ぼした影響も理解しておらず、正直な話いまいち真剣になり切れていない。一方で過剰に気に病むのも良いことではない。バグが発生するのは仕方ないから減らす努力をしましょうということを言われた。とりあえずはテストの充実化だろう。

その他は自分の進捗報告も含め特に何事もなく終了。勉強会は発表者が変わりつつ先週に引き続きAHC017の話だった。先週紹介されたDynamic Connectivityは実用性に疑問が残ると感じたが、今日は実際に高速化に寄与したいくつかの手法が紹介された。大体はグラフが平面的で、さらに辺のコストと頂点のユークリッド距離がほぼ等しいことに由来していると考えている。

試していないこととしてdijkstraを行う際の優先度付きキューをC++標準のものからフィボナッチヒープに切り替える高速化が挙げられたが、それが効くケースが出現しそうにないという理由で効果がないものと考えている。少なくともオーダー的な改善は $M=O(N)$ なので存在しない。しかし自分も試していないため断言はできない。

先週同様質疑応答が盛り上がり午後8時終了。それからずっと週記を書いていて、日付が変わる直前にギリギリ投稿できた。今朝方何気なくJOI本選オープンに出たら週記を各時間を失った上書く内容も増えて大変だった。もともと今日は午後11時半からECRがある予定だったが、いつの間にか木曜日にずれていて助かった。

他人のブログ記事をいくつか読んだ後セミナー準備を開始し、午前6時くらいに完成した。今日は前回の残りがなかったため多少時間がかかったが、なんと明日は先生の用事で午後2時開始となっている。つまりこの時間まで起きていても全く問題ないのだ。

ゴミを出した。ほんの少し雪がちらついていてびっくり。天気予報によれば昼過ぎには止んでいるらしいし、今のところ路面に雪も積もっていないので、原付で登校できるだろう。

セミナーが午後2時開始という余裕と、原付で登校できるという余裕が合わさって、うっかり午前9時までラノベを読んでしまった。急いで就寝。

02/14(火)

なかなか起きられず、午後1時45分になってようやく布団から出た。原付で向かわないとギリギリの時間。しかし外を見るとまだ雪が降っていた。朝より勢いが増してすらいる。しばらく迷ったが地下鉄で登校することにした。この時点で大遅刻が確定したため先生にメールで連絡しておいた。

午後2時半にようやく教室に到着。その上買ってきた昼食を食べ始めるという有様だったが先生からは特に何も言われなかった。まあ何も言われないだろうと思っているからやっている。そういえば、昨年度の4年ゼミで同様のことをしたときは叱られたのだった。

教室に入って一息ついた段階で、途中で購買で買ったパンを食べようと思ったら、先生に止められた。僕はその時、本当にそのタイミングでパンを食べてよいと考えていた
週記（2021/12/06-2021/12/12） - kotatsugameの日記

午後3時半ごろまでは同級生の発表だった。今回から、正確には前回からグラフ理論の教科書を読んでいるらしい。自分が読んでいるDiestelとは違うもの。まずグラフの閉曲面への埋め込みに関する章を読み進めるようで、今日はその導入だった。自分もちょうどいまDiestelで平面グラフの章をやっているので、関連がいろいろあるだろうと楽しみにしている。

少し休憩して午後4時前から自分の発表。今日は準備してきたうち半分しか終わらなかった。また発表中、準備時に犯したミスにたくさん気づいた。幸い今日発覚したものはその場で修正できたから良かったが、こういうことが続くのはまずい。原因は明らかで、前日になって初めて教科書を読み、同時にメモを作っているからだ。何回か読むくらいは最低限やるべきなのだろう。

先週日記にも書いた以下の疑問についてTwitterのほうでリプライを頂いたので、セミナーの合間に少しやり取りしていた。足し算も階乗も原始再帰的だが、それと今の $\Pi_1$ 文などの話は関係なかったということらしい。講義資料で隣接しており混同してしまっていた。

「素数が無限個存在する」、つまり「どんな数にもそれより大きな素数が存在する」ことを表すΠ1 Π 1 文を書く問題の解説がよくわからなかった。
週記（2023/02/06-2023/02/12） - kotatsugameの日記

素数判定の論理式で掛け算を使っているように、足し算や掛け算は普通考える算術に含まれるので変数の上界にも使えて、階乗はちゃんと $\Pi_1$ 文の範囲で再帰的に定義しなければ使えない。この観点から解答例を確認すると確かにそうしていた。なかなか誤植がひどくて意図を汲み取れていなかった。

学食で友人と会い、夕食を共にしてから午後7時過ぎ帰宅。早々に布団に入って寝落ちした。

02/15(水)

午前0時半に目を覚ました。先週末、というか月曜日の朝型オープンコンテストに参加したJOI本選のジャッジがAtCoderで公開されていた。オープンで提出したコードを一通り出したが特に得点の変化はなかった。

JOI 2022/2023 本選過去問 - AtCoder

Bだけコードゴルフした。SCCは想定解ではなかった。 $|X_i-X_j|\le E_i-E_j$ という式を、絶対値を $\max$ で置き換えることでバラすと $X_i-X_j\le E_i-E_j$ かつ $X_j-X_i\le E_i-E_j$ という式が得られる。それぞれ添え字を不等号の片方にまとめると $E_i-X_i\ge E_j-X_j$ 、 $E_i+X_i\ge E_j+X_j$ となる。

つまり各住人を $(E-X,E+X)$ にプロットしたとき、右上に他の住人がいない人を数えればよい。点を適当にソートすればできる。bashで書いたものが現在の最短となっている。

食事して布団に戻り、しばらくなろうを読んで午前5時くらいに寝落ち。

午後2時にまた目を覚ました。購買に行きたいが、すでに春休み期間に突入しているためあと1時間で閉店してしまう。それまでに起きて、シャワーを浴びて、歩いて大学へ……と考えるとどうにも気力が湧かなかった。布団に横たわったままなろうを読んでいるうちに閉店時間を過ぎ、その後午後5時にまた寝落ちした。

午後7時過ぎにまたまた目を覚ました。今回は特に何かしようとすることもなくひたすらなろうを読み続け、日付が変わるくらいに寝落ち。

02/16(木)

午前3時起床。昨日はずっと布団の上でなろうを読んでいるだけだった。食事も丸一日摂っていないのでひどく空腹。2時間ほど耐えてなろうを読み続けていたが、さすがに身を起こして食べ物を口にした。

トヨタコンのオンサイトで泊まるためのホテルを探した。いいものがまったく見つからない。最寄りが渋谷駅であるようなホテルはすべて目が飛び出るほど高い。その中でThe Millennials 渋谷というホテルは値段もちょうど良いし写真も綺麗だったが、よくよく調べるとカプセルホテルだった。それで普通のホテルと変わらない値段をしているというのは自分の常識の埒外にある。

渋谷駅から少し離れるとようやくそこそこの値段の宿が見つかった。いくつか見繕ったところで今日は終わり。

しばらく日記を書いた後、ラノベの注文をした。3月発売の新刊を中心に17冊。今回チェックした中で最も驚いたのは以下の本。カクヨムで読んだことのある作品の書籍化だが、そういう企画が進行しているのを全く知らなかった。覚えていなかっただけかもしれない。

famitsubunko.jp

kakuyomu.jp

昼過ぎに少しだけ生協に行った。今日は非常に天気が良く路面に積もった雪がすっかり解けたため、原付が使える。日陰に止めてあってまだ座面に氷が張っていたので、手で少し剥がしてから乗ったが、太陽の下に出たら残りもすぐに溶け消えた。最初からそうしておけばよかった。

予約していたラノベを受け取ったり菓子パンを買ったり昼食を摂ったりして帰宅。布団に入ってラノベを読み、午後3時前就寝。

午後8時半ごろに目を覚ましてずっとなろうを読んでいた。午後11時半からECR143。

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

Aは $s+{\rm rev}(t)$ をどこで切るかという問題なので、この文字列で同じ文字が隣接するのが1か所以下かを判定する。

Bは $l=k$ という線分がないと $f(k-1)\lt f(k)$ とできず、同様に $r=k$ という線分も必ず必要。逆にそのような線分だけ選べば条件を満たせるので、これが十分条件でもある。

Cはお茶 $i$ を味見役 $j$ がどれだけ飲むか考えると、 $j\lt i$ なら当然0、そうでない場合あるインデックス $r$ が存在して $i\le j\lt r$ なら $B_j$ 、 $j=r$ なら $A_i$ の残り、 $r\lt j$ なら0という風に分かれる。この $r$ は $B$ の累積和上で二分探索することで求まる。一々 $j$ に対して答えを加算していられないので、 $B_jx_j+y_j$ という形で持って $x$ をimos法で更新した。

Dは、一つの三角形をどのように塗り分けても全体の重みに加算される辺は0本または2本となるから、すべて2本ずつ加算されるようにするのが最適で、実際に達成可能である。これで最大値は求まるのであとは数え上げ。まず各三角形について赤1個青2個で塗り分けるかその逆かを決める必要があって、全体で半々にする必要があるから ${}_{n/3}\mathrm{C}_{n/6}$ 通り。またどの辺を加算するかにも自由度があり得るので、三角形ごとに求めて掛け合わせる。

EはExplosionで選ぶ $i$ を全探索する。 $h_i$ を減らす理由はないので、左右独立に答えを求めて足すことを考える。右側だけ説明する。条件は $h_i\gt h_{i+1}$ だが、これを $h_i+i\ge h_{i+1}+(i+1)$ とすることで、単に右に見ていった時の累積MINに合わせればよいとわかる。同じ値で揃っている区間を持って更新していけばよい。 $h=0$ となってしまう部分は更新の度に取り除いておく。

Fは二分探索。操作回数を固定するとどの頂点から長さどれだけのパスを作ればよいかわかるので、本当に可能か木dpで求める。各頂点が持つのは「自分より下にいくつパスを伸ばせるか」または「自分より上にいくつパスを伸ばさなければならないか」で、なるべく葉のほうに押し付けながら遷移する。

Gは制約の「 $p$ は必ず一通り以上存在する」というところから考察を始めた。 $p_1$ となれる頂点は $a$ の値とグラフの次数が等しい必要がある。そのような頂点は複数ありうるが、どの二つについても隣接することはあり得ず、またどれを $p_1$ としても $p$ が作れるべき。以下同様に、すでに選んだ頂点に隣接する点の次数を減らしていって一度 $a$ と等しくなった頂点は、その後どのタイミングで選んでもよい。

逆にこれに違反するような順番では $p$ は作れない。具体的には、どの隣接する2頂点も $p$ でどちらが先に並ぶかは固定されている。この関係はDAGになっていて、 $x$ から $y$ あるいは $y$ から $x$ に到達可能なペア $(x,y)$ のみがniceでない。その数え上げはbit並列による $O(N^2/w)$ しか知らないが、TLを確認すると4secだったので自信を持って提出。2sec弱で通った。後から頂点番号をトポロジカルソート順に振りなおしてメモリアクセスの効率化を図ったら1secを切った。

ちょうど1時間でノーペナ全完、2位。かなりうまくいったから手元動画を撮っておけばよかった。それにしても1位のtouristが圧倒的すぎる。

そのままTCB55に参加した。日曜日終了だからここに感想を云々かんぬん。こういう注意書きはどんな形であれ書いておく必要があると信じる。

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

4問目まではよい。5問目は $\max(w_1,\dots,w_i)=i$ となるような $i$ で切れるので、それを数える。6問目は、各整数についてそれが出現する最も左の位置を $l$ とおくと、その整数が $B_l,\dots,B_N$ に1ずつ寄与しているので、 $l$ をsetを使って管理する。

7問目。まずインデックス $\bmod M$ で等しいとき集合も等しいということを満たしたい。対応する集合の共通部分を取っておくと、その部分集合なら何にでも揃えられることがわかる。よって残りは集合が等しければインデックス $\bmod M$ が等しいということを満たすだけ。

$\{0,\dots,9\}$ のすべての部分集合について、それに含まれる集合にしか揃えられないインデックスを数え、作れる部分集合の数より大きくなっていないか確かめるというコードを書いた。しかしWA。集合の要素がもともと0-indexedなのに1引いているのに気づき直したがまだ1ケース落ちている。

実はこの判定方法が怪しいことはわかっていた。じゃあなんで提出したのかという話だが。冷静になるとインデックスと集合を対応付ける二部マッチングで解ける。2WAしたので-22pt。TechFULのコンテストでペナを付けるのはかなり久しぶりな気がする。

8問目。手で実験すると、 $S_k$ の先頭 $(k-1)!$ 項の操作を行うごとに数列は先頭 $k$ 項が後ろに一つrotateされるとわかる。この操作列は同じものが繰り返して $k-1$ 回現れているから、例えば入力だと最初の $a_{N-1}(N-1)!$ 回の操作で数列全体が $a_{N-1}$ 回rotateされることになる。さらに残りの操作列は $S_{N-1}$ だと思ってもよいので、以下再帰的に処理できる。

実装では、数列がrotateされた回数を管理しつつ、 $a_i$ を処理するタイミングで $v_{i+1}$ の値を確定させていった。残っている数のうち何番目に大きい数が該当するかわかるので、BIT上で二分探索して取得すればよい。

9問目は準開基を知っていますかという問題で、知っているので解ける。 $\mathfrak{M}$ （に $\{0,\dots,N-1\}$ を追加したもの）から有限個の元を取ってきて共通部分を求めると開基になっていて、この開基に任意個の和集合を取る操作で閉じるように集合を追加したものが $\mathfrak{M}$ を含む最小の位相になっている。自分は学部2年で習った。

上に書いた手順をそのまま実装すればよい。開基 $\mathfrak{B}$ を求める際は、 $O\subset\{0,\dots,N-1\}$ が入っていることを $\bigcap\{O_i\in\mathfrak{M}\mid O\subset O_i\}=O$ によって判定する。そこから作る位相に $U\subset\{0,\dots,N-1\}$ が入っているかは、 $\bigcup\{O\in\mathfrak{B}\mid O\subset U\}=U$ によって判定する。前者で適当に包除原理を使ったら2個以下の共通部分しか求めておらず1WA、-15pt。

10問目は結構面白かった。各 $X$ に対し $f^K(X)=X$ を達成する $f$ を数える。この $X$ はすべてループに乗るから、まずそのループだけ考える。「これまでいくつの要素の行き先を決めたか」と「そのうちいくつを $X$ に含めたか」を持つ2次元dpを書いた。

それぞれ $i$ 、 $j$ とおく。次に作るループの長さを $l$ とすると、ループへの要素の並べ方が円順列を考えて ${}_{i+l-1}\mathrm{P}_{l-1}$ 通りある。このループを $K$ ステップ進むと、要素は $g=\gcd(l,K)$ としてサイズ $l/g$ のブロック $g$ 個に分かれるから、 $0\lt n\le g$ に対し $X$ に $n\times l/g$ 個追加する方法が $\binom g n$ 通りある。重複して数えるのを避けるため $n=0$ は許していない。

最後にすべての $(i,j)$ について、求めた場合の数に残り $N-i$ 要素の選び方と行き先合わせて $\binom N i\times N^{N-i}$ を掛け、足し合わせれば答えが求まる。とりあえずこれでサンプルが合った。計算量が $\Omega(N^3)$ だが、よく見ると $j$ の情報を使っていない。これで $O(N^2)$ になってAC。正確には $\gcd$ を毎回求めているので $\log$ をつけている。少し時間がかかって-2pt。

合計で-39ptだった。今回の9問目は問題文の読解から完全に知識ゲーでヤバいと思う。「最小の位相」という用語に定義がないのが気になる。

朝まで日記を書いた後、1時間ほどインターンの進捗を産んだ。今日触ったコードはいずれ先週立てたサーバと通信して動かす予定だが、まだそこまで完成してはいない。

オンサイトのホテルを決めて予約した。もともと前泊のみの予定だったところ、イベント直後にUniversal Cupを走る予定になったので後泊もすることにした。本来なら少し余裕をもって仙台まで帰れるはずなので2泊分の宿泊費を出してもらえるかはわからない。ダメだと言われたら1泊分は自分で払う予定だ。いろいろ探して、伝えられていた相場より少し休めのホテルにした。

実は上のほうで触れたカプセルホテルThe Millennials 渋谷には結構興味があった。共用部が充実していると聞いたから談話室みたいなものを想像していて、そこで競プロ談義したら楽しいだろうなと思っている。しかしコンテストに出るには向かないので避けた。

午前10時頃布団に入ったものの、なぜか目がさえていた。1時間近くYouTubeを眺めてようやく眠りに落ちた。

02/17(金)

午後2時直前に起床し1on1。

今朝がた産んだ進捗を説明した後、サーバと通信できるようにしようとしたが、認証回りがうまくいかない。2時間の1on1のうちほとんどをこれに費やした。結局1on1終了後少し経ってから解決したらしく、方法を教えていただいた。以下その説明。単に技術的な話題なのでここに書いてもよいだろう。

やりたいことというのは、Basic認証の先にあるAPIを叩くことだった。Basic認証を突破するために、AuthorizationリクエストヘッダーにIDとパスを渡す必要がある。一方でAPIを叩くためには同じ方法でTokenを渡す必要がある。これが被っていて、同時に渡す手段がなく困っていた。

APIのTokenを別のヘッダーで与える方法で解決できたようだ。Basic認証をかけているnginxの設定ファイルを書き換えることで、そこを通過する際にToken情報を正しいヘッダーに渡すことができる。もともとそこに入っていたIDとパスはすでに使い終わっているから必要ない。あとは通常の通信と同様に進むということらしい。

また1on1後に月曜日に言及したバグが修正されたので、自分でも直っているか確かめていた。手元で実行したら修正前後の出力で大量にdiffが出たので、どうやらバグを埋め込んだ当時は本当にチェックせずコードをpushしてしまったらしい。大反省。

午後6時前に外出。まぜそばを食べてゲーセンに向かい閉店まで遊んだ。今日は眠くて大変だったが、なんだかんだ理論値を四つ出した。マーシャル・マキシマイザーは好きな曲なので頑張って粘着した。手元動画も撮った。

今日の理論値 pic.twitter.com/25V1phc3Ga
— こたつがめ (@kotatsugame_t) 2023年2月17日

マーシャル・マキシマイザー理論値手元 pic.twitter.com/B5Htz4l3cu
— こたつがめ (@kotatsugame_t) 2023年2月17日

閉店後立ち食いそばを食べ、ドンキで菓子パンやお菓子を買い込んで帰宅。途中にある公園でブランコを漕いだりして少し遊んでいた。

#東北大学深夜徘徊サークル pic.twitter.com/YJbGFXaDm1
— こたつがめ (@kotatsugame_t) 2023年2月17日

帰宅してから手元動画を投稿し、シャワーを浴びて布団へ。ラノベを開き、「才女のお世話」4巻を読了した。

3巻を読んだのは半年以上前らしい。その巻のヒロインが幼馴染ポジションだと思っていたが、彼女は一時期共に過ごしていただけで、この巻のヒロインこそが真の幼馴染だった。名前だけは1巻から出ていたので、いよいよ登場かと思うと嬉しさがある。

主人公の成長を彼女は知らない、ということがこの巻のメインだったと思う。最後に解決するまではなかなか辛い展開だった。舞台となった夏季講習で主人公が受けている授業の内容が彼女にとっては非常に難しく、少しわかると虚勢を張りつつ主人公も太刀打ちできないだろうと思っていたら、かなり良い成績を叩き出されて愕然……という描写があった。特に虚勢を張るあたりがなかなか自分に刺さった。

個々のシーンとしては好みのものが多かった。夏期講習の場でも、休日の海水浴でも、ヒロインたちは注目を浴びている。主人公がそういうところに意識的なので、自然に関連する描写が増えて嬉しい。

午前7時就寝。

02/18(土)

正午直前に起床してAHC018開始と同時に問題を読み、提出はせずまた寝た。このタイミングで問題を読んだことは順位表から分からないが、これくらいは書いていいだろうと思っている。

RECRUIT Nihonbashi Half Marathon 2023 Winter（AtCoder Heuristic Contest 018） - AtCoder

今度は午後2時直前に起床してUniversal Cup 4回目に参加した。今日のセットはUkraine由来。問題文が短くて非常に読みやすかった。チームでAEIKFCBJを解き、8完66位。自分はAKCBを担当した。

Dashboard - Anton Trygub Contest 1 (The 1st Universal Cup, Stage 4: Ukraine) - Codeforces

先頭から順番に読み始めた。Aの問題概要を理解した後、すぐにはわからないと思ってBに進んだが、一番最初にFAが出たので慌てて戻ってきた。よくわからないままサンプルの四つ目を見てそれっぽく並べ、しばらく証明っぽいものを考えたり順位表でほとんどペナが出ていないのを確かめたりしてから提出。無事通った。結局証明はできていない。

次にFAが早かったEがかっつさんによって通された。二度ほど提出して両方落ちたかに見えていたが、いつの間にかリジャッジが来ていて最初の提出が通っていた。

solved数を見てぷらさんがIに、自分がKに取り組んで、立て続けに通った。Kは半ばエスパーで強連結成分が1個かチェックするコードを出した。

全頂点を通る有向閉路が取れればその閉路に沿って要素を並べられ、その後好きな順列にできることは分かっているが、関節点があるとどうなるかよくわかっていなかった。日記を書いているときに改めて考え、有向閉路の上で好きに並べ替えられるのだから適当にswapを実現すればよいことに気づいた。

この後自分がC、ぷらさんがB、かっつさんがFに取り組んでいた。少し経ってからFが通り、自分もCを通した。

基本的には左からdpしていく。見ている位置より左にあるパスの数が状態。閉路の重みを最小化するのだから、新しい頂点を追加するときはできるだけそれを使って2本のパスを繋げたい。繋げるパスがない場合は新しく1頂点のパスを追加するしかない。あるいは、このタイミングで繋ごうとすると小さな閉路になってしまうケースもあって、その場合はどちらかの端点を伸ばすだけになる。

以上3種類の遷移のうちどれが行われるかは、見ている位置より左にあるWとBの数の差が1歩右に進むことでどう変化するかによってのみ変わる。つまり状態数が常に　たった一つなので十分間に合いそう。しかしよく考えると、長さ2以上のパスはどちらの端点で繋げるかで2通りの自由度があるのに、長さ1のパスはどちらも変わらない。これらを考慮して場合の数を求める必要がある。

長さ1のパスの本数を持ちたくなったが、実はパスを作る・伸ばすときに次に使う端点も決めてしまうことで、変わらず一つの状態で扱える。場合の数を2倍するのを先に行っておくというアイディア。最後、閉路にするときだけ端点を区別しなくてよいので、答えを2で割ってから出力する。頂点は四つ以上あるので必ず不必要な2倍が行われている。

以上の説明はコンテスト後に考えたもの。コンテスト中は端点が2本または1本生えている頂点がたくさんあるという捉え方だったので、端点を二つ繋ぐとその相方同士を新しくペアにして考えてよいということに気付くのにも時間がかかったし、2倍するタイミングも結構ガチャガチャして無理やりサンプルを合わせていた。

ぷらさんがBで詰まっていたのでバトンタッチした。このタイミングでは自分がB、ぷらさんがJ、かっつさんがDに取り組んでいた。

BはFAが9分だしこの時点でsolved数もかなりある簡単枠に見えていたのに、取り組んでみるとかなり苦労した。実験結果から同一の $n$ に対して $\gcd(n,k)$ が同じなら答えも同じになるようだったので、 $k\leftarrow\gcd(n,k)$ として考えることにした。

最も単純なケースでは、同じ周期 $k$ を持ち1周期の和が一致する $a$ と $b$ について $f(a)=f(b)$ である。これでは十分に重複を省けていないが、 $k$ 項ごとに区切るのは良いのではないかと考えた。 $f(a)_2=f(a)_1-a_1+a_{k+1}$ なので、 $k$ 項ごとの値の変化に注目する。01列の値の変化と言えばXORである。

長さ $n$ の01列を先頭 $k$ 項とその後ろに分け、後者については値そのものではなく、ちょうど $k$ 項前の値とのXOR $n-k$ 個で表現する。こうしても当然 $2^n$ 通りあって、すべての数列を漏れなく重複なく表現できる。列 $a$ と $b$ が $f(a)=f(b)$ を満たす場合、この表現にどういう関係があるか考えた。

まず明らかに先頭 $k$ 項の和 $f(a)_1$ と $f(b)_1$ が一致している。さらに、そこから和を取る範囲を1項ずつずらした時の変化が等しいのだから、 $a_{k+1}-a_1=b_{k+1}-b_1$ のような関係が $n-k$ 個ある。正確には $n$ 個あるが最後の $k$ 個はそれ以外から復元できる。

この関係はほとんど $a_{k+1}\oplus a_1=b_{k+1}\oplus b_1$ なので、少なくとも表現における $n-k$ 個のXORは完全一致する。しかしこの書き換えは十分性を失っている。

XORが0の場合はよいが、1の場合例えば $a_1\ne b_1$ だとXORが一致しても差は一致しないことがわかる。逆に $1\le i\le k$ について $a_i\ne b_i$ なら $a_{k+i}\oplus a_i=a_{2k+i}\oplus a_{k+i}=\dots=0$ という条件を加えると十分になる。

ここでXOR $n-k$ 個を固定して数え上げることを考える。 $1\le i\le k$ で独立に扱えて、各 $i$ に対し $a_{k+i}\oplus a_i=a_{2k+i}\oplus a_{k+i}=\dots=0$ となるのが1通り、そうでないものが $2^{n/k-1}-1$ 通りある。前者をタイプ1、後者をタイプ2とし、タイプ2が $0\le c\le k$ 個あるとして先頭 $k$ 項について考えてみる。

改めて、そのようにXORを決めた元で $f(a)=f(b)$ となるような $a$ 、 $b$ の先頭 $k$ 項の関係を書く。まず総和が等しいことが一つ。次に、タイプ2に対応する $i$ では $a$ と $b$ の値が一致していることが一つ。これで必要十分なのだった。

重複を数え上げるのではなく $f(a)$ の種類を数え上げようとすると、タイプ2の部分が異なるか、タイプ2の部分で一致してもタイプ1の部分で総和が異なるようなものを考えればよい。前者は $2^c$ 通りあり、後者は $0\dots k-c$ の $k-c+1$ 通りある。

以上をまとめると、求めるものは $0\le c\le k$ に対する $\binom k c (2^{n/k-1}-1)^c2^c(k-c+1)$ の和となった。とりあえずこれで実験と答えが合う。マルチテストケースで $n$ の総和に制約がないので $O(n)$ のこの式は間に合わないが、Wolfram|Alphaに投げたら閉じた式になった。無事AC。

残り2時間。JとDで迷って、Dはよくわからない構築っぽいと感じたのでJをぷらさんと一緒に考えた。1回操作するごとに順列全体の転倒数の偶奇が変わるので、1回おきに答えが $n$ となる。そうでない場合を考える。まず自明なケースとして、順列がソート済みだと答えは-1。これは $p_i\gt p_{i+1}$ なる $i$ をsetで持っておくと差分更新でチェックできる。

そうでない場合、答えの下界は $n-2$ だと分かった。 $p_i\gt p_{i+1}$ なる $i$ で $p_i$ を取り除いても $p_{i+1}$ を取り除いても転倒数が偶数のままなら、両方一緒に取り除くことで奇数にできる。よって答えが $n-1$ かどうかを判定する問題になった。

ここで、各 $i$ に対し「 $p_i$ を取り除いたときの、転倒数の変化の偶奇」を管理する。 $p_u$ と $p_v$ をswapするとき、まず、その前後で $u$ と $v$ 以外のインデックスに対応する値は変化しない。

また $p_u$ から $p_v$ に変化したインデックス $u$ に対する値は偶奇が $|p_u-p_v|$ だけ変化するとわかる。 $(p_u,p_v]$ （あるいは $[p_v,p_u)$ ）の範囲にある $p$ との各ペアについて、転倒数に寄与する・寄与しないが一斉に切り替わるからだ。 $v$ も同様。

これで解けたので実装をぷらさんに託しNを考えていた。たくさん場合分けをして簡単なケースから考えていたが、メインのケースに突入する前に詰まってしまい、ちょうど書き上がってサンプルが合わないらしいJのデバッグに回ってその後戻ってこられなかった。

Jのコードを共有してもらってかなり長い間眺めていたが、まったくバグが見つからなかった。しかし手でサンプルを試した瞬間解法の伝達ミスを発見。上では $i$ について値を持っていたのに対し、コードでは $p_i$ について値を持っていたのだ。それ以外の考察にミスはなく、ここを修正したら即座にサンプルが合ってそのまま通った。このデバッグに1時間弱かけていて、手を動かさずコードを読むだけで済ませようとしたことを反省した。

最後の数分はDを考えていた。これまで何度も提出されていて、どれも落ちてしまっている。コードを読んでもよくわからず諦めモードで問題を眺めていたところ、ふと思いついた構築がどんぴしゃりの正解だった。 $a_{i,j}=1$ なる $i$ と $j$ の間すべてに辺を張り、条件を満たしているか確かめるというもの。残り5分くらいでかっつさんに急いで解法を伝え実装してもらったが間に合わなかった。

この構築の正当性について。まず $a_{i,j}=1$ なら $d_{i,j}=1$ となるため良い。そうでない場合頂点 $i$ と $j$ の間の最短経路は長さ偶数のパスとなってほしい。そのようなパスが存在するなら、適切に切ると頂点 $k$ であって $i$ と $k$ の間、 $k$ と $j$ の間の最短距離が奇数となるようなものが取れて、 $a_{i,k}=a_{k,j}=1$ となっているはず。よって今作ったグラフでは $i$ 、 $k$ 、 $j$ という長さ2のパスが存在し $d_{i,j}=2$ となる。

こういう考察をしておくと、「条件を満たしているか確かめる」と言いつつ実際は $a_{i,j}=0$ なる $i$ 、 $j$ に対して上のような $k$ が存在するかチェックするだけでよい。コンテスト終了後に自分で実装してみたらなんと2分で終わってしまった。中途半端に解法を伝えるのではなく、かっつさんから実装を奪い取って自分で書くのが正解ムーブだったらしい。

少し休憩してから感想戦。Eは三つ以下の分割さえ考えれば良いというのは典型的な考察だと思ったが、そのあとのチェックが思ったより大変そうだった。

Iは $a_{i,j}\leftarrow a_{i,j}-i-j+1$ と補正するとすべて0以上かつ $a_{n,m}\le 1$ より最大値が1となるようで、あとは行・列が「広義」単調増加となるように01を並べる問題。この初手は問題を読んですぐ出てきたらしいが頭が良すぎる。

Fはかっつさんによって2部グラフで長さ4のサイクルを求める問題に帰着され、自分がABCで既出だなあと言っている間にぷらさんが具体的な問題を見つけてきて下さった。

F - Find 4-cycle

自分はBとCの解法を整理できておらず、合わせて1時間近く話したうえ最後まで説明しきれなかった。感想戦をすることを自分から提案しておいてこの体たらくとは。上でその二つの問題について、特にBについて長々と書いたのは、それを埋め合わせとするつもりだったから。書き上げたのが日曜日の朝方で、無事広義でコンテスト当日のうちにチームに共有することができた。広義でというのは、自分がまだ寝ていないから当日中だということ。

そんなことがあって感想戦が終わったのは午後8時半だった。菓子パンを食べて午後9時からARC156。

AtCoder Regular Contest 156 - AtCoder

Aは場合分けを繰り返して解く。1の個数が2個でないケースはすぐ処理できる。そこから1回で達成できるケース、2回で達成できるケースを取り除くと残りは本当に少なくなって、個別に対処できる。実際の考察では最初に3回で達成できるケースを思いついていたので、特に引っかかることはなくノーペナで通った。

Bは簡単。最初から書かれている数を無視して新しく書き込んだ数の最大値を固定すると、それを達成するのに最低限必要な操作が一意に定まり、残りは最大値以下から多重集合を自由に決めるだけで重複なく数え上げられる。

Cは難しかった。サンプルが貧弱だが両方類似度が1なので、たぶん常に1とできるのだろうと考えた。木からある1点を取り除くとちょうど半分ずつの連結成分に分かれたとして、それぞれの番号が $P$ ではごっそり入れ替わっていると良さそうに見える。実際はダメダメだが、考察はここから得られた。

ちょうど半分ずつに分かれるというのは強すぎる仮定だから、適当に根を決めたときにそれぞれの部分木を入れ替えるくらいで考えておきたい。まず根の直接の子だけ見てみると、番号をrotateして $P$ とすることで、根を含めどの二つも同時に共通部分列に含まれないようにできていると気付いた。

ここから、同じ深さにある頂点を集めて番号をrotateすると良いのではないかと予想した。根以外のどの深さにも2頂点以上あってちゃんとrotateが行われているとし、適当に図を描いて確かめてみたところ、本当に類似度が1になっていた。パスの頂点の深さが順に上がって下がってという変化しかしないことを考えると、どの2頂点も $P$ においては逆順に出現してしまうとわかるので、これで証明もできた。

深さに関する条件は根を直径の中心の1点あるいは2点とすることで達成できる。実装してから $O(N)$ のコードになっていることに気づき、制約が $N\le 5000$ なのを訝しがりながら提出。ジャッジが微妙に遅いのを見て、ようやく類似度1の判定が $\Theta(N^2)$ なのだろうと感づいた。無事AC。

Dは面白かった。 $\sum A_X$ が等しい $X$ はたくさんあるだろうから、まず同じ値になる $X$ を数え上げ、それが奇数になるものだけ計算するという方針が立つ。 $c_j=\#\{X_i=j\}$ と定め、これについて考えた。 $c$ が同じなら当然 $\sum A_X$ は等しくなる。

$c$ に対して $X$ がいくつあるか数えるのは多項係数だが、二項係数の積で書くこともできる。 $\binom{K}{c_1}\binom{K-c_1}{c_2}\dots\binom{K-c_1-\dots-c_{N-1}}{c_N}$ だ。これが奇数だというのだから、Lucasの定理を $\bmod 2$ で適用できる。

整数を2べきの集合だと思うと、まず $c_1\subseteq K$ 。このとき $K-c_1$ と $K\setminus c_1$ を同一視することができて、 $c_2\subseteq K\setminus c_1$ となる。以下同様。よって考えるべき $c$ の条件は $\bigsqcup c=K$ となった。非交和であることに注意。

これでかなり状態数が減ったので、dpを考え始めた。 $c_1$ から順に決めるのは、和とXORにそれほど嬉しい関係がないためできない。一方 $K$ の立っているbitを下から $c$ のどれに割り振るか考えると解けるようになった。和において今後更新されない下のほうのbitを無視できるので、持っておく値の種類数が十分少なくなる。

実装したらサンプルが合ったがWA。しばらく考えて、無視してしまった「今後更新されない下のbit」の扱いにミスを見つけた。無視する際無条件で答えにXORしていたが、場合によっては答えに偶数回寄与するためXORしてはいけないものもある。具体的には、 $K$ においてまだ決めていないbitの数を $m$ 個とすると答えに $N^m$ 通り分寄与するため、その偶奇を見る必要があった。

かなり盛大なミスだと思ったが、確かにサンプルでは落ちないようだ。修正したら通った。

Eは解けなかった。条件が $S=\sum X$ として $S$ が偶数かつすべての $i$ について $X_i+X_{i+1}\le S/2$ だと分かったが、数え上げるのが面倒すぎる。包除をするつもりだった。 $X_i+X_{i+1}\gt S/2$ となるような $i$ について、実は同時に $X_{i+1}+X_{i+2}\gt S/2$ ともなれるので2個ある可能性があり大変。

$S$ が偶数という条件だけで数え上げるのはサイズが大きくて難しい。まずここが解けていない。一方包除で取り除くべきケースについては $X\le M$ より $S$ がそこそこ小さいので数か所で全探索を使えるのだが、 $O(1)$ で計算すべき場合の数もたくさんあって、それがひたすらしんどかった。変数の範囲に制限があって、二つの和が固定されていて、何通りありますか？みたいなものだ。

整理しきれず終了。4完14位だった。

コードゴルフはAのみで、入出力回りで大敗。範囲演算子をフリップフロップとして使う際の評価戦略を利用するテクはAWKならよく見るが、他の言語では初めて見た。行番号を簡単に見ることができるので今回強いようだ。そういう機能の存在は辛うじて見覚えがあるとはいえ、自力で思いつけるとはとても思えない。

perlop - Perl の演算子と優先順位 - perldoc.jp

ARCの動画を投稿した。手元でエンコードしてファイルサイズを落としてから投稿しようと思ったら、逆に2GBくらい増えてしまったため、今回も撮ってそのままアップロードしている。

www.youtube.com

しばらくなろうを読み、朝方まで日記を書き、布団に入ってからラノベ「才女のお世話」5巻を読了した。

前巻から引き続いて主人公の過去に焦点が当たっていた。メインヒロインがいよいよ自分の恋を自覚するという展開。これまでの恋と親愛をごっちゃにしたような甘えっぷりも良かったが、4巻に渡って十分堪能したので、ここで一歩進むことは歓迎したい。シーンとしては主人公が昔暮らしていた町をヒロインと歩いているときにヒロインの美しさで注目を浴びるところが好みだった。

シャワーを浴びて布団に入り、少しなろうを開いたところ一瞬で寝落ちした。正午くらいだった。

02/19(日)

午後7時半起床。コンテストに出る準備をした。今日は午後8時からCFで5時間コンテスト、さらにその間にいつもの時間でABCがある。両方同時に参加したが日記では別々に書く。

まずCFの5hから。

Dashboard - SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) - Codeforces

Aはよい。Bを読んで区間dpを書き始め、思ったより難しかったのでいったん諦めて以降はsolved数を見て開いていった。

Hは $b$ のsuffixで $a$ の部分列となるようなもののうち最長のものの長さを答える。

Lは $s$ に含まれる+、-を $p$ 個、 $n$ 個と置き、 $a$ のボタンを+で押したのが $p_a$ 回、-で押したのが $n_a$ 回とすると $(p_a-n_a)a+( (p-p_a)-(n-n_a))b=0$ が条件になって、整理すると $p_a-n_a=(n-p)b/(a-b)$ となる。 $a=b$ のケースに注意。 $p_a-n_a$ は $-n$ 以上 $p$ 以下の整数にしかなれないので、そうなっているか判定。

Fは基本的に、ある1頂点から出る辺とそれ以外の辺に分ければよい。次数が $n-1$ 未満の頂点を選べばそれで条件を満たせる。そのような頂点が存在しなければ完全グラフで、この場合1頂点から出る辺をさらに2分割することで対応できる。

Gを考えている間にABC開始時刻になり、2時間弱そちらに取り組んでいた。戻ってきて改めて考えても解けなかったため、いったん離れて別の問題を解いていった。

Bは相変わらず区間dp。マージの際一番下のブロックの位置に自由度があってどうしようかなと思っていたが、よく考えるとマージの対象となった区間の左端・右端のブロックからそれぞれ右下・左下に伸びる直線の交点にあると思ってよい。自由度とは実はそれだけしかないはずだ。よって区間以外の情報が必要なくなり、ちゃんと間に合うdpができる。

Jは結構面白かった。元の頂点が $2^k$ 倍になっているので、2進数で $k$ 桁の添え字をつけることで管理する。張られている辺は3タイプある。まず元の頂点が同じで添え字がちょうど1bit違う2頂点の間に辺がある。元のグラフにおける辺は、端点が同じ色なら同じ添え字を持つ頂点間の辺になり、違う色なら添え字が対称、つまり合わせると $2^k-1$ となる頂点間の辺となる。小さい範囲で実験して気づいた。

ここから実際に直径を求める。片方の端は対称性から添え字 $0$ の頂点だとしてよく、 $n$ 通り試すことにする。そこから元のグラフでBFSすることで、各頂点で添え字 $0$ の頂点までの距離、添え字 $2^k-1$ の頂点までの距離が求まる。

途中の頂点の中で添え字を変えるような移動を行うのは終点で行うのと変わりないので考えなくてよい。よって後は、どの添え字が一番遠いかをそれぞれの終点について求めるという問題になる。立っているbitの個数にしか興味がないので考えるべき候補は $k+1$ 通りしかない。 $O(1)$ で求まるはずだが計算量に余裕があったので全部試した。

Cに進んだ。できるだけ区間を半分にしていくような貪欲に基づいて実装してみたらサンプル2が合わず、半分にするのは最適ではなかったと気づき諦めた。

この時点でGが200人以上に解かれていたが自分はまだわかっていない。他の問題に進むよりこれを通すべきだろうと考え、改めて取り組んだ。しばらく考えて天啓がひらめいた。実は長さ $n$ の区間 $n$ 個に含まれるWの個数の最大値が答えとなる。なぜなら、Wが足りない区間は適切に延長することで必要な個数を確保できるし、延長の向きを制御することで区間が被ることもないから。

合計で1時間くらい使ってしまったが、こういう発想一発のような問題はすぐ思いつくか一生思いつかないかだと考えていたので、長い時間を使って解法に至れたのは驚きだった。

少しIを読んだ後Cに戻ってきた。もうしばらく適当な貪欲を試した後、方針を切り替えた。ある $x$ について全体を幅 $x-1$ の区間に分割したとき、 $x$ 以上の区間を使い切る前に分割が終われば後手勝ち、そのような $x$ がなければ先手勝ちとするもの。

先手は $x$ を降順に使い、現在の分割で残っている最大の区間を選び左端を端点とするという戦略。後手は分割する点を列挙しておき、できるだけその点を取ろうとする戦略。実装して提出するとTLEで、それを修正しているうちにコンテストが終了した。TLEの原因はsetの末尾にアクセスしようとしてしまっていたからで、後から投げなおしたらなんと通ってしまった。数分足りなかったということで残念。

結果は8完89位、良くない。次にABC290について。

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290） - AtCoder

ABはよい。Cは0から順番に一つずつ $B$ に入れていき、必要な数が $A$ になくなるか $B$ のサイズが $K$ になったタイミングでやめると次の数が答え。

Dは印のついていないマスだけ見て $D$ マス進むのではないのがポイント。 $g=\gcd(N,D)$ とすると $N/g$ 回操作するごとに $x$ がループして手順iiが1回だけ行われるので、その回数を手順iだけ考えた時の番号に足すことで答えになる。

Eは主客転倒で数のペアに対しそれが答えに寄与する回数を数える。操作が必要な数のペアはたくさんあるので、逆に操作が必要ない、つまり値が等しいペアについて考えて全体から引く。その全体は $|X|$ を全探索することで $O(N)$ で求まる。

今 $i\lt j$ かつ $A_i=A_j$ として、このペア $(i,j)$ が対称の位置に来るような $X$ は $\min(i,N-j+1)$ 通りあるから、 $i$ と $j$ を動かして足し合わせたい。 $A$ が等しいインデックスだけ集めた列を作り、その中から $j$ を全探索すると、 $\min(i,N-j+1)=i$ となる範囲が列の二分探索で求まるので、 $i$ を動かしたときの和が計算できる。

Fは結構難しかった。 $X$ から木を作るのは難しいと考え、木から $X$ を作ろうとしていたが、考えているうちに $X_i\ge 2$ なる $i$ を全部一直線に並べるだけで直径の最大化ができると気付いた。

その頂点数を $k$ と置くと選び方が $\binom{N}{k}$ 。並べ方は考えないので順列ではない。残りの $N-k$ 頂点の次数は1だから次数の余りが $(2N-2)-2k-(N-k)=N-k-2$ だけあって、これを $k$ 頂点に割り振るので重複組み合わせで計算すると $\binom{N-3}{k-1}$ 通りとなる。これに直径 $k+1$ を掛け、和を取ると答えになる。

Wolfram|Alphaで計算した。最初直径を掛けるのを忘れていたら $\Gamma(N-1/2)/\sqrt{\pi}$ のような式が出てきて、頑張って二重階乗に直したのだがサンプルが全然合わなくて愕然とした。正しい式を入力したら単なる階乗だけで書けてしまった。

G。連結成分のうち深さ最小の頂点を固定して考える。その頂点が葉から $d$ 段（ $0\le d\le D$ ）上にあるとすると、それ以下には最初に $K^0+K^1+\dots+K^d$ 頂点あって、ここから適当に頂点を切り落として $X$ にするのが目標。

葉から $k$ 段（ $0\le k\lt d$ ）上った先の頂点以下を切り落とすと、頂点数は $K^0+K^1+\dots+K^k$ だけ減る。つまり額面がその値であるようなコインが $d$ 種類あるので、枚数を最小化しつつ必要なだけの頂点を切り落とすという問題になった。本当は切り落とすべき頂点が残っていることも確認しなければならないが、たぶん大丈夫だろうと思った。

コインの額面に約数・倍数の関係がないので、貪欲に取ってよいのかわからない。ダメだと思ってしばらく考えてみるも全然解けず、本当は大丈夫なんじゃないかという気持ちになってきた。 $K=2,3$ で小さい範囲を試し、貪欲が成立していることを確かめて提出したら通った。この貪欲が正当なら1種類のコインを $K+1$ 枚以上使うことはないので、切り落とすべき頂点が必ず残っていると言える。

Exは解けず。両側から小さい値を順に埋めていく $O(N^2M^2)$ のdpを書いたが、合っているか間違っているか以前にTLEで全然ダメだった。適当に探索する範囲を絞るも手元で2.7secくらいにしかならなかった。

7完18位。Gの貪欲は正当らしい。公式解説にQiitaの記事が貼ってあった。なんだか見覚えがある。額面が約数・倍数関係にあるより弱い条件があったということは記憶していたが、探しに行かなかったのが敗因か。

硬貨の問題が貪欲法で解けるための条件 - Qiita

CFが終わってからコードゴルフを始めたが、もうあらかた縮め終えられていた。とりあえずコメントのしようがないものから、Aはdc、DはRuby。EのPerlはそもそもアルゴリズムを理解していない。これとBCF以外、つまりG以降は手付かず。

BはVimで、あるかわからない $K+1$ 個目のoを探す方針がうまくいかないのはわかっていたが $K$ 個目を巻き込んでxに直してから改めて1文字だけoにするという方法で回避できるらしい。こういうoff-by-oneの回避はVim コードゴルフの花形という感じがして、自力でできた試しがない。

CはRuby。 $0\dots K-1$ から $A$ に含まれない値のうち最小のものを探し、なければ $K$ を出力するというもの。操作回数云々をちゃんと言い換えるとこうなるようだ。何も考えていなかった。

FもRuby。 $(N-1)!(N-2)!$ の逆元を計算したいとき、 $(N-1)!^2/(N-1)$ と見ることで逆元を2乗するだけになり短くなるようだ。その2乗は逆元を求めるときに ${\rm mod}-2$ 乗する代わりに $2{\rm mod}-4$ 乗することで行える、という更新で掠め取った。しかし冷静になるとこれは ${\rm mod}-3$ 乗である。結局最短コードは取れなかった。