AtCoderで水色になったので有用そうなことを書く

2022年3月くらいに「緑コーダくらいやってみるか」と始めて、惰性で続けて水色コーダになりました。そこまでに考えたことを書いときます。書かないと忘れるからね。

前提（私のこと）

（AtCoderのノウハウを読むだけなら、ここはスキップできます）

書き手の背景とやってた目的

私はアラフォー。Engineering Managerといった管理職のロールが多いです。

普段仕事でプログラムをあまり書かないんですが、逆にプログラミングの理解度を底上げする意義があるなぁ、と考えました。データサイエンティストと計算量の会話をすることもあります。

コンピュータ科学系の学部・大学院にいました。ですんで自分を「素人」と言うのは無理があります。といいつつ、例えばICPCの強い人が同期にいたのに在学時から最近に至るまで自分自身では競プロはほとんどやってませんでした。なんでかねー。

あるときコーディング試験で、いわゆる「Union-Find」を要する問題が出まして、解法に気づいても当時はアルゴリズムをその場で書き下す準備がなかったもので、正答出来ませんでした。今でもUnion-Findは若干トラウマです。ちなみにその問題を出した方、私を見てギャグで出してきた感じが若干否めず。普通にコーディング面接は通りました。だったら聞いてくるなよ。

というわけでこの領域にはいつも引け目やら苦手意識やらが先行する感じだったのでしたのですが、最近はプログラミングコンテストも以前より取り組みやすくなりましたし、実務でもコーディングを要求する選考も国内で一般的になってますんで、せっかくなので少しやっておこうかと思い立った次第です。

もともとRustを勉強するつもりではじめたんですが、気づいたら問題は全部Pythonで解いてます。Rustは別途がんばるます……

競プロ周りの書き手の変遷

今回意識したのはAtCoderの中でもABCのみです。「幅広い経験を積む」みたいな意味では他のサイトも調べる方がベターだとは思いつつ、かなり無視気味です

最初の頃はABCでもC問題で躓いてました。言い換えると、開始時点でもA、B問題はたいてい難なく通せるレベルからスタートしてます（幾何の公式を覚えてないことが多く、問われると弱いです）。上のグラフの変遷でもわかります。「惰性」書きましたが、もともとの目標は「取れそうだし、とっとと緑取る」だったのです。

スキルアップのために

（ここからが本題です）

世の中にすでに多くの学習コンテンツがありますので、あんまり基本的なことは書かなくていいかなー……ということで、非常に偏った意見だけを書きます。

最近のABCで高度なアルゴリズムの重要性は高くない

「高度な」の定義〜。ダイクストラくらいは出ます。

例えばセグ木、もしくはさらに高度に遅延セグ木みたいの、ABCのE問題くらいだとめったに（全く？）お目にかからない印象です。2-SATも、C++のACLに入っている一方で、正直本番で一度も見てないです。実戦期間がたかだか半年強だから、というのもあると思います。後半（F・G・Ex）の事情もわかりません。

高度なアルゴリズムはその場で考える類のものではなく「知っているか知らないか」で勝負がつく、という側面はあります。レア感あるアルゴリズムで二分するのをABC的には良しとしないのかもしれません。私が大学時代に教わったような、定番寄りの基本的なアルゴリズムをきちんと書ける方が効きます（私が学んだのはもう干支1周以上昔だけど……）

「定番寄り」も人によって感じが違うので、たとえば私が思いつく範囲だと

• DP（動的計画法）
• 二分探索、優先度キューみたいに標準ライブラリに入ってそうなやつ
• 累積和
• 一時期は数列の和の公式など、高校数学の各種公式系統
• ダイクストラ、せいぜいワーシャルフロイド
• たまにUnion-Find
• など

ユーザ解説等で無理やり高度なやつ（例えば「wavelet matrixでも解ける」）、といったものはありますが、目標を考えると無視して良いです

逆に言うと、私は「高度」と言えるアルゴリズムを今でもまともに扱えません。それで「水色コーダ」なわけですから 、ある意味では安心しませんかね……？しないか。

「解ける」を「確実に早く解ける」にするのが効く

大量の（高度な）アルゴリズムを覚えておく必要まではない、とすると、何で差がつくのか。確実さ・スピードです。

AtCoder Replay (β) 見ると、過去のコンテストの順位の変遷を後から追いかけられます。順位の変遷からは「近い順位の人と比べて、自分がどういう傾向で順位を上げ下げしているか」を見ることが出来ます。

図で順位が早く下がっているという場合「その順位帯の他の人より、自分が明らかに弱い」と考えて良いと思います（400位あたりで「弱い」とか言えるレートじゃないんすけど、弱いのは事実！）

上図の私のケースを例にとります。上記の図において、私の順位にもっとも露骨にマイナスに効いているのは、多分ですが「D問題を解いている30:00あたりで一気に400人に抜かれている」といったことです。

言い方を変えると、（Aから順番に解く人が多数派であるとして）「D問題は20分で解けるのが望ましかった」という判定になるはずです。……ちなみにこの回、私のABC経験では過去最高の出来だったので、「満点！」と思えばそれはそれで満足なんですが、あくまで上を目指す場合は「弱いところ」を冷静に分析するのが良いんです！

そういうことを考えながらコンテスト中に解いた過程を思い返すと、このD問題、なるほど、解法こそ私も思いついたんですが、入力する段階で個人の体感の上でも「だいぶ手間取った」印象があったのでした……。具体的には、アルゴリズム的には確信はありつつ、与えられたテスト入力に対しては出力が一致せず、細かな修正を何度もした後で手元のテスト入力でOK、そのあと提出して即ACした感覚があります（ここでWA絡むとまた悲劇がありますが、このときはそういうことはなかったのでした。奇跡？）

結局、上図を元にした振り返りの結論としては「頭に描いていたものをコードに落とす能力が同じ順位帯の人より低かった」となるはず。この振り返り結果は練習にも活かすべきです。

今回の成績でもすでに異様に成績が良いのでして（水色パフォ、３００位代。それ以前の最高は８００位くらいです）、（水色下位である）私の中では圧倒的に過去最高のできなんですが、もし２０分早かったら黄パフォです（F問題が壁で上位者も解けてませんでした）。それは、すげぇ。

私の前掲のコンテストの結果についてはこうなった、というだけですが、こういう分析は緑圏くらいまでであれば一人ずつ毎回必ず見いだせる気がします。

あと、あくまで「ABCの水色」くらいだと、がんばって蟻本を読むよりは、累積和を10秒で書けるようにしたり、よくあるタイプのDP問題での勝率を上げたり、時間をかければ解けると思える問題を「あと10分」早く確実に（ペナルティ受けずに）解けるようにしとくほうが「効く」印象があります。

同じくらいのスキル感の人と比べて手間取ってしまう瞬間は誰にでもあると思います。あるのは仕方ないとして、頻度面でそういうケースが少ないほうが、当然レートは伸びやすいです。問題を解くたびに、きちんと「何が手間取らせる要因か」は細かめに理解しとくと、緑〜水色では非常に効果的と思います。

※ 難しいことを書いている印象があるかも、という方に一応説明しとくと、私、dif200くらいで苦労する方にアドバイスする立場でもあります。躓く要因は全然違いますが、得意不得意はそのあたりでももう出ていて、「再帰が厳しそうだ」「ifに乗せる条件文がうまく整頓されてない」など、見いだせる改善点はやはりたくさんあります。今回の「手間取った」とも違いますけど、上を目指せない要因分析はその段階でも可能っちゃぁ可能だという印象あります。ただ、課題を自分で見いだせない可能性は確かにありますね。他の方に助けを求めましょう

短期と長期で目標を（ゆるく）セットしとく

以下のような問題へ取り組むアプローチは多分有効と思います。

• 短期目線では、「簡単」と思える問題をより早く確実に解けるようにする
• 長期目線では、新しいアルゴリズムや解法をじっくり習得する

社会人で熱心に取り組む場合、実態としてもこうなるのかなと思います。平日は灰〜茶、休日に緑〜水色、みたいなリズムですかね

AtCoder Problemsは基本的には毎日見てました（お布施しましたよ！）

上図は曜日ごとに解いた最高難易度のヒートマップです。一時期だいぶがんばって平日水色やっているように見えますが、実はかなり逆詐称の水色（昔の水色はかなりそういうのが多いのです）であって、意味のある「水色の練習」にはなってないのでした！色が目的化するのは良くないです……

ネット上で他の経験者がよく「精選問題」を提示してくれます。私も喜んで使いますが、こういうスキルについては、精選問題を解くだけでは十分伸びない気がします。方向性としては「長期」にむけた数ヶ月単位での仕込みと考えたほうが、（特に時間配分が難しい社会人目線だと）正しい印象があります。

上の「長期目線」で習得したアルゴリズムは、多分１〜２回は実戦では役に立たないか、下手すると「ハンマー持ってるから釘に見える」状態で、誤った適用をしてレートにマイナスに働く可能性もあります。お手製のライブラリがバグっていたりすることもありますからねー。

ちなみに「短期」「長期」で目標を厳密にする必要はあんまり感じません。特に片手間だと目標を厳密にすると負担になります。「あ、Grundy数やっとくかー」くらいの気軽さで長期も良いと思います。私の場合、遅延セグ木は半年それで放置されています。だって出ないじゃん

難易度配分や傾向は冷静に判断する

「たくさん解こう！」みたいな指針だと効率は悪くて、どのくらい「自分をいい感じにいじめられるか」で練習成果が変わってきます。練習の仕方そのものについて、例えばこういう本を読んどくと良いかもです。

上図は自分が取り組んだ問題の色の分布です。

問題数水増ししたくて（AtCoderで1000問解きました！……と言いたくなる病）、灰系の問題をやりたくなる……のですが、あまり意味がない印象。実戦で必ず2問くらいやることを考えると、練習でABCの灰を解く理由は（私の場合は）ありません。緑問に躓く確率が高かった時期に緑の問題を意識的に増やしました。基準としては「緑 100問」みたいな感じ。 AtCoder Problems だと Recommendation のおすすめに従うのでも良いと思います。

色は所詮参考程度、というのも大事。例えば昔のABCの緑や水色、いまだと茶くらいになっちゃってるのもあるんですよね。また、ARCやAGCの問題を混ぜた場合、difが全然違う方向向いてますし、典型90問やJOI系の問題に至っては全部Other、AOJは数にすら加わりません。遊びなんだから、ここは色遊びにとらわれず真剣になりましょう。

他の人の回答を見て咀嚼する。場合によっては同じスタイルで書いてみる

あまりネットでおすすめする声を聞かないのですが、間違いなく効きます。

特にPython書きで「なんか遅い」原因がわかってない段階だと、全然違うビューが見えることも多いかと。C++だとわからないんですが、Pythonだと一見些末な書き方の違いで速度が全く違ったりします。場合によってはTLEとACを分けることがあります。出題者側もPythonフレンドリーにしてくれている印象ではあって、最近の問題ではだいぶ少ない印象ではありますけどね。

ある人の提出では、コメントを丁寧に書いているだけの差分かもしれませんし、ある人の実装では sys.stdin.buffer を使っていて「なんで？」と思ったりします （input = sys.stdin.readlineする理由はなんでですかね、みたいな）。

リスト内包表記でタプルのリストをめっちゃエレガントに書くよりリスト２個の方が圧倒的に速い（TLEとACの境界をまたぐ）とか、そういうのも他の人のコードを見てこそ気づきます。「実戦の結果で知る」はそのままレートに跳ね返る副作用がありますので「Pythno遅い」系統の、ある意味ではどーでも良い話で事故るなら、本番以外のほうが絶対に良いです。

個人的な感覚だと、C++書きのネイティブ競プロerが書いた黄色〜橙問題の解説を愚直にPythonに書き下すと割とよくTLEします（ただしサンプル数一桁ｗ）。こういうの、「分かりやすい」解説だと端折っていることが多い印象があるのですが、躓いたときに原因を理解して対策を施すのが大変なので、見つけ次第やっとくのがおすすめ、かもしれません

界隈の年齢層とか運営を多少想像する

ここ1〜2ヶ月で（書いた時点での2022年9月〜10月頃とそれ以前の比較）傾向が変わったので今後減るかもしれませんが、一時期は本当に「高校数学じゃん」というのばかりで辟易した記憶があります。手元にチャート式おいて公式を引っ張り出す、みたいなね……

実際、出題者や活発に活動されている方（つまりレートが高く、また出題者サイドにいる方）の半数以上が高校生〜大学生という印象です。それはそれで「割と当然」感はある一方で「数列A」とそれを操作する「数式」だけが出てきて「和の公式・式変形で問題解けます」みたいのを見ると少しモチベーション的にイマイチ感は否めません……えーとプログラミング？

それはさておき、こういうのは避けられない側面もありますんで「出題者の心理」を解読して、メタ気味の対策を取ることを覚えておいても良いでしょう。「彼らは何者か」を理解するのは、この手の問題解決には割とよく効きます。出題者何歳だっけ……までは私はやってませんけど。

高校数学が多いようであれば、高校数学のチートシートを手元においておくべきですし、先んじて高校数学の問題を解いとく、というのも手です。実際、期待値DPくらいに手を出すと、高校数学の統計・確率知らずには先に進めないでしょう。「高度なアルゴリズム」以前のこういうところを地道に突き進めるのは当然かと思います。

逆に、この記事を書いている時点（2022-10）では、ABCのC〜D圏の問題が若干JOIの予選・本戦問題に近くなりはじめた印象を持たないこともないです（とはいえJOIをそこまで私も知っているわけではない、いや、殆ど知らない！）

高校数学の亜種ばかりだと、スポンサー目線だと微妙なはずなんですよね。私が採用担当だったら、競プロの問題はさておきクラウド前提のアーキテクチャ質問します……。なお、ここ数回のABCの問題はその点だととても納得感があります。

そういうお仕事の世知辛い話はさておき、出題者側はロボットじゃないですし、こういう継続するイベント類の座組を整えるには色々試行錯誤がつきものです。解く側も「おすすめ問題」で思考停止して愚直に問題を解くのではなくて、多少で良いので舞台裏を想像する方が、結果としては建設的な時間を過ごせるかなと思います。

追記

運営が公式に発信しているものとしては、たとえば社長のアカウントとかは自明にそうなんですが、ここ最近はトヨタとの絡みでAHC寄りに興味が寄っている気もしていてABC枠のこの記事で参考になる情報はあんまりないです（強いていうと、AHCをやる頃合い、というメタな考え方はあります）

比較的ABC・ARCあたりで情報源になるのは、ベタですがkyopro_friendsさんかなーと。公式解説もしょっちゅう書いてますし、運営内での問題設定の話も良くされてます。

これを書いている時点（2022-11）だと、特にA〜Dあたりで問題傾向・難易度をいじっている様子はあります。一方でD問題くらいで出てくるアルゴリズムの種類が増えているわけではないです。また発信内容からすると「DPの重要性ばかり盛り上がるな！」みたいな気持ちを感じ取ってます。

この憶測が正しいかどうか、今後のABCの出題から判断するしかないですが、一旦はDPを重点的にやると緑・水色コーダにはだいぶ近づくのかなと。

緑・水色観点だと、DPについて下記2つで十分すぎるほどの練習にはなるので、まずはやってみてはいかがでしょうか。私は半分も完了できてないです。参考まで、最近の「区間DP」は黄dif後半の問題でした。

バチャが効くイメージはなかったが、勉強のリズムを小刻みにするのは有効な気がした

多分、私にはバチャは早すぎるんだと思います。バチャよりは1問1問精査する方が効くイメージばかりが先行します。上のような「実戦での順位の遷移」みたいな分析から、練習課題を特定できるイメージもあまり持てませんし……

バチャはわからないんですが、ほぼ毎日ある程度意義のある問題（A問題で連続提出のコンボつなぐとかじゃなくて！）を解くのは良かった気がします。ここは本当に気分の問題。

追記文章

人気が出ると適当に追加されていきます。私も人なので

ACの「温度感」を把握する

「色」で難易度を区分して解く、のもそうですが、「ACの有無」は「自分がその問題と解法を十分理解して解いたか」としばしば連動していません。

私の具体例を。例えば以下の問題を考えてみます（つい最近私が出会った例）

黃difですので、そもそも私のレベルでそうそうさらっと解けるものではなさそうです。コンテスト本番ではここまで全然到達していません（4完で終わってます）。言い換えると、ここには成長の種が、ある！（かもしれない！）

コンテスト後、解説を読んで実装してACは出来ました。実装はそこまで難しくないので。この段階で、AtCoder Problems で「黄difの問題を解いた」という事実は残ります。

（以降、具体的な解法はあえてぼかします）

ただ、「ACもらった」とはいえ、この段階では解説に出てきた「劣モジュラ関数」については理解していません。この問題の解説では2通り考察方法が書かれているのですが、一方が劣モジュラ関数の考察を含むもの、もう一つは別の経路をたどるものです。最終的に実装はおなじになり、私は後者の理解で実装してAC出しました。さて、両方わかっている人のACとの実力差はどのくらいでしょうか。

この問題は「理解ができる解法がある」だけまだマシです。私の場合ですが、赤dif以上だと「いみが、わからん(´・ω・｀)」という解説がほとんどになります。いみがわからないのでは、本番どころか練習で何時間考えても自力で解くことは出来ないでしょう。

この問題については「理解ができない解法がある」ということは「その解法でないと解けない問題が出たら、解けない」という単純な事実を意味します。AtCoder Problems等で定期的に問題を解くとして「ACできた、今日のお勤めは終わり！」では、良い習慣にはならないです。

別の（もう少し簡単な）例

こちらは緑difです。「水色目指す〜」的なレベルだと解法は思いつくと思います。

で、このときの私の最初の解法は以下

意識的にダイクストラ法を一回だけ使って解いています（あえて工夫してます）。これは公式解説等とは異なります。

考察時、ACを取るのは所与として、疑問としては以下のようなことが思い浮かびました

• この問題でダイクストラとワーシャルフロイドで本質的に差が出るだろうか
• この問題で差が出る出ないに関係なく、他の問題でダイクストラ法を複数回回すのではダメなケースはあるのだろうか。それはどういうときか

当然「よくある疑問」のはずでして、調べてみればすぐに解説を書かれている方がいます（解説中で上の問題も言及されてますね）

全ての問題について、最初にAC取る段階でありとあらゆる分析をする必要まではないとは思います。疲れちゃうからね。

ただ、練習時に「単にAC取ってその問題を忘れてしまう」のと「ACとTLE・WAの境界を探ってみる」のとでは、練習の（解いた問題数に対する）品質は著しく違う、とは言えるかと思います。余力があるときには、特に練習時にはあえて思いつく限りの迂回をしておく、というのも良いんじゃないかなと思います。

「たくさん問題を解くのとどちらが良いか」は難しい話で、それぞれの人の状況次第と思います。一つ言えるのは、「たくさん解くようになると、案外サラッと解いた問題は忘れている」ということ。私の好みでもあるんですが「解けた」だけでなくて「なぜ解けたか（また、どういう状況だと実戦で解けないことが起き得るか）」も考えておくと、記憶の定着と応用力には良い方向で差がついていくのかな、と思います。

Pythonだと、O(N)解法でもNが10^6の桁数で指定されていると定数オーダーでTLEが発生して困ってしまう、ということがあったりします。O(N^2)でNが10^3のケースのほうが最近のAtCoderだと多いかもです。練習のときにあえてハマって置くと、Pythonのどういう実装が相対的に高速か・低速かを具体的に理解できるようになるので、トータルでの競プロ力は多少は上がるかなとも思います。まぁこれについてはC++使えばいいってのはありますけどね

他の人の解法と比べる

（書いたあとで気づいたんだけど上にも同じ趣旨の文章あったわ……より具体的な例に出会ったのでこちらも残しときます）

練習中には「他の人の解法と自分の解法でスピードが段違いの場合、その実装を見る」ということを良くします。自分の書き方のスタイルに寄せたときに同じスピード感になるのか、といったところも見るために、自分のスタイルに多少調整して実行（提出）してみる、ということもしょっちゅうやります。

解けたと思って嘘解法、もしくは嘘とは言わないけど非効率寄りの実装になっていたり、また特にPythonだと、アルゴリズム以外のPythonやpypy3固有の事情でスピードが段違いになることがあります（不用意にタプルを使ったりすると定数の部分でめっちゃ遅くなったりするんですよ）

ですので「どういうときに速度が変わるか」「自分の書き方ではどこが定数部分で遅くなりやすいか」についての「センス」を磨いておくと、微妙なところで効きます……効くように思います。

ほぼ水色difの以下の問題を考えてみます

解法はわかったんですが、とにかくTLEが出る出る……。最終的に以下でACですが

実行時間: 2929 ms

制限時間３秒に対してこれは……絶対にもっと良い書き方があるやつです。

私の中ではまずは３つ思いつきました。

• どこかでbisect化できる（が、気づかなかった）
• どこかで非常に効果の高い枝刈り的な操作ができる（が、気づかなかった）
• 妙に遅い定数コストの操作がある（が、気づかなかった）

というわけで公式解説の実装を見つつ、実際に自分の実装とスピードを比べてみます

実行時間: 1466 ms

速度が倍違う……だと……ショックだ(´・ω・｀)

結論としては、たぶんですが、私はワーシャルフロイドの心を理解してなかった ということのようでした（具体的な説明は飛ばします）。似ているようで、アルゴリズムの細部が全然違うようです。というわけで「３つ思いついた」どれとも違っていて「アルゴリズムが十分適切ではなかった」でした。……あれ、それ普通にまずいやつだよね。しょぼーん

しょぼーん……はさておき、こういうときはきちんと差を読み取ることはやっといたほうが良いように感じます。思いつく範囲で私なりに解釈すると

• 私の実装はワーシャルフロイド「ではない」。３重ループの内側が圧倒的に非効率（これが致命傷）
• sys.stdin.buffer は、まぁ分かる（私も使いました）
• 「64ビット範囲でほぼ無限と言える値」の扱いがエレガント
• zip(ABC, ABC, ABC) ……なるほど？スピードと言うよりはここの計算量どうでも良いからつきつめてない感じがするな……

アルゴリズム的には１番目が全てです（心を理解してなかった）。ただ他方で、些末なところでの差分は理解できる範囲では理解しときたいかなと思ったりはします。手を抜くべきところは手を抜いて、定数速度アップよりは実戦でタイプしやすくバグが発生しづらい実装のほうが良いんですよね（競プロだもん）。まぁあんまり突き詰めると、またもや「Pythonやめたら？」になりますが。

※ なお、こういうコードを提出してみるとき（自力でない他者のコードや解説をコピーしている場合など）、私は良く main_ref() という名前で実装が自分のものではないことがわかるようにしてます。自力実装じゃないことを将来の自分が見ても分かるようにですね。可能な限り参考先も残しときます。

おまけ

• 最初のタイトル「振り返る」になってたんですが明らかにスキルアップ記事です。そっちにタイトルを変更しました
• 「追記文章」を追加しました