ABC250 E - Prefix Equality

初めに

atcoder.jp 解けなかったので

敗因

X_i := \lbrack 1, A_i \rbrack と \lbrack 1, B_p \rbrack の集合が等しくなるような最小の p

Y_i := \lbrack 1, A_i \rbrack と \lbrack 1, B_p \rbrack の集合が等しくなるような最大の p

みたいなものを考えて, set の比較が O(1) でできると信じていたので裏切られて TLE. (WA はなぜか分からない) atcoder.jp

解法

サイズだけ考える→重複を抜いたもので考える atcoder.jp

終わりに

いろいろな別解があるっぽい(User解説がたくさんあったので)

目を通してみて, お勉強するかも?

ABC294 F - Sugar Water 2

初めに

atcoder.jp 解けなかったので

敗因

典型1 最大/最小から K 番目の要素は答えで二分探索する←知ってた

典型2 ふたつの組み合わせの数え上げは, 片方を固定してみる←知ってた

典型3(?) 砂糖/食塩水の問題はある濃度に達するまでの砂糖の量とかをみるといい←知らなかった

解法

「 x % 以上の溶液が K 個以上あるような最大の x を求める」問題に言い換える.

これは「 x % 以上の溶液はいくらあるか?」という問題を用いて二分探索できる.

全ての溶液に対して, 「 x %にするための砂糖の量との差」を求めておいてソートしておくことで, 片方を固定したときに二分探索を用いて, その溶液と混ぜた時に x % 以上になる溶液の個数が分かる.

よって, O(log \, \frac{1}{\varepsilon} \, N \, log \, N) で答えを求めることができた.( \varepsilon は許容される最大誤差)

atcoder.jp

終わりに

くやしい...

AGC004 B - Colorful Slimes

初めに

atcoder.jp 解けなかったので

敗因

実はけっこう前から温めてた問題. 最初は精選100 + 50 問で, RMQ の練習問題としておいてあったのを見て.

普通に考察すると何回魔法を使うかで場合分けして最小値をうまくとるみたいな噓貪欲をはやして 9 WA (In 21 cases)...(ちなみにどういうケースで落ちてるかまだ分かっていません...) atcoder.jp

解法

魔法を使う回数を固定する( k とする)と, スライム i を捕まえるためには, スライム i, i-1, \ldots , i-k を捕まえればよい.

(これはスライム i 以外のスライムと干渉しない. (Editorial PDF の図みたいに, 魔法を使うところにスライムを捕まえるイベントを適切位置に挿入していくようにすれば構築できるので.))

よって, ans_k = k \cdot x + \sum_{i=1}^N min(A_i, A_{i-1}, \ldots , A_{i-k}) となるので RMQ を用いると O( N^2 log N ) で解けた.

atcoder.jp

( min(A_i, A_{i-1}, \ldots , A_{i-k}) は累積minみたいな感じで O(1) で計算することができるので log を落すこともできる(公式 Editorial の解法))

atcoder.jp

終わりに

魔法の使う回数固定は合ってただけに悔しい.

(魔法操作に購入操作を挿入するという考え(→各スライムの購入は独立という考え)ができませんでした...)

あと RMQ は想定解じゃないのか... (そもそも静的区間minだから線形RMQすれば O(N^2) か)

codefes2016C C - 二人のアルピニスト

初めに

atcoder.jp 解けなかったので

敗因

昨日解いた AGC020B みたいに, 各山について最小値 / 最大値がひとつ前から線形に求まるか...? みたいなことを考えていました. 実際は決まるのは最大値だけなのでそれは考えなくてもよいです. (よく考えると最大値しか知らないから最小値が出てくるわけがないがないですね...)

解法

条件を整理しましょう. T をみると,

\displaystyle \cdot \, H_i = T_i ( T_i \ne T_{i-1} ) \\ \cdot H_i \le T_i ( T_i = T_{i-1} )

が成り立ちます. 同様に B についても考えると, \displaystyle \cdot \, H_i = T_i = A_i ( T_i \ne T_{i-1} \wedge A_i \ne A_{i+1} ) \\ \cdot H_i = T_i \le A_i ( T_i \ne T_{i-1} \wedge A_i = A_{i+1} ) \\ \cdot H_i \le T_i = A_i ( T_i = T_{i-1} \wedge A_i \ne A_{i+1} ) \\ \cdot H_i \le min(T_i, A_i) ( T_i = T_{i-1} \wedge A_i = A_{i+1} )

等号の部分はよしなにします. atcoder.jp

終わりに

うーん, もうすこし詰めたら解けそうだったなあ...

AGC020 B - Ice Rink Game

初めに

atcoder.jp 解けなかったので

敗因

例えば A_K は必ず 2 でないといけなくて, A_{K-1} は 2, 3 でないといけなくてみたいなこと( -1 のときはどうなるのかを)を考えていました. ( -1 になるときを中心に考察を進めても難しいので) K = 10^5 から線形にできる方法を考えるべきでした.

解法

各ラウンド直後の最小, 最大をもっておけばそのひとつ前が計算できます. O(K) です. 具体的には, L_i, R_i を i ラウンド後の最小 / 最大値としたときに,

L_{i-1} = \left \lceil \frac{L_i}{A_i} \right \rceil \cdot A_i

R_{i-1} = \left \lfloor \frac{L_i}{A_i} \right \rfloor \cdot A_i + ( A_i - 1 )

が成り立ちます. atcoder.jp

別解

( log がつくけど)二分探索でも通ります. 「広義単調増加関数同士の合成関数もまた広義単調増加関数になる」そうです(知りませんでした, これって自明ですか? よく考える余地があるかも?). そうすると Editorial での g が広義単調増加関数になるので二分探索ができます, と. なるほど... 最小最大で分けて二分探索をして逆転してしまえば -1 . 賢いですね. atcoder.jp

終わりに

よくかんがえれば dp なのか, むずかしい...