09/26(月)

午後4時半起床。インターン先定例会が始まっている。布団から飛び起きて会議に接続した。

今週の進捗、というか稼働状況は、勉強会スライドを作っただけ。先週やると言ったことに全く手を付けられていない……。今週こそ頑張りますと言って終了。勉強会は自分の番。質疑応答含め1時間半ほどの発表で、午後7時前に終了した。その後スライドを公開した。

勉強会0926.pdf - Google ドライブ

今日のテーマは文字列の列のソート。長さの総和にだけ制約がついているような文字列たちを辞書順でソートするとき、どういう計算量になるのか調べた。よくあるシチュエーションだが、初めて出会ったとき本当に間に合うか心配にならなかっただろうか。僕はちょっと戸惑ったことを覚えている。結局何も考えずにソートして間に合うので、そういうものだと捉えていた期間が長く、具体的な計算量とその証明方針を知ったのは結構後になってからだった。

列の長さを $N$ 、文字列の長さの総和を $S$ とするとき $O(S\log N)$ でソートできることを、代表的なソートアルゴリズムであるマージソートとクイックソートで証明した。解析がしやすいアルゴリズムなので結構簡単。ところがstd::sortでは証明できなかった。大まかな話はスライドに書いたが、後からリプライを頂いて、ヒープソートというよりはそのGCC実装が解析しにくい形になっているのが原因だと理解した。各要素のヒープ上で移動する回数を抑えられず、下のツイートの計算量解析が成り立たないのだ。

pop 操作における 2 つの (親子関係にある) 文字列の swap において、深さが減少する方の文字列にコストを負担させます。1 つの文字列に着目すると、高々 log(N) 回コストを負担することが分かります: 深さは広義単調減少で、真に減少するときだけコストがかかるので。→ O(S log(N))
— 熨斗袋 (@noshi91) 2022年9月26日

なぜそんな変な実装になっているかの理由付けもしてもらった。一般のケースではいかにも高速になっていそう。

あまり関係ないが、こういう仕様になってる理由は察しがついた。元々葉にある要素は小さいがちな上に binary heap の要素の大部分は葉の近くにあるから、pop に伴う push down はほとんど葉の近くまで行く可能性が高い。
1. 左右どちらに push down するか判定
2. push down を停止するか判定
— 熨斗袋 (@noshi91) 2022年9月26日

発表に対するコメントで、文字列ソートの定数倍高速化について面白い話を聞けた。比較するときに勝手に求まるLCPを保存しておくと速いというのだ。例えばマージソートだと、ソート後に隣接する要素間のLCPが求まっていて、これを使うと次回のマージで先頭いくらかをスキップできる可能性がある。クイックソートはLCPでバケツソートすると単に2分割するより細かくできる。普通に比較していて求まるようなLCPが、確かに使いやすい値になっていた。

日付が変わるまで日記を書き続けていた。日曜日を勉強会の準備に充てたため土日の分がまるまる未完成だった。そんなことは先週の時点で分かっていたのだからもっとしゃかりき書いておけば良かった。夏休みの宿題を溜める癖は今になっても治っていないということだろう。宿題はぶっちぎることができるが、週記はそうもいかない。甘えればすぐ途切れてしまうから、自分をよく律さねばならない。

午前0時の直前になっていったん投稿。まだ微妙に書き足りない部分がある。とはいえ疲れた。集中が切れたので、ラノベを読み始めた。しばしばTLを眺めつつ、午前4時半に1冊読了。

「お隣の天使様にいつの間にか駄目人間にされていた件」7巻。文化祭。6巻の夏休みと同じく好きなシーンもあるし展開的には好みなのだが、頻繁に挟み込まれる主人公とヒロインの甘いやり取りにちょっと飽きが来てしまった。両片思いは好きなのにくっついたらあとは興味が離れていくだけとは、なんとも業の深い嗜好である。

また週記に戻って、書き足りない部分を完成させた。読み返しを一切行っていないが今日はここまでにしたい。明後日水曜日の来客に備えて部屋の掃除とゴミ出しを行い、しばらくPCでハーメルンを読んでから布団へ。TLを眺めていたら寝落ちしたらしい。午前9時半だった。

09/27(火)

午後7時起床。もう遅い時間だが今日はゲーセンに行きたい。準備していざ出発、と思ったら、日曜日にAmazonで注文したものがもう全部届いていた。お金を出してお急ぎ便にしただけはある。開けて冷蔵庫に入れたり段ボールを片づけたりしたら午後8時半になってしまった。

食事をスキップして閉店まで目一杯遊んだ。今日は新曲を埋めた後手元動画を撮影していた。成果としては理論値+1。OPがついに99%台に乗った。

非実在系女子達はどうすりゃいいですか？理論値手元 pic.twitter.com/fEdgRKwK7m
— こたつがめ (@kotatsugame_t) 2022年9月27日

OP 99%乗った！ pic.twitter.com/hTsHBZPLTs
— こたつがめ (@kotatsugame_t) 2022年9月27日

ラーメンを食べ、日付が変わってから帰宅。手元動画を投稿した後、しばらくYouTubeで時間を溶かした。

CF #823 div.2のE問題を解説を見ながらupsolveした。数列の最小値か最大値を固定するという方針は明らかで、最小値に対してその倍数を全探索すると数列が $1$ ばかりの場合にTLEするが、最大値に対してその約数を全探索すると十分少ないという話らしい。この事実はあまり意識したことがなかった。あとは区間の両端としてありうる範囲をそれぞれ絞り込む。前計算も実際に求めるのもそこそこ面倒だった。

Submission #173748947 - Codeforces

午前5時から先週の週記の校閲を行っていた。3時間ほどかけて最後まで目を通し、完了。その後しばらく日記を書いて午前10時くらいに布団に入った。しかしそこからノクターンノベルズを読み始めてしまい、就寝が午後1時前になった。明日は夕食を外で食べ、その後部屋に帰ってきて家飲みの予定。

09/28(水)

午後4時半起床。準備していたらたいぺーが部屋に来たので、店まで一緒に行くことにした。午後5時を過ぎてから悠々と出発したら、店が思ったより遠くて10分ほど遅刻してしまった。

今日は成龍萬寿山という中華料理屋。5品でかなり満腹になった。ツイートの写真に写っている順に水煮肉片、チンジャオロース、海老チャーハン、コーンスープ、杏仁豆腐。水煮肉片はホスフィンが注文した料理で、程よい辛さが非常に美味しかった。中華のコーンスープは、小さいころコーンポタージュだと思い込んで注文してがっかりした覚えがあるが、今ではどちらも好物である。

食事 pic.twitter.com/zeKm6tGC82
— こたつがめ (@kotatsugame_t) 2022年9月28日

食事 pic.twitter.com/k2r6DZ32I4
— こたつがめ (@kotatsugame_t) 2022年9月28日

ドンキでおつまみやお酒の割り材とボードゲームを買い、帰宅。昨日届いたお酒を並べて飲み始めた。

飲酒 pic.twitter.com/ba7x1BM3pm
— こたつがめ (@kotatsugame_t) 2022年9月28日

買ってきたボードゲームは「Gobblet Gobblers」と「Blokus」で、どちらも二人用の対戦ゲーム。三人でプレイできるボドゲというのはなかなか難しかった。

「Gobblet Gobblers」は面白かった。基本的には $3\times 3$ のマルバツゲームを駒で行う。ただしこの駒は大中小とあり、既に置いた駒を動かしたり、より小さな駒を覆い隠したりできる。普通のマルバツゲームと同様に考えれば、初手は中央に絶対に覆われない大の駒を置くのがよいはず。すると以降取れる手が二通りくらいしかなく、人力で解析できそうに見えたが、さすがにそんな単純なゲームではなかった。初手の最適性も謎だし、実は見落としている手があるかもしれない。

「Blokus」は難しかった。相手からの浸食を完全にブロックしようとすると窮屈になるし、盤面がかなりスカスカになってしまって面白くない。自陣の隙をなくすよりは敵陣の隙をつくほうを積極的にするべきらしかった。このあたりが自分は下手くそ。

その他音MADやネトフリを見ていた。今日は自分を含め全員疲れていたようで、午前2時くらいにはみんな横になってしまった。自分は床で寝落ち。午前3時頃にたいぺーが帰宅する気配で一旦目を覚まし、見送った後布団に入って再度寝直した。

09/29(木)

午前6時、ホスフィンの起床とともにこちらも目を覚まし、二人で1時間くらい後片付けをした後帰宅を見送った。

昼前までずっとYouTubeを見ていたらしい。この動画が面白かった。ラストで急にピザを配り歩き始めたため、ゲリラ的に他ライバーとのやり取りを目の当たりにできて得をした気分になった。

www.youtube.com

しばらくラノベを読んでから原付で外出。学食は外まで人が並んでいたので諦め、生協でパンを買うにとどめた。その後ガソリンスタンドで給油し、バイク屋に点検のため原付を預け、徒歩で帰宅。またしばらくラノベを読んで、午後3時半ごろに寝た。

午後10時半起床。グダグダ時間を潰して午後11時半からECR136。

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

Aは $n=1$ または $m=1$ のときは $(1,1)$ 、それ以外は $(2,2)$ を出力した。Bは $a_i=a_{i-1}+d_i$ とすれば1通り復元できるため、それ以外の方法があると $-1$ になる。具体的には、 $d_i\ne 0$ かつ $a_{i-1}-d_i\ge 0$ なる $i$ があるとき。

Cはちょっと面白かった。まず先手が $n$ を持っている場合は先手必勝。そうでなくて、後手が $n$ も $n-1$ も持っている場合は後手必勝。このどちらでもない場合というのは、後手が $n$ を持っていて先手が $n-1$ を持っている場合となる。すると、この二つを組にして無視することができて、先手後手を入れ替えた $n-2$ の場合に帰着される。

Dは二分探索。根からdfsするとき行きがけに辺を付け替えてしまい、WA。なぜなら、根に近い頂点のほうが少ないため、辺の付け替えはできるだけ浅いところで行いたいから。帰りがけに付け替えるようにしたら通った。

Eは非常に難しかった。左の列からdpしようとしたが、直前に掃除したマスの行を持つ方針だと、どのマスを掃除してはいけないのか正確に管理し続けるのが辛い。考え方を変えると非常にシンプルになった。行の移動を必要になる列でのみ行うことにすると、例えばある列で上から下に移動した場合、その次の列では上の行にあるマスを掃除できない。逆にこれさえ守っていれば良いようで、直前の列で行の移動を行ったかと今どちらの行にいるかを持つdpで解けてしまった。

Fは解けず、5完24位。

朝までずっとラノベを読んでいた。2冊読了。

「クエスト：プレイヤーを大虐殺してください」。非常に面白かった。VRMMOで暗躍する系の話は、「黄金の経験値」しかり、かなり好み。そもそも暗躍する主人公が好きだし、その上VRMMOということもあってあまり責任とか倫理とか考えなくてよいような気持ちになれる。1巻ということでゲームを始めるところからスタートしたが、大多数とは異なる行動をした主人公にだけ発生したイベントもあってスムーズに成長し、すでにいい感じに謎めいた強力なキャラとなっていて楽しかった。ゲームとして不平等じゃないか、などは考えないようにすべし。

「無気力ニートな元神童、冒険者になる」。主人公の勘違いが行き過ぎていてちょっと肌に合わなかった。そういう意味で振り切れているので、特徴的ではあったか。

午前9時就寝。

09/30(金)

午後1時半起床。午後3時から1on1があるため、それに向けて進捗を産む必要がある。1時間くらいグダグダしてからようやく取り掛かったが、ほんの数行書き足すだけで終わったので、30分で何とか形になった。これを持って1on1へ。

議論しながら少しずつコードを変えていったのだが、そのたびに不等号の向きを取り違えたりインデックスを間違えたりとバグを埋め込み続けてかなり大変なことになった。実質ペアプログラミングみたいな状態だったからこそ気づくことができたバグたち。出力がどうなってほしいかをあまり把握できていなかったため、一人だったらこんなものかと納得してしまった可能性がある。ともかく、これでまた小さなタスクが一つ片付いたため、次のタスクを振ってもらった。

1on1が終了したのが午後4時40分で、直後からサークルのバチャに参加した。自明四つ、覚えていた問題二つで、最後の問題は頑張って考察した。

解説の前半は同じステップを踏んだが、共通部分の長さの2倍だけ減ることが分かればこの時点で解ける。 $i$ に対して $A_{i-1}$ を記録しておき、 $A_i$ を昇順に見てより小さい要素に対する記録を削除することで、 $A_i=\min(A_l,A_{r+1})$ のときの $\max(A_{l-1},A_r)$ の最小値が区間MINによって求まる。

https://kenkoooo.com/atcoder/#/contest/show/239f29f1-3a23-4fc3-b019-8e081f9b9f13

バチャ終了までは解説をチェックして過ごし、その後通話を繋いで感想戦。除算の除数が定数の場合と変数の場合の速度差についてなど、1時間ちょっと喋って終了。

仮眠しようと布団に寝っ転がったが、あまり眠くなかったのでしばらくラノベを読んでいた。1冊読了。

「英雄と賢者の転生婚」2巻。主人公とヒロインのイチャイチャは今の気分に合わないので微妙だが、それ以外はよかった。1巻で登場した高慢ちきなかませ犬的キャラがまさか主人公グループに入るとは。相変わらず一皮むけば気風のいい男で、好感度は高め。この巻では主人公グループの主人公・ヒロイン以外のキャラのバトルシーンが多く、やはり主人公に無双してほしい自分としてはその点はちょっと残念だった。

午後9時20分になったので、yukicoderの問題を読んでから寝た。星がやたら少ないのが気になっていたが特に詐称というわけでもなかったようで、どれも見た瞬間頭の中では解けた。

yukicoder contest 362 - yukicoder

1時間半で起床。まだyukicoderのコンテストが終わっていなかったので、寝る前に考えた解法を実装した。危なげなく全問AC。ツイートを拝見する限りもっと高難度の問題も用意されているそうなので、コンテストとしてまとめて出題するならそちらも含めてほしかったなという気持ちがある。解説を読んだ感じ、教育的な問題にしようとの意図があるらしく、そこは理解できないこともない。

午後11時半からCGR22に出た。

Dashboard - Codeforces Global Round 22 - Codeforces

Aからちょっと面倒。 $a$ の値で $b$ を $X$ と $Y$ に分けたとき、 $|X|\ne|Y|$ なら $X,Y$ から $\min(|X|,|Y|)$ 個ずつを倍にできる。そうでないならどちらかが1個倍にできない。倍にするものは大きな値から貪欲に選ぶ。

Bはまず決定できる $a_{n-k+2},\dots,a_n$ が広義単調増加かチェック。残りの $a_1,\dots,a_{n-k+1}$ はすべて $a_{n-k+2}$ 以下なので、この和 $s_{n-k+1}$ は $a_{n-k+2}\times(n-k+1)$ 以下である必要がある。逆にこの不等式を満たせる場合、必要なだけ $a_1$ を小さくすることで構成可能。 $k=1$ の場合は $a_{n-k+2}=\infty$ と思えば常に構成可能とわかる。

Cはよくわからない。とりあえず偶数の個数と奇数の個数を数えて、 $O(1)$ で判定できる方法を考えていたが、普通にメモ化再帰してよい制約だった。

Dも謎。まず $b_1,\dots,b_k\gt k$ かつ $b_{k+1},\dots,b_n\le k$ であるような $k$ が一意に定まる。後は $b$ が同じ値をまとめ、その値と等しいインデックスを配置した直後に並べればよい。複数ある場合は、元の列が存在するという制約からそのうち高々一つだけが後ろに並べたいものを持っているため、それがちゃんと一番後ろに来るような順番で置く。先頭は $b=0$ または $b=n+1$ で、これも制約からどちらかしか存在しない。結局 $k$ の情報は使わなかった。 $k=0$ を見落として1ペナ。

Eは難しいというか面倒だった。右と左から累積和を取って、これが同じ値になる位置で切ればよい。 $a=0$ がない場合はそのような位置が高々一つなので更新も簡単。ただ、今はそうではない。そのような区間が交差していない場合は、長さをそれぞれ $A$ と $B$ とすると、切る回数を全探索して答えが $\sum_{k=0}^{\min(A,B)}\binom{A}{k}\binom{B}{k}=\binom{A+B}{A}$ 倍になる。交差している場合はさらに一致していることもわかって、間はどこで切ってもよいため2べきを掛ける。端の扱いには注意。

実際はもうちょっとぎこちないことをしていた。 $\binom{A+B}{A}$ の部分は手で実験して違う式を得て、さらに閉じた形にしなくても計算量的に間に合ったため、ここまで整理できていない。端の扱いをチェックするにはサンプルが弱すぎてかなり不安になったが、この時点でかなり詰まってしまっていたのでわざわざ愚直と比較する気は起きない。エイヤと出したら通った。

Fはすぐ解けた。次数の降順に聞いて連結成分を作っていく。 $d_u$ が $d$ のうち最大だったとすると、 $u$ を $d_u$ 回聞くことでサイズ $d_u+1$ の連結成分ができる。ここの次数の総和は、それぞれの次数を上から $d_u$ で評価すると $d_u\times(d_u+1)\lt(d_u+1)^2$ となって条件を満たす。次に、今使った頂点たちを除いて同様のことを繰り返すが、途中で既存の連結成分が出てきた場合はそれとマージし、その頂点に関しては終わりにしてよい。クエリを投げるたびに連結成分が二つマージされるので、最大 $n-1$ 回のクエリで解が求まる。

Gはかなり難しかった。どういう風にセルを消せば条件が達成できるのか実験してみると、興味深い性質が見えた。右上から左下に向けて $k-1$ 本のマスを共有しないパスだけ残せばいいらしいのだ。より正確に言えば、右上と左下にすっぽり収まる $(k-1)\times(k-1)$ の三角形を作り、斜辺となる $k-1$ マス同士を繋ぐようなパスと共に残す。

これが見えればあとは貪欲で解ける。入力で0となっているマスを全部通ればよいので、パスを左から順番に構築していき、左に進まないと通れない0が存在しない限り下に進むという貪欲が正当。パスはマスを共有できない、つまり交差しないので、一度取りこぼすと取り返しがつかなくなるから。斜めの座標を大量に使う実装方針を取ってしまったので、手元で図を描きつつ丁寧丁寧丁寧にコーディングした。その甲斐あってかなりスムーズにサンプルが合い、残り7分で投げたら通って感動。

システスも全部通り、7完35位、レートは2954→2969(+15)。Eに45分もかけているのがかなり痛い。

今年のTCO Finalsがオンライン開催になったことが発表されていた。参加者に対しては結構前に伝えられており、しばらく秘密にしておいてくださいと言われていたのだ。もうこちらからも言いふらしてよさそう。

2022 Topcoder Open Finals Announcement: Change of Plans — Topcoder Forums

30分後からTCO Finalsに関するオンラインミーティングがあるらしい。
週記（2022/09/19-2022/09/25） - kotatsugameの日記

午前4時から3時間でDMOJのコンテストに参加した。感想は終了を待って、来週の週記に書く。

DMOPC '22 September Contest - DMOJ: Modern Online Judge

昼まで日記を書いていた。布団に入ってラノベとノクターンノベルズをそれぞれ少し読み、午後2時半就寝。

10/01(土)

午後8時半起床。9月分の読書記録をまとめてツイートした。積読の増分が3桁になってしまったのにはさすがに危機感を覚える。

9月の集計
買った：19冊
読んだ：10冊
積読：+9冊
積読（累積）：+100冊
— こたつがめ (@kotatsugame_t) 2022年10月1日

午後9時からABC271に出た。

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271） - AtCoder

Aはdcチャンス！と意気込んだら2桁にゼロ埋めするのを忘れて1WA。また出力が本当に大文字か確認していたのもあって、手間取りながらのACだった。Bはよい。配列の長さを動的に決める練習だろうなとわかる。Cは二分探索。やたら大きな $a_i$ の処理に少し手間取って、もっと簡単な方法があるのではと思ったが、適当に貪欲すると壊れそうだったのでそのまま実装しきった。

Dもよい。Eは面倒そうなことが書いてあるが、整理すると $dp_B\leftarrow\min(dp_B,dp_A+C)$ という遷移を $E$ の順に行うだけでよかった。Fでは一瞬手が止まったものの、何とか半分全列挙を素早く思いつくことができた。いわゆる解法ガチャ。

Gはちょっとややこしかった。 $N$ 回目のアクセスまでの残り回数と今何時の直前かを持ってdpすると、いつものループがある遷移になる。このループはアクセスの残り回数ごとに独立なので、式変形で解消することで残りアクセス回数が $1$ 少なくなった状態から $24\times 24$ の行列で遷移できる。これを行列累乗し、最後のアクセスに関する部分を別に計算することで解ける。

Exは謎。とりあえず適切に反転して $A\ge B\ge 0$ の状態にした。全通りの $s$ に対して各マスがどんな距離にあるかちょっと実験してみると、どうやら $(+1,+0)$ 、 $(+2,+0)$ 、 $(+1,+1)$ という移動の組み合わせで書けていそう。なので、最初にBFSでそれらの移動にかかるコストを調べ、適当に掛け算して答えとしてみた。愚直と比較して合うまで移動パターンを増やすのを覚悟していたが、もうこの時点で一致してしまったので提出。無事通った。

全完6位。上に学生が3人いて賞金は手に入らなそう。Aの1WAがなかったとしても変わらないようだ。残念。

Cはやっぱり貪欲だと壊れる問題らしい。Gはdpのループ部分を解消する際に除算を行う必要があって、この除数がゼロにならないことを一切確認していなかった。ゼロになったら解けないだろ、みたいな気持ちで通してしまった。まだ痛い目を見たことがない。

コードゴルフをした。AはACしたときのdcが最短。BとCはAWK。EはRubyで書いたが負け、Perlでさらに縮んでいる。他は手付かず。

TopCoderに参加する環境を少し整えた。これまでずっとAppletのほうからコードのテストを行っていたのが非常に面倒だったので、手元で完結させたい。今はCodeProcessor、FileEdit、TZTesterというよくあるプラグイン3点セットを使っているので、これをGreedに乗り換えればいいのかと思ったが、それ以前によく見るとTZTesterなのだから今の状態でできてもおかしくない。実際、調べるとすぐ出てきた。

TZTester Home Page

テンプレートにテスト用のコードを追加すればいいらしい。適当な問題でコード生成を試しながら調整し、以下のようなものに落ち着いた。問題文をコード中に埋め込むと、乱数生成の際に定数の補完が効いて便利。しかし手元でこのファイルをコンパイルする場合はその部分のコメントアウトが必要になるので、テンプレートの時点でそうしておいた。これまではコンパイル以降を全部Appletから行っていたので特に問題なかったのだ。

あとはテスト用コードのためにヘッダファイルvectorとsstreamをインクルードする必要もある。テストの実行については、グローバル変数が初期化されないのに注意しておきたい。

$BEGINCUT$
/*
$PROBLEMDESC$
*/
$ENDCUT$
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;
class $CLASSNAME${
    public:
    $RC$ $METHODNAME$($METHODPARMS$){
        
    }
$TESTCODE$
};
$BEGINCUT$
int main(){
    $CLASSNAME$ __test;
    __test.run_test(-1);
}
$ENDCUT$

そうやって準備を整え、午前1時からSRM839に出た。

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

Easyは選ぶ人数をあらかじめ決め打つdpで4乗。どこか見覚えがあると思ったら、ABCで出題されていたらしい。まあこの難易度で既出も何もあったものではない。

Medは難しかった。直感的には、各要素に対してその左にあってswapで飛び越えられないようなものを見て、転倒数への寄与を数えればよさそう。ただしこれを達成する過程でうっかり余計なものまで飛び越えてしまい、転倒数が増える場合がないかが心配だった。このことは、値 $x$ が飛び越えられる要素は $x$ 以下の値でも飛び越えられるということから問題ないとわかる。

最初の状態において、どの位置より左にある要素を飛び越えられないかチェックするときは、stackで見ている位置から左に進んだ時の累積maxの変化点を管理し、その上で二分探索すればよい。stackはランダムアクセスできないので実際にはvectorを使った。セグ木上の二分探索でもよいが、ACLはSRMで使えないし、自前のセグ木には二分探索を実装していないので、今紹介した方法を考える手間が発生した。これを前計算しておき、値の大きな要素から順に見てBITを弄ることで、具体的な転倒数への寄与が求まる。

HardはMo。これが1000点はちょっとあり得ない、と舐めてかかったら実装に手間取って点数は低めになってしまった。

30分残して全完。チャレンジフェーズは特に何もせず、Roomでも何も落とされていなかった。しかしシステスで8つも落ちてびっくり。Medで2乗の解を投げている人が二人もいたので、ちゃんと確認しておけばよかった。自分は無事全部通って9位、レートは2785→2807(+22)。最近の傷が深すぎてまだまだ癒えない。

朝まで日記を書いていた。午前7時半から30分ほど椅子の上で眠ってしまったらしい。意識を取り戻してすぐ布団に移動し、就寝。

10/02(日)

午後5時起床。食事したりTLを眺めたりして2時間ほど使った後、後期の履修を決めようとした。

前期に取った単位と必修を除く、残りの能動的に集めなければならない単位は八つらしい。うち六つぶんくらいは今セメスターで履修登録しておきたい。めぼしいものを見繕っていたら、他研究科の集中講義で面白そうなものがあった。ぜひ受講したいが、調べても日程が出てこない。そもそも履修登録の方法についても教務課に問い合わせる必要がありそうなので、早めに一回話を聞きに行く必要がある。

そのうちに午後9時になったので、ARC149に出た。

AtCoder Regular Contest 149 - AtCoder

Aは $M\mid(10^k-1)/9\times l$ を満たす $1\le k\le N$ 、 $1\le l\le 9$ であって $(k,l)$ が辞書順最大となるものを探す問題。とりあえず分母の $9$ を払ってさてどうするか……と一息ついたら、 $(k,l)$ を全探索できることに気づいた。また、 $10^k$ は $k$ をインクリメントしながら求められるのに、毎回二分累乗法で求めようとしてしまい、 $\bmod 9M$ 上の積がlong longをはみ出てしまうので__int128を持ち出したりと、後から振り返ればかなり遠回りして解いてしまったようだ。

Bはこんなの片方をソートするのが最適じゃないと解けないだろと思って実装。不安だったので、 $A$ をソートする場合、 $B$ をソートする場合、一切いじらない場合の3種類の値を求めた。考察も証明もせずにAC。

Cは面倒。とりあえず偶数を作りたい。 $N$ が偶数の場合は上半分に偶数を、下半分に奇数を並べることでだいたいOKになる。真ん中は $a$ と $2a$ を隣接させることで3の倍数にできる。 $N$ が奇数の場合もほぼ同様だが、中央の奇数は下だけでなく右にも偶数が隣接するので、これを何とかする必要がある。適当なペアを選んで並べておくことにした。

ここから $3$ が素数であることを完全に忘れた考察。真ん中に並ぶのは $a=1,3,\dots,2N-1$ となった。すると、 $2a\le 4N-2$ が $N^2$ 以下でない場合はこのような並べ方ができない。計算したところ $N=3$ の場合だけ壊れるらしいので、そこは全探索して埋め込んでおいた。また $N$ が奇数の場合に中央に並べるペアは $(1,2)$ と $(4,8)$ にした。 $1+8=9$ が非素数になる。

WA。 $3$ が素数であることに気づいて考察を修正。まず、真ん中に並ぶのが $a=3,5,\dots,2N+1$ となるため、 $4N+2\le N^2$ が必要となり $N\le 4$ の場合にうまくいかなくなる。 $N=4$ は全探索では求まらないが、適当に順列をシャッフルし続けるとすぐ見つかったので、それを埋め込んでおいた。サンプルにあるのを完全に忘れていた。 $N$ が奇数の場合のペアは $(3,6)$ と $(11,22)$ に更新。これで通った。

Dは面白かった。操作は $x\mapsto|x-D|$ のように書けて、例えば $x$ として区間 $[l,r]$ （ただし $l\le D\le r$ ）があったら $[l,D-1]\mapsto[1,D-l]$ 、 $D\mapsto 0$ 、 $[D+1,r]\mapsto[1,r-D]$ に分けて $[1,D-l]$ と $[1,r-D]$ をまとめる、イメージ的には折り畳むような変化と捉えられる。ここまでは結構早めの段階でたどり着けたが、畳んだものをうまく戻せないように思ってかなり長い間詰まっていた。

実は戻せる。 $[1,D-l]$ と $[1,r-D]$ のうち短いほうについて、それぞれ長いほうの区間のどの値と重なっているかメモしておくと、以降は長いほうの区間しか見なくてよい。こうやってメモするたびに区間が短くなっていくので、メモする回数は $O(\max X)$ 。答えを求めるときは、メモした値と対称の位置にいることがわかるので、答えが確定している値まで辿っていくことでちゃんと復元できる。この部分はUFのようにして実装した。変数名のミスで1WAしつつ何とか通した。

残り15分しかなく、Eの考察はあまりできなかった。4完34位。Bの証明は言われてみればという感じ。コンテスト中は本当に何も思いつかなかった。

コードゴルフはBのみ。LISのコードを過去問から引っ張ってきたが、アドホックな改善で1B負けている。他は手付かず。

午後11時半からCF #824 div.2。

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

Aはちょっと難しい。休日云々を忘れると $l_1+l_2+l_3=n-3$ かつ $l_1,l_2,l_3\ge 1$ が条件とわかる。ここで $l_1\le l_2\le l_3$ とし、 $x=l_2-l_1$ 、 $y=l_3-l_2$ と定めると、条件が $l_1\ge 1$ 、 $x,y\ge 0$ 、 $l_1+(l_1+x)+(l_1+x+y)=3l_3+2x+y=n-3$ と書き直せて、このもとで $\min(x,y,x+y)=\min(x,y)$ を最大化する問題になった。まず $l_1=1$ が確定し、 $2x+y=n-6$ となる。 $\min(x,y)=k$ だったとすれば $2x+y\ge 2k+k=3k$ なので、 $k\le(n-6)/3$ が必要。逆に $k=\lfloor(n-6)/3\rfloor$ が達成できるので、これが答えになる。

Bは最小値を最大化すればよさそう。実際、 $a_1$ が達成できる。できるだけ $2a_1-1$ のブロックを作るように分割したとき、ブロック数を変えずに各値を区間 $[a_1,2a_1-1]$ に収まるようにできるから。

Cは先頭から順に変換前の文字として都合の良い最小のものを当てはめていく。使用済みの文字でなく、今見ている文字と同じでなく、さらにその変換を確定させたときに長さ26未満のループができてしまわない文字。一番最後の条件は、毎回ループをたどって判定した。

D。setはそのうち2枚が決まると残り1枚も一意に定まる。よって5枚のカードでsetが二つあるということは、その共通部分がちょうど1枚であることを意味する。 $O(n^2)$ かけて2枚のカードを全探索することでsetを全列挙し、各カードについてそれを含むsetの種類数を求めておくと、meta-setの共通部分となるカードを決めたとき、残りはsetを二つ組み合わせる場合の数になる。どんな二つを取っても、先ほどの話から決めたカード以外に共通部分を持たない。

Eは大変だった。 $d_{1,i}$ と $d_{2,j}$ が対応するとき、 $d_{1,i}+d_{2,j}$ または $|d_{1,i}-d_{2,j}|$ が $|p_1-p_2|$ に一致するらしい。これを使うと $|p_1-p_2|$ の候補が $O(n)$ 通りになるので、とりあえず全探索する。この値が $p$ だとすると、 $d_{2,j}=p-d_{1,i},p+d_{1,i},d_{1,i}-p$ のうちどれかだとわかる。 $|p-d_{1,i}|$ か $p+d_{1,i}$ だと書いておこう。

$d_{1,i}$ を大きなほうから順に見たとき、 $d_{2,j}=p+d_{1,i}$ なる $j$ があるなら、必ずそれとペアにするべきである。なぜなら、より小さな $d_{1,\ast}$ に対してこの $d_{2,j}$ は対応できないから。このような貪欲を、 $d_2$ をmultisetで管理しながら行って、すべての $i$ に対して対応する $j$ が見つかるかチェックする。

ここまでくれば必ず解を作れる。 $p_2=p_1+p$ と決め打っておく。対応するペアが $(i,j)$ だったとして、 $d_{1,i}+d_{2,j}=p$ または $d_{1,i}-d_{2,j}=p$ のとき、 $h=p_1+d_{1,i}$ とできる。そうでなければ $d_{2,j}-d_{1,i}=p$ であり、この場合は $h=p_1-d_{1,i}$ とすべき。この値が必ず非負になる程度に $p_1$ を大きく取ればよい。ここで $p_1=10^9$ と決め打ったりしてはいけない。 $p\gt 10^9$ の可能性がある。

Fに1時間くらい残したが解けなかった。地獄のような実装をしてサンプルが合う直前にタイムアップ。5完8位。

Fのupsolveをした。持っているpebblesとbeadsの組を $(x,y)$ と書く。各 $x$ に対して達成可能な最大の $y$ を取り、これをグラフに書くと、折れ線がつながった上に凸な形になる。これを管理すればよい。 $i$ 日目は折れ線上の点に対し $(-p_i,+q_i)$ から $(+p_i,-q_i)$ までできて、これは $x$ 座標の範囲が $2p_i$ で傾き $-q_i/p_i$ の線分を傾きが降順になるような位置に挿入することで表現できる。

こうやって書くとイメージ的にすぐ納得できるが、コンテスト中は大変な苦労をして式変形から導いた。折れ線をなす線分や担当する区間を変数で書いて、どのような遷移がありうるか考えればそんな感じになる。流れで実装時も各線分の情報をまじめに管理しようとし、遅延セグ木に乗せたり頑張ったのが上で触れた地獄のような実装。しかも書き上げたものを提出したらWAだった。グラフの $x\lt 0$ または $y\lt 0$ の部分を削除する必要があって、今の実装だとどうやっていいのかわからない。

いったん式の具体的な形を完全に忘れると解けた。折れ線の両端点を持ち、形は傾きとそれが担当する $x$ 座標の区間の長さだけを管理する。線分の追加は、端点をずらした後新しい傾きと長さの組を挿入することになる。折れ線上の点は線分たちを傾きの降順に舐めて更新していくことで求まるのだ。典型テクなので思いつくべきだった。線分の追加後に折れ線を辿って端点をずらし、座標が負でないようにすることで、不適な部分の削除も行える。doubleだと精度が足りないようで、long doubleを使ったら無事ACした。

また履修を決める作業に戻った。上で触れた集中講義は受講できるか、できたとして卒業要件に含められるかちょっと怪しい気持ちになってきたので、そうでない講義を追加で一つ受講することにした。これを決めるのにまたリストを上から下まで眺めていたので時間がかかった。

昼前まで日記を書き、布団に入って少しラノベを読んで正午就寝。寝る直前にチュウニズムの大型アップデートの情報が流れてきた。アプデで消える要素の回収のため、それまでに2回くらいはゲーセンに行っておきたい。

10月13日(木)より『CHUNITHM NEW PLUS』がバージョンアップ！『CHUNITHM SUN(チュウニズムサン)』の稼働が決定！本日から新情報をドンドン発表していくので、お楽しみに！！

●ニュースはコチラからどうぞ！https://t.co/hMNFsFHeCI pic.twitter.com/4q3fOO0hHm
— チュウニズム公式@10/13(木) CHUNITHM SUN稼働開始！ (@chunithm) 2022年10月3日