100問埋めます!
解説も大変だけど書きます!
SRM 601 div1 easy WinterAndPresents
問題
$N(≦50)$個の箱があり、箱iにリンゴとミカンが$apple(i),orange(i) (≦10^6)$個づつ入っている。
すべての箱から$X$個づつ取り出した時、この果物の組(リンゴ、ミカン)の組合せは何通りあるか?
解説
$X$個それぞれで組は独立して見ることができる。 どのような組合せでもよいがX個必ず取り出せるとして、各箱からX個取り出す。 このときリンゴの取る数を最大化したときと、最小化した時までの組の値は(5,1),(4,2),(3,3),(2,4)のように連続している。 したがって最大化したときと最小化したときの値がわかればよく、これは箱の中身の和の最小値を$MinSumBox(≦2*10^6)$として、$O(MinSumBox*N)$時間で解くことができる。
計算量:$O(MinSumBox*N)$
SRM 602 div1 easy TypoCoderDiv1
問題
ratingが2200以上をbrown coder,それ未満をciel coderと呼ぶ。
初期レート$X(0≦X≦2199)$と$N(≦50)$個のコンテストのrating変化$D(i)(≦10^9)$が与えられる。これらに符号を割り当て、レートの変化を行う。
2200以上である状態が連続しないとしたとき、最大何回coderの名称を変化させられるか?
解説
最後までどうするのが最適化わからないので、DPで解きたい。が、愚直なdpを考えると、
$dp(t,i):=t$回目でレートが$i$になるときの変化の最大値となり、$i$の空間が10^9となってしまう。
ここで、2200以上が2回以上連続しないという制約を考えると、現在のratingが2200以上のものがそれ以上になるときは遷移しなくても良いということがわかり、2200以上はかなり疎であることがわかる。
したがってそのような遷移をmapの上で書けば良い。
計算量:$O(Rating*NlogRating)$ (logはとれる)
SRM 603 div1 easy MaxMinTreeGame
問題
$N(≦50)$頂点の木が与えられ、頂点$i$には値$cost(i)$が割り振られている。
2人で枝をカットし、グラフの片方を残すゲームを行う。
先手は得点を最大化、後手は最小化する時、最大何点得ることができるか?
解説
これ気づくと楽しい。
木の中央にMaxがあるとする。先手がどのように木をカットしても残ったグラフの端について、最小な頂点のみを残してカットすればMaxでない値をゲームの得点にできる。
したがってMaxをとることはできず、先手も1個だけ残しておくのが最適になる。
したがって最適な行動をすると木の葉の値の最大値しかゲームの得点にすることができない。
計算量:$O(N)$
SRM 604 div1 easy PowerOfThree
問題
それぞれの$k$に対してxかyのどちらかに$±3^k$の移動のみで $(k=0,1,2,…)$
$(0,0)$から$(x,y) (-10^9≦x,y≦10^9)$に移動できるか?
解説
まず対称性から絶対値のみを考えても問題ない。
どちらかに$±1$が加算され、どちらかに$±3$が加算され…を考えると、値の下から行動を決めていけば良いことになる。
これは3の倍数で下の値が(0,[1or2])or([1or2],0)のとき正しい動きが可能と言える。
1のときは加算、2のときは減算に対応する。
$-3^k$の加算は、$3^{k+1}-3^k$みたいに見れば良い。
値を$\frac{1}{3}$すると問題のサイズも$\frac{1}{3}$になる。この繰り返しで矛盾を見れば判定ができる。
計算量:$O(log \, max(x,y))$
SRM 605 div1 easy AlienAndHamburgers
問題
$N(≦50)$個のハンバーガーに$type(i)(≦10^2),taste(i)(-10^5≦taste(i)≦10^5)$が割り振られている。
部分集合$S$におけるハンバーガーの嬉しさを(Sのtypeの種類数)*($\sum _S taste$)とする。
嬉しさの最大値は?
解説
$taste$で降順ソートする。
1つづつハンバーガーを集合に加えていった時、$taste>=0$のときは常に正。
また、$taste<0$であっても種類数が増えたときは、多少$\sum taste$が減少するが種類数の増加によって最大値を更新できる可能性がある。
降順で無い順番で最大値を得ることができたとして、降順に並べ替えた方が$\sum state$は大きいはずなのでこれで正しい。
計算量:$O(NlogN)$