SRM616 620 Div1easy

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))$

Submission

SRM 617 div1 easy MyLongCake

問題

長方形のケーキを切る。
友達の人数が$n(≦10^5)$以外の$n$の約数であったことだけは覚えている。
どの人数が来てもケーキを等量渡せるような切り方をしたとき、最小の分割されたケーキの数は?

解説

約数の部分に印をつけていく。
重複する部分は1度だけ切れば良いとしてみると、約数の切れ目で切れば最小の個数にできる。(これは必要なので)

計算量:$O(NlogN)$

Submission

SRM 618 div1 easy Family

問題

ある子ども$i$の親が$p1(i),p2(i)$であるという家族関係が与えられる。
このとき、親の性別が2種類としたときにありうる家族関係が存在するかを判定せよ。
(辺の数)$≦10^2$

解説

ある子の親について二部グラフである必要があり、これを満たせば存在する。
連結でないものも存在するので注意。

計算量:$O(|P1|)$

Submission

SRM 619 div1 easy SplitStoneGame

問題

2人でゲームを行う。1より大きいタイルの山を選択し、これを空でない2つの山に分け、他の山に別々に配置する。
これを行えなくなった方の負けとする。
(山の数)$≦50$,(各タイルの枚数)$≦50$

解説

各手順で山の数自体は1ずつ減少し、残りが2個になると手番が回ってきた方の負けである。
また、1より大きい山が1つでも存在すればゲームは山が2個になるまで続けることができるので、勝敗は以下のようになる。

3個以上の山で、山の数が奇数で、1より大きい山が1つでも存在するとき、先手の勝ち
そうでないなら負け

タイルの枚数を$N$として、
計算量:$O(N)$

Submission

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))$

Submission

Share Comments
̃Gg[͂ĂȃubN}[Nɒlj
comments powered by Disqus