05/24 (MON)
9:00 起床。最近は月曜日の朝はのんびりしている。朝食をバタバタすることに嫌気がさしていたのでちょうどいい。 全く話は変わるが、最近剃刀負け防止のためにかなり弱い剃刀を使って髭を剃っていた。狙い通り剃刀負けはあまりしなくなったのだが、今度はあまり剃れないという事態が発生している。 仕方なく今日は久々に元々使っていたタイプの剃刀を使うことにした。あんまり綺麗に剃れるのでびっくりした。 しかし顔がヒリヒリして痛い。早く勝利を知りたい。
10:30 ぐらいに大学へ向かう。電車内で今日の典型を確認する。★3 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_av
問題概要。$ N $ 問の問題が与えられて、それぞれの問題は完全回答で $ A_i $ 点、部分点が $ B_i $ である。 ある問題に取り組む時、 $ 1 $ 分で部分点を獲得することができ、もう $ 1 $ 分で残りの点数を獲得することができる。 テスト時間が $ K $ 分の時、最大で何点獲得することができるか。ただし $ \frac{A_i}{2} < B_i < A_i $ である。
太字部分のおかげでクソ簡単に解ける。まず、各問題を $ 2 $ つに分割すると、$ 1 $ つ目の問題を解いてからしか $ 2 $ つ目の問題を解けない。 一見すると取れる点数の順序が制限されて厄介だが、部分点は半分以上のため残った点数は部分点より小さい。 つまり、全ての問題は $ 2 $ つの問題に分割した上で点数が大きい方から取っても順序を違反することはない。 分割してソートして貪欲。計算量は $ O(N \log N) $。
大学について作業をするや否や昼の時間なのでケイジャンビーフチーズ&ライスを食す。
今週は写真を撮ってみた。思いの外頭の悪そうな昼食となった。本気で月曜日はこれしか食えなくなった。
昼食をとって少しすると、ゼミが始まる。ゼミが終わる。作業をしたりプリンターやスキャナーの設定をみたりしていた。 スキャナーとかいう機械、スキャンしかできないんだからスキャンぐらいちゃんと問題なくやって欲しい。
ふと気になったので今日の典型について、過半数制約がないバージョンを考えてみる(というかなんとなく考えていたことをまとめた)。 部分点が過半数の問題をタイプA、部分点が半分以下の問題をタイプB と呼ぶことにする。 タイプA の問題は上と同じように分割して得点順にソートする。 タイプB の問題を $ 2 $ つ以上の問題を部分点のみ獲得するような解き方は得をしない。 なぜなら、部分点のみを獲得している $ 2 $ つの問題を $ i $ と $ j $ とした時に、$ \max(A_i, A_j) \geq B_i+B_j \quad (\because A_i \geq 2 B_i ) $ が成立するためだ。 さて、タイプA の問題に $ X $ 分使うことにすると、タイプB の問題には $ K - X $ 分使うことになる。
- タイプA の分割済みの問題を得点の大きいものから $ X $ 問解く(累積和前計算で $ O(1) $ )。
- タイプB の決め方はやや複雑。
- $ K - X $ が偶数なら $ A_i $ が大きい方から $ \frac{K - X}{2} $ 問解く。(累積和前計算で $ O(1) $ )
- $ K - X $ が奇数のとき部分点のみを獲得する $ 1 $ 問を選んでからそれ以外の問題について偶数と同じ処理で良い。
- 愚直にやると $ O(N) $ かかる。
- 部分点のみを獲得する問題が、タイプB の問題を $ A_i $ の降順に並べた時に $ \frac{K - X - 1}{2} $ 番目以内かより後ろかで場合分けする。
- 以内の場合は $ \frac{K - X - 1}{2} $ 番目までで $ A_i - B_i $ が一番小さいものを部分点として選ぶとよい。
- より後ろの場合は $ \frac{K - X - 1}{2} $ 番目より後ろの部分で $ B_i $ がもっとも大きいものを選ぶとよい。
- 以上の $ 2 $ つの場合はどちらも累積 min や累積 max を前計算することで $ O(1) $ で処理できる。
以上の処理により、全体の計算量のボトルネックはソートの $ O(N \log N) $ になって解けた。と思う。
色々やっているうちにジャッジが来たので、書いて投げる。AC。制約がバージョンのジャッジも欲しい(わがまま)。 あとでランダムテストはするかも。
おやつにプリンを食べて、作業を再開することにした。 あとはいつもの月曜日通り作業したり喋ったりしているうちにいい時間になる。 今日の進捗自体は微妙だった気がするが、体調も精神状態もいいのであまりに気にしないことにする。
気分がいいので帰りにゲーセンに行ってしまう。これは完全に失敗だったが、楽しかった。 ボルテに $ 998244353 $ 人の待ちができていたため、pop'n music のリハビリをすることにした。 絶望的なまでに下手くそになっていたが、なんとかして地力を戻していきたいね(写真なし)。
この時点でクソ眠かったため今日のコドフォはパスかもなと思っていた。 帰宅する。実家ぐらしは神。ご飯を残してくれていた。感謝しながら食べると元気が出た。 眠いことには眠いが元気が出たので当然コドフォに出席させていただくことにした。 というか結局大体の場合コンテスト出たさに負けてコドフォやってしまうんだよな。
Dashboard - Codeforces Round #722 (Div. 1) - Codeforces
コドフォ惨敗した。気持ちだけが先行して脳が付いてきていなかったらしい。
A 問題。$ L_i $ か $ R_i $ 以外を選んでも得をしないといういつもの性質がある。なぜなら、中途半端な値にして場合分けして考えるとわかるが伸ばししろがあるか不変かのどちらかであることが簡単に確認できるためだ。ここでコンテスト中は脳が腐っていたため、木 DP のマージパートに $ O(2^{B}) $ ($ B $ は枝の数) と勘違いしてしまい人生が終了した。本当は着目している頂点でどちらを取るか決めれば枝達はそれぞれが独立に決まるため、$ O(B) $ でマージできる。
B 問題。これも難しかった。つかみどころがなくしばらく困っていた。パラメータが少ない定数個しかない問題は再帰的な構造が存在することを疑ってみるのがいいと思いだした。ここで $ x $ の時の答えを $ f(x) $ として改めて観察すると、一番外側をペアにするとき中の状態は $ N-1 $ と同じになり、 $ f(N-1) $ だ。同様にして外側 $ i $ 個ずつをペアにするときは $ f(N-i) $ であることが分かる。あとは、包含関係が存在しないパターンが残されている。この場合すべてのペアの距離が同じなのでよく考えると、$ N $ の約数の数だけこのパターンがある。約数の個数を前計算した上で累積を持ちながら DP をすることで計算可能。あとで思ったのだが左端をどことつなぐか考えるというアプローチも悪くなさそうだ。
C 問題。こういうの得意なはずが AB のムーブの焦りからか落とした。一つ目の木で根からの任意の頂点へのパスに含まれる頂点集合で、二つ目の木では祖先-子孫の関係が一切ない部分集合の最大値を求めれば OK。根から頂点へのパスを全探索するみたいな問題は、DFS で行きがけに追加、帰りがけに削除みたいなことをしてやるのが鉄板。当然この時は revert が可能なデータ構造である必要があるのに注意。頂点の数を最大化するため、追加した頂点で祖先-子孫の関係ができてしまいそうになった時子孫の方を残すのが常に最適である。自分の思いついた解法は、頂点追加時に遅延セグ木(双対セグ木)で部分木を頂点番号で塗りつぶす。そしてその子孫が追加されそうになった時に、祖先の塗りをクリアして改めて子孫の部分木を頂点番号で塗りつぶす、というもの。revert も自明に可能。これで解けた。今回子孫は祖先より頂点番号が大きいことが保証されるため逆パターンは考えなくてよい。
しかし Twitter を見ていると、単純に頂点を set に追加して、追加した頂点の Euler Tour 順の直前と追加した頂点を見て、追加した頂点が直前の頂点の子孫(部分木内に存在する)なら直前の頂点を削除する、で良いことが分かる。たしかに追加前が祖先-子孫の関係が存在しないことが保証されているため簡単に証明ができる。賢い。しかもこれの優れている点は上の青字の制約を満たさない木の制約の時も逆パターンが簡単に書ける。遅延セグ木で逆パターンをやろうとすると割と地獄だし定数倍重そう。
結果は爆死だったが、BC 問題で得られた経験と知見からすれば -92 は安いものだと自分に言い聞かせて寝た。
05/25 (TUE)
深夜コドフォで直後に復習じみたことをしていたため起きられるわけもなく、11:30 起床。最悪な気分になりながら朝食をとる。
大学から TA の給料振込のための講座番号を教えてもらっていないという電話がかかってくる。申し訳なさすぎる。すぐ回答する。 その後も一応ちょっとした作業をしていて、昼飯を食べる。昨日の残り物がメインだ。おいしい。
昼食後に今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_aw
問題概要。長さが $ N $ で全部 $ 0 $ のビット列と $ M $ 個のアイテムが与えられる。各アイテムにはコスト $ C_i $ と区間の左右を表す $ L_i $ $ R_i $ が与えられて、アイテムを使うことで、持っているビット列の $ L_i $ から $ R_i $ を Flip させることができる(端を含む)。任意のビット列を作るために必要なアイテムの合計コストを求めよ(不可能なら $ -1 $ を出力)。
区間の Flip なんてものはもう確実に累積前 xor に読み替えて端と端のみに $ 1 $ が寄与していると考えるのが典型だとF - Perils in Parallelとかその他多数の問題で学んでいる。実際そうしてみると、累積前 xor の最後の要素以外の $ 0 $ と $ 1 $ を自由に決められるような集合を取れば良い。作りたいビット列が決まれば「接続行列を係数にもつ線形方程式」と同じ形だと思う。opt さんの LSI.pdf をほやほや~と思い出すと、適当な全域木を取ってきて、葉から処理して係数を追い出していくので連結成分ごとに矛盾する可能性があるのは $ 1 $ つのみである。$ 1 $ つは自由が利く今回の問題では、全域木であれば条件を満たしている。よって $ N+1 $ 頂点 $ M $ 辺のグラフを考えて最小全域木を取れば OK。
Flip の問題が累積 xor でキレイになる問題で痛い目を見た(B - Tree Edges XOR)ためこれからは一生確かめる。
そういえば、類題で tute くんの問題の No.1244 Black Segment - yukicoder を通していなかったことを思い出したのでやる。 この問題は $ M $ 個の区間 Flip が与えられるのは同じなのだが、区間 $ [A,B] $ を包含するようなある $ 1 $ つの区間内を全て $ 1 $ にしてそれ以外は $ 0 $ にすることが目標。目標を達成する最小の区間 Flip 回数を求める。累積を考えるとやはりグラフに落ちる。$ A $ 以下の頂点と $ B $ より大きい頂点の距離として最小のものを求める。これは最短距離問題なので、複数始点 BFS で解ける。当然どの始点からもどの終点にも到達できない場合は Impossible となる。提出して無事 AC。 他の人の提出を見たけど、複数始点複数終点ではなく辺を張る段階で頂点をまとめてしまう実装もあった。
今週も週末にピアノを対して練習しなかったので反省した。今日も $ 3 $ 時間ぐらいしか弾かなかった。相変わらずクソ難しいんだけど光明が見えてきた。
夕食の後、いつも通り水曜の午前中締め切りのショートレポートを書くために講義を視聴する。が、なんか今週は課題がなかった。 そのあと今週のジャンプを読む。今週で一番話が動いたのは呪術廻線かな。あとは、どう持っていきたいのかよくわからなかった野球漫画が打ち切りになりそうな雰囲気がある。呪術廻戦は結構世間的に人気らしいのでネタバレを平気な顔して書くことが憚られるな。Dr. STONE はなんかとりあえず仲間は全員復活した。死人も生き返ってしまう。すぐ打ち切られる漫画は大体方向性がよくわからないため、話がブツ切れに感じられてしまい、結果として話の大きな流れを全然思い出せないんだよな。
時間が余ったので競技プログラミングを少しやる。先週からあまり時間がとれていないので気になる。
D - 大ジャンプ を解く。 問題概要。$ 1 $ ターンに $ X $ 軸と $ Y $ 軸の正の方向・負の方向にそれぞれ $ \frac{1}{4} $ の確率で $ D $ だけ移動する。$ N $ ターン後にちょうど座標 $ (X,Y) $ いる確率を求めよ。
まず、当然 $ X,Y $ が $ D $ の倍数でなければ到達することはできない。以降では $ \frac{X}{D}, \frac{Y}{D} $ を $ X,Y $ 、$ D=1 $ として問題を解く。 メモ化再帰では $ O(N^{3}) $ ぐらいかかるなと思いマシな解法を探す。$ X $ 軸と $ Y $ 軸に問題を分割できないか考えたところ、まず $ X $ 軸方向に $ a $ 回、 $ Y $ 軸方向に $ b $ 回移動するの確率は $ \binom{N}{a} / 2^{N} $ であることがわかる。 あとはそれぞれの軸について考えると、$ a $ 回中ちょうど $ (a-X)/2 $ 回負の方向に進む必要がある。よって、$ a $ 回 $ X $ 軸方向に移動したときに $ X $ にいる確率は $ \binom{a}{(a-X) / 2} / 2^{a} $ である。$ b $ 回 $ Y $ 軸方向に移動したときに $ Y $ にいる確率も同様に求めることができ、$ 3 $ つの確率をかけ合わせれたものを全ての $ a,b $ の割り振りについて足し合わせれば答えが求まる。割り振りのオーダは $ O(N) $ で、二項係数の前計算が $ O(N^{2}) $ のため、ボトルネックは後者になり間に合う。 今回、DP も似た大きさのものの足し算だし、分母が $ 2 $ の累乗だったため誤差に強そうと思い double の上限下限のみ慎重にやって AC。ちなみに軸別に分けて条件付確率を求めなくても、条件式を連立させれば多項係数によって普通にとけそう。
05/26 (WED)
起床は 10:30 。正直もっと早く起きて散歩やランニングをしたかった。最近運動不足によって体調がおかしくなっているように思う。
週記の昨日の夜のことを書きつつ朝食を食べる。あと今日もピアノと向き合わなければならないだろう。
とりあえず今日の典型を確認する。★3 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_az
問題概要。$ N $ 段の階段があり、$ 1 $ 回に $ 1 $ 段か $ L $ 段上がることができるとき、$ N $ 段をちょうど上り切る登りかたは何通りあるか。
超ベーシックな一次元 DP 。なんか最近同じことを典型90 でした気がするけど、気のせい? 気のせいじゃなかった。典型 42 で同じことをした。 遷移が $ O(1) $ で、トポロジカル順も小さい方からなので本当に素直に $ O(N) $ で解ける。 因みに、遷移が $ 2 $ つしかないため二項係数を使って経路長でループを回すことによって解くこともできそうだ。 遷移が $ 2 $ つの時は二項係数を使うことができ、高速化できる場合も少なくないためアンテナを張ることを忘れないようにしよう。
ふと埋めようと思ったので F - Graph Smoothing を解いてみる。
問題概要。 $ N $ 頂点 $ M $ 辺の単純グラフと非負整数列 $ A $ が与えられる。以下の操作を $ K $ 回行う。
- $ M $ 辺から uniform random に $ 1 $ つ選び、つなぐ頂点を $ x, y $ としたときに $ A_x $ と $ A_y $ の値を算術平均で均す。
操作後の $ A_i \quad (1 \leq i \leq N) $ の期待値を答えよ。
$ N \leq 100 $ と小さい。こういうのは順序が大切になってしまい、寄与ゲーにすることは難しいと思われる。$ N $ が小さいので DP を考えてみる。状態数 $ O(NK) $ で遷移が $ O(M) $ の DP を簡単に思いつく。 当然これは $ K $ がデカすぎて不可能。期待値の線形性によって $ M $ 個の遷移をまとめて $ O(N) $ にすることができる。 DP の遷移が同じものを $ K $ 回行うとき、 $ K $ がデカすぎるという問題は、多くの場合行列累乗かダブリングによって解決する。 $ M $ 個の遷移行列を足し合わせて $ N \times N $ の遷移の変換行列ができる。今回 $ O(N^{3} \log K) $ が十分間に合うので行列累乗したものと最初の $ A $ ベクトルを掛けることで $ K $ 回行った後の $ A $ の期待値が計算できる。
この回の ABC では DE で実装に失敗しまくりパニックになっていたから F が難しく見えたが、全然そんなことはなかった。 さて、作業をしなければならないのでしばらくは作業をしている。今日はやることが多くて SRM を見送ることになりそうだと思った。 作業内容はちょっと話せないのでスキップさせて頂く。
さて、ちょっと競技プログラミングでもやってリフレッシュしようと思い、F - Minflip Summation 開く。最近当日 AC できなかった ABC-F の埋めをさぼってしまっているため消化の意味合いもある。
問題概要。$ 1 $ と $ 0 $ と $ ? $ からなる文字列 $ S $ が与えられる。これを $ K $ 個連結したものを $ T $ として、$ ? $ の部分は $ 0 $ にも $ 1 $ にもなり、すべての $ ? $ を $ 0 $ か $ 1 $ に書き換えた後の文字列を $ T' $ とする。全ての $ T' $ について、全ての文字を同じにするのに必要な区間 Flip の最小回数を求め、和を答えよ。
測らずも昨日の典型と被っている (区間 Flip という点で)。例に従って累積前 xor を考えてみる。累積前 xor の世界では区間 Flip $ [i,j] $ は $ i $ と $ j+1 $ の $ 2 $ つの位置を Flip する操作になる。 よく観察すると、結果はランレングス圧縮したサイズを $ M $ として $ \left \lfloor \frac{M}{2} \right \rfloor $ となる。 整数集合 $ S $ を与えたとき、 $ cnt(i) $ を $ S $ の要素で正定数 $ A $ で割った余りが $ i $ であるものの数とすると、
$$ \sum_{x \in S} \left \lfloor \frac{x}{A} \right \rfloor = \frac{ \sum _ {x \in S} x - \sum _ {i=1}^{A-1} i \cdot cnt(i)}{A} $$
は明らかである。今回の問題では $ A=2 $ でこの変形をすればよく、$ T' $ をランレングス圧縮したサイズの集合を $ U $ として
$$ \sum_{M \in U} \left \lfloor \frac{M}{2} \right \rfloor = \frac{ \sum _ {M \in U} M - cnt(1)}{A} $$
と書ける。実は $ cnt(1) $ は簡単に求められる。なぜなら、$ T' $ の先頭と末尾が同じパターンの場合の数であるからだ。ただ $ S="?" $ であるときに注意したい(このケースで無事に WA をもらった)。
$ \sum _ {M \in U} $ を求めるのには、各隣接のランレングス圧縮したサイズへの寄与を考えればよい。$ 01 $ か $ 10 $ になっていれば $ 1 $ 寄与している。基本的にはこれを $ K $ 倍すれば良いが、連結しているため先頭と末尾の隣接も $ K - 1 $ 回分考えなくてはならない。 よって上の式をそのまま計算することができ、$ O(N) $ で解けた。
因みに行列累乗で解くこともできる。こういう時も行列累乗を思いつける柔軟な思考を持っていたい… 木曜日は早く家を出るため頑張って寝る。というか SRM 出ないのだから本気で寝た。
05/27 (THU)
6:30 起床。いつもどおりに身支度をして家を出る。 今日は意識があったため、行きの電車の中で典型を確認する。★5 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_ay
問題概要。$ N $ 個の品物があって、ちょうど $ K $ 個選ぶことを考える。各品物の値段は $ A_i $ 円 $ (1 \leq i \leq N) $ で、値段の合計が $ P $ 円以内になるように買いたい。 品物の選び方の通り数を求めよ。
なんだかナップサック問題 Like な設定だ。こんなものは効率的なアルゴリズムがあるはずがないのでいつものだろう。 制約を見ると、$ A_i, P $ がアホみたいにデカく、$ N \leq 40 $ だった。 こんなものは半分全列挙だと思い、終了。
大学につく。木曜日なので 1 限を大学で受けている。今日の課題も問題なくできそうなので安心。 しばらく作業をする。最近大学での作業で混乱していて停滞していたため、考察用紙にまとめて整理したらだいぶ見通しが良くなった。
昼飯を食べる。来週はタンドリーチキン丼を食べないと言っていたにもかかわらずキッチンカーの前にきたら口が勝手に動いていた。馬鹿。
明日の輪講発表のスライドができていないため、ミーティングが終わり次第帰宅してスライドを作成する。 自分が発表に選んだ論文が思いのほか読みにくかったことを思い出す。最悪である。 どうスライドにしたらよく伝わるかイマイチわからないままよくわからないスライドが錬成されてしまった。
さらっと言っているが、夕食の前後はずっとしょぼいスライドのために時間を使っていて、そのまま寝た。 そのためまじで書くことがない。と思ったけど、 1 問だけ競プロの問題を通していた。
最近の ABC-F だが、コンテスト中にいいところまで詰められたにもかかわらず落としてしまった問題だ。 問題概要。長さ $ N $ の順列が与えられる。これを昇順にするために $ 3 $ つの操作を行える。
- コスト $ A_i $ を払って $ i $ 番目の要素を好きな位置に移動させる。
- コスト $ B_i $ を払って $ i $ 番目の要素を左端に移動させる。
- コスト $ C_i $ を払って $ i $ 番目の要素を右端に移動させる。
こういうそのままでは余りにもつかみどころがない問題は、緩い決定をすると見通しが良くなったりする。 それぞれの要素について、動かすかどうかを決定したと考えてみる。 動かさないものは少なくとも昇順である必要があることは明らかである。また、動かすものは数字の大きさによってかかるコストが確定できそう。 具体的には動かさないものの最大より大きければ $ \min(A_i, C_i) $、動かさないものの最小より小さければ $ \min(A_i, B_i) $ のコストかかりそう。
コンテスト中はここまで来て、要素の小さい順のいわゆるソート DP をすれば最後に動かさなかった要素の index を状態にもつ二次元の DP でできるなあとぼんやり思ったまま時間が終了した。 実はよく詰めると in-place DP のセグ木高速化のテクニックで $ O(N \log N) $ になることがわかった。 いやー筋が悪そうには見えないんだから、ちゃんと DP 高速化を考えればよかったなと思った。 そもそも元々貰う DP が苦手なため in-place DP のセグ木高速化が全然見てないんだよね。参っている。AC。
05/28 (FRI)
9:30 ぐらい起床。前回の輪講発表はスライドに致命的な間違いが存在していた反省から、ちゃんとスライドを見直す。 結構真剣にこれをやっていた。また、終わった後も普通に作業をしていて全然ここに書ける内容がなくて助けてほしい。
諸々終わって今日の典型を確認する。★3 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_az
問題概要。$ N $ 個のサイコロと $ 6 $ 面に書いてある数字が与えられる。全てのサイコロの出目の組み合わせについて、$ N $ 個の出目の積の総和を求めよ。
当然そのままでは計算量が爆発していて、積の総和を式にしてみると、和と積には分配法則が成り立っているため結果的にそれぞれのサイコロ内の数字の和の積になる。 こういうのは寄与か分配法則を用いたいい漸化式が書けると相場が決まっている。
ゼミ発表がある。発表をする。またキョドってしまう。 日本語スライドだと見ながら何を話そうとしていたかが動的に追えるが、英語スライドだと自分が何を言おうとしていたかを十分思い出せないという問題がある。 これを解決するために、発表する前にどこで何を話すかを確認しておいた方が良さそう。 自分の発表が終わって人の発表を聞く。 ゼミが終わる。
ゼミが終わったので典型を AC しておく。このあとはだらだら漫画を読んでいた気がする。 適度な頻度で自分が読んでいる漫画についてこの週記に記録してもいいかもしれない。気が向いたら記録をしてみる。 ネタバレに気を使った方がいいかなとか思うと感想を入れることができないのだが、まあこんな週記を読む人も多くないしいいかも。
夕飯を食べた後、なぜか寝てしまう。夕飯の直後に横になるのは危険であることはよく知られているので反省。 起きたら Div.2 まで 2 分だったのでさすがに間に合わないと思い、諦めた。 その後 Streak をつなぐ虚無の作業をして就寝。
05/29 (SAT)
10:30 起床。朝食を食べる。今日は鬼のように体の調子が悪い。 今日の典型を確認する。★7 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_ba
問題概要。インタラクティブだ。極大値を $ 1 $ つだけ持つような隠された配列がある。 $ 1 $ 回のクエリでは配列の $ k $ 番目の要素の値を得ることができる。 $ N \leq 1500 $ の制約で、$ 15 $ 回以内のクエリを用いて最大値を求めよ。
典型初のインタラクティブである。この制約では極大値=最大値なので、まず思いつくのは隣接差の二分探索である。 離散の極大値探索においては、隣接差の二分探索が優れている。なぜなら極大値の $ 1 $ つを取りたいようなシチュエーションでも壊れないためである。 また収束速度もやや速いはず。特にインタラクティブの場合はわずかな収束速度の違いもクリティカルになったりするので大切かも。
ここまではいつものインタラクティブだ。しかし、このままでは $ 2 \log _ {2} N $ ぐらいの回数がかかり、これでは満点がもらえない(最悪 $ 22 $ 回ぐらいかかる)。 ここで前の結果を再利用する極値探索アルゴリズム、黄金分割探索を思い出す。 こいつは黄金比の分割で三分探索みたいなことをすると、どっちを捨てても次の必要な値の片方は再利用によって求められるというもの。 離散関数でやる場合は定義域の値の幅をフィボナッチ数になるようにすることによってフィボナッチ数の分割によって同じことができる。 $ 17 $ 個目のフィボナッチ数が $ 1576 $ のため、注意してやるとギリギリ $ 15 $ 回のクエリ以内で最大を求めることができる。
体調が悪いのでガチでだらだらしていた。とはいえちょっと作業したりはしていた。後は漫画を読んでいた。 『その着せ替え人形は恋をする』を読んだが、面白いかも。ちょっとエッチだけど、最近の漫画はこんなもんなのかな。僕にはわかりません。 最新刊を待つまでの間にまた新しいものを読み始めるため、破綻しそうになっている。
21:00 から ARC があるので頑張ろうと意気込む。
NOMURA Programming Contest 2021(AtCoder Regular Contest 121) - AtCoder
A 問題。露骨にひっかけに来ている感じがしたので慎重にやる。 問題は $ N $ 個の二次元点のチェビシェフ距離の $ 2 $ 番目に大きいものを求めるというもの。 $ X,Y $ 座標でソートして端と端、端と端から一個動いた場所の差を計算してそのうち $ 2 $ 番目の値を出すと壊れる。 なぜなら、同じ組に対しての値が存在する可能性があるためだ。そのため、そこの重複に気をつけて丁寧にやる。AC。
B 問題。$ 3 $ 色のわんこが合計 $ 2N $ 匹いて、ペアを組んだときに色が違う時に、$ |a_i-a_j| $ だけ不満度がかかる。 不満度の合計の最小を求めよというもの。 ちょっと考えると、全ての色のわんこが偶数匹ずついたら $ 0 $ になるとわかる。 奇数匹の色がある場合を考えると、合計が偶数匹なので、奇奇偶 のパターンしかない。 ここでコンテスト中は大喜びして、奇数の色どうしで最も不満度が小さいペアを出して答えにした。 WA を貰う。ここで胃が爆発しそうになりトイレに行くが、推移的なペアを組むことがあり得ることに気づく。 トイレから駆け出して AC。
C 問題。基本的に $ 1 $ から(左から)埋めていきたい。しかし、パリティの制約があるため難しい。 状況をよーく洗うと、左側の正しい部分を壊さずにパリティ合わせをすることがすることが可能になる。 パリティ合わせを壊してしまい、何回か余計なペナルティをもらいながら AC。
D 問題。わからん。
E 問題。D よりは解けそうな気がしたが、難しい。後日また考える。
というわけで ABC 3 完。perf 2128 なのでセーフだが、C の回収が遅すぎるせいで E に時間を回せなかったのが痛かった。
体が体なので本日の活動を終了する。
05/30 (SUN)
超眠い。10:45 起床。朝食を食べる。 昼飯を食べに家を出ることになる。ついでにゲーセンに行く。
3 クレぐらいしかやってないが大満足した。Sailing Force [MXM] 9988 UC が出て、ランキングを見たら今作 30 位以内ぐらいのスコアだった。 さらっと ECHIDNA [MXM] も一発で PUC 出ており、なんかすごいよかった(適当)。
昼飯を食べに行く。デニーズに入る。オムライスとポテトとパフェを頼んだ。全然そんな気はしなかったのだが、重かったらしく帰ったらぐったりしていた。
家に帰って胃が復活したら、しばらくやるべきことを処理し続けていた。気がついたら夕食を食べ終わって ABC の時間になっていた。 今日は黄色コーダーになれるかどうかがそこそこかかっているため、ちょっと緊張した。
AtCoder Beginner Contest 203(Sponsored by Panasonic) - AtCoder
A 問題。難しい。考えてる時間が惜しいので if 文を三本書いた。
B 問題。言われた通りの数字を愚直に足し上げるだけ。
C 問題。適当にやりすぎると、間に合わないので丁寧なタイプのシミュレーションをする。 こういうのにもだいぶ慣れてきた気がする。
D 問題。最初は座標圧縮した上で分布を考えてうまく差分更新できないか考えていた。 $ O(N^{3}) $ 以上は少なくともかかりそうで方針を変えようと思った。そういえば中央値の最大化最小化は決め打てば分布の値が $ 2 $ に落ちるんだった。 よって二分探索を使って $ O(N^{2} \log N) $ をする。AC。この時点で $ 100 $ 位を切っていたので緊張。
E 問題。問題文に沿って遷移を考えると、ある $ Y $ 座標にいけるかどうかを考えながら $ X $ 方向に進んでいくみたいなことにすれば良さそう。 ただ座標の幅が広いのでそのままはできない。$ N $ から隣接する黒色だけ考えれば良いから最悪でも $ M+1 $ の幅だけ考えれば良い。 $ X $ 方向に進んでいくと黒が存在したらその時点で $ Y $ 座標隣接のどちらかがに到達可能であった場合、黒の $ Y $ 座標に到達可能にする。 よく考えると、これは $ M $ 回しか行われないため、in-place にやれば間に合う。 完全に実装方針を間違えている。死ぬほど時間をかけながら AC。この時点で F を通さなければ黄色になれなそうなことに気づきくそ焦る。
F 問題。焦りから残した数の最小と最大の比を最小化すれば良いと思ってしまう。 ゆえに残しは区間になり $ \left \lfloor \frac{a_{i+(N-K)-1}]}{a_i} \right \rfloor $ の最小値が高橋くんの操作回数だと思い込んでいた。 何もかもが間違っている。これでは通らない。だめなことに気づいたのは終了の 5 分前だ。 DP でできそうなことにコンテスト後に気づき、解ける。黄色になれなかったため声出た。
Codeforces に出る。Combined だ。 不快感がかなりあったのでここではあまり触れないが、問題文に補足が追加された時に題意は変わらないはずと考えるのは当然じゃないか? 題意が変わらないと考えた結果、完全に混乱して時間を浪費してしまった。結果普通に題意が変わっていた(おそらくは writer の条件書き忘れ)。
いや、題意が変わったならアナウンスにそれをちゃんと書いてくれないか?「条件を書き忘れていました。すみません。」ぐらいせめて書いてくれよ。 競プロなんて問題文が正しいことが保証されて、競技者の信頼の上に成り立ってるんだから writer を疑ってくれというのはクソすぎないか? 俺は競プロがやりたいのであって、writer の気持ち当てコンテストがやりたいわけではない。 なんか間違ったこと言ってますか?このまま rated でも良いけど、今後はこういうのやめてほしい。やめてほしいから煽り気味にお気持ち表明 Comment した。
不快感にのまれながら就寝。