しょ〜うぃん広場

おもにTech系なブログ、ときどき個人的なブログ

AtCoder Beginner Contest 137

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

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

C問題

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

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

D問題

この考え方だとO(N2)になるなーどうするんだろう…って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 をまた掛けると、最大値が取り出せる。

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

AtCoderを始めてみる

DMM英会話は56日目で終わってしまった。 はじめの頃は成長を感じていたのだけど、50日ぐらいやると大体慣れてきてボトルネックが語彙力になってきた。 これ以上DMM英会話続けてもコスパ悪いなー、単語帳やるか〜って思っている間に英語学習のモチベーションが下がって英語勉強は終焉を迎えた。

そのあとは進捗50%ぐらいで半年ぐらい放置されていた Switch のゼルダをクリアしたり、Bloons TD 6 というぼくが中学生ぐらいのときに始まったシリーズのタワーディフェンスゲームをやったり、Switch で FF XII THE ZODIAC AGE をやったりしていた。

ゲームも同じジャンルをやっていると飽きてしまうので、アクションRPG(?)からTDからRPGからいろいろやる。 あとは Automachef っていう食品工場を自動化するゲームもちょっとやった。Factorio に1000時間近く溶かした自分なら楽しめるかと思ったけど、操作性が良くなくて途中で飽きた。

先週ふとメールボックスをみたらAtCoderの大会開催メールが来ていることに気づいて、久しぶりにやるかーと思って2年振りぐらいに挑戦してみたら意外と面白かったので、AtCoderちょっと力入れてやってみるか!という気持ちになっている。 これもまたゆっくりやっているとすぐに飽きてしまうので、10月末までの70日ぐらいで青色(上位5~6%ぐらい)に到達することを目標に短期決戦でやっていこうと思う。

ざっと見た感じBeginnerコンテストのD問題は確実に解答、E問題は半分ぐらいの確率で解ければ青色にギリギリ入れるラインのように見えるので、それを目標にC~E問題を中心に解いていく。 現状はC問題はほぼ確実に解けて、Dはう〜んできそうだけどできない。という感じ。

DMMのときみたいに、解いた問題をここに垂れ流していこうと思う。 過去のBeginnerコンテストのC~E問題が中心だと思うけど。

DMM 英会話 56日目

Teacher: Shiloh

Today I attended to the wedding party of my friend of high school. I feels very happy to see their ceremony. His wife speeches for appreciation of her parents, and tears are dropped to my face. Recently I easily cry when I hear something related to parents' and children's love. My friend looks very masculine when he speaks that from this time I always be with you and protect you.

Today is the best day as the first time of Golden Week.

DMM 英会話 55日目

Teacher: JanetT

This is 6th time to get her lesson. When I talk to her, I can speak English fluently. It may because when I cannot remind the words I want to say, she tells me that. Other teacher wait me until I finished to speak completely. I prefer former way; correcting in real time.

DMM 英会話 54日目

Teacher: Chrissofia

Recently I cannot feel the improvement of my speaking skills. I know I need to study English more except for DMM, for example remembering new vocabulary. My colleague recommends me the book "どんどん話すための 瞬間英作文トレーニング". It may be better to read the book and use DMM alternately every another day. (There's no plan to do both, haha)

DMM 英会話 53日目

Teacher: Genie

Today's topic is "burnout". Recently not so often, but I sometimes feel burnout. The article said that the person who likely to be burnout is, people who is perfectionist, people who don't ask for help and people with unhealthy life. Except for last one, these are corresponded to me. I just realized why I could often burnout. This article is very valuable for me. Though I may not change my style, realizing the causes would make me less stress.

DMM 英会話 52日目

Teacher: Mileza

Today, we talk about our human being ancestor. There is some scientific difficult words like Homo Floresiensis, australopithecines. Especially australopithecines is learned as "アウストラロピテクス" Japanese sound, so it's difficult to speak correct sound.

By the way, I couldn't take a lesson yesterday. 30 minutes before starting lesson, teacher suddenly canceled.