AtCoder Beginner Contest 189

C

N^2未満の解法はぱっと思い浮かばない

lごとに累積minを持ちながらl,rを全探索、で O(N^2)になるが、ABC-Cで10^8は見たことが無い

 N \leqq 10^4の意図がよくわからない

 x \leqq 10^5を見てxの全探索を考える

xの値ごとに、全ての要素がx以上であるような区間の長さのmaxを求めればよい

xを降順に見ると、全ての要素がx以上となっている区間が次第につながっていくことが分かる

→UnionFindでやる

 

冷静になると最大長方形問題

長方形の右上端を全探索、左下端を探す時にstackでよしなにやると O(N)でできることが有名

 

D

問題文に漸化式が書いてあるのでDPを考えたい

N=60で踏みとどまる

数え上げなのにmodを取らない設定、[2^60 \leqq LONG_MAX]を意図していそう?

じゃあDPでいいか

 

dp[y_iが][0か1か] として計算

y_iが0のときはi以下のxはなんでもよいので、一次元でよかった

 

E

とりあえず式にするべき

(x,y)に対する変換操作を整理すると、x,yのswap、係数の反転&定数項の加算からなることがわかる

→x,yがswapされた回数と、x,yの係数、定数項の値を持って変換結果の累積を持っておけばよい

 

累積を持っておけば十分であることに気づかず、クエリをaでソートしたりしていて燃えていた

書くことが多いと処理を忘れがち、まとめておくのがよさそう

ちょっと重めの実装に慣れていないので、こういうのが出ると早解きに失敗してよくない

 

F

とりあえず期待値の線形性を考えたい、各マスから移動する回数の期待値を求めればよい?

→うまくいかなかった

マスN-1の結果は明らかなので、マス目のindexに対し降順にDPをすることを考える

マス[i]からスタートする場合の合計操作回数を順に求められたらハッピー

振り出しに戻るマスの遷移式でE_0が出てきて、遷移式が循環して困る

→式変形をして循環を消したい

単純に移項するだけ(期待値を求めるときによく見る)では消せない

とりあえずdp[0]をxと置いてDP遷移をすると、各dp[i]はxの一次式になっていることがわかるので、この式の係数をDPで求めればよい

E_0がE_0の一次式で書けるので、単純に移項するだけになる

 

貰うDPを書いたら、遷移のindexで大変なことに...

 

dif2000以上の考察・実装が2000未満より明らかに遅い、春休みはここを何とかしたいな