AtCoder Beginner Contest 137 - しょ〜うぃん広場

今回は青色までということにしているので、C++は使わずにPython3で頑張っていこうと思う。仕事でPython書いているので一番すらすらかける。頭で考えたアルゴリズムをすいすい実装できないのがイライラしてやめたくなりそうなので、一番かける言語でやっていく。

青色に到達するまでに解かないといけない問題を見てみると、大体だれかがPython3でACを出しているのでできるはず。

C問題

愚直に書いたらTLEになった。 C問題は大体そのまま書いたらACになることが多いので、おーって思いながら書き直す。

結局AC出すまでに30分弱ぐらいかかってしまって、ちょっとこのC問題は難しかったように感じる。自力でできた。

D問題

この考え方だとO(N²)になるなーどうするんだろう…って30分ぐらい悩んでコード書く前に解答を見た。ソートして最大値を取り出すところはO(N)かかると思っていたけど、優先度キューというものを使えばO(logN)でできるらしい。

Pythonだと heapq ライブラリが提供されている。手元で実行時間比較してみた。

lst = [random.randint(1, 10000) for i in range(1000000)]

time sorted(lst)[0]
435 ms

time min(lst)
18.3 ms

time heappop(lst)  # 詰めるところは省略
26.9 µs

heapq 取り出すのめちゃくちゃ速い。僕の理解だと詰めているときにソートしているはずなので、heapqの取り出しはO(1)でできているはず。

ただ詰めるところまで時間を考えるとmin()しても同じ

In [1]: def _heap_pop():
    ...:     for i in range(1000000):
    ...:         heappush(lt, random.randint(1, 10000))
    ...:     heappop(lt)
    ...:

In [2]: time _heap_pop()
CPU times: user 1.54 s, sys: 22.8 ms, total: 1.56 s
Wall time: 1.56 s
-----------
In [3]: def _min():
    ...:     lst = [random.randint(1, 10000) for i in range(1000000)]
    ...:     min(lst)
    ...:

In [4]: time _min()
CPU times: user 1.43 s, sys: 21.5 ms, total: 1.45 s
Wall time: 1.45 s

つまり繰り返しリストから最大/最小値を取り出すときには heapq を使うとよさそう。 1回だけなら min(), max() でも変わらないようだ。

heapq のTipsとして、最大値を取り出したいときの方法がある。 heapq はpopで最小値しか取り出すことができないので、リストの中の最大値をとることはできない。最大値がほしいときには heappush する時に要素に -1 を掛けて入れて、取り出した後に -1 をまた掛けると、最大値が取り出せる。

これは他の人の解答をみて学んだのだけど、頭いいなーと思った。