Topcoderさん、10^8ができたりできなかったりするの謎
SRM 606 div1 easy EllysNumberGuessing
問題
数当てゲームを行う。元の数字Xに対して、$N(≦50)$個の予想した値と、その差の絶対値が与えられる。
絶対値の値は大小どちらかはわからない。
元の数字が1つに決まるならその値を、2つに決まるなら-2を、決まらないなら-1を出力せよ。
解説
最初の回答から答えは2つ以下に絞り込むことができる。
以降は正しい答えの積集合のみを残していけばよく、そのサイズが0→無理、1→その値、2→特定不能、となる。
値は制約を守るものを取るとは限らないので注意。
計算量:$O(N)$
SRM 607 div1 easy PalindromicSubstringsDiv1
問題
文字列が与えられる。これを与えられた順番で連結した際に得られる文字列を$S$とする。 $S$にふくまれる’?‘にそれぞれ等確率で’a’~‘z’が割り振られる時、文字列$S$の連続部分列が回文になる期待値を求めよ。
$|S| ≦ 10^4 $
解説
これ速く解けないの絶対にダメそう
回文の中央を決定し、そこから伸ばしていくとする。
この際、文字列が固定ならば回文の判定が可能。片側が’?‘のときは$\frac{1}{26}$で一致し回文に、両側が’?‘のとき回文にするためには片側に合わせればよく、$\frac{26}{26} *\frac{1}{26} = \frac{1}{26}$である。
あとはあり得る連続部分列についてこれらの確率を足せば求める期待値になる。
計算量:$O(|S|^2)$
SRM 608 div1 easy MysticAndCandies
問題
$N(≦50)$個の箱の中にキャンディが入っている。今合計で$C$個あることがわかっているが、それぞれの箱に入っている数が$low(i)~high(i)(≦10^7)$個であることしか分からない。 箱の部分集合を選択した時、最悪の場合でもキャンディが$X(1≦X≦C)$個ほしい。この部分集合の選択の仕方のうち、箱の最小数を求めよ。
解説
全体の集合を$S$とする。
- なるべく最低個数が多いものを選択するのが良い。
集合$T$を選択した時、残りの箱に最大数キャンディが入っているとしたとき、選択したキャンディの数は、$max(C - \sum _{S \setminus T} high ,\sum _T low)$である。
これを見ればよく、$(low,high)$を組にして降順ソートすれば良い。 - 上記の$S \setminus T$について、$\sum high$が少なければ選択した箱にはキャンディがたくさん入っている。
同様の式について、$(high,low)$を組にして昇順ソートすれば良い。
1,2のどちらかに答えは含まれるので、これを両方見れば良い。
計算量:$O(NlogN)$
SRM 609 div1 easy MagicalStringDiv1
問題
文字列$S(|S|≦50)$中からいくつかの文字列を消して’<<<…>>>‘のようにしたい。 この文字列の最大値は?
解説
無駄な部分を消せば良い。
消し方がわからないので、軸を全探索し軸の左右の<>それぞれの数をみた。
計算量:$O(|S|^2)$
SRM 610 div1 easy TheMatrix
問題
$H*W(1≦H,W≦10^2)$の白黒の盤面が与えられる。任意の長方形を選択した時、市松模様なら良い盤面であるとする。
良い盤面の最大面積を答えよ。
解説
これは最近知ったテクニックで解いた。
幅$W$を全探索する。
この際1stepで$W$を増加させる際、$H$の情報を1次元の配列に落とし込む。
すると$W$に$O(N^2)$時間、$H$に$O(N)$時間で検査できるので全体$O(N^3)$で解ける。
1次元の配列は以下。
$color(i):= i$行目は0/1から始まる配列であれば0/1、そうでないなら-1
これは各$i$について$W$を変化させた時、正しいかを$O(1)$で更新可能。
更に$color$を見たときに、0/1の連続部分列の最大長を見れば市松模様の最大高さ$(H)$が求められる。
計算量:$O(N^3)$