競プロがんばりたい

ABC189

コンテスト参加

結果

A $\ 02:34$

B $\ 05:31$

C $\ 31:42$

D $\ 79:27$

$2$ WAの $4$ 完でパフォは $1083$ ，rating変動は $+38$ で $752 \to 790$ でした．

考察

A問題

$C_1==C_2$ かつ $C_2==C_3$ ならWon，それ以外ならLost

B問題

sumみたいな変数に $V [i ] \times P [ i ]$ を順次足していく．

sumが $100 \times X$ を超えたら $i+1$ を出力して終了， $N-1$ まで足しても越えなければ $-1$ を出力して終了．

$100$ で割るのが怖かったのでかけ算の形に変形しました．

C問題

左端 $l$ を決めて，右端を $l+1 \to N-1$ まで全探索．

それぞれの区間の中での最小値(min)を右端を動かすたびに更新して，min $\times(r-l+1)$ が一番大きいような区間を探索．

(区間の中の最小値) $\times$ (区間内の数字の個数)がその区間の最適なみかんの食べ方だからです．

この問題は $O(N$ $^2)$ で解けます．

D問題

後ろから見ていき， $S [ i ]$ がANDかORかで場合分け．

ANDが来たら， $x_i$ は $1$ で確定なので $i-1$ 番目に行きます．

ORが来たら， $x_i$ が $1$ だと $x_0$ ～ $x_{i-1}$ まではどの $0, 1$ の組み合わせでもtrueになるので， $2^{i}$ を答えに加算して $i-1$ 番目に行きます．

感想

前回，前々回と冷えっ冷えだったのでうれしいですね～

(地味に前回のコンテスト記事書き忘れてたw)

また緑すれすれ来たので次で戻れるといいなぁ～

卒論に殴られているので，精進記事はしばらく書けなさそうです．