SRM607-610 Div1E

するめたのしいね ところで明日TOEICらしいけど競プロしかしてないね(ア

・SRM607 Div1E PalindromicSubstringsDiv1

小文字アルファベットと?からなる文字列Sが与えられる.?の所には小文字のどれかが等確率で入る.Sの回文になっている部分文字列の個数の期待値を求めよ,という問題.

和の期待値は期待値の和 | 高校数学の美しい物語

期待値の線形性から各部分文字列についてそれが回文であるような確率を求め,その総和を求めればいいことがわかる.すると自然に"dp[i][j]=区間[i,j]が回文である確率"という区間DPが浮かぶのでやる.先頭と末尾は同じ文字である必要があるという性質からその2文字をのぞいた区間に帰着できるので回文と区間DPは相性がいいね.

・SRM608 Div1E MysticAndCandies

n個の箱があり,i番目の箱にはキャンディがlow[i]個以上high[i]個以下入っている.箱に入っているキャンディは合計でC個である.確実にX個以上のキャンディを食べるには最小で何個の箱を選べばよいか,という問題.

何故か300点.いくつかの箱を選んだとき明らかに(選んだ箱のlow[i]の和)個以上のキャンディが食べられるが,よくかんがえるとC-(選ばなかった箱のhigh[i]の和)個以上ともいえることがわかる.したがってlow[i]をソートして大きい方から選んでいったとき最小何個で和がX以上になるかとhigh[i]をソートして小さい方から取りのぞいていったとき最大何個まで和がX以上のまま取りのぞけるかを計算し小さい方が答え.

・SRM609 Div1E MagicalStringDiv1

>か<からなる文字列Sが与えられる.いくつかの文字を取りのぞいて>がいくつか並んだあとに<が同じ個数だけ並んでいるような文字列にしたい.最小でいくつ取りのぞけばよいか,という問題.

ある位置に注目したときそれより左に>がa個,それより右に<がb個あるとすると>がmin(a,b)個並んだあと<がmin(a,b)個並ぶような文字列にするのが最適.これを全ての位置について計算してやればよい.

・SRM610 Div1E TheMatrix

各マスに0か1の書かれたグリッドが与えられる.隣り合うマスに書かれた数字が異なるような長方形の面積の最大値を求めよ.

長方形を全探索して各長方形が市松模様になっているか調べるのは遅いので,長方形の左上だけ固定してみる.するとマスに書かれた数字が交互になるという条件から簡単に縦と横にどれだけ伸ばせるか調べられるのでやるだけ.