[AtCoder] 橙(2400+)になりました

2019.11.04
  • AtCoder Rating History(1)
  • AtCoder Rating History(2)
  • AtCoder Charts
  • AtCoder Scores
  • AtCoder Problems(1)
  • AtCoder Problems(2)

テンプレネタですね。

各回のコンテストについては別途記事にしていますが、レーティングがキリの良いところを迎えたこのタイミングで、1度総括的な記事を書いておきます。解いた問題数や、コンテスト成績の推移については上の画像参照で。

スポンサーリンク

AtCoderを始める (2019/04) まで

数学

平均的な競プロ上級者と比べても、数学を強みに出来る寄りだと思います。

  • 大学受験数学は全て（ほぼ全て、かも）できる。
  • 大学数学科学部レベルの数学は大体理解している。
  • IMO（国際数学オリンピック）が7～8割くらい？解ける（金メダルボーダーくらい）。
    ※ 競プロとの親和性が高そうな、組み合わせ分野の問題は、その層の人の中では苦手寄り。

ゲーム

ん？ゲーム？AtCoderはネトゲですからね。

  • ぷよぷよ：プロゲーマーより下くらい（ぷよスポ switch 3000）
  • みんなで鍛える全脳トレーニング：全3くらい？で頑張ってた。
  • HOJ：これは競プロに含まれますか？一時期全1あって割と強かったと思うけど、いろいろ追い抜かれていて驚く。
  • ぷよぷよクエストアーケード：全1プレイヤとして頑張ってた。
  • BrainWars：全5～10くらい？で頑張ってた。
  • poker：ゲームでリアルマネーが増える現象は良いが、それ以外があまり面白くなくて停滞中。

→ 次にやり込むゲームとして 競プロを選択。

プログラミング

  • 15年以上前に、BASICを少し書いた。当時センター試験のプログラミングが解ける等。
  • 情報科学の専門教育を受けたことはない。割と我流。
  • C++も少し経験あり。HOJのソルバー書くために少し勉強した。
  • 流行りにのってデータ科学を始めた。python触って2年くらい。

アルゴリズム知識

  • 数学を学ぶで見聞きしたもの以外はほとんど知らなかったと思う。
  • dpって何？dijkstraって何？最小全域木って何？等、基礎的な単語もあまり聞いたことがない。

ProjectEuler

About - Project Euler
A website dedicated to the fascinating world of mathematics and programming
projecteuler.net
  • 「数学の人がプログラミング勉強するなら」ということで教わり、C++で少し進めていた。
  • 中難易度＋が全然埋められなくて300問くらいで一度停滞。

だいたい時系列

  • 2019/04：ProjectEulerを再開。
  • 4/24：AtCoderで初めて問題を解く。4/27：ABCコンテストに初参戦。
    • 当時は相場が分からなかったが、この時点での初期能力値は2000前後ということになるのではないだろうか。
    • 以降、出られるコンテストには全て出る。
  • アリ本を買う、読む。
    • 数日でざっと1周。そのあと1ヶ月くらいかけて丁寧目にもう1周。終盤の上級編はさらにもう数回。
    • これだけ出回っている教材なので、アリ本で解けないものが目立つ状態で多くの人より上に行こうというのは当然無理だと思った。
  • 4～6月：ProjectEulerを解きまくる
    • 7月頃までは、AtCoderよりもこっちをメインにやっていました。
    • 土日祝の全てはもちろん、移動時間も常にノートを開いて考えまくったり、有給とって1日中問題を解いたり。この頃が一番時間を使っていたかもしれない。
  • 5月下旬：ABC-D問題を埋める
    • 考察に数時間かかったり、バグはまりで数時間かかったり、アリ本等を調べて数時間かかったり。
  • 6月：
  • 7月：
    • 難易度3が相当きつかった。コンテスト時間内基準だと、半分ちょい解けている程度だろうか。
    • アルゴリズム知識が活用できる場面が一気に増えて急に競プロらしく（主観）なり、かなり良い勉強になったと思う。
  • 8月：
    • 8/8：ProjectEulerで最高レベル帯に到達してとても喜ぶ。少しひと段落つけて、AtCoderを頑張ろうと思う。
    • この時点で934AC。PythonのAC数ランキングの1位を10月までの目標にしてみる。
    • 8/22：上記の目標を達成してしまう。社会人にとっても夏休みがある時期ですからね。
    • 8/25：形式的べき級数記事を書いた。そこそこ拡散してもらえる。形式的べき級数談義が目に付くようになったり、そこに口を挟んだりする。 Python AC数の1位も合わせて、twitterで認知される度合いが高まる。
  • 9月：
  • 10月：
    • 速度に価値観を寄せる。
    • 難問を考える時間を減らしても良いなと思う。自作ライブラリはこの時点で0だったが、少しは用意しようと思う。
    • ABCコンテストの2周目をやり始める。昔解いた問題の再挑戦も、勉強として有効であると気づく。
    • 10/5：AGC-Dが数学問題の当たり回。他の問題も含めて上手く乗り切れて、銀パフォ。
  • 11/4：AGC040で、レーティング2411に到達（イマココ）

「Pythonで競プロ」という選択について

他言語との比較をする場合は、PythonとC++の比較を想定しています（他、知らない）。

利点（主観）

  • コード量が少ない、直感的に書きやすい。
    • ほぼ語られないが、主観というよりも客観的事実として挙げてもよいと思います。
    • 現状、自作ライブラリやマクロ定義のない0からのコーディングでも、ほぼ同パフォーマンスが出せます。 問題の考察部分の勉強を主体に出来たことが、短期実力向上に大いに役立ったと思います。
    • C++では、マクロやライブラリを整備した上でコーディングスキルを高めることで、不利を感じることを減らしているのだと思います。ので、十分な準備と修練を積んだ競プロ勢にとっては、ここの利点が薄まっているのかと思います。
  • jupyter notebook
    • インタラクティブに試行錯誤できる感じが私には馴染みました。 マークダウンやlatexもその辺に書けて快適。
    • コードブロックがあるから設計が雑でもある程度書きやすい。
    • 関数ごと、行ごとの計測も簡単。

デメリット

  • TLEに弱い件
    • 実装が下手だと、同じアルゴリズムでもしばしばTLEする。下手なPythonは下手なC++に比べて大きく不利。
    • （と言われているが、実際にはACがとれない問題はほぼない。）
    • 少なくとも私がACしているもの（AtCoder Problems 参照）の大部分は、不自然な定数倍改善をせずとも自然にACがとれる。
    • ※ AtCoder以外の事情は分かりません。Euler では使えるライブラリの幅も広く、JITコンパイル等の恩恵も受けられるため、 速度で困ることはまずありません。
  • 界隈のレベルが高くない。情報量が少ない。
    • 単純に（競プロが）強い人は少人数なので。黄で10人前後、橙は私が初めてというデータも見たことがあります（「Python勢」の定義次第で多少揺れるデータかと）。
    • 言語仕様に強い人も少ないように思います。私も全然強くないです。
    • 難問では、参考にできる他の人のコードが少ない。（黄クラスが取り組む問題では提出から既に少数、1件もないこともよくある。その層の人口が少ないので当然）。
    • 総じてC++で競プロをやるのに比べると、上質な情報に触れられる場所がかなり少ない。
    • TLE云々よりも、この要素の方が一番大きいと感じています。最初そうなのは仕方がないので、私も少しずつ良い情報を蓄積していければと。

Python勢向け

  • 界隈にはわりと言葉の強い主張も落ちていて、不安を感じることもあると思いますが、習得言語としてPythonを選択したことに対して卑屈になりすぎず、堂々と取り組みを続けて欲しいです。もちろん言語の移行も選択肢のひとつです。
  • 世の中にはPythonコードをC++コンパイルするなど、Pythonの利点を維持しながら弱点を克服する方法も充実してきています。ある程度のパフォーマンスが求められるタスクであっても、Python知識が活用できるものは少なくないと思います。なお、AtCoder環境（言語アプデ）も、Pythonのパフォーマンスを引き出しやすい方向で調整が進んでいるようです。
  • 開催されるコンテストでは、Python / PyPy でACできることは、保証されていません。そのせいACできなかったとしても、コンテストに注文をつけるのはやめましょう。Python勢が「不当な評価」を受けたわけではなく、自身の問題解決能力（使用言語も含む） が不足していただけ、能力通りの「正当な評価」を受けただけの話です。
  • そもそも自由に言語選択しているのに「Pythonだから損をした」という言及ばかりしていれば、単純に見苦しく感じますし、「AC保証のある言語(C++)を使えば」という反応が返ってくるのも当然です。
  • ただし、事実として、ほぼ全て問題は Python / PyPy でACできます。例えばこれまでの rated contest で、難易度2800以下のものは全てACできることが証明されています。ので、たいていの「Pythonだから〇〇」は、Pythonのせいではないです。単に自身の能力不足です。後ろ向きな発言ばかりせずに、前向きにスキルアップに努めましょう。自身がTLEして他にAC者が居るとき、あるいはACした場合でも実行速度が大きく劣る場合などは、スキルアップのチャンスです。
  • 【勉強になるもの】
    基本的なデータ構造の計算量や、標準ライブラリで利用できそうなものは、雑でもよいので一通り見ておくのが良いでしょう。あまり誰も使っていないものでも、便利なものが出てくる余地がまだまだあると思います。
    また、Pythonは低レベル処理は苦手で、他言語で書かれた基本的な低レベル処理を呼び出すのが得意です。低レベル処理はなるべく自作せずに、世の中にある仕組みを利用することを念頭に置く方が、言語の強みが活きると思います。現 AtCoder 環境では、標準ライブラリ以外にnumpy, scipyが利用でき、特に numpy の汎用性が高いです。
    競プロで使っている人は多くはないようですが、これらは多くのpython入門書でも扱われており、競プロ以外でも多くのタスクに利用できるため、学習する価値も高いと思います。
    • https://numpy.org/
    • https://www.scipy.org/ （競プロでよく使うのは scipy.sparse.csgraph にあるもの）
    • ※ 現AtCoder環境では、PyPy と numpy が両立しないため、numpyの恩恵とJITコンパイルの恩恵の2択を迫られる（しかもコーディング前に）ところが少し厄介です。要注意。

その他

強い言及も減ってきたようには感じていますが。

  • 「C++にすれば？」等々
    • 相手を選びましょう。マウンティングなら目障りな話で。
    • ゲームで最初に選ぶキャラみたいなものです。本人は何となく馴染んだとか、見た目が好きとかで、とりあえずそのキャラでゲームを進めてみようと思っているかもしれません。 （※ 実際、ゲームの「キャラ差」レベルの範疇かと思います。）
    • 相手を思いやってですか？ゲームの初中級者に、秒単位の最適化を競うRTA専門家が「なんで○○のキャラ使わないの？」とか言っても、興が削がれるだけでしょう？「動画勢によるありがたい講釈」レベルはなおさらで。
    • 競プロPython界隈は単純に初中級者が多いです。C++ほど文化も成熟していないですし、黄＋コーダーもほぼ居なければ、本気で橙赤＋になろうと励んでいる人も多くはないように思います。
    • 「本気で上位を目指すための相談を受けた」とかでもないのなら、 ゲーム初中級者を目にしていると思って、大人しく見守ってあげればよろしいかと。
  • 「Pythonは利点が皆無」等々
    • 世の中でのPythonでの普及を見るだけでも、中身を知らずとも、Pythonという選択に一定の合理性はあることに想像が及びませんか？
    • 総合的にC++に分があるというのは正しい気もするけれど、誇張しすぎるとただの非常識なお馬鹿発言です。言語には得意・不得意当然あります。
  • 「Pythonで橙・赤は無理・困難」等々
    • とりあえず、「橙は無理」の反証には成功しました。
    • そもそも例えば touristさんが、りんごさんが、pythonを使うと赤くなくなるほどにパフォーマンスが下がると本当に信じていますか？（多少の練習は前提で）
    • 憶測や誇張で、言語間の格差を強調するような言及はあまり望ましくないと思います。Python使用者に対して、時には現実を突きつける必要があるかもしれませんが、なるべく事実に基づいて、相手のためになるような言葉を使うようにしてあげるとよいと思います。
    • ちなみに「Pythonで橙・赤は困難」は正しい主張だと私も思います。ただこれは、任意の言語に対して「橙・赤は困難」が成立するため。例えばC++でのそれとの度合いを比べないと、言語評価の参考にはならないミスリードな主張です。

雑多なこと

黄まで・黄から先

求められるスキルレベルの違いも小さくないと思いますが、「2000」を明確な境界として、環境要因でも上を目指すのが一気に大変になります。

  • 黄まで：ABCコンテストは月3回くらい。当然ABCコンテスト以外にも参加するので、月に数十問が自身の力を評価してくれてレートが変化します。
  • 黄から先：rated 回は月2回に満たない。月に数百問を勉強しても、そこで成果を出せなければ評価が得られない。
    • ratedコンテストの半分以上はAGC。6問コンテストとはいえ、黄色最低水準付近だと、2～3完目標の戦いが多いと思います。
    • なので、月間に4～5問程度しかレーティング評価に結びつかず、黄最低水準はある意味では最も辛い時期と言えるかもしれません。AGCの3～4完が目指せるようになると、もう少し充実してくると思います。
  • このレート帯にとってコンテスト回数が昔よりも減っている、という言及を見かけます。私はここ半年のことしか知らないので、真偽は不明です。

成長がレーティングとして可視化されるまでに時間がかかるため、モチベーション管理が急激に難しくなる段階にあるのではないかと感じました。ふんばりどころですね。

知識面でも穴が減ってくる時期で、新規の知見を手に入れる労力も増えてきます。勉強しなくてもある程度の成績は出せてしまうレベルなのも、勉強・成長を止める要因となりかねません。

レーティングよりも、「過去問のAC数」「昔解けなかったものが解けた嬉しさ」「解きなおすと速く実装できた・実行時間が縮んだ」「本やブログで知らなかったものを知った」などに自身の成長を見出して、向上心を持ち続けることが大事になってくるのではないかと思います。

たくさん解くということ

  • 半年でAC数上位 20 位に来ました。無茶をした自覚はないですが、界隈では多い方のようです。
  • 他のコンテストを併用していないので、色々合わせると私より上にもっとたくさん居ます。
  • この水準で問題数をこなしている方がとても少ないのは、割と意外でした。
    • 私の場合、ここまでにだいたい ～1000時間 というオーダーではないでしょうか？
    • 他のゲームでも、スポーツでも、1000時間というのはそこまで珍しい数値ではないのではないかと思います（半年だと頑張ってる方かな？）
  • 例えば「平均的な青・水色帯のプレイヤが取り組んでいること」しかしていないと、青・水までしか到達しないのは自然なことかと思います。それより上を目指したければ、何か（競プロ外での素養 / 勉強の質・量 / 練習の質・量など）で、周囲を上回らないといけません。練習量を稼ぐのは、分かりやすい方針の 1 つではないかと思います。
  • 「虚無埋め」について
    • 当人の実力からは学ぶところのない程度に簡単な過去問を埋めることを指す、競プロ方言。
    • 本当に虚無なら超短時間で埋まるんで、埋めるかどうか考えるくらいならさっさと埋めるのでも良いと思います。物量もそれほど多くないです。

ProjectEuler

  • 速解き不要、手元環境で自由に問題に向き合える。のでそこは初心者にも安心要素。
  • そこからAtCoderへ入門したときのハードルは「手元環境ではなくAtCoder環境で答を出さないといけない」こと。
    • 入出力の形式を合わせないといけない。世の中のライブラリが何でもは使えない。
    • REなどとしか返ってこないのでデバッグが難しい。ACにならない入力ケースが正体不明。
  • 出題傾向も違うし、速解きも要らないので問われる部分はだいぶ違う。AtCoderでのレート向上目的だと遠回りな気はする。ある程度知識が飽和してきた人には新鮮で良いかも。
  • 解答のシェアは解いた人の間でってのが原則なので、解けるまで調べたり粘ったりし続けるのが苦手だときつい。
  • 競ってレーティングを上げるような「ゲーム感」が少なく、流行しないのは仕方ないと思う。

速解きについて

  • 速度差での競争には、今でも興味が薄いです。
  • しかし過去問でAGCの4問目に手がつく頃から、「速度も重要」という感覚になりました。
  • 「N完の中で上位に行く手段」というよりも、「N完の安定度を高め、またN+1完を目指す手段 」 として、速度が必要になってきます。
    • 150分3完するのであれば、 例えば 「A：20分、B：60分、C：70分」くらいかと思います。ですがこれだと少し事故ると2完です。
    • そしてここから4完を狙うとします。「A：10分、B：30分、C：40分、D：70分」みたいなペースになってきます（数値は雑ですが、ある程度納得感のある数字ではないですか？）。
    • 「N+1問目を解く」のは当然難易度も高いので、3問を4問にするには速度1.33倍では不足。3完目標と4完目標では、速度が2倍くらいは違うのではないでしょうか？
  • ある時期までは、どれだけ時間がかかっても解ければ勝ち。せいぜい、着想の鍵を復習して終わり。だったものを、どう確実に短時間でまとめられたのかの復習を意識し始めました。私の場合、「意識するだけ」でも効果があったように思います。
  • 現状認識（主観）
    • ライブラリも用意した方が良い（そんなに優先度は高くない）。
    • 考察と実装の往復を減らすのがとても大事。
      • 考察はなるべく細部まで一気に詰める。
      • 勘違いで巻き戻ったり、細部と思ってたところが大変だと大損しがち。
    • ノート上で細かい添字レベルまで含めて立式できてしまっていると実装が速い
    • 計算物を言い換えている場合などは、手計算か愚直実装でのサンプル合わせの優先度が高い

役に立ったアルゴリズム知識

  • よくこのタイプの記事で取り上げられているが、うーん。
  • いくら勉強しても、本番で役立つ要素（ratedのコンテストで、自身にとっての勝負どころに関わってくる）は月に数個程度なので、何が成果をあげるかは運です。何なら勉強したことの大部分は役に立たなかったｗ
  • 知識やテクニックを何でも取り入れていって、少しずつ打率が上がっていくことを信じる。
  • ただしその中でも、 アリ本のあらゆる場所は成績に直結する確率が高くて、間違いなく効率が良いです。過去問でも「解けなかった / 実装で詰まった → アリ本に近いのがあった → アリ本習熟度が低い自分を反省」は何度も経験して、そのたびにアリ本の完成度に驚かされます。

役に立った勉強題材

  • アリ本の全体
  • ABC コンテスト 旧 CD・新EF
  • ARC コンテスト C (E)

学ぶコンテンツ数を増やしてもいいけど、この程度の範囲をスーパー高い精度で仕上げるだけでも相当レベル高いかと思います。「答覚えてるおかげで瞬殺できる」ようにするだけでも相当なレベルかと（これは練習量で必ず達成できる → 個人的にいまの目標ラインの1つ）。

極端に変わった発想が必要なものは少なくて典型度が高め。熟考しながら進められれば十分黄コーダーあると思いますが、橙上位・赤＋と上がるにつれて、典型・常識として持てていたり、短時間で実装しきれるのものの割合が一気に高くなる印象を持っています。

  • その他、読んだもの・読んでいるもの
    • 「アルゴリズムデザイン」：読了（演習問題を除き）
    • 「Introduction to Algorithms」：半分
    • 「みんなのデータ構造」：読了 （演習問題を除き）
    • 「離散凸解析と最適化アルゴリズム」：半分
    • 「Competitive Programmer’s Handbook」：未

学術書は、流石に手法が競プロに直結する部分は少なく感じます。ただし、アルゴリズム分野における標準語が身に付いたり、基本的な議論の順序が身に付いたりするので良い感じです。最後に挙げたものは競プロが題材なので、アリ本と合わせて基礎知識をそろえる役に立ちそうです。

スポンサーリンク
タイトルとURLをコピーしました