ABC408の感想戦
目次
AtCoder Beginners contes 408 に参加して、今回は A と B の 2 問しか回答できなかった。ただ C 問題で imos 法という頭の良いアルゴリズムを解説で知れたので、後日復習する。
ソースコードはGitHubを参照
A - Timeout
一定時間刺激がないと寝てしまうという人がいて、その人に起こす刺激を与えた時間の数列が与えられる。それで、最後まで起きていたか、途中で寝てしまったかを答える問題。
- 前回刺激を与えた時間を覚えておいて、刺激時間との差分が寝てしまうまでの時間を超えているか調べる。
- 一度寝たら起きないので、寝てしまうまでの時間を超えていたら、そこで結果を表示して終了できる。
B - Compression
重複を含む数列が与えられるので、数列を小さい順に並べる問題。ただし重複は省いて答える。
- Python の
Set型は、重複を許さない（無視する）ので、ソートしてから重複を除くよりは、最初に重複を除いてしまったほうが簡単。 List型を変換するのではなく、直接Set型で受ける。- Python のソートには、関数の
sorted()とメソッドのsort()があることに注意。sorted()は、引数をソートした結果のList型を返す。今回sort()を使うと、Set型をList型に変換した後でsort()を使う必要がある。 join()の引数は、文字列の List が必要。
n = int(input())
a = set(map(int, input().split()))
sorted_a = sorted(a)
print(len(sorted_a))
print(" ".join(map(str, sorted_a)))C - Not All Covered
N 枚の壁がって、砲台毎に守る壁の範囲が与えられる。そして、もっとも守りが薄い壁を見つけて、突破するために破壊が必要な砲台の数を答える問題。
- 壁を表す配列を考えて、守る範囲が与えられるたびに各壁の防御数を更新していくと、予想通り制限時間をオーバーしてしまった。
- 壁を 1 枚づつではなく範囲として考えて、分割して考えたらと思ったが実装が時間内に終わらなかった。
- 解説をちらっと見たら、imos 法（いもす法）というアルゴリズムを使うと驚くほど単純なコードになるらしい。
この imos 法というアルゴリズムは、よく出てくるアルゴリズムらしいので、自分で手を動かして実装してみる。