ratedな新ABCに初参戦
5完91分0WA, 262位でした。pf1943, rate 1661->1699. 0完で溶かしたrateを回収しているが、回収速度は遅い...
経過
A
はい
B
tupleを初めて使ったら14分もかかった、キレそう
C
全探索でいいのはすぐわかったが、実装が遅すぎる(11分)
D
これもだいたい全探索でいいのは分かったが、実装が遅すぎる(19分)
E
区間を前倒しにするアイデアはすぐ出て、「区間を指定して、各点で指定した値とminを取る＋値を取得する」というクエリができればいいことまでは帰着できたが、そこから
よくわかんねー → RMQか～ (ライブラリコピペ) → RMQじゃないやんけ！ → 遅延ver.でオーバーキルできるな！ → ライブラリはあるがどう使うんだっけ (は？) → 思い出しました
とひどいムーブをしてクッソ時間がかかりましたとさ。
地味に問題文を読み間違えていたのもダメ。
F
Eが終わってあと10分もなかった。適当に言い換えを考えてたら終わりました。
振り返り
B
文字列と数の組がN個ある (番号つき)。文字列で昇順、数で降順にソートして、番号を順に出力せよ。という問題。N<=100.
頑張ってソートしましょう、という問題。本番ではtuple<string,int,int>を使ったが、pair<pair<string,int>,int>でもできる。
昇順と降順が混ざっているのは、数を-1倍すれば昇順に変えられる。数じゃなかったら頑張って順序を入れるしかなさそうだけど、時短テクとして優秀っぽい。
E
本番では遅延セグ木を貼った。モノイドとしてライブラリ化したのも持ってた(パクってた())ので簡単だったが、それで対応できない問題も出うるので想定解を見ておく。
問題としては「時間の区間と数の組 ([a_i, b_i), x_i) がN個ある。Q個の時刻t_jについて、t_i in [a_i, b_i) となるときのx_iの最小を出力せよ(ない時は-1)」という形になる。これをO((N+Q)log N)で行いたい。
この場合「イベントソート」を用いるとよい。作戦としては、
・multiset evを用意する
・ev に「a_iにx_iを追加」「b_iにx_iを消去」というイベントを、時系列順に行う。
・時刻t_iになったら最小値を取得する
というもの。イベントリストを(tupleなどで)管理してソートしておき、時刻ごとにそれ以下のイベントを全部やるとよい。
いもす法とかと似たアイデアな気がする。最小じゃなくて和を取得ならもろですか。時系列でなくても、「前から順番に見る」アイデアは持っておこう。
F
問題をまとめると
・蓮0からはじめて、A歩進んでB歩下がる(A>B)のを繰り返し、蓮N-1に到達する
・同じ座標を2回は踏めない
・蓮0からN-1までの点に値が決まっていて、踏んだ蓮の値の和が得点
・得点の最大値を求める
というもの。N<1e5.
AとBで全探索するとO(N^2) かかりそうだが、実はありうるパターン自体がそんなにないというのがミソ。
ありうるパターンについて踏む蓮を見ると、d=A-Bとして、0,d,2d,...とN-1,N-1-d,N-1-2d,...を踏んでいる。なので各dについてN/dパターンくらいしかなく、全部足してO(Nlog N) くらいのパターンしかない。前の結果利用 (DP) により各パターンでの得点はO(1) で計算できるので、これで解けました。
N%d==0の時は前からと後ろからが被るので注意 (1敗)。またN%d>0のときN-1-kd>dまでしかパターンがないので注意 (3敗)。たとえばN=14, d=3だと、0, 3, 6, 9と14, 11, 8, 5を踏むパターンはあるが (A=5)、0, 3, 6, 9, 12と14, 11, 8, 5, 2を踏むパターンは無い。
踏む蓮の形をちゃんと考察すれば素直な実装で解けてしまう。こういうの速く解けるようになりたいなぁ。まあEまででクッソ時間がかかってそもそも考察できなかったんですが。
今日の典型
・-1倍でソート反転。
・イベントソート。順番を無視するのも、順番を入れるのも、典型ですね。典型とは...
・逆数和はO(log N). N以下のdの倍数を1<= d <=Nすべてで列挙するとのべO(NlogN)になって間に合う、というのをたまに見る気がする。
