AtCoder Beginner Contest 125
Beginner Contest 125 まではA~Dまでの4問題だったようだ。 6問題ある前提で、D問題まで確実に解けて、E問題を半分ぐらい。と考えていたが、6問になったのは意外と最近なことがわかってしまった。
これからどうやって練習していこうかちょっと迷うが、とりあえず今回はBとC問題を解いてみて難易度を確認する。
B問題
思ったより簡単だった、6問ある場合のBとC問題の間でB寄り。ぐらいの難易度だった。 一発AC
C問題
最初に思った解法だとTLEだったので、もう少し計算量を減らすようにしたらACだった。 O(N)を意識できるようになってきた感じがする。
大体最初に思いつく解法はO(N2)な事が多くて、そこからどう計算量を減らせるかなーって考えることが多い。
ちなみにこの問題の解説を読んだけど何を言っているのかわからなくて難しかった。
自分は解法はこう。 1. 与えられたAのなかで2番目に小さい数字を取り出す 1. その数字でAの要素の中で割り切れない数字が1つ以下になるかどうか確かめる。 1. 1つ以下になればその数字が答え。2つ以上あればそこから1減らした値でまた(2)を行う。
1つだけ数字を変えることができるので、1つ割り切れないものがあってもその数字を変えれば良いという考え。 最初に一番小さいものではなくて、小さいものから2番目を取っているのは一番小さい数字を変更する可能性があるため。
感想
家に帰ってきた時間が遅くて、時間的にD問題を解く時間がなかったけど、30分でBとCが解けたので良かったと思う。 と書いたところで、このコンテストの順位を見に行ったのだけど、40分でA~Cを解いている人は水色かそれ以下のランキングの人だった。 青色を取るにはこのコンテストでD問題まで解かないといけないらしい。
次回はこの問題のD問題を解いてみようと思う。
AtCoder Beginner Contest 126
C問題
問題文読んでそのまま書いたらACだった
D問題
問題文読んでそのまま書いたらTLEだった。
親の頂点からの距離が偶数か奇数で子の頂点の色が決まることはわかったが、親から順番に子を辿っていって色判定しているとTLEになる。
原因は辺の情報を[1, 2] のようなリストのまま持っていて、親が決まったと時に、子を探すのにリストの1,2つめの要素を両方見ていかないと行けなくて、根から頂点を辿っていくときの効率が悪かった。
children_of = [[] for _ in range(N)] children_of[1].append(2) children_of[2].append(1)
のように、双方向で辺の情報を持っておいて、ある頂点につながっている頂点をO(1)で出せる状態にしたらACした。
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 英会話 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)
