ABC190

結果

A \ 02:58

B \ 05:52

C \ 18:57

D \ 69:21

ノーペナ 4完で，パフォは 1055，rating変動は +29で 790 \to 819でした．

考察

A問題

・C=0のとき

高橋くんが先にアメを食べるので， A \leq Bなら高橋くんのアメが先に無くなり，負けます．逆に， A \gt Bなら高橋くんが勝ちます．

・C=1のとき

上の逆で， A \geq Bなら青木くんの負けで， A \lt Bなら青木くんの勝ちです．

B問題

X [ i ] \lt S かつ， Y [ i ] \gt Dを見つけた瞬間Yesで終了．

最後まで見つからなければNoを出力．

C問題

K人の人がどっちの皿にボールを置くかでbit全探索．

bitが 0なら皿 C[ i ] にボールを置いて，bitが 1なら皿 D[ i ] にボールを置くと考えました．

bit列に対応する皿にtrueを貼り付けて， M個の条件のうちいくつを満たしているかを見ていく．

bit列を変化させたときに，条件を満たしている個数の最大値を更新していけばいけます．

計算量は O(2^{K} \times M) ．

D問題

等差数列の部分和は，項数を n，左端の数を l，右端の数を rとしたとき， \dfrac{n(l+r)}{2}です．

これが Nに等しいので， n(l+r)=2Nを考えることになります．

ここで， r=l+(n-1)であることも考えると， n \lt l+rです．(感覚的に自明ですが)

n, l+rは正の整数なので， 1 \to \sqrt{2N}の範囲で nを全探索すればOKです．

上記のように， l+r=2l+(n-1)なので l, rも O(1)で計算可能です．

割り算とかも出てくるので，いいかんじに吟味して条件を満たしていればカウントしていきます．

感想

B < A < C < Dの順で難しいと思いました．

B問題は頭空っぽで書けるけど，A問題は地味にややこしくてこっちの方が難しかった...

(緑に戻った!!)