03/27(月)

午後2時半起床。シャワーを浴びて午後3時からパ研合宿1日目のコンテストに出た。

パ研合宿2022 第1日「Jikka」 - AtCoder

Aはよい。Bは設定が完全に既出で、制約だけが違う。 $M=1$ のとき不可能とすればOKかと思ったら、その前にちゃんと $N=1$ のケースを弾いておく必要があった。

Cもよい。Dは「 $t$ 席連続で座らせて1席空ける」のを繰り返すパターンでギリギリ $K$ 人座れる最小の $t$ を求めその通りに座らせたら、端までちゃんと使いきれないことがあるらしくWA。コンテスト中はこの原因に思い至れなかったが、方針を変えて3席のうち1席空けるのを貪欲に繰り返してみたら通った。

Eは円をできるだけ対角に寄せてみてチェックする二分探索。Fは全探索。Gはダブリングで $Y$ から深さの差-1回親に移動したときの頂点を求めた。Hは体力が正の参加者をsetに持ち、setの全体から引かれた値と共に管理した。Iは等しい値をUFで表現し、先頭から等しくない値の条件を見つつできるだけ小さい値を入れていった。

Jはまずパスの長さを求め、中央値を計算するのに必要な値を「 $ST$ パス上で重みの小さいほうから $k$ 番目」という形で表現し、それらを並列二分探索で求めた。辺の重みを昇順に見つつ、これまで見た辺に1、見ていない辺に0を割り当て、パスの和を求められれば良い。HLDにBITを乗せることで実現できる。二分探索も入れて $\log$ 三つだが800msで通った。

Kは後ろから順に、現在の位置を先頭としたとき累積MAXを更新する点をBITで管理した。クエリは先読みして答える。Lは現在追加できる $\mathrm{mex}$ の最大値を状態に持ってdp。Mは値 $0$ 、 $1$ を表す超頂点を作って等しい値をUFで管理した。

NはBSGS。Giant Stepの幅を3の倍数にしておくと上手くいく。最初の提出が $A=0$ のケースにやられた。これに対しては数回だけ探索してダメだったらダメとすればよいのだが、その実装に失敗してさらに2WAしてしまった。

ここまで解いたところでちょうど午後4時半になったため、切り上げてインターン先定例会に参加した。正直なことを言えば裏でOを考えていたのだが全く解けなかった。結果は14完7ペナで8位。

定例会。先週は進捗がない。今週はいつもの1on1に加え、かなり久しぶりに最初のメンターさんとの1on1も予定されている。最近不甲斐ないので何を聞かれるかドキドキしている。

勉強会はChatGPTについて。出力のモデレーションのためOpenAIは専用のモデルやデータセットを用意している、ということが印象深かった。このことを聞いて去年言語学の講義で学んだ「刺激の貧困」を思い出したが、改めて考えてみると特に関係はなさそう。学習のためのデータは倫理的に良くないものだろうがいくらでも用意できるからだ。

New and improved content moderation tooling

人間の文法はすべてを経験から獲得するということができない。なぜなら、経験する文はすべて文法的に正しいはずで、正しくない文、いわゆる非文は原理的に経験できないから。これを刺激の貧困という。
週記（2022/12/19-2022/12/25） - kotatsugameの日記

勉強会が終了してから日付が変わる直前まで先週の週記を書いていた。5hを書くのを諦めたら残っているのはラノベの読書記録だけだからすぐ終わるだろうと思っていたが、全然そんなことはない。後から読み返した時のために印象深いシーンや考えたことを書きたかったのに、読んでから日が空いたせいですでに記憶が薄れてしまっていた。

ポジティブでない感想はツイートしにくいので、特別面白いというわけではなかった作品については読了ツイートに何も書かないことが多いのだが、それならそれで代わりに日記の下書きに書いておくべき。まあそういうことは百も承知で、ただ自分の怠惰ゆえになかなか習慣化できない。

週記を投稿してからセミナーの準備に取り掛かった。明日は平面グラフの双対を扱う予定。導入部分をどう喋るか考えている間は非常に眠くてかなり苦労した。命題の証明に入ったら目が冴えてきて、午前5時くらいに何とか完成。

30分くらいパ研合宿1日目のコードゴルフをした。コンテスト中のコードも含めここで触れておく。Aはdc。Bもdcで、ゼロ除算を行えたか否かでスタックサイズが変わるのを利用し出力を制御した。

Dは $3,6,\dots$ とそれ以外をこの順に並べ、末尾から $K$ 項出力する解法が天才的。「それ以外」の部分に $1\dots N$ を置いてからuniqueしても同じものが得られて縮んだ。Ruby。

Eは自分は解説を読んで初めて $O(1)$ 解の存在を知ったが、コンテスト中にすでにその解法のdcによる提出があった。出力すべきものをまとめると $\min(H+W-\sqrt{2HW},H,W)/2$ になるようで、さらにこれを $\min(H+\min(W-\sqrt{2HW},0),W)/2$ としていた。かなり上手い。

Gは木のdfs順に頂点に番号を振ると、 $X$ の子の番号と $Y$ の番号を比較しながら二分探索することでどの子以下に $Y$ が存在するか求まるらしい。これもかなり頭の良い方法。番号を振る順番を制御したら少し縮んだ。Ruby。これら以外の問題は手付かず。

このコンテストによって（カウント対象のサイトでの）AC数が合計10000問を超えたらしい。

Solved By kotatsugame
AtCoder: 4396
Codeforces: 2389
AOJ: 1347
yukicoder: 1534
Library Checker: 25
CodeChef: 151
TopCoder: 163
Total: 10005https://t.co/0T2dyMlczx
10000問解きました
— こたつがめ (@kotatsugame_t) 2023年3月27日

布団に入ってからなぜか1時間ほどハーメルンを読み、1時間寝落ちし、次の30分で最新話まで追いついた。「お兄様は嫁がせたい」。

syosetu.org

懲りずにまた知らない原作の二次創作を読んでしまった。主人公が不老不死なのは世界観と合っていなそうだが個人的には好み。原作知識持ちなので未来の展開を前提に動いていて、しかもあまり説明がないので正直よくわからない部分もいくらかある。しかし主人公の設定が好きなので楽しく読めた。

午前8時にようやく就寝。

03/28(火)

午前9時45分起床、準備してすぐ出発。今日の眠気はさすがにヤバいことが予想されるので生協でエナジードリンクを買った。いつものように10分くらい遅れて教室に到着。

午前中は同級生の発表。いよいよクラトフスキの定理が示されるというところで、直前の補題の証明にコーナーケースがあって解決するのにかなり時間がかかった。どうやら場合分けを頑張るしかなさそう。自分も同時に考えて早々に完成したものの、後から彼の場合分けを聞くとそれより遥かに綺麗でびっくりした。自分は競プロで培った腕力で押し切ってしまったようだ。

彼が黒板で場合分けしているのを眺めつつ、一足先の休憩時間ということで昼食を摂ったりスマホを触ったりしていた。昨日のパ研合宿1日目N問題を解けるBSGSライブラリについての記事を読んだ。

逆元の存在を仮定せずに離散対数問題を解くアルゴリズムを解説しました。https://t.co/E8RWzLkSmN

個人的に欲しかったやつ。
— maspy (@maspy_stars) 2023年3月28日

作用をfunctional graphの辺だと思うとかなり見通しが良くて感動。普通の離散対数問題だと作用に逆元があってグラフがループの集合になり扱いやすいということらしい。さらに、合成数modの離散対数問題を解くときは最初に $\log\mathrm{mod}$ 回探索するが、これもループに入るまでの辺の数がそれで抑えられるという解釈ができる。

午後1時半から自分の発表。3時間かかってパ研合宿2日目と完全に被ってしまった。それほど詰まっていたという感触はなく、単に新しい概念を念入りに説明していたからだと考えている。ついでに1.9章の飛ばした内容を少し回収したのもある。

解散して午後5時くらいに帰宅。今日はエナジードリンクのおかげで眠気に襲われず最後まで乗り切ることができた。ここぞというときにしか飲まないのでそれほどカフェインに耐性がついていないはずで、今日みたいな日には非常に役に立つ。

訪れた眠気で集中力を切らしたまま、ゆっくりパ研合宿2日目のupsolveをした。5時間くらいかけてFまで解いた。

パ研合宿2022 第2日「パ研杯」 - AtCoder

Aは $A$ に含まれない街を全部選ぶのが最適。Rubyでパパッとコードゴルフもしておいた。

Bは単調減少な区間の先頭 $x$ と末尾の要素 $y$ を固定し、それ以外の要素が $x$ より前、 $x$ と $y$ の間、 $y$ より後ろのどこに並ぶか考える。 $(y,x)$ に含まれる要素はどこでもよいがそれ以外は一つしか候補がない。よって $3^{x-y-1}$ 通りの決め方があり、それぞれについて具体的な並べ方は適切にソートするしかないため一意。

つまり求めるものは $\sum_{x=2}^N\sum_{y=1}^{x-1}3^{x-y-1}$ であり、計算すると $\frac{3^N-2N-1}{4}$ になる。コードゴルフ的にはすでにdcの解が存在し、縮める隙を見つけられなかった。

Cは非常に面倒。 $A$ と $B$ を混ぜて並べておくことで、クエリごとに $A$ の要素のみが指定された区間、 $B$ の要素のみが指定された区間、両方の要素が指定された区間と、それらの区間の間を考えればよいことになる。区間の内部についてはあらかじめ計算してセグ木に乗せておく。区間の間は定数個しかないためその場で処理できる。定数倍が重めの $O(N\log N)$ 。

Dは直近に出現した0と1のインデックスを持つdp。片方が直前のインデックスになるので、もう片方をセグ木のインデックスと対応させることで実家dpになる。書き上がってからよく見ると列を右に伸ばしつつ区間和を取得しているだけだったので累積和で十分だったし、さらに両端が単調に増加するので和を変数に持っておくだけで良い。線形時間で解ける。

Eは演奏者を熟練度の降順に見て、これまで見た人だけで $M$ 種類の楽器をカバーするのに必要な移行コストをそれぞれ計算した。この値は単調減少なので、最後に $X$ を見つつどの人まででカバー可能か調べれば、その人の熟練度が調和度になる。

考慮する人の集合が決まれば、まず担当者がいる楽器について移行コストが最も高い人を割り当て、残った人を移行コストの昇順に担当者のいない楽器に割り当てるのが最適。前半は差分更新できる。後半は移行コストを座圧してBITに乗せ二分探索をすることで、誰まで移行コストを支払うことになるか求められる。 $O(N\log N+Q)$ 。

Fはちょっと良質なギャグ。 $N=1,2$ の場合一意なので $N\ge 3$ とする。まず明らかに $A_i=i$ なる $i$ が存在してはならない。ここで $A$ が順列でないならば、 $A$ に出現しない要素を中心とするウニグラフを作ることで必ず達成可能だと分かった。逆に、 $N\ge 3$ より長さ2のパスが存在してその真ん中の頂点が $A$ に出現することはないから、 $A$ が順列の場合は達成不可能。

$A_i\ne i$ かつ順列にならないような $A$ を数え上げる。まず $A_i\ne i$ を満たすため、一つ一つの-1を候補 $N-1$ 通りから好きに埋める。 $B$ の時点で順列でないならこれで求まっている。そうでなければ順列となるケースを取り除く必要があるが、ここは完全順列を求めるのと同様、 $A_i=i$ となるような $i$ の個数を考えて包除原理を行うとよい。

1時間ほどAHC019に取り組んでみた。とりあえずサンプルプログラムより良い解は作ったもののここから大幅に改善できそうなアイディアもないし、ちょっとしたアイディアだと実装が面倒でやる気が出ない。

MC Digital Programming Contest 2023（AtCoder Heuristic Contest 019） - AtCoder

午前3時まで日記を書き、2時間ほど布団でハーメルンを読んで就寝。

03/29(水)

午後1時過ぎ起床。TopCoderからアンケートが来ており、ここで要望を出せばTCOに復活の目があるかと思って答え始めたが、ひたすらプログラミング学習と就職に関する設問が続いて心が折れた。

半からパ研合宿3日目のコンテストに出た。チーム戦だがソロ参加。

パ研合宿2022 第3日「teamwork」 - AtCoder

最初にAを読んだらすぐ解けた。最小費用流が思い浮かぶが、この問題設定なら左半分の端から右半分の端まで壁を配置するマスがひとつながりになっているから、最短経路を求めればよい。最近Universal Cupで出た問題の簡単なバージョンがこの考え方を使っていた。

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Regional/3221

この後は順位表に従って進んでいった。

Eはまず $A$ に10⁶以上の素数を入れ、残りを $1,2,\dots,K$ で埋めた。ここで $K=29565$ であった。その後 $1\dots 2\times 10^6$ に対し「 $1\dots K$ のどれかで割り切った時の商の最小値」を求め、 $A$ に入っている10⁶以上の素数を除き $B$ に入れた。重複要素を取り除くと長さが10⁵未満になったので、残りを適当な値で埋めて完成。

Fは隣接要素のXOR $N$ 個を総XORが0になるという条件で数え上げ、初項の分 $2^M$ 倍すればよい。 $T$ または $U$ に一致するものの数を考えて包除原理。その数 $k$ が $N-1$ 個以下なら、 $N-1$ 個になるよう適当に埋めた上で最後の1個を適切に決めれば必ず総XORを0にできるから、場合の数は $\binom{N}{k}2^k(2^M)^{N-1-k}$ となる。

$k=N$ の場合はちょっと難しい。 $T$ または $T\oplus(T\oplus U)$ を選ぶと考えると、 $T\oplus U$ をいくつか選んで $\bigoplus T$ を作る方法を数え上げる問題になる。適当に基底を取ればできる。包除の式も $k=N$ の場合の符号も間違っている状態で投げて1WA。

Jは結果こそギャグだが考察は少し面白いと感じた。 $iP_i$ の最小値を決め打つと、各 $i$ に対して $P_i$ の下限が決まる。 $i$ が小さいほうが下限の制約が厳しいから、先頭から順に空いている値の最大値を当てはめていくのが判定問題としては最適。

問題を解く場合はさらに $iP_i$ の最大値を最小化することになるが、これも先ほどの戦略が最適となる。よって $iP_i$ の最小値を決め打つまでもなく $O(N)$ で最適な $P$ が求まるから、実際に計算して答えを求めればよい。考察に自信があったので、 $N\le 5000$ なのに線形で解けたことに対し特に不安感はなかった。ACを確認後パパッとRubyで縮めておいた。

Iは先頭の要素を決めると以降それに含まれるbitを無視してよいという考察から、そうやっていくつかのbitを無視した上での最小値を貪欲に置いていく解法を提出して1WA。正解は累積ORにおけるbitがどの順番で増えていくか全探索すること。これをbitDPで計算するためには「あるbitの集合に含まれる $A$ の数」が高速に求まれば十分で、ゼータ変換で前計算できる。

Bは $A$ と $B$ を値の昇順、タイブレークは $B$ を優先して並べ、前から順に $A$ の要素なら確定させるか $B$ による更新対象に、 $B$ の要素なら捨てるか更新対象に埋めるということをする。一番最後が $B$ の要素だった場合捨てられないことに注意。更新対象がいくつ残っているか持つdpで $O((N+M)N)$ 。同じ値はまとめて遷移する必要があるが計算量的には変化しない。

Dは、逆から考えるとボールが偶数個入っている箱を一つ選びボールの半分を別の箱に入れるという操作になる。なので一つの箱に $\sum A$ 個のボールが入っている状態からだと、できるだけ他の箱に振り分けたとしても2で割り切れない部分はどうしようもない。正確に言えば、奇数 $P$ を用いて $\sum A=2^k\times P$ のように表したとき、最初の $A$ がすべて $P$ で割り切れる必要がある。

逆にこれを満たせば必ず達成可能だった。逆から考えるのをやめたら構築できた。まず各要素を $P$ で割って考えてもよい。 $\sum A=2^k$ という条件から奇数が偶数個あるはずなので、適当にペアにして操作することですべての要素を偶数にできる。次に4で割ると2で余る数について同様のことを行う。以下順に続けていけば、最終的に一つの箱が $2^k$ 個のボールを持つ状態になる。

Cはまず $R=|S|$ としてもよい。これで答えとなる文字列が $|S|$ 通りになったので、順に比較して最大のものを求めた。比較はトヨタコン決勝Dと同じ発想で、二つの文字列が初めて異なる位置を求め、そこの文字だけチェックした。ただし異なる位置を求めるのにSA+LCPは使えない。ロリハと二分探索で行った。実はこのロリハがモノイドになる。

対応する文字列においてどの文字がどの順で現れるかと、その文字が現れる位置に1、それ以外に0を置いて計算したハッシュ値を持っておけばよい。積やハッシュ値の計算は文字の種類数を $\sigma=26$ として $O(\sigma)$ 。二分探索のため $O(|S|\log|S|)$ 回区間積を求めるので、セグ木でさらに $\log$ をつけると9secくらいかかってしまった。DSTを持ち出すと $O(\sigma|S|\log|S|)$ になって1356ms。

8完10位。もう一問に手を出せるような時間がなく、他の問題はほとんど考えられていない。逆に読んだ問題は全部解けたということで、これは良かった。

1時間後からCF div.2があるが、サボってゲーセンに行くことにした。3月は全然行けていないので終了が近づいてきたイベントの進捗が危うい。ちょっと計算したところ04/12までに4回くらいゲーセンに行かないと終わらなそうだった。やよい軒で夕食を摂ってからプレイ開始。

今日はずっと新曲を埋めていた。ワールドイズマインの理論値を出そうと1時間ほど粘着した結果、1回しかプレイできてないものもいくつか残っている。そのうえ結局理論値は出なかった。ということで特に成果はなし。

プレイの合間にTLを見ると今日のCodechefのコンテストが全員Ratedだというツイートが流れてきた。LunchtimeもCook-Offもなかったはず、と思いつつコンテスト予定を見に行くとStartersが全員Ratedになっていた。それはStartersではないだろ。

何にしても、CF div.2ならともかくこれまでサボるという選択肢はない。午後11時前に切り上げ、立ち食いそばをササッと食べて帰ってきた。何とか間に合って半からCodechef Starters 83。

https://www.codechef.com/START83A

CONSTRは奇数回連続する文字は1文字、偶数回連続する文字は2文字が連続している状態から生成できるので、これを連結したものが答え。XOR_ORDERは上の桁から見つつ、どの数の大小関係が確定していないか考えた。dpしなくても遷移できる状態は一意である。

ROTMINは先頭からaが連続していればいるほど嬉しいので、どこまでaを続けられるか二分探索した。各文字をaにするための操作回数は（元々aでなければ）Type 1とType 2を足すと26回になるので、それぞれ少ないものから貪欲に取るのが最適。その後、残りの操作回数を使って後ろのほうを適当に調整しておく。Type 2を使い切った後もType 1でaにできる文字が残っている可能性があることに注意。

MEXSEGはちょっと面倒。「MEXが $M$ 以上で長さが $L$ 以下の区間」を数える関数を作り、二次元累積和のように足し引きして答えを求めた。 $M=0$ の場合は簡単。そうでない場合区間に $0\dots M-1$ を含む必要があるので、区間の左端に上限、右端に下限がつく。この上で長さ $L$ 以下の区間を数えるには $\sum_{i=0}^x\sum_{j=0}^y[i+j\le l]$ という形をした式を計算する必要がある。丁寧に $O(1)$ にした。

SLAYSは簡単。 $D$ が区間の最大値未満なら明らかに不可能、最大値より大なら明らかに可能。よって最大値と等しい場合に可能かどうかを判定する。各 $i$ について、 $i$ 番目のダンジョンから $D=S_i$ の状態で戦い始めたときどのダンジョンまで進めるかというのを $i$ の降順に計算できるため、最大値を達成する一番左のインデックスを取得して対応する値をチェックすればよい。

BEAUTY_SUMが全然解けなくて結構な時間唸っていたが、順位表を確認するといつの間にか最後の問題GUESSPFMXにたくさんACが出ていた。読んだら一瞬で解けた。1要素ずつソートされた状態を保ったまま挿入することを考えると、とりあえず先頭に置いてクエリを投げ、どの値まで累積MAXを更新しなくなるかチェックするだけで適切な位置が求まる。

またBEAUTY_SUMに戻るも相変わらず解けないままコンテスト終了。6完12位で2855→2848(-7)。GUESSPFMXはコンテスト中に追加された問題で、想定難易度は結構低めだが最後にしか追加できなかったので最終問題になったらしい。途中で問題を追加しなければ良かったのではないだろうか。

BEAUTY_SUMのupsolveをした。コンテスト中はパスのLCAを固定して木dpっぽく計算することを考え、出来ずに終わった。ところがなんと重心分解なら似たことが可能なようだ。木dpが出来なくなる代わり、毎回部分木のサイズをかけて計算しても全体で $O(N\log N)$ になる。今回はそこに $\log$ がつくがそれでも当然問題ない。

重心分解した木のある頂点 $u$ をLCAとして固定し、 $u$ の部分木に属する各頂点 $v$ について $(f(u,v),g(u,v))$ を求めておく。こうして集めた $(f,g)$ の組から二つ $(f_1,g_1)$ と $(f_2,g_2)$ を取り出したときの $\max(f_1,f_2)\cdot\min(g_1,g_2)$ の総和が求められればよい。LCAが $u$ にならないパスも作ってしまうが、 $u$ のある子以下の頂点だけ集めて計算し、元の総和から引くことを繰り返せば取り除ける。

総和は $g$ を座圧してBITに乗せることで計算できる。まず $f$ の昇順に値を見ることで $\max(f_1,f_2)$ を固定できる。 $\min(g_1,g_2)$ はBITのインデックスに応じて $g_1$ と $g_2$ のどちらになるか決まるから、個数を求めるBITと $\sum g$ を求めるBITを用意することでそれぞれ対応できる。

しばらくハーメルンを読んだ後、朝方に2時間半ほどインターンの進捗を産んだ。先週やるべきだったタスクとして、人力で作成してもらったデータを機械学習によるものと同様の形式に揃えるコードを書いた。

布団に入ってさらに2時間くらいハーメルンを読み、午前9時半就寝。

03/30(木)

午後3時少し前に起床。インターン開始時のメンターさんとの、久しぶりの1on1に臨んだ。

今日は修士2年になる自分の就活がどうなっているかという話だった。ありがたくも自分を評価していただけているようで就活を始める際にはぜひ声を掛けてほしいと以前言われていたのだ。もちろん忘れていたわけではなく、博士課程に進む心づもりだからまだ就活を始めていないだけ。そもそも博士課程に進もうとしていることすら伝えていなかったので、それを改めて明言し、この話は終わりになった。

1時間の1on1の予定だったのに本題が10分ちょっとで終わってしまったが、その後時間いっぱい雑談に付き合っていただいた。自分が1年くらい前にやっていたことのその後とか、今やっていることの展望とか、気になっていたことはいくつかあったのでいい機会だった。

午後4時終了。いつの間にかPAST13が公開されていたのでCまで解いた。コードゴルフ的にはABは出遅れて負け、Cは勝ち。

第13回アルゴリズム実技検定過去問 - AtCoder

午後5時から今度はいつもの1on1。昨日書いたコードを説明し、良さそうということで次は人力によるデータを使った機械学習の精度評価を実装することになった。いくらか仕様を詰めて終了。

あまりに眠いので布団に倒れこみ、午後6時半から5時間ほど寝ていた。起きて食事し、そこから朝まで日記を書いていた。

集中が切れたタイミングでハーメルンにのめり込み、「転生したら倒産確定地方トレセン学園の経営者になってた件」を一気読みした。非常に面白かった。ウマ娘の二次創作と言いつつ、本質は逆行転生。それも経営者となって未来知識で会社を盛り立てるという好みどストライクの作品だった。人望のある主人公も良かった。

syosetu.org

シャワーを浴びて正午くらいに大学に向かい、学食で食事し、予約していた本を受け取って帰ってきた。その本の中から1冊をしばらく読んで就寝。午後3時半ごろだった。

03/31(金)

午後10時半くらいに起床。yukicoderで開かれていたエイプリルフールコンの問題を少し眺めたが、特に取り組みはしなかった。2019年・2021年に1問ずつ出題したので1年おきということで今年も出題しようかと考えていたものの手が回らなかった。

yukicoder April Fool Contest 2023 - yukicoder

トヨタコンの懇親会でお話しし、「11文字の檻」をお薦めさせてもらった方が読了されたそうだ。気に入っていただけたとのことで良かった。

こたつがめさんがあーだこーだーで「儚い羊たちの祝宴」勧められていて、とても面白かったので
トヨタコンでお会いした際に、期待と羨望の眼差しで再度お勧めの本伺いました
そこで「11文字の檻」を勧められ、面白くて一気読み
「恋澤姉妹」は特に好きで、最初から最後まで心が踊らされました！ https://t.co/UmxWkofWHV
— H20 (@H20_dhmo) 2023年3月31日

以前自分があーだこーだーでお薦めした本を読んでくださった方。他にお薦めの本はないですかと聞かれ、できれば短めとのことから複数巻前提のラノベを挙げるわけにもいかず、窮した結果読書記録を眺めて「11文字の檻」を見つけた。
週記（2023/03/13-2023/03/19） - kotatsugameの日記

食事して午後11時半からCF combinedに出た。

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

Aは $a_i\le i$ なる $i$ が存在することが必要十分。

Bは $x$ が常に奇数なので $n$ も奇数である必要があり、実はこれが十分条件。操作を逆に考えると、戻した後も奇数になるような操作は常に一意であり、それを適用すると必ず $n$ が小さくなるのでそのうち1に辿り着く。操作回数も大体 $\log_2 n$ 回なので制限には余裕を持って収まる。

Cは最後に出来上がる順列の長さ $k$ を決めると $k$ 以下の数をできるだけ残すのが最適なのでコストが定まる。また $k=a_i$ なる $i$ が存在せず、かつ $k\ge 2$ なら $k\leftarrow k-1$ としたほうが得であるため、調べるべき $k$ は1または $a$ のどれかの $O(n)$ 通りしかない。

Dは $h\le a$ のとき $n=1$ 、そうでなければ $n=\left\lceil\frac{h-a}{a-b}\right\rceil+1$ 。ここから $n$ に対する $h$ の範囲が求まるのでtype 1のクエリが処理できる。type 2のクエリは $h$ の上限・下限に対して $n$ を計算し、一致しているか見ればよい。

Eは難しかった。まず $a_s=0$ である必要がある。また $s$ を一つ固定したとき、そこから辿り着ける範囲を表す連結成分を考えると、それに隣接する頂点を優先度付きキューで管理しながらBFSすることで極大な成分が求まると分かった。さらに、別の $s'$ からスタートして同じ連結成分にたどり着いた場合、その二つをマージしてよい。

よってマージを繰り返し全体を連結にできるか判定する問題になったが、使える辺を探すのに苦労した。先ほどの解法における優先度付きキューを連結成分に紐づけて管理し、マージの度に使える辺を全部取り出すことで実現できた。取り出した辺は別に保管しておき、1本1本見ながらまたマージしていく。このとき優先度付きキューもマージテクでマージする。

Fは大変。各頂点に対し「子の最大値に1足した値」を書き込むと、根の値が木のvalueと一致する。逆に根の値を決め打つと木の各葉に対しそこに割り振れる値の最大値がわかる。

goodな木は「ある葉を選んで子を $m$ 頂点追加する」という操作によって1頂点のみの状態から生成できるが、割り振れる値の最大値の多重集合という観点から見ると、最初の集合は根の値1要素のみ、操作は「ある値を選んで削除し、1小さい値を $m$ 個追加する」というものになる。こうして作った集合によって $a$ をカバーできればよい。

特に、根に $a$ の最大値より $\log_m n$ くらい大きな値を書き込んでおけば必ず達成可能なので、調べるべき答えの数は少ない。しかしそれぞれ試しても間に合うだろうと思って出したらTLEした。 $m$ が小さければ1回試すのに $O(n)$ かかるケースが存在する。

実はこの判定問題はセグ木に乗る。値をインデックスとして区間 $[l,r)$ に対し「 $r-1$ が何個あれば $l\le a\lt r$ なる $a$ を全部カバーできて $l-1$ が何個余るか」を考えると、 $r-l$ の情報を含めることで区間のマージができるから。扱う値は非常に大きくなるので逐一 $\min(\ast,n)$ としておくとよい。これで通った。

Gは解けず6完29位、2828→2896(+68)。Fは $m$ 進数と捉えるとわかりやすかったようだ。コンテスト終了後に動画を投稿した。

www.youtube.com

Gを解説をガン見しながらupsolveした。先頭から累積的に求めた値全体に関して考えるとき、逆に末尾から見ていくと扱いやすいというのは面白かった。しかしその後dpをする際は結局前から計算している。ここの遷移が解説に書いてあるものと一致することを飲み込むのに時間がかかった。

遷移を導くには「 $a_i=\pm 1$ とした場合の結果」をそれぞれ集めてくるべきで、つまりより考慮する範囲が広いものから貰ってきていることになる。ここが自分の考え方とどうにも合わなかった、はず。うまく言語化できているのか自信がないが、一度そういうものだと分かってしまうと分からなかった頃の気持ちにはなかなか戻れないので、これが精いっぱいである。

朝まで日記を書き、布団で1時間くらいハーメルンを読んで就寝。午前9時半だった。

04/01(土)

午後2時少し前に起床し、すぐUniversal Cup 10回目に参加した。今日はZhejiangセット。

The 1st Universal Cup. Stage 10: Zhejiang - Dashboard - Contest - QOJ.ac

書く

1400-1900 UC

感想戦少しだけ

月が変わったので先月の読書記録をまとめてツイートした。1週間だけ頑張って本を読んだので積読の増分が一桁に収まった。

3月の集計
買った：21冊
読んだ：12冊
積読：+9冊

積読（累積）：+37冊
— こたつがめ (@kotatsugame_t) 2023年4月1日

食事し、シャワーを浴びて午後9時からABC296に出た。

AtCoder Beginner Contest 296 - AtCoder

Aは答えがNoになるケースを判定するのが楽。 $S$ にMMまたはFFが含まれるかチェックすればよい。sedで書いた。僅差でFAだったらしい。

Bはインデックスに気を使って実装。Cは片方を固定してもう片方の存在をsetで判定した。

Dは $a$ を決めると $b=\lceil M/a\rceil$ とするのが最適。商列挙で $b$ を全通り試した。

Eは $A$ から作ったfunctional graphにおいて $S_i$ から $K_i$ ステップ進んだ先の頂点が $i$ となるようにできるかチェックする問題。ただし $S_i$ は $K_i$ に応じて決めることができる。 $i$ がグラフのループに乗っているなら必ず可能で、乗っていないなら $K_i$ を十分大きくすることで必ず不可能になる。

Fはまず両方の数列をソートすることを考えた。ソートしても一致しない場合は明らかに不可能なので取り除いておく。ソートするまでのswap回数の偶奇は、値がdistinctである場合転倒数の偶奇と必ず一致するが、1回の操作で $A$ と $B$ それぞれ1回ずつswapされることからこの偶奇が $A$ と $B$ で等しいことは必要条件。

実は十分条件にもなっているんじゃないかとエスパーし、証明した。 $A$ または $B$ だけを2回swapできる操作手順を構成すればよい。2回のswapで対象となる要素が被る場合とそうでない場合に分けて手で作った。

最後に値がdistinctでない場合を考えるが、これは必ず達成可能。要素に適当に順序を入れることで仮の転倒数を求める。これで偶奇が食い違ったという場合は、等しい要素のswapを1回足すことで、ソートされた状態を崩さず転倒数の偶奇を入れ替えることができるから。こういう話は何度か見たことがあるはず。

GはPCKの過去問で既出でライブラリを持っていた。今回のような問題を1点ずつ $O(\log N)$ で解くというもので、多角形の1点を固定し偏角を二分探索するNyaanさんのユーザ解説と同じアルゴリズム。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0412&lang=ja

整数用の幾何ライブラリにも整備してあったので誤差を避けるためそちらのコードを使ったが、実はverifyしていなくて不安だった。後から確認したら普通の幾何ライブラリと全く同じコードだった。

しかしPCKの過去問では多角形の内外判定しか要求されていないので、verifyが不十分なのは変わらない。点が多角形に重なる入力がないことを逆手に取り、そう判定した場合必ず落ちるようなコードを書くという間接的なチェックを行っていた。問題なく動作していることが今回確認できたのは幸運だった。

Exは1行ずつ決めるdp。1行に存在するどのマスが連結かという状態にこれまでに連結成分が途切れたか否かも含めたものを持っておけば遷移が可能。つい最近TCB56の10問目で見たので、その時の実装を思い出しながら書いた。それでも25分かかってしまった。

46分でノーペナ全完、3位。Dは $a=1\dots\sqrt M$ を試せばよかったらしい。商列挙に少し手間取ってしまったので、これを思いつけなかったのは残念。

コードゴルフ。Aは最初の提出でOK。

Bは似たような問題があるのでそのAWK提出を参考にしようとしたが、入力形式や制約が結構異なる。Perlで書いたらかなり縮んだ。1行ずつ読み込んで*の存在を正規表現でチェックし、行番号は$.を、列番号はマッチした位置を使った。特に列番号については、1から8にPを文字列としてXORすればaからhに対応させられるというのがかなり効いた。

A - Where's Snuke?

CはPerlで、負け。Eはそれぞれの頂点からダブリングで十分な回数グラフを進んだ後重複を取り除いたものがループ上の頂点になるという解法がシンプルで短い。Perlで書いたがこれも負けてしまった。他は手付かず。

動画を投稿した。

www.youtube.com

ABC中からDMOJのRatedコンテストが始まっていた。土曜日午後10時から日曜日午後1時までの好きな区間で出られるというやつ。確か昨日までは順位表が公開されることになっていたので、情報が集まるのを待ち明日早起きして参加するつもりだった。しかし今確認したところ非公開に変わっていた。

ただ、今からもう1本コンテストに参加する体力もない。変わらず明日参加することにした。コンテスト時間が4時間から3時間に縮んでいたので午前10時までに開始すればOK。睡眠時間に余裕があると思い込んでじっくりハーメルンを読みふけっていたら、就寝が午前4時くらいになってしまった。

04/02(日)

午前9時起床。食事して予定通りの時間にDMOJを開始した。

Wesley's Anger Contest Rejects - DMOJ: Modern Online Judge

書く

1000-1300 DMOJ

夜までハーメルンを読んでいた。「転生チートトレーナーvs転生チートウマ娘」を読了。非常に面白かった。人間味のないオリトレーナーもひたすら強いオリウマ娘もどちらも好き。すっとぼけたエピソードタイトルだがシリアスシーンはとことんシリアスで、コメディとの振れ幅を楽しく味わえた。

syosetu.org

インターン先勉強会の自分の発表が明日に迫っている。ようやく準備を開始した。題材だけは一応決めてあって、ACLのソースコードを読んで定数倍高速化テクを学ぼうというもの。スライドを書き始める前のテクを探して列挙する作業を続けていた。

眠すぎて耐えられなくなったので午後10時半から仮眠。30分くらいで起きるつもりだったのに1時間近く横たわっていた。午後11時半からのCF div.2にはギリギリ間に合った。録画環境を整える暇はなかった。

Dashboard - Codeforces Round 862 (Div. 2) - Codeforces

Aは $n$ が偶数なら何をXORしても総XORが変化しないので $\oplus a=0$ かチェック。 $n$ が奇数なら $x=\oplus a$ でよい。全探索想定なのか、真面目に解こうとするとちょっと慎重になるべき場合分けが要求された。

Bは最小の文字を先頭に持ってくるべきで、複数ある場合は最も後ろに出現したものを使うのが最適。直感だけでなくちゃんと証明もしてから提出した。

Cは放物線と直線を平面に描いて考えようとしたが、単に式変形するだけでよかった。 $ax^2+(b-k)x+c=0$ の判別式が負になるのが条件で整理すると $k$ の上限と下限が分かる。 $k$ をソートして二分探索すれば求まる。誤差だったり不等号の等号あり・なしが面倒だったので、周りをいくつか探索した。

Dはまず直径を一つ取る。 $k$ が直径より大きいなら $G_k$ は辺を持たない。そうでない場合、各頂点に対して最遠点が直径のどちらかの端点であるという事実から、その端点との距離が $k$ 以上になる点全体が一つの連結成分、それ以外の点が孤立点となる。

Eは $a$ に同じ値が3回以上出現するならどの辺に対してもMAD候補になるが、最終的な解法には関係なかった。まず2回以上出現する中で最大の $a$ と、それを持つ頂点 $u$ 、 $v$ を取る。 $u-v$ パスに乗らない辺に対しては答えは $a$ 。次に $u-v$ パス上の辺に対する答えを求める。

$u$ を根としてdfsし、マージテクで各頂点以下に存在する $a$ の種類と個数を求めることで、ある辺を切り離したとき $u$ を含まないほうの部分木のMADを求めることができる。問題は $u$ を含むほうだが、辺が $u-v$ パス上にあるなら、 $v$ を根とするdfsによってそちらの部分木のMADを計算できる。これで必要な値が揃った。

F1は実際に $n$ 回 $F$ を適用した。 $F$ を適用した後の数列の最大値 $X$ は「 $a_i+a_j\le X$ を満たす $i\lt j$ が $N-1$ 個以上ある」を満たす中で最小の値だから、二分探索で求めることができる。1回の判定は尺取りっぽく行えば $O(N)$ 。

$X$ が求まれば、まず $X$ 未満の $a_i+a_j$ を $O(N)$ で列挙し、残りを $X$ で埋めることで求める数列が得られる。ここで $X$ 「以下」の $a_i+a_j$ が $O(N)$ 個であるとは限らないので、それを列挙してはいけない。

最後に、1回 $F$ を適用すると要素が倍くらいになることに対処しなければならない。これは $a$ の最小値を全体から引き、別に $\bmod{10^9+7}$ で管理することで回避できる。 $\min a$ とそれ以外を足すと $n-1$ 個の数ができるので、 $F$ を適用した後の最大値は $\max a+\min a$ 以下となる。よって最小値を全体から引いた値は元の数列より小さくなり、特にオーバーフローを避けることができる。