AtCoder黄色になった
注: この記事のPythonはPyPyを含む
黄色になった
やっと黄色になれました!長かった… pic.twitter.com/TQfGqMNre9
— Lgeu(るぎう) (@lgeuwce) June 22, 2019
年が変わる前に黄色になりたい → 無理だわ。AtCoder始めて1年経つ前に黄色になりたい → 無理だったわ。何が何でも黄色になりたい → なったわ。
黄色になるまでにやったこと
精進
C++はunratedだった平成ABCでしか使ってない
初見で解けなかった問題はACしないようにしてる(これは多分良くないが)ので少なめに出てると思う
知識
やった
青のときとの差分で(青のときの記事は今見ると微妙なので貼らないけど)
やったけど使えてない
やってない
- 最小費用流
- 遅延評価セグメント木
- プリム法
- Rolling Hash
- Trie木
- Suffix Array
- 行列(ABCで出たけど)
- 高速フーリエ変換(FFT)
- kD木
- 幾何
- 永続データ構造
ポエム(Python競プロについて)
賛否両論ありそう
Pythonの実行速度
AtCoderにはPyPyがあるので、その辺のスクリプト言語とは話が違う
このおかげで、保証されていないとはいえ、実際のところratedなコンテストではPythonで通せない問題は0に近い(黄coderが解かないような高難易度の問題は知らないが)
まあ定数倍で厳しい気持ちになることもあるけど、他の人の提出を見ると「頭悪い実装してた…」ってなるので…
「C#が遅いせいで落ちたー><」ってなることもたまにあるけど、単純に書き方が悪いことが多いので、実際はそんなに落ちないイメージ。
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年6月10日
Pythonもだいたいこれ
Pythonの利点
配列Aをもとのindexを保持したままソートしたい
C++の場合は
V<pair<ll, ll>> B; rep(i, A.size()) B.emplace_back(A[i], i); sort(B.begin(), B.end());
普通だな!
pythonなら
B = sorted(zip(A, range(len(A))))
楽~~~~~~~神~~~~~~~~~(実行速度を気にするならB = sorted(enumerate(A), key=itemgetter(1))
としたほうがいいかもしれない)
コードが短く書けると間違いにくく・速く実装できるし、デバッグもしやすくなって、
これはかなり大きな利点だと思う
あとitertoolsのおかげで再帰を書く機会が大きく減るのが嬉しい
再帰は天才過ぎて頭がバグるのでitertoolsがあると天才を無駄遣いしなくて良くなる
next_permutationで解けちゃうよ的問題、C++とかPythonが有利過ぎるとは思うんだけれども、それでも「順列を全て生成する」というのはやっぱり基本操作として出来てほしいなぁ、と思うので、やっぱりちょこちょこと出していきたい問題ではある
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) May 12, 2014
itertools知る前は自力で書いてたので許して
結局Python競プロってどうなの
2019年6月現在Pythonで橙以上が存在しないので、Pythonが過小評価されている印象がある
これのせいで黄色が限界とかいう説まであるが、Pythonで黄色の人がC++使い始めたら途端に赤になるなんてことは有り得ない
少なくともAtCoderにおいては、自分はPythonの実行速度で悩むより頭の回転速度で悩むことがずっと多い
Pythonは実装が簡単に済むので余計なことに頭のリソースを割かずに済み、このレート帯ではC++に比べて不利ということはないと思う(似たことは他の人にも言及されている:
titiaのノート: AtCoderで青になるまで)
頭の回転が速い人ならPythonでももっと上の色に十分到達できるはず
黄色しかいないのは確かですが、2色ダウンするほどのハンデではないと思うので、単純に使い手が別言語に変えちゃうのが、高レートの人がいない最大の理由ですね><
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年3月9日
(どちらかというとPython競プロを長い期間続けている人が少ないことが原因な気がする)
Python競プロはまだ発展途上だと思っている
去年の段階ではPythonサブウエポン無しで黄色の人は3人程度(iehnさん、yaketake08さん、ukikagiさん)しかいなかったが、半年で4人増えた(hoxoshさん、ikatakosさん、maspyさん、自分)
http://atcoder-circles.com/circles/pythonista
Python橙coderが出るのも時間の問題だと思う