11/28(月)

午後4時過ぎに起床。半からインターン先の定例会に出席した。

先週はEC2を触っただけ。得られたデータのチェックすらしていないので、今週はそれを見るのと、あとは関係するコードを読んでみる予定だと言った。

勉強会はベイズ推定の話。話題自体は何かの講義で聞いたことのあるものだったが、発表スライドの作りが丁寧で具体例やグラフが多くあり、非常に楽しめた。式変形もしっかり書かれていて、特に数式の文字を色分けしていた労力には頭が下がる思い。意味を視覚的に把握しやすいかと思って自分も以前少しやってみたものの、あまりの面倒さにそれほど徹底できはしなかった。

終えてからはずっと先週の週記を書いていた。午後9時にひとまず書き終え、校閲をしないまま投稿、その後セミナーの準備を始めた。先週用意した分が半分残っているのでちょっと余裕がある。続きから読み始めた。

相変わらずMengerの定理で、三つ目の証明。これまでの二つとは違いそれほど帰納法に依存していない証明のため、この定理を無限グラフの場合に示すときにも使えるらしい。しかし無限グラフの導入まで全然たどり着いていない今はただただ複雑怪奇なだけの証明に感じられたので、いっそ飛ばしてしまうことにした。その後はcorollaryがいくつか置かれていたので、これだけ準備。メモにして4ページ分程度。

午前1時前に完成。その後すぐDMOJのコンテストを強行した。金土日を逃し、今こそが参加できる最後のタイミングだった。

DMOPC '22 November Contest - DMOJ: Modern Online Judge

P1は「両隣のどちらかが消える」という条件が消える人自体にも成り立たなければならないことを見落として1WA。__MMを繰り返すのが最適である。

P2は辺が斜めになってもよいあみだくじということでちょっと詰まったものの、辺が互いに交差しないためすべて平行になるよう各縦線を伸ばしたり縮めたりすることができて、結局平行な辺のみを考えてよい。よって答えは単なる転倒数で、 $O(N^2)$ が通るので実装も楽。

P3は $i=2\dots N$ について $i$ の倍数の順番が保存されていなければならない。ここからどの数がどの数より前に来るかという情報を抜き出しDAGにして、大きな数から使うトポロジカルソートをすればよい。 $i$ としては素数だけ考えればよいが、わざわざそうしなくても辺の数が $O(N\log N)$ なので通ると判断した。

P4は大変。まず最短手数については、色 $C$ が塗られた頂点を全部削除したときできる連結成分のうちで最大のものだけ残すようにすればよい。それに対する操作方法の場合の数は、連結成分から生えている色 $C$ の頂点とその先の部分木を全部消す方法なので、木dpの要領で計算できる。適当に根を取り、色ごとにdpの値をmapで管理してマージテクを行うことで、残す連結成分が根を含む場合はとりあえず答えが出せる。

あとはこれを全方位木dpにする。dpの値を色ごとに管理・更新するのは見ないこともない話で、頑張ればできる。今見ている連結成分に関する答えを記録するのは、全部の色に対して行う必要はなく、見ている頂点とそれに隣接する頂点の色に対してだけでよい。これもできる。問題は同じ連結成分を重複して数えないようにすること。サイズが同じ連結成分が複数あり得るのは正気の沙汰ではない。

全方位木dpで頂点を動かす際、乗り越えた頂点の色に対してカウンターをインクリメントしておくことにした。このカウンターが連結成分に番号を付けたような意味になって、参照することで同じ連結成分の情報を複数回カウントしないようにできる。

必死の思いでサンプルを合わせたのにテストケースの一つ目がそれではないようで、1度目・2度目の提出が1ケースも通らず非常に苦しかった。手元で適当に試した結果長さ3のパスグラフで落ちてくれて、どれを根としても合うよう修正したら全ケース通った。

残り1時間を切っている。P5は適当な条件を掻き集めただけでは通るわけがない。P6は部分点1のみ。終盤は主にP5を考えていて、特に進捗なく終わった。410点。

終わったらもう午前4時。シャワーを浴びて少しラノベを読んでいたら就寝が午前6時前になってしまった。

11/29(火)

午前9時40分起床。かなり危ない。買っておいたゼリー飲料を朝食とし、すぐ出発した。

午前10時から5分くらい遅れて教室に到着。エアコンが壊れているらしく非常に寒かった。午前中は同級生のセミナー。前半は細かい話が多くて辛かったが後半は新しい概念の導入で楽しかった。

先生に関数型言語を触るのをしきりに勧められていて、僕からはHaskellでAtCoderの問題を解くとよいのではないかと言っておいた。特にAtCoderについては、簡単な問題をバンバン解いて向こうでジャッジしてもらうスタイルがプログラミング言語学習には非常に良いはずだと強くプッシュしておいた。

そういう話をしていたら午後1時くらいになっていた。購買で買ったパン等を食べ、半から今度は自分のセミナー。

1時間半かけて先週準備した分の残りを終わらせた。証明の最後は細かい詰めを延々繰り返していてただでさえ非常に複雑なのに、準備時の記憶が薄れていて読み直しもしておらず、結果発表にかなり難航してしまった。聴いている側としても疲労困憊だったらしくここで終わりになった。昨日準備した分はまた来週に持ち越されることになる。

今日は博士課程の方の発表がない。この後、特に準備してきたわけではないちょっとした話題を二人それぞれが話し、午後4時過ぎに解散になった。

DMOJのコンテストが終了していた。9位でレートは2825→2855(+30)、highest。P4の連結成分の重複をなくす方法に、連結成分の頂点数で割るというものがあって目から鱗。ただし自分の解法だと、頂点の数だけ答えに足されるとは限らないので使えない。

DMOPC '22 November Contest - DMOJ: Modern Online Judge

夕方から雨の予報で、すでに小雨が降っていたため急いで帰宅した。しばらくTLを眺めた後、ハーメルンの更新を読んだ。

syosetu.org

なろうのほうでも連載されている。そちらで一区切りついてから一気にハーメルンに投稿しているようなので、なろうのほうが新しい話を先に読める。
週記（2022/08/08-2022/08/14） - kotatsugameの日記

ということで、ついにハーメルンのほうに投稿され始めたため、読んだ。やはり面白い。主人公がいよいよ表舞台に姿を現す……わけではないが、それに近い行動は取っている。そのシーンは最高だった。

午後9時から午前2時まで日記を書いていた。頻繁に集中が切れてYouTubeに吸い込まれてしまう。いっそ切り上げて別のことをしたり積読を消化したりするべきなのに、YouTubeで時間を浪費してしまうのはかなり最悪。何とかするよう心掛けたいが、モニターを見ているとYouTubeの画面も目に入ってきてしまうのでなかなか難しい、と最近特に実感している。

それからしばらくラノベを読んで、午前3時半に就寝報告のツイートをした後ハーメルンを開き、30分ほどで寝落ち。なんだか眠る気になれなかったが眠気だけはしっかりあったようだ。

11/30(水)

午後4時起床。ぐっすり眠れて快適。もう少し眠ってしまおうかとしばらく布団でYouTubeを見ていた。

布団から出てPCの前に座ったが、やるべきことからの逃亡のためDMOJにあったよくわからないコンテストのミラーに出た。来週月曜日の午後2時までのコンテストだから、ギリギリここに内容を書いてもよいだろう。

12/07追記：言い忘れていたが、この週記の公開はちゃんとコンテスト終了後だった。

COCI '22 Contest 1 Unofficial Mirror - DMOJ: Modern Online Judge

1問目はよい。2問目はちょっと面倒。一つのチョコレートによる差分がどんな値のものまで購入するかを二分探索する。 $c$ がある区間の外にあるなら購入するという条件になるので、 $c$ をソートしておくと個数なり金額の和なりが求まる。

3問目は適当な一つの円の半径を $r$ と置き、他の円の半径を $r$ の1次式で表せばよい。 $r$ の係数は $\pm 1$ が交互に現れ、特に奇閉路があると値が高々一意に定まる。そうでなければ面積の和、つまり半径の2乗和を最小化する必要があるので、 $r$ が取れる値の範囲と2次関数の軸を見ながら頑張る。これを連結成分ごとにやる。解が存在しない場合の出力がNEなのを最初NAだと思い込んでいて、修正しきるまでに3WAを重ねた。

4問目は対角線の長さの半分を $d$ とすれば $d\mid x$ かつ $d\mid y$ かつ $x/d+y/d$ が奇数となることが条件。まず $d=\gcd(x,y)$ が条件を満たすかチェックし、満たすならその約数で素因数 $2$ を同じ数だけ含むものを数えればよい。斜めになっているからと最初45度回転かと考えていたが、簡単に解けた。

5問目は区間の右端を固定するごとに区間の $\gcd$ が $O(\log h)$ 種類となるので、それぞれ最大の区間を求めればよい。左に見ていったときの累積XORが変化する位置を管理すると、右端を右に動かすごとに更新できる。

1時間ちょっとで全完。2問目と3問目が思ったより難しくて軽い気持ちで始めたことを後悔していたが、残りはすぐ解けたのでまあまあ快適なコンテストだった。

午後6時から、明日の講義での発表に使う資料を作り始めた。

PDF資料はあと一人分くらい残っている。一度は最初の人が発表することになったものの、中間テストなどで忙しそうだったので、自分と先生で少しずつ担当することにした。
週記（2022/11/21-2022/11/27） - kotatsugameの日記

とっとと終わらせて遊びに行くつもりだったのに、なんだかんだ午前2時までかかってしまった。なまじ関係する話をいくつか知っているだけに、あれもこれも言及したくなってしまう。しかしそれで不正確な言葉を口走ってもよくないから、ちゃんと知っていると自信を持てることのみ、また関係のない話をできるだけ省くように頑張った。そもそも持ち時間も少なめ。

また時間がかかったのは内容を吟味していたからだけではない。相変わらず今日も集中を切らしまくって、途中でYouTubeを見たりラノベを読んだりとやりたい放題だった。特にラノベについては1冊読了。

「転生魔王の魔術師範」。最近ちまちま読み進めていたもの。あまり没入できず、そうやって細切れに読んでしまった。淡々としていたのに急に主人公が死にかけたり、裏切り者を強引に仲間に引き戻したりと、なんとなく引っかかってしまう展開がいくつかあった。主人公の強さもいまいちピンとこない。

資料をClassroomにアップロードしてから別のラノベを読み始めた。かなり好みの作品だったためじっくりじっくり読み進め、午前7時半読了。

「Vのガワの裏ガワ」。非常に面白かった。ヒロインはVTuberで、そのデザインを担当したイラストレーターが主人公。前半はヒロインがVTuberデビューするまでの話で、ここが特に面白かった。登場人物の導入と、全員を巻き込んでVTuberを作り上げる過程が絡み合い、とてもワクワクした。

実際にデビューすると人気は爆発。最初1か月の配信や登録者数の増え方などの様子がダイジェスト形式で描かれた。セリフこそ順風満帆といった感じだが、話の構成から不安感を覚えずにはいられない。だってまだ本の半分までしか到達していない。すでにこんなに大成功していて、じゃあ後半は一体何をするつもりなんだ。

案の定、この後にはかなり苦しい展開が待ち受けていた。これ以上のネタバレは避けておくが、ともかく辛い話に入って、しかし前半でがっちり心を掴まれているためズルズル読み進めていけた。1巻だからちゃんと最後までには解決してくれるだろうというメタ読みもある。これも的中し、ちゃんと丸く収まって読後感は非常に良い。

この巻はVTuberになるまでとなってすぐの話だった。しかし各キャラクターが非常に魅力的であることは十二分に伝わっている。彼らの日常がもっともっと読みたい。2巻以降が非常に楽しみである。

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

12/01(木)

午後3時45分起床。急いで大学に向かった。いつものように購買でラノベを買いつつTAへ。

昨日の日記でも書いたように、今日は自分と先生が発表を担当する日だった。事前の予定ではそれぞれ30分程度で済ませ、残り30分で今後の講義について話し合う予定。

結論から言えば、自分が60分、先生が50分発表に使ってしまいすべてが崩壊した。20分も講義が伸びると受講している学生にも申し訳ないし、部屋を使おうとして外で待っていたサークルの面々にも申し訳ない。今日は完全に自分が悪く、あまりの罪悪感から逆に何も言えなかった。

内容自体絞れていたとは言えないし、言及しないと決めたこともうっかり口走ってしまったりしていた。ギリギリで完成させて終わりではなく、ちゃんと発表練習くらいすればよかった。時間も短いしちゃんと話すべきことを話し終えなければならないしで、普段のセミナーと全く違うということをちゃんと認識できていなかった。

その後来週・再来週に何をやるかだけ手早く決めて解散。ただ相変わらず中間テストシーズンだし、いっそ休講もありなのでは？と言ってみたところ、なんと休講になった。もともと来週の木曜日は大学院の何かのオンライン説明会と被っていたのだ。

ICPCや帰省用に学割を発行し、学食で食事して午後7時頃帰宅。

11月の読書記録をツイートした。前半かなり頑張ったものの後半で失速し、1日1冊ペースには全然届かなかった。かろうじて積読は減らせたようだが、焼け石に水と言わざるを得ない。

11月の集計
買った：19冊
読んだ：22冊
積読：-3冊
積読（累積）：+116冊
— こたつがめ (@kotatsugame_t) 2022年12月1日

ICPC用の新幹線の切符を取りたい。日程や時刻の見当を付け、紙にメモして午後8時半ごろまた外出。今日のみどりの窓口はガラガラで、ほぼ待たずに購入できた。

その後ゲーセンに行って閉店まで遊んだ。今日はWACCAコラボイベントの新曲を埋めていた。高BPMの曲が多くて大変だろうと譜面動画を見た時から思っていて、実際かなり疲れたわけだが、そこそこ良いスコアは出た。SSSすら出ないのではないかと心配していたのだ。

14+ pic.twitter.com/c60PHn7AoX
— こたつがめ (@kotatsugame_t) 2022年12月1日

ラスクレでは「TiamaT F:minor」をプレイしていた。SSSの手元動画が撮れたものの、ラストでしょうもないミスを出しせっかくのスコア更新チャンスを台無しにしてしまったのが悲しい。そもそも中盤からすでにボロボロ。冒頭で三つアタックを出した後、それなりに長い間AJで通ったので緊張してしまった。運指らしきものは組んでいるが運ゲーの域を出ていない。

TiamaT:F minor 7-2 手元
悲しいなあ pic.twitter.com/bcHfem3dFT
— こたつがめ (@kotatsugame_t) 2022年12月1日

ちなみに、チュウニズムのグッズキャンペーン的には12/07までにあと13回プレイする必要がある。1日ゲーセンに行けば達成できるだろう。

油そばを食べ、日付が変わったあたりで帰宅。しばらくダラダラTLを見た後シャワーを浴びて日記を書き始めた。さらに今日は、11/14の週の週記で空欄のままになっていたうち日曜日のCF combinedについても書いた。

間にしばらくネット小説を読みふけってしまい、時間はかなりかかっている。午前7時頃切り上げて布団に入り、少しラノベを読んで就寝。

12/02(金)

午後2時ちょっと前に起床。トイレに行ったりしていたら午後2時からの1on1に少し遅れてしまった。

今週はなんと何もやっていない。本当は今日午後1時くらいに起きて、いつものように1時間くらい何かしてお茶を濁すつもりだったのに、ぐうすか寝てしまった。なので今日はタスクに関連することの説明だけで、1時間半ほどで終わった。

その後大学に向かい、サークルの前に一度文学部のキャンパスに足を運んでみた。集中講義のための偵察である。教務課に突撃して教室がある建物を教えてもらって、実際に足を運んで確認。さらに原付を停める場所についても見当を付けておいた。

教室の情報も出ていたが文学部のキャンパスに不案内でわからない。講義開始までに一回偵察に行きたいと考えている。
週記（2022/11/21-2022/11/27） - kotatsugameの日記

午後4時40分からはサークルバチャ。上のようなことをしていたら開始時刻に少し遅れてしまった。

https://kenkoooo.com/atcoder/#/contest/show/50596519-5265-4ab0-a91e-0723e08427f8

5問目まではよい。6問目は $N\bmod 4$ で場合分けしてしまい、それでも頑張れば構築できるのに一部頑張り損ねて1WA。7問目は解いたことがなく少しひるんだものの、取り組んでみると非常に簡単だった。部分点の $O(N^2)$ はよく見るdpで、遷移をちょっと睨みつけるとすぐ $O(N\log N)$ になる。線形時間でも解けるがそこまで詰める必要もない。

しばらく感想戦をした後、午後7時前くらいに解散。

黒板でこたつがめさんがゴルフしてた pic.twitter.com/veSn6aG6YO
— とりゐ(競プロ) (@torii_kyopro) 2022年12月2日

学食で夕食を摂って帰宅した。しばらくハーメルンの更新分を読んだ後、yukicoderのAdvent Calendar Contestの1問目を通して2問目であれこれ考えているうち、yukicoder 370の時間になった。

yukicoder contest 370 - yukicoder

Aは $B-A\lt x\lt B+A$ なる $x$ を数えるので $B$ が消える。Bは多項係数になって、 $A$ の要素はできるだけ均したほうがよさそう。

Cは $N$ からどんどん0に置き換えていくと、 $K$ ギリギリにした後のつじつま合わせを1要素で行えるので、操作回数は高々2回。1回でOKかの判定は尺取りでできる。

Dは(を $+1$ 、)を $-1$ とすると、最初に $+(N-1)$ を置き、その後 $-(N-1)+(N-2)$ 、 $-(N-2)+(N-3)$ 、……、 $-1+0$ とすることで一意になる。文字数の総和が $N(N-1)/2\times 2=N(N-1)\lt N^2$ でうまいこと条件を満たしている。

Eはかなり苦労した。端から順に操作することを考えると、 $A$ の交代和が $\bmod M$ で0に等しいことが良い数列であることと同値。チェックは簡単だが数え上げが辛かった。辞書順で大小関係が決まるインデックスを固定すると、それより左の項は一意。しかし右の項が問題で、要素の上限が $M-1$ なら最後の項を弄ればどうにでもなるのに、 $M-2$ なのでそうもいかない。

交代和の符号も考慮したうえで、 $i$ 項目より右によって $\bmod M$ で $0\le k\lt M$ を作る方法が $dp_k$ だとわかっているとしよう。このとき、 $i-1$ 項目より右とした場合に対応する $dp_k'$ がどうなるかを考えてみる。本当なら $dp_k'=\sum dp$ としたいところ、 $M-1$ を置けないので $dp_k'=\sum dp-dp_{k\pm 1}$ となる。この $\pm 1$ が具体的にどちらであるかは、交代和の符号による。

インデックスがずれているとつらいので、オフセットを弄ることで対応すると、更新としては $dp_k\leftarrow\sum dp-dp_k$ ができればよくなる。これは作用素が1次関数で区間和を取得できる遅延セグ木で実現可能。

これで、固定したインデックスの左右について交代和がどうなるか分かった。 $L$ と $R$ としよう。 $R$ はまだ確定していない。あとは固定したインデックスにおける値を $a$ とする。すべて交代和の符号も含めた値にしておくと、必要なのは $L+a+R\equiv 0\pmod M$ で、辞書順の条件で $|a|$ が取れる値の範囲が制限されている。しかしそれでも対応する $R$ が区間になるので、セグ木の区間和取得で対応できる。

眠気もあって合わせるのに一苦労。出したら落ちてしまったので、自信のなかったオフセットのインクリメント・デクリメントを入れ替えたら通った。

Fをしばらく考えて解けず、Gに進んだ。こちらは少し考えたら急に閃いた。Small Multipleと同様に解ける。

D - Small Multiple

Fに戻ってきた。まず先ほどまで考えていたことの説明から。操作回数をキーにしたdpは、具体的な $A$ を考えず $S$ から直接答えを出せるのでそれっぽい。しかし遷移のためには1要素ずつ見る必要があって、どうしても高速には書けなかった。

次に $A$ を固定した場合を考えてみた。累積和を取って、それが初めて負になる位置を探すと、それより左のどこかを区間の左端として操作しなければならない。累積和が最大となる位置が最適で、操作後にはその値の倍より少し大きい値が累積和に出現することになる。これを繰り返すと、高々 $O(\log N)$ 回の操作で累積和に十分大きな値が出現し、他の項が負になる余地がなくなる。

改めて考えてみればすでに解けていた。つまり、操作回数が少ないので、それをキーにして行うdpが十分高速。

全完6位。Fがかなり面白かった。Eは解説の $M-1$ 進数を考える方法が天才すぎる。

ラノベを1冊読了。「ログアウトしたのはVRMMOじゃなく本物の異世界でした」3巻。主人公が活躍して称賛されるのは大歓迎のはずだったが、あまりにも行き過ぎていると感じてしまい好みから外れた。ヒロインたちが何か一言喋るごとに、ついでに主人公への誉め言葉も口にしているような印象がある。またこの巻も2巻と同様VRMMOパートと現実世界パートがほぼ完全に分かれている。今のところ二つのストーリーがただ平行して進んでいるだけに思えて、どちらも中途半端に見えてしまった。

Advent Calendar Contestの3問目を通した。dpの遷移をセグ木で高速化する。遷移のたびに1要素開けるのでインデックスで頭を壊してしまいがち。たまに見るだけなのであまり上達しない。

#822063 (C++14) No.2139 K Consecutive Sushi - yukicoder

午前1時からSRM842に参加した。

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

Easyは文字ごとに数えてdp。Medは $C$ が小さければ桁dp、大きければ全探索。Hardは同じ色が塗られたマスを区間にして管理。解法は全部自明で、実装を頑張るだけのセット。

チャレンジフェーズではvectorの配列外参照をしているコードを見つけたものの、手元で写経してみると全然落ちなかったので手は出さなかった。それは結局システスで落ちて、ほかにも結構な数落ちていたが、自分のコードは問題なく全部通って全完5位。2878→2912(+34)。

ちゃんと通したので遠慮なくこき下ろすことができる。ABCから3問取ってきたみたいなセットでdiv.1をratedにするのはどうなんだ？12月に2回予定されていたうち片方が消えてこれが今年最後のSRMらしいが、本当にこのセットを残すので正しかったのか。

ICPCのチーム紹介ドキュメントの制作に取り掛かった。今年もAAのQuineを書くつもり。技術的には昨年の時点で十分なものが完成しているため、それほど苦労はしないだろう。今日はExcelのマスを塗りつぶして元になるAAを作った。

kotatsugame.hatenablog.com

午前5時から日記を書きつつ、Advent Calendar Contestの2問目を検索して通した。

#822117 (C++14) No.5009 Draw A Convex Polygon - yukicoder

not522.hatenablog.com

午前8時就寝。

12/03(土)

午後2時半過ぎ起床。

午後3時からOpenCupの代理コンテストに出た。今日やる予定だったのはPetrozavodsk Summer 2022. Day 6だが、これはMulti-Universities Campにもあったセットだと発覚。代わりにDay 7をQOJで走った。

Petrozavodsk Summer 2022. Day 7. HSE Koresha Contest - Dashboard - Contest - QOJ.ac

チームで5完。個人としては、今日は5時間一問も解けていない。残念。考察が終わった問題の実装を積極的に担当するべきなのかもしれないが、チームの中だと実装も速いほうではないし……と尻込みしてしまう。逆の立場でICPCのチームメイトから似たようなことを言われたことがあるので、その場合は必要ならこちらから実装を押し付けていくことを意識したい。

序盤でAを誤読しいたずらにペナを生やした後、Gと心中した。求める空きスペースがある領域を $n\times n$ から $(n-2)\times(n-2)$ に12回のクエリで縮めるという方針で、 $12n/2=6n$ とクエリ回数がピッタリだったためかなりそれっぽかったのだが、解説を読んでみると全然違うことをしていた。 $n$ の偶奇に関する考察だけは合っていたのが救いか。ここもほとんどエスパーみたいなものだった。

感想戦では二分探索の中で全探索するときの高速化テクを教えていただいた。今日のセットのこれを使うらしい問題は、その先も難しくて全然わかっていない。

wata-orz.hatenadiary.org

午後9時からABC280。

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder

Aはgrep -cを使うと#が含まれる行数が返ってくることに気づかず2WA。Bはよい。Cは深く考えずに初めて異なったインデックスを出力した。文字列の末尾についても意識する必要はない。

最後の文字のケース、C++だとstring sに対してs[s.size()]でアクセスするのが合法でヌル文字が返ってくるため、何も考えなくてもよい https://t.co/avheGNBHdW
— こたつがめ (@kotatsugame_t) 2022年12月3日

Dは二分探索。あらかじめ $K$ を素因数分解しておくと、ある素因数を階乗がいくつ含むかは簡単に求まるので判定問題が解ける。素因数の個数がint型に収まらず1WA。Eは期待値dp。

Fは連結成分ごとに解く。重みの和が0でないループがあれば、それを適当な向きに何回も通ることでポイントをいくらでも増やせる。そういうループがない場合は適当に木を取って考えてよく、答えがその木における2頂点間の距離になる。距離を求めるのにLCAを計算する必要があると思って実装しきったのに、最後答えを求めるだけになって初めて式を考えてみると、 $Z={\rm lca}\;(X,Y)$ として $(d_Z-d_X)+(d_Y-d_Z)=d_Y-d_X$ となるため $Z$ を知る必要がなかった。

残り時間はずっとGと格闘していた。 $x\le x'$ とすると、2点 $(x,y)$ 、 $(x',y')$ の間の距離が $y\le y'$ なら $\max(x'-x,y'-y)$ 、そうでないなら $x'-x+y-y'$ となることをまず確認した。XY平面上である点から距離 $D$ 以下の六角形領域を図示し、考察を進める。

選ぶマスを二つうまく決め打つと、その両方から距離 $D$ 以下の頂点同士も互いに距離 $D$ 以下にならないかということを考えた。これはダメだが三つならどうかということで、 $x-y$ の最大・最小・ $x$ の最小を決めると良いと思い込み実装した。しかしWA。 $Y$ 座標の差が $D$ より大きなペアを含んでしまう可能性が残っている。

改めて書き直そう。点を $x-y$ でソートし、距離 $D$ 以下の2点を取る。この二つを必ず選ぶと固定し、その間に並ぶ点のうち2点からの距離がどちらも $D$ 以下の点を抜き出す。それらをどう選ぶか数え上げたい。上で示した距離の式のうち $x'-x+y-y'$ は必ず $D$ 以下なので、残り考えるべき条件は $X$ 座標・ $Y$ 座標の範囲が共に $D$ 以下となることである。

抜き出した点を $x$ でソートし、1点 $(x_1,y_1)$ を $X$ 座標が最小のものとして決め打ってみる。すると $X$ 座標に関する条件を満たすような点は区間になる。区間内の点のうち1点 $(x_2,y_2)$ をさらに決め打って、 $Y$ 座標が最大の点としてみる。ただし $Y$ 座標が同じ値は $X$ 座標のソート順によって並べている。

当然 $y_2\le y_1+D$ である。実はこの時点で、区間内の点であって $Y$ 座標が $[y_2-D,y_2]$ であるような点を自由に選んでよい。 $y_2\lt y_1$ のとき、もし $Y$ 座標が $y_2-D$ の点を選んでしまうとまずいように見えるが、そのような点は $x'-x+y-y'$ が $D$ を超えてしまうため存在しない。この事実は最初意識しておらず、日記を書いている途中に気づいた。

よって選べる点の個数を数えて2の肩に乗せ、答えに足せばよい。実は各 $y_2$ に対してこの値を管理することができる。 $X$ 座標の条件による区間はずれていくだけなので、1点追加・削除ができれば十分。例えば $(x,y)$ を追加する場合、 $(y,y+D]$ に対して2を掛けたり、 $[y-D,y]$ の個数を数えて2の肩に乗せた数を $y$ に加えたりすることになる。削除はこの逆。 $Y$ 座標を座圧して、遅延セグ木やBITを使うと実現できる。

計算量は $O(N^3\log N)$ 。コンテスト終了2分半後にサンプルが合って、提出したら2994msで通った。

久しぶりの6完で119位。序盤のコードゴルフなど関係なく遅かった。FでLCAを書いていたのがかなり無駄。Gは2点間の距離を $\max(|x-x'|,|y-y'|,|(x-y)-(x'-y')|)$ と書けるらしい。 $(x,y)\mapsto(x,y,x-y)$ として3次元空間におけるチェビシェフ距離になる。

コードゴルフ。AはRubyだった。BashやPerlを試していて、速度差で負け。BはAWKでこれも負け。CはPerlで、文字列のXORを取ってヌル文字にならなかった位置を探す。Dは解説にある別解をRubyで実装した。Eは期待値dpがdcで提出されており、解説のほかの方法を試しても縮みそうにない。以降は手付かず。

Advent Calendar Contestの4問目を通した。円盤を小さいほうからいくつ、どの杭に揃えたか持ってdp。いくつか遷移があるように見えて最小手数がわからず、Rubyで $\bmod$ を取らない値を管理して解いた。解説を見て納得。今注目している円盤を動かす前にそれより小さい円盤をどかす必要があるか考えていたが、どかした先の杭に対応するdpの値を見るだけでよかった。これで遷移が1通りになる。

#822373 (Ruby) No.2147 ハノイの塔のおもちゃ - yukicoder

さらにAOJ-ICPCから1問解いた。800点のFloating Islands。解説ブログが上がっていたので読む前にチャレンジしてみたら、うまいこと解けた。

Floating Islands (AOJ 2571) - あああああ

$d\leftarrow\min(d,n-1)$ としてよい。後から気づいたが別にしなくてもよかった。ともかく、その元で $\sum d\lt 2(n-1)$ だと答えは-1。そうでない場合を考える。まず頂点を $p$ でソートしておく。

両端の頂点とその間にある $d\ge 2$ なる頂点をパスになるように結び、余っている次数を使って残った $d=1$ の頂点を連結にするのが最適だと感じた。特に、パス上の各頂点が担当する $d=1$ の頂点は区間になる。パス上の頂点を $p$ が小さいほうから順に見て、 $d=1$ の頂点をどこまで結んだかでdpする。

今見ているパス上の頂点を $(P,D)$ とする。遷移幅に $D$ 以下という制限があること、遷移コストの式が絶対値記号を含むことが面倒。まず後者を解消できた。 $p\lt P$ なる頂点が残っていれば、今のタイミングでできるだけ結んでおくべき。なぜならこれ以降結ぶコストは大きくなる一方だから。残りは $p\ge P$ のケースで、これで遷移コストから絶対値記号が外れる。

あとはコストの式を適当に分解するなりなんなりして遷移できる。遷移幅の制限については、優先度付きキューで持っている値を適宜popすることで対応可能。実はここはスライド最小値でもよく、それを使うと計算量が $O(n^2)$ になる。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7142498

12/05追記：上の実装は、キューに入っている遷移すべてのコストを増やすのをオフセットを弄ることで実現しているが、これだと別に $p$ と $P$ の大小関係で分ける必要はなかった。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7146119

シャワーを浴びて日記を書き、午前5時くらいに布団に入った。ここから12時間寝れば睡眠調整として完璧だ、などと考えていたのに、うっかりAdvent Calendarのブログやハーメルンを読み始めてしまった。午前7時過ぎに寝落ち。

12/04(日)

午後4時過ぎに目を覚ました。12時間睡眠とはいったい何だったのか。再度眠ればよいのにハーメルンに手を出してしまった。

1作読了。「超犯罪都市デスシティ　～世界最強の殺し屋～」。設定が好みだった。ただし、最新話近くで神話時代の話をしているのがコテコテすぎてちょっと苦手かも。

syosetu.org

別のハーメルンをしばらく読み進めた後、午後7時前に布団から出る。食事してチーム紹介ドキュメントのAA Quineの準備をしていた。

午後9時に近づくにつれソワソワ・ドキドキして何も手につかなくなった。じっと耐えて時間が過ぎるのを待ち、午後9時からAGC059に参加した。およそ4か月振りのrated。

AtCoder Grand Contest 059 - AtCoder

AはAGCのA。直感的には、一つ文字を固定してそれ以外だけ操作し、揃えていくのがよさそう。ということで一番最初は各文字の連結成分数を数え、小さいほうから二つが答えと考えた。しかし反例がある。例えばABCBCBAという文字列があったとして、Aを固定するとBCBCB→BCCCB→BBBBB→AAAAAと3手でできる。連結成分数を見るとCを固定して4手と答えたくなってしまい、間違い。

そこで、文字を固定するのはそのままにして、間を先ほどのような方法で変換する手数を求めることにした。間の連結成分数を $c$ とすると $\lfloor c/2\rfloor+1$ 手かかるので、これを固定した文字で区切った区間ごとに求める。両端の処理など非常に面倒くさいのを何とか実装し切ったものの、提出するとWA。

ここでふと天啓があり、隣り合う2項が異なる位置を数えてみた。これを2で割った値がだいたい答えになっていそう。微妙にずれているなと思ったものの、先頭と末尾の文字も隣り合っていると見なすことで見事に一致した。出したらAC。

実は書き換えている最中、最初の提出で一部 $N$ と $Q$ を取り違えていることに気づいていて、もしかしたらこれがWAの原因かもしれないと考えた。しかし先ほどの解法と今のエスパーを見比べると後者のほうがいかにも「AGCらしい」から、それを提出。前者も後から提出してみたものの普通に落ちた。

Bは簡単。種類数を $k$ とすると、ソートして並べることでペア数 $k$ が達成できる。また、各色の出現回数を降順に $A_1,\dots,A_k$ としたとき、 $A_1\ge k-1$ なら同じものを並べた後間に埋め込むことでペア数 $k-1$ を達成できる。

同じことを、最初に並べるのを2種類にすることで $A_1+A_2-2\ge k-2$ の場合にも行えることに気づいた。これもペア数 $k-1$ 。より一般に、いずれかの $i$ について $A_1+\dots+A_i-2(i-1)\ge k-i$ ならペア数 $k-1$ が達成できる。

実はペア数 $k-2$ 以下は達成できないのではないかと考えた。 $k-1$ と1引いていることから木の頂点数と辺数の関係を思い浮かべ、示すことに成功。色に対応する $k$ 頂点がペアを辺と見たときに連結になる必要があるため、必ず $k-1$ ペア必要となる。

あとは実装すればOK。並べ方がちょっと面倒だったが無事一発で通った。

Cは大変。まずどういうケースで質問がスキップされるか観察する。相異なる三つの数 $x,y,z$ があって、 $(x,y)$ と $(y,z)$ を質問した後に $(x,z)$ を質問されるとしよう。すると $P_x$ と $P_y$ の大小関係が $P_y$ と $P_z$ の大小関係と一致する場合に質問 $(x,z)$ がスキップされる。つまり大小関係で $P_x$ と $P_z$ の間に $P_y$ が位置してはならない。

より一般に、 $(x,y_1),(y_1,y_2),\dots,(y_k,z)$ が質問されて大小関係が一致していれば $(x,z)$ はスキップされてしまう。しかしこの時点でまだ質問のスキップが確定していないなら、例えば $(x,y_k)$ という質問がそれ以前に行われているはずだから、結局 $(x,y_k,z)$ で先ほど見た三つの数の場合に帰着される。つまり、上に示した三つ組に関する条件が十分条件になっている。

順列を数え上げる。まず、最後に質問されるペア $(A_{N(N-1)/2},B_{N(N-1)/2})$ について、これを $(x,z)$ とすると、 $y\ne x,z$ なる $y$ のどれについても $P_x$ と $P_z$ の間に $P_y$ が位置してはならない。このことを、 $x$ と $y$ を真っ先にマージすることで表現しよう。

そのように、後ろからペアを見てどんどんマージしていき、その過程を二分木として表す。条件はまだすべて表現できていないので、例えば三つ組 $(x,y,z)$ であって $P_x$ と $P_z$ の間に $P_y$ が位置してはならず、かつ $x$ と $z$ がマージされる前に $x$ と $y$ がマージされてしまったものについて、別にメモしておく。

二分木の葉でないノードについて子のどちらを先に並べるか決めると、 $2^{N-1}$ 通りの順列が得られる。正確にはその逆順列が $P$ だが、ともかくそれらだけが条件を満たす候補である。さらにその中で、メモした条件まで満たすものを数え上げればよい。

最初は「 $x$ は $y$ の前に・後ろに来る」という条件を管理しながら木dpする方針で考えていた。しかしこれは計算量が爆発してしまう。上のノードで子の順番を変えると、それに関係する条件「のみ」が変わるため、下のほうのノードに課される条件が指数関数的に増えてしまう。この方針に見切りをつけたのは残り1時間くらいのところだった。

上を変えると下も変わるのが問題なら、上と下がどういう関係かを考えればよいと思った。つまり、最初に子の順番を適当に定めた後、そこから入れ替わったか・入れ替わっていないかを真偽値で管理し、その間の関係を見る。なんとこれで条件がうまく表現できることが分かった。

$N-1$ 個の真偽値に対してそれぞれ真・偽の頂点を用意し、入れ替わりの状態が一致するかしないかで適切に辺を張る。これをUFで行い、矛盾が発生すると答えは0通り。発生しないなら連結成分を見て適当に割り振ればよくて、答えは2べきになる。

assertを大量に入れて実装した。分岐予測が効くと期待出来てパフォーマンスへの影響は少ないはずだから、アルゴリズムから導かれる状態があるなら入れ得だと思う。最近はよく使っている。

最初の提出ではREが出てしまったが、詳細を見るとACとREの2通りしかないから答えが間違っているわけではなさそう。手元で小さなランダムケースを作って試すとすぐREが再現でき、それを解決してもう一度提出したら通った。デバッグが快適でよかった。

残り30分はDを考えて、特に何もわからずコンテスト終了。結果は3完46位、パフォーマンス3032、レートは2864→2882(+18)でhighest。Cはもう少し早く通せたかもなあとは思う。ratedが全然ないのにじわじわとしか上がっていないのは苦しいが、逆にあまり下がっていないということで順調と言えなくもない気がする。

午前2時くらいまでTLを眺めながら余韻に浸っていた。

AA Quineの作成に戻り、午前4時頃にひとまず完成。パディングのために入れた文字列をチーム名などに置き換える作業は残っているが、それはチームメイトの意見を聞きつつ締め切り直前にやることにしたい。

それからインターン先勉強会の準備を始めた。明日発表なのでかなりギリギリに見えるが、考えがあってこうしている。つまり、いま作ったAA Quineについて発表を行うつもりなのだ。内容自体もおおむね昨年のブログ記事から引っ張ってくることができるので間に合うだろうという見込み。逆にAA Quineについて発表するからこそ、先に今年のチーム紹介ドキュメントを形にしておく必要があった。

kotatsugame.hatenablog.com

午前10時に完成した。シャワーを浴びて布団に入り、少しハーメルンを読んで午前11時半ごろ寝落ち。