8/8 束の間の夏休み
8/3で無事に春学期の期末試験を全て終えて夏休みに突入した. しばらくは休養がてらアニメ見たりして過ごしてた. 昨日から大学の夏期集中講座でまた学校に来ている. なんだかオープンキャンパスで高校生がいっぱいいたり, 何かのイベントで小学生がいっぱいいたりして普段とはかなり違う雰囲気.
- B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder [解答]
スライムがN個あってそれぞれの大きさA[i]が与えられている. スライムは自分の大きさの2倍以下の大きさのスラムを吸収してその分大きくなることができる. こうしてスライムが吸収を繰り返して最後に残るスライムが1個になる時, 最後に残るスライムは何通り考えられるかという問題.
とりあえず, 大きさの昇順にソートして考えてみる. 昇順に並んでいれば, i番目のスライムは1からi - 1番目までのスライムを吸収することができる. i番目のスライムがそれら全てを吸収すると大きさは, A[1]からA[i]までの和sumとなる. この時A[i + 1] <= sum * 2であればi番目のスライムがi + 1番目のスライムを吸収することができる. A[i + 1] > sum * 2であれば, どう足掻いてもi番目のスライムは全てのスライムを吸収することはできない. よって, A[i + 1] > sum * 2となる最大のiを探せば, 答えはN - iとなる. そのようなiが存在しない場合は答えはNとなる.
実際の実装では降順にソートして, A[i] > sum(A, A + i - 1)となったところでループを抜けるって感じにしてます. -
B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder [解答]
光が2個めの反射点に辿りついた直後, 残っている正三角形の領域は平行四辺形になっていることに注目すると考えやすい. このあと何度か光が反射すると再び平行四辺形ができる. この時, 何回光が反射すると次の平行四辺形になるかは二つの辺の長さから計算できる. また, 次の平行四辺形の辺の長さも同様に計算できる. 具体的には辺の長い方をa, 短い方をbとするとa = b, b = a % bになる. これを見てわかる通り, 辺の長さはlogで減っていく. イメージとしてはユークリッドの互除法みたいな感じ. これをbが0になるまで繰り返す.
