05/10 (MON)
9:00 前後に起床。月曜は研究室に行って on demand な講義を再生したり作業をしたりする日にしているが、今日は大学に提出書類などを作成するなどしていてゆっくりめに家を出た。この時間の電車は空いていて最高だと思う。 行きの電車の中で今日の典型 90 問を見た。
https://atcoder.jp/contests/typical90/tasks/typical90_aj
二次元平面上の点が $ N $ 個与えられて、指定された $ Q $ 個の点について、$ N $ 点の中で最遠のマンハッタン距離を答えろというもの。これどうせキーワードは「マンハッタン距離は 45 度回転」だろ。
まあ「45 度回転」なんて思わなくても $ |X|=\max(X,-X) $ であることを思い出せば、すぐに $ 4 $ 通りの式の $ \max $ であることに気づき、変数分離をすることでそのうち本質的なものは $ 2 $ つであり、マンハッタン距離は $ (x+y, x-y) $ のチェビシェフ距離と等しい結果が得られる。比が違ったり次元多かったりしたときにも使えるテクニックの方で頭に入れておきたいと思って再確認した。 この時点では眠くてスマホコーディングする元気はないので帰宅したら書こうと思った。
このタイミングで毎日の生活にメリハリがなさすぎるため、週記を付けることを決意。
昼前に大学に到着する。昼前なのであまり作業もしないまま大学に来ているキッチンカーへ先輩方と向かう。曜日によって来るキッチンカーが決まっているが、月曜はケイジャンビーフチーズ＆ライスを毎週食べている。牛肉とチーズが好きなチー牛野郎なのでこれしか食えない体にされつつある。 飯のあと、ゼミがある。後輩の輪講 ONLY の回だ。去年僕も読んだコードなのだがあまり詳しく思い出せないな、などと思っているうちに終了。昼からは作業をしていた。具体的には書かないが、C++ のコードを C で書きなおす必要があり本当に助けてほしかった。
20:30 頃に大学を出た。さすがにこの時間から飯も食わずにゲーセン行くのは戦士すぎるため直帰。帰りの電車では普通に寝まくっていた。デレステの営業だけ設定したかも。
帰宅。実家住みに感謝しながら晩御飯を食べる。おいしい。 今日の典型をコーディングする。脳が解けていてなぜか 2WA 貰いながら AC。 学部生の課題の採点、仕事、ピアノの譜読みなど色々なことに思いを馳せながら全て投げて ARC 118D - Hamiltonian Cycle の続きを考えていたが、解けない。 競プロすら投げて、今日は今朝買ったジャンプを読む。2:00 頃までじっくり読んでいた。 Dr. STONE の続きが最近とても気になる。まだスイカ以外のキャラクターは石化したままだ。 矢吹健太朗の絵が結構好きなのであやかしトライアングル読んでいるのだが、読んでる最中に親が入ってきたら嫌だな。今週もエッチだったし。 というかジャンプに掲載されている殆ど全ての作品は読んでいる。少年なので。 気が付いたら寝ていた。
05/11 (TUE)
13:30 に起床。最悪。驚くべきことにこの時間で二度寝はしていない。一度寝でここまで寝られる日はなかなかない。スマホで時間の確認と今日の典型の確認をする。
https://atcoder.jp/contests/typical90/tasks/typical90_ak
$ N $ 個の料理が与えられて、それぞれが $ L_i $ 以上 $ R_i $ 以下のコストをかけて $ v_i $ のスコアを得る。コスト合計がちょうど $ W $ になるような料理の作り方があれば価値の最大値を答えよ、という問題だった。制約を見て O(NW) とか O(NW log W) が間に合うのでナップザック DP である。連続部分列に対して同じ更新を行う DP は遷移をセグ木を使って高速化できる。この場合は in-place DP でセグ木高速化をするのが一番楽そう。一回の更新の中で幅が一定なので、スライド最大値を使って余計な $ log $ を付けずに済んだりする。ABC200E - Patisserie ABC 2 もこれだった（こちらは更新が加算なのでより簡単に $ log $ が取れるが）。さすがに典型☆5は見た瞬間だな。
朝食が消滅したので、親に申し訳なく思いながら昼食をとる。本当にカスなので申し訳なさがすごい。今日は講義を受ける予定もなければ、コンテストもないし大学へ行く予定もない。明日の昼までのショートレポートがあるぐらいだと思う。このショートレポートは講義内容の要旨と軽い意見を 400 字以内にまとめるというもので、講義を受けてさえいれば一瞬で終わる。などと思いながら午後の過ごし方（すでに午後だが）に思いを馳せていた。
飯を食べ終わったので、採点、仕事、ピアノの譜読み、作業の 4 つの内どれをやろうか悩んだ。正直どれもクソ大事なタスクである。ピアノのレッスンが明日なので、とりあえず譜読みを優先することにした。Twitter で競技と音ゲー以外のことを全く話さないため自分がピアノを弾かなければならないことを時々忘れる。実家住みでピアノがあることはすごく有難いが、家族の都合に合わせて練習をしなければならないのは、このコ某ナ禍の苦しみポイントの一つだと思う。
16:00 ぐらいからウォーミングアップから譜読みを開始。ラ・カンパネラと言う曲なのだが、譜読み自体は簡単で手の運動が鬼のように遠い。アマゾンで第三の腕を購入したいレベルで遠い。体感 5 キロぐらいある。四苦八苦しながら 3 時間ほど練習した。早くある程度弾けるようにならなければ…
夕食をとった後、今日の典型を実装する。in-place DP をセグ木で高速化やっぱり実装が楽だ。in-place だとキャッシュに載りやすくなり思っているより早くなるからあまり $ log $ を落とす気にならないんだよな。とはいえいざと言うときに落とせないのはまずいと思ったのでスライド最大値でも通しておいた。deque に添え字を入れる実装をしているのに添え字と比較していたりして無駄な時間を要した。 スライド最大値（最小値）はほぼ自動で書けるようにしておきたいな。
この時点でもう今日は休むフェーズに入ろうと思ったのだが、ここで昼食時に思いを馳せていたところの 400 字レポートを書くことにした。講義音声が配られるタイプの講義なのだが、3 つある内の 3 つ目の音声が壊れていることを思い出した。報告しようとしていて完全に忘れていたのだが、課題に関係ある部分でなかったため 400 字のレポートを書く。せっかくこの時間に身体を縦にしていた記念として、ついでに on demand の講義を一つ消化しておいた。大体知っている内容で涙がちょちょ切れてしまったが消化したという精神的優位が得られたため良しとした。
提出を終えた後は、競技プログラミングを少しやった。虚無を 2~3 問と青 diff を 2~3 問解いた。 経験的に二分探索をしたくなるような設定でなぜ二分探索が効くのかについてちょっと整理したくなってきた。いろんなパターンがあるため、これから見つけたらメモしておこう…
布団に入ってもこうの動画をみているうちに寝落ちした。
05/12 (WED)
11:00 に起床。二日連続で寝坊したが、このぐらいならまだ許容範囲かな。トーストとコンビーフの朝食をとる。例によって今日の典型を見る。今日は☆3 か。
https://atcoder.jp/contests/typical90/tasks/typical90_al
$ 2 $つの整数 $ A,\,B $ が与えられてその最小公倍数を求めよ。ただし $ 10^{18} $ を超える場合はそれを報告せよ。と言う問題だった。 最小公倍数は $ \frac{A \times B}{\gcd(A,B)} $ なので $ \frac{A}{\gcd(A,B)} $ と $ B $ の掛け算が $ 10^{18} $ を超えるか確認すれば良い。単純にやるとオーバーフローして壊れるので $ \frac{A}{\gcd(A,B)} > \left \lfloor \frac{10^{18}}{B} \right \rfloor $ で判別すればいい。多倍長や 128 ビット整数を使えばそのままいけそう。
余談だがこの記事を書いている最中にまた床関数とかの括弧の大きさを自動で調整するやつの書き方を調べた。全く覚える気がないので本当に毎度調べてしまう。よくまとまっているチートシートをローカルに落としてしまおうか…
そうこうしているうちに正午を回ってしまう。譜読みの優先度が MAX なので昨日の続きをすることに。 昼飯には、買ってきてもらった弁当を食す。そぼろと卵の弁当なんだけどシンプルでおいしかった。食した後また譜読みに戻る。 右手が言うことを聞かないため叱咤していたら時間になってしまっていた。急いで家を出てピアノ教室に向かう。下手すぎて泣きそうになるも、終えて帰ってくる。
ピアノから帰ると 15:30 ぐらいで典型のジャッジが来ているかなと思って確認したら、追加されていたので提出。AC。 今日は作業をしなきゃいけないんですよね～って心のクソデカ声で叫びながらちょっと疲れたのでデレステを起動した。
馬鹿なので 3 時間ぐらいデレステをしていた。理性の敗北。でもデレステの感覚を思い出してきた。そうだこのゲームをスマートフォンでやるにはそれなりにコツがいるんだった。具体的には複数指運指の使いどころが難しい。
夕食を食べたらさらにやる気を失ってしまった。2 時間ぐらいマンガアプリでマンガを読んでいた。5 時間連続で生産性のない活動をしていたことになるのでまずいと思い、せめて競プロをすることにした。とくにやりたい問題もなかったので Problems の Recommend 機能を使うことにした。D - Double Landscape があったので適当に選ぶ。Diff 1670 だと思って舐めていたら酷い目に遭った。普通に 40 分以上かかったので割と助けてほしいな。
問題概要は、$ N \times M $ の表に対して $ [1,N \times M] $ の数字を重複なく書き込むことを考える。$ A_1, A_2, \cdots, A_N $ と $ B_1, B_2, \cdots, B_M $ が与えられて、$ i $ 行目の最大値が $ A_i $ 、$ j $ 列目の最大値が $ B_j $ となるような書き込み方の通り数を求めよ、というもの。重複がないから $ A $ や $ B $ の内部で数字の重複があったらその時点で $ 0 $ なことがわかる。また、$ A $ にも $ B $ にも含まれる数字がある場合、その行と列が交わるマスは必ずその数字を書き込まなければならない。また、とりあえずマス $ (i,j) $ は $ \min(A_i, B_j) $ 以下の数字を書き込まなければならなそうだということがわかる。大きい数字の方が明らかに書き込みづらいので、制約を守るようなまだ書き込まれていない $ X $ の書き込み方を $ X $ の大きい方から求めて掛け算をしていくといいと思った。最後のサンプルが合わない。参った。よく考えたら、$ A $ や $ B $ に数字があるってことは、その行や列にその数字がなければならないことに気が付いた。行や列に書き込みのある数字の場合はより強い制約で置くように書きなおしたらサンプルが合う。提出。AC。 こういう問題を速く解くにはどうすればいいか途方に暮れていた。と思ったけど自分で最初に書いていた条件を忘れていただけなので競技痴呆をやめることによって改善されそう。自分で書いた考察メモはちゃんと見よう！
C - 掛け算 も Recommend されていたためやる。$ a_1, a_2, \cdots, a_N $ と正整数 $ A, B $ が与えられるから、数列で最小の数に $ A $ を掛けるという操作を $ B $ 回行った結果をソートした上で、$ mod 10^{9}+7 $ で答えろという問題。冷静に考えると、 $ a $ 内の数字は実行する演算に比べて差が小さいなと思う。全部が $ 1 $ 回以上掛けられたらすべての数を $ A $ で割ることで過去の状態と同一視することができる。全部が $ 1 $ 回以上掛けられるのにかかる操作回数は $ A \geq 2 $ なら $ O(N log A) $ ぐらいな気がする。これぐらいなら愚直に計算が余裕にできる。結構実装が嫌で、疲れていることもありいやいや言っている時間が長かったので反省。結局 $ A=1 $ のパターンを忘却して $ TLE $ を一回食らってしまった。
この時点で 1:00 になっている。木曜は早起きしなくてはならないため寝る。
05/13 (THU)
7:00 起床。眠いし寒い。適当にパンを食して家を出る。家を出て少し歩くと雨が降っていることに気が付く。最悪だが予定した時刻の電車に乗れないのはもっと不愉快なので我慢してそのまま行く。 いつもの通り電車内で今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_am
問題概要は、$ N $ 頂点の木が与えられてすべての頂点の組に対してその距離の和を求めよ、というもの。脳がうまく起動していないのか最初に全方位木 DP をして最後に $ 2 $ で割る解法を思いつく。もちろんこれでも $ O(N) $ なので問題はないが、こういう問題は寄与を考える方が筋が良いだろう。実際にそれぞれの辺の寄与を考えると、その辺を切ったときに出来る $ 2 $ つの木のサイズの積になる。これを足し合わせればいいので部分木のサイズを持つ簡単な木 DP で良い。
大学に着く。木曜日はオンラインの 1 限があるのだが、これを受けてから登校すると微妙な時間なのでいつも大学で聴いている。今週の課題はものすごく簡単そうということがわかった。今日は朝から胃が重くダルかったのであまり作業に身が入らない。だめそうなので研究室に置いてあるルービックキューブで遊ぶことにした。過去のしょっぱいタイムを塗り替えるために普段使っているのとは別の揃え方を調べて覚えた。作業に戻ったり、周りの人と喋ったりしているうちに昼の時間となった。
木曜はキッチンカーのタンドリーチキン丼をたべることが決まっている。いい加減別のメニューを試したいが冒険して口に合わなかった時のことを考えるとできない。胃が重いためタンドリーチキン丼が想像よりつらかったけどいつも通り美味しかった。
色々やってちょっと早めに大学を出た気がする。大学を出る前に典型を通す。作業はできたと思ってから何度もデバッグをしていたし、体調も微妙だったので今日の進捗はあまりよくなかった。気分転換にゲーセンに行くことにした。身体が不調なのか指が思い通りに動かなくて困った。一応それなりに満足して帰宅。
帰って夕食を食べる。帰ったら夕食があるって本当にありがたいことですね…。今日は何をやってもダメそうなのでベッドで横になった。 週記の今日の分を書いていないことを思い出したので急いで書く。日付も回っているので今日はもう寝ようかなと思うが典型以外一問も通していないのはマズそうなので少しだけ競プロをやることにした。
B - Boxes を解くことにした。 問題概要は、円環上に数字が並べてあって $ 1 $ 回の操作で任意の位置から時計回りに $ -1, -2, \cdots, -N $ を数字に実行できる。この操作を任意回行って全ての数字をピッタリ $ 0 $ にすることができるか判定せよ、というもの。問題がシンプルでかなり好み。問題文のみからでは自明な解法は浮かばない。引いていくこと考えるのは面倒なので、逆の操作で最初の数列を $ 0 $ から構成できるかを考えた。自明な性質として、$ 1 $ 回の操作で総和は $ \frac{N(N+1)}{2} $ 増える。よって与えられた数列の総和がこの倍数でなければ NO が判明する。ちょっと詰まるも $ 1 $ 回の操作の右隣との寄与の差は大体 $ +1 $ で端と端の部分だけ $ -(N-1) $ である。差に注目すればもっと扱いやすい制約として考えられそうだ。操作回数は 総和÷$ \frac{N(N+1)}{2} $ で決定するため、それぞれの位置について連立方程式から操作の開始位置として選んだ回数を求められる。あとは非負整数条件や操作回数の条件を確かめて問題がなければ YES。AC。考察 $ 15 $ 分の実装 $ 5 $ 分。難しい実装でもないのに遅い気もする。
うーん、操作が厄介なため操作が単純になるような量に着目するのは典型な気がする。あとは未知数が $ 2 $ つの式が一つしかないからもう一つを探すというのもアプローチの一つかもしれない。
あと気分でCoding Gameを登録した。やり方は明日にでも見ようか。
05/14 (FRI)
9:00 に起床するも、昨日のダルさが全然抜けてなかったので二度寝して正午過ぎに起床。朝食は食べないことにした。 レトルトのハヤシを温めている間に今日の典型問題を確認する。今日の問題は☆7なので見てすぐとはいかない。ハヤシを食べながら典型問題を考える。食べながらだと余り集中できないが、問題をグッと睨むと $ O(N3) $ で解けた。と思ったが嘘だった。わざわざ嘘のためにスペースを使うのはもったいないので割愛。改めて考えると依存関係にサイクルがないため、最小カットで最適化できるタイプの問題であることがわかる。世間では「燃やす埋める」と言われるやつだろう。実はまだ最大流ライブラリを作っていないため、WSL 環境でこの問題を通すのが面倒なので、実装を後回しにする。ライブラリをちゃんと作って早く人間になりたい。
典型を考えたり Twitter を見たりしている内に TA の時間がきた。TA の時間、最近本当に暇なため手元でずっと作業をしている。三週連続ぐらいで一回も質問が来ない。学部生の間で使えない TA の烙印を押されている可能性があるな。最後にされた質問も Eclipse の使い方だし、本音ではそんなの俺に聞かないで欲しい。TA の時間が終わると、ゼミの時間となる。自分の発表回ではないため聞く。色々あったが終わる。やんわりゼミの後に教授と相談する予定になっていたのだが、それを zoom で言い忘れる。これ確か前もやった、人はなぜ同じ過ちを犯すのか。急いで slack で連絡したら相談に漕ぎつけた。懸案事項も解決してハッピー。
夕食を食べる。夕食後はダラダラしていた。具体的には YouTube を閲覧していた。もこうがマナー講師にバチボコに怒られている動画面白すぎて呼吸困難になる。
例によってこのまま日付が変わるのはよくないと思い AtCoder Problems を開く。
D - Classified を解くことにした。こういう問題結構すき。問題概要は、$ N $ 頂点の完全グラフがある。全ての辺を正整数で色分けして、同じ色の辺を使って移動して元の頂点に戻った時に通る辺の本数が偶数になるような色分けで辺に割り当てた最大の整数を最小化せよ、というもの。
一番最初に出来るだけ少ない二部グラフに分解する問題だなぁということを理解した。最初の $ 10 $ 分ぐらいは $ N=4,5 $ の図を書いて唸っていた。とりあえず、頂点数 $ N $ の二部グラフを考えてみたところ、よく見たら補グラフは完全グラフ 2 つになっていることに気づいた。完全グラフのサイズが小さい程最適なのは自明なので、できるだけ半分に分割すればいいわけだ。分割統治的に再帰的に解けるなと気づいたので実装に入る。実装が下手でビビった。あと偶奇で分割していたが余計混乱する原因になったので反省。$ 15 $ 分ぐらいかけながら AC。 思ったけどこういう問題、大体再帰的に解けるよな。メタ読み下手くそなのであまり意識しないようにしてはいるけど。
C - 収集王 も解いた。グリッドに $ N $ 個のコインがあってあるマスに降り立つと同じ行/列のコインを収集できて、ちょうど $ K $ 枚収集できるような降り立ち方は何通りかと言う問題。これは流石に自分にとってはやるだけにしないとまずそう。グリッドがデカく $ N $ もデカいので二次元累積和とかはできない。同じ行/列の個数系の問題は交差する地点に置いてあるかどうかだけが本質がち。行/列についてそれぞれ何個コインが存在するか求めておいて、和が $ K $ になるものを基本的に考えればいい。降り立つ地点（＝交差する地点）にコインがあって和が $ K $ の数を引き、$ K+1 $ の数を足すことで問題ない。AC。$ 10 $ 分以内に AC できなかったので反省。
05/15 (SAT)
11:11 起床。朝飯を食しながら今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_ao
$ N $ 個の座標が与えられて、それらを全て含むような最小の周を持つ多角形で覆う。この多角形の中にある (周も含む) 格子点の数を数えよ。 多角形は明らかに凸包。なので $ O(N \log N) $ で凸包を作る。最初に思いついた解法はそこから三角形に分割して Floor Sum を使って内部の格子点の数を重複を気にしながら数え上げるというものだったため、いやだなぁという旨のツイートをした。 しかし冷静になると、ピックの定理 - Wikipediaとかいうのがあったなあと思い出す。多角形の面積は原点中心の三角形の符号付面積の総和で求められる。辺上の格子点の数はまあ頑張って数えれば、あとは定理の式を整理すれば答えが出そう。
典型を考えていたり、ちょっとだけ作業をしていたりしたりしたら昼食の時間になってしまう。
昼飯を食いに出かける。ファーストキッチンを食べた。ここのポテトの質めちゃくちゃ高くないですか？すいてる昼飯どころ目的で来たけどポテトがうまいのを思い出せて満足。そのあとはゲーセンに向かう。身体の調子は悪くなさそうなのだが、あと一歩みたいなのが多かった。もうそういう日だということにした。最後の悪あがきをしたら SOUND VOLTEX で初の 19PUC が出た。一応めでたい。欲を言えばもっとかっこいい曲で決めたくはあったけど。
帰宅。鬼のように音ゲーをしていたせいで帰ると 19:00 前とかそんなん。 晩飯を食べる。音ゲーで完全に疲れているけど今日の ABC 大丈夫かななどと思う。とりあえず指のウォーミングアップも兼ねて既 AC の問題を解きなおしたりして時間を待つ。ABC が始まる直前に口にガムを放り込み集中力を高めようとしてみる。 A-E が「実家」みたいな問題だったため、ガムの集中力もあってか自分にしてはそう悪くないタイムで駆け抜けられる。 F がクリティカルっぽい考察までいくも詰め切れずタイムアップ。132 位で perf 2400 なのでヨシ！レートが 1964 になった。東京五輪だ。 しかし明日は ARC だ…流石にここまできて 1900 付近に戻されたら萎えるので体調によっては不参加を決めさせていただくかもしれない。
さて、 Google Code Jam Round 2 がある。ABC が終わって間もなく始まるのでバタバタしたが、特に問題はないように思える。特別眠くもなかった。
A 問題を開く。いきなり interactive である。interactive は詰まると絶望しかないので、戦々恐々としながら問題文を見る。見えない数列があって、区間を与えると最小値のインデックスが返る query をコスト $ \frac{10^{8}}{r-l+1} $ で実行できる。 $ 6 \times 10^{8} $ までコストを消費できて、こいつらをスワップすることで昇順にしろ、と言う問題。見た瞬間調和級数かな？と思ったが、そんな簡単なわけが…と謎読みをしてしまい時間を浪費する。全人類が一瞬で通しているため投げると通る。
B 問題を開く。問題については長くなりそうなので割愛。コイツに自分の今回の GCJ は破壊されてしまった。コーナーケースを見落としたり、コーナーの処理をミスったりして 4~5 ペナと無限時間を費やして AC。
C 問題を開く。こちらも問題については割愛。個人的にそんな得意そうな問題ではないし、small を通そうと思ったが順位表を見るにこれは large も通さないと結構やばそうな雰囲気があり、しばらく考えた後一旦 D 問題に行くことを選択。
D 問題を開く。難しそう。問題文は割愛するが、small は二部マッチングを解けばよく、Dinic を貼って通す。が、実装がへたくそすぎて、かなりの時間を費やしてしまっていた。
C に戻る。しばらくサンプルを使って色々試したり、唸ったりした結果 large まで解けた。が、この時点で残り 2 分だった。もう small すら間に合わないなと思ったので日本人の順位表を眺めたりしていた。
最終順位は 1514 位、c を投げていたら順位はもう少し上がっていただろうが読み通り ABcd は落ちていたらしいのでやはり C を通さなければならなかったな。A の迷いの時間、 B と d に使った時間みたいなのを何とかすれば来年は Round 3 に進めそうだな…
完全にふてくされてしまったので、明日は何もしないことにした。寝る。
05/16 (SUN)
12:00 起床。よく寝た。朝ごはんは食べないことにした。最近朝食を抜きすぎているのでそろそろ反省の方をさせていただきたいと思います。兄と一緒に KFC を食べに行くことにした。食べた。おいしかった。KFC のオリジナルチキンっておいしすぎないか？ウマ娘の話とか聞きながらダラダラして、ちょっとゲーセンで遊ぶことになった。
うっかり DDR にクレジットを入れてしまったため全身疲れているが、17:00 からえでゅほがあるため帰宅。
https://codeforces.com/contest/1525
A 問題。$ 1 $ リットルずつ入れて行って $ k : 100-k $ を作る問題。最大公約数でしょう。
B 問題。全体以外の区間を自由に並び替えられる操作を何回で与えられた数列を昇順にできるでしょうという問題。 昇順なら $ 0 $。端が正しい数字なら $ 1 $。それ以外なら $ 2 $。とやってしまいがちだが、よく考えると左端に $ N $ 右端に $ 1 $ がある場合は $ 3 $ になる。 結構ペナをもらっている人が多かった印象。
C 問題難しくて、D 問題を先にやる。一列に並んだ空き席と座られている席（半分以下）があって、人を移動して元々座っていない席にのみ人を座らせたい。移動量の最小値を求めよという問題。 これは移動先の空き席の集合が決まれば左から順番に人を割り当てれば良い。移動がクロスしなければ損しないよくある奴だ。この前のえびまさんのお誕生日コンテストでも見たな。E - Min Cost Sort ←これだ。 よってあとは空白を使う使わないを選択していく二次元 DP でいける。
C 問題。難しい。左右どちらかの向きを向いているロボットが一次元上に配置されていて、$ 1 $ 秒に $ 1 $ 向いている向きに移動する。左右に壁があり、壁にぶつかると向きを変える。ロボットどうしが整数座標でぶつかると爆発する。それぞれのロボットが爆発する時刻を報告せよ、という問題。 パリティが一致するロボットしかぶつかって爆発しないので分ける。あとは set をそれぞれ $ 2 $ つずつ使って時系列に沿ってシミュレーションする。こういう set いじいじ系が本当に苦手。
E 問題。制約で罠を仕掛けに来ている。$ N $ 個の直接支配する都市と、支配したい $ M $ 個の地点が与えられる。それぞれの都市から $ M $ 地点に対する距離が与えられて、支配されたターン数で支配領域が $ 1 $ ずつ増えていくので、ランダムな順番で $ N $ 都市を支配した時の支配できる地点の個数の期待値を求めよ、という問題。 最初はゴニョゴニョ bit DP とか考えていたが、期待値なので主客転倒を考えると、余事象が簡単に求められるため答えが出る。C より簡単じゃないか？
残念ながら E のバグとりが間に合わず 4 完。まあ耐え。
夕ご飯をたべる。肉がうまかった、助かります。 お腹いっぱいで ARC を辞退しようかかなり迷ったが、まあなんとかなるの精神で出場。
AtCoder Regular Contest 119 - AtCoder
A 問題。こういうのは一番影響のでかい文字から決め打っていく。今回は $ b $ を決め打てばあとは $ a $ を最大化するだけ。
B 問題。クロスせずに $ 0 $ を移動するだけ。さっきの問題の残像で解けるな。
C 問題。むずい。足してから引けばいいので実質マイナスは気にしなくて良い。区間に着目した時に端から消していって全部消せたら OK なのだが、その手続きを式に落とすと引き算の連結になり偶数和と奇数和が一致することと等価であることに千年かけて気付く。遅すぎる。偶奇の寄与を +- として累積和テーブルを作っていつもの等しい組みを数えるやつ。
D 問題。むずすぎ。依存関係をグラフにして SCC をするという嘘を生やす。これを一時間以上かけて実装して丁寧に WA をもらう。これで最大化できるのは操作列の最長だ・・・
E 問題。リバースというが、評価値が影響を受ける範囲はスワップより少ない。隣接二項を方向つき区間としてやると、これをつなぎ変えることになる。よく考えると逆向きの区間どうしをつなぎ変えても意味がないことに気がつき、最終的に区間の共通部分の長さの倍だけ改善することがわかり、あとはイベントソートなりなんなりで解ける。この問題を先にやってればなあ・・・
C が遅かった割には 耐えていた。ナイス耐え。黄色入りは来週以降に持ち越し。
なんかすごい夜更かしをした気がするが、何時に寝たか覚えていない。
週の後半はなんか自由人みたいな生活を行なっていたが、週記を始めたことで横になっている時間は減ったのでこの調子で来週も活動をしたい。
