SRM 616 div1 easy WakingUp
問題
アラームが設定されている。
時刻$start(i)(≦10)$から周期$period(i)(≦10)$で強さ$volume(i)(≦10^3)$の音量がなる。
時刻0における睡眠度を$S$として、1秒経過すると睡眠度が$D(≦10^2)$増加し、アラームの音量の総和だけ減少する。
$S≦0$となると起床する。
いつか起床できるような最大の$S$を求めよ。
もしどのような値でも起床可能なら、-1を出力せよ。
解説
周期の最大値が$2520$なのでこれでシミュレーションする。 2周期みたとき、最小値が減少しているならば必ず起きれる。 もしそうでないなら、最小値の値が最大の$S$に対応する。
計算量:$O(LCM(period))$
SRM 617 div1 easy MyLongCake
問題
長方形のケーキを切る。
友達の人数が$n(≦10^5)$以外の$n$の約数であったことだけは覚えている。
どの人数が来てもケーキを等量渡せるような切り方をしたとき、最小の分割されたケーキの数は?
解説
約数の部分に印をつけていく。
重複する部分は1度だけ切れば良いとしてみると、約数の切れ目で切れば最小の個数にできる。(これは必要なので)
計算量:$O(NlogN)$
SRM 618 div1 easy Family
問題
ある子ども$i$の親が$p1(i),p2(i)$であるという家族関係が与えられる。
このとき、親の性別が2種類としたときにありうる家族関係が存在するかを判定せよ。
(辺の数)$≦10^2$
解説
ある子の親について二部グラフである必要があり、これを満たせば存在する。
連結でないものも存在するので注意。
計算量:$O(|P1|)$
SRM 619 div1 easy SplitStoneGame
問題
2人でゲームを行う。1より大きいタイルの山を選択し、これを空でない2つの山に分け、他の山に別々に配置する。
これを行えなくなった方の負けとする。
(山の数)$≦50$,(各タイルの枚数)$≦50$
解説
各手順で山の数自体は1ずつ減少し、残りが2個になると手番が回ってきた方の負けである。
また、1より大きい山が1つでも存在すればゲームは山が2個になるまで続けることができるので、勝敗は以下のようになる。
3個以上の山で、山の数が奇数で、1より大きい山が1つでも存在するとき、先手の勝ち
そうでないなら負け
タイルの枚数を$N$として、
計算量:$O(N)$
SRM 620 div1 easy PairGame
問題
数$(x,y)$があるとき、$(x+y,y)$or$(x,y+x)$へ進めることができる。
最終的に$(a,b)$と$(c,d)$に到達可能な$(x,y)$のうち、$x+y$の値が最大になるものは?
$(a,b,c,d≦10^6)$
解説
$(a,b)$と$(c,d)$がどのように構成されてきたかは一意に定まる。
数を減らしながら作成されるこれらの2つの経路のうち、一致するものの最大値を直接見れば良い。
計算量:$O(max(a,b,c,d))$