AtCoder で伸び悩んでいる人々を見て思うところ (2025/12)

思うところがあるので書きます。

qiita.com

直近で見たのはこの記事ですが、こうした内容はあまり珍しいものではなく、むしろ比較的よく見てきたものに思えます。 改めて探そうとしてもなかなか見つからなかったのですが、見た記憶がありますというのを信じてもらうことにします。

本題

しばしば見てきた取り組み方について、「こういうのを見てきたよ」「こうした方がいいと思うよ」というのを挙げていきます。

人によって前提知識やレベル帯、主に数学への慣れなどは違うでしょうから、「こうした方がいいと言われても困る」というのもあるとは思いますが、できるところからこつこつ身につけていくといいんじゃないかなぁくらいの気持ちで書いています。

問題文の読み方

問題の内容を理解しないうちから「まず入出力例から見る」といった癖がある人はそれなりに多くいると思います。 入出力例（や説明文）を見てなんとなく「こういうことだろう」と予想してから問題文を読むのは、思い込みや誤読の原因になりがちですし、あまりよくないだろうと思っています。

とはいえ AtCoder の問題文は数学数学しすぎな感があり、たとえばあまり数学に慣れていないプログラマが「競技プログラミングというものがあるらしい、やってみよ〜」と思い立って読むとぎょっとしそうとは思います。直近だと ABC 436 B とかがその類な気がします。

コンテスト中の読み方についてとやかく言う気はあまりないですが、少なくとも復習のときには問題文を丁寧に読む訓練をするのが AtCoder（に限らず、競プロやアルゴリズムのお勉強）に慣れていく上では重要だと思います。

記号がたくさん出てきて読みにくいときには、（インタフェースとして）入出力形式を見ると整理しやすい気がします。

知らない記号・用語・概念が出てきたときは Google などで調べつつ覚えていくのがいいと思いますが、検索して上位に出てくる記事が一般的でない定義を採用している（例：部分文字列）ことも考えられるので、どうしたものかなと思っています。最近だと問題文中に補足がある場合が多いので、それを読むのがいいと思います。

数学特有の言い回し（「任意の〜に対して、〜」「〜が存在して、〜」「特に、〜」「高々」など）もつまずきがちなポイントな気がします。見慣れない言い回しが出てきたときは日常の言い回しとして無理やり解釈しようとせず、「何々 数学 言い回し」などで調べるとよいかもしれません。

考察のやり方

一般論

「制約を見て想定解の計算量を予想する」「予想した計算量になりそうなアルゴリズムを予想する」「そのアルゴリズムに当てはめられるように考える」といったことをしている人がそれなりにいるように思います。 これは考察と呼ぶには相応しくなく、「メタ読み」や「パターンマッチング」と呼ばれる邪道テクニックに近い気がします。「C 問題で $N\le 10^5$ で $998244353$ で割ったあまりだから DP だ」「クエリ問題で $N\le 10^5$ だからセグ木だ」なども同様です。

まずは問題文をきちんと読んで問題設定を理解しましょう。 問題設定と言っているのは、「クエリを処理させる問題です」「通り数を求めさせる問題です」とかいったざっくりとしたジャンルの話ではなく、具体的にどういう対象を扱っているのか・どういう操作を考えているのかとか、そうした詳細な部分を含めた話です。

note: 慣れてきたらここを済ませた段階で実装に入れるようになるかもしれません*1が、慣れる前の人がそうしたやり方だけ真似しようとするべきではないと思うので、丁寧にやりましょう。

次に（計算量を改善させることはまだ意識せず、問題文で指示された通りに）入力例を紙とペン*2で実際に試し、出力例通りのものが得られることを確認しましょう。 そうしたら、今さっき手で行った方法をそのまま実装した場合の計算量がどうなるかを考えてみましょう。 このとき、たとえば列を扱おうとしているならどういうクラスを使うかも意識するとよいでしょう。

そうして計算量が求められたら制約と実行時間制限・メモリ制限を見て、大丈夫そうなら実装に取りかかります。 「自分が思いついたままの愚直な方法だと通らないだろう」と決めつけようとせず、計算量の見積もりをしましょう。 「$N \le 10^6$ なら全探索は無理だろう」のように思い込む人もいますが、たとえば（そういう問題設定で）解の候補が $O(N)$ 個しかなく、それぞれ $O(1)$ 時間で列挙できるような状況では $N\le 10^6$ でも全探索ができそうですね。

さて、大丈夫じゃなさそうなら、効率の悪そうな部分を探して高速化を図ります。自分の手を動かして具体例を試すことで「ここの計算だるいな」「これさっきも計算したよな」ということに気づきやすくなります*3。

あるいは、問題の言い換えが必要になることもあります。そうした際にはきちんと証明をするのが重要です。「たぶんこういうことが成り立つ気がする」と祈るのはよくないです。あやふやなまま実装に進むことで、誤りが考察にあるのか実装にあるのかが曖昧になりどんどん沼にハマっていきます。 証明のやり方を知らないのであれば、証明のやり方を調べて身につけるのが第一歩かもしれません。 いきなり難しい問題に対して証明を考えようとするのではなく、過去に「直感的に明らかだろう」と判断したような問題を証明の練習問題として使うのがいい気がしています。

言い換えの着想を得るために実験をしたくなった場合は、そのためのコードを書くのも悪くはないでしょう。ただし、予想を立てた後にきちんと証明をするのも忘れないようにしましょう。

コーナーケースと呼ばれるものについても適切に対処しましょう。闇雲に「ある値が $0$ のとき」「長さが $1$ のとき」「すべての値が等しいとき」のような「あるあるコーナーケース」を試すのではなく、自分の行いたい操作を行うための事前条件を整理することで確認するべきです。 また、コーナーケースは実装の段階になってから気をつける事項ではなく、考察の段階で考慮しておくべきことであるというのを念頭におきましょう。

添字を 0-indexed にするのか 1-indexed にするのかといった細部についても、実装の段階になってから考えるのではなく考察の段階で済ませておきましょう。 問題文で 1-indexed で与えられたものを実装時は 0-indexed にしたいと思っているなら、考察の段階でも 0-indexed にした状態で整理するべきです。 いわゆる添字ガチャ（サンプルが合うまで添字をいじって祈る）もやめましょう。

お気に入りの記事である On "is this greedy or DP", forcing and rubber bands by -is-this-fft- を紹介しておきます。 「これは貪欲法で解けるか？ や、解けないから DP だな」といった態度は適切ではないということや、その他考察に関するスタンスの話を（やや難しめの）例題を通して解説しておられます。

自分の中でアルゴリズム（というか、名前のついた「何々法」で解くという方針）を決めつけて当てはめるというのではなく、その問題と向き合うところが第一歩だと思うのですが、やはりそこが初心者には難しいのかもしれません？

高速化に関して

まずは愚直な解法はわかっている（定義通りに計算することはできる・なにを計算するべきかはわかっている）段階に立てているか確認しましょう。 そうできていないうちから高速化のことを考えても「よくわからないものが高速に計算できた」になってしまいます。

たとえば、解候補を全列挙して確認する解法を高速化したいのであれば、（全列挙している限りは解候補の個数のオーダーの計算量は最低でもかかるので）全列挙をしない方針を考えることが多いでしょう。 このとき、大きな二択として「すべての解候補を考慮するが、まとめられるものはまとめて考えることで、すべてを陽に列挙せずに済ませる」なのか「特定の条件を満たす解候補のみを考慮することで、列挙する個数を減らす」なのかがあります。たとえば DP は前者*4、貪欲法は後者に該当します。

note: そういった事情から、「全探索ではなく DP をする」のような表現はあまり適切ではない気がしています。あくまでもすべてを暗に探索はしているというスタンスです。

前者の高速化においては「適切なまとめ方をできているか？」が考慮すべきことで、後者では「そういう条件を満たさない解を見捨てて問題ないか？」が考慮すべきことです。 自分が行おうとしている高速化がどちらなのかを意識するとよい気がします。 特に貪欲法については典型的な証明のパターンがあるので、それを身につけておくだけでも変な解法の誘惑に負けることは減るのかなと思います。

こうした高速化は「区間和を求めるのに累積和を用いることで高速化する」「値の検索に平衡二分木を使うことで高速化する」といった単純なものよりも難しいと思います。ある程度きちんとした証明が必要になるためです。

コードの書き方

考察が終わった後は、問題のことで悩まずに実装を終えられるのが好ましいでしょう。 たとえば標準ライブラリの関数の引数の順番のような、問題設定とは関係ない部分で手が止まるのはいいと思います*5。 一方で、「そういえばこういうケースはどう対処しようかな」といったことで悩むのであれば、考察に戻るべきだと思っています。

さて、よく「競プロでは可読性より実装速度重視」といった思い込みがある人を見ます。 実装速度が重要ではありつつ、可読性の低いコードによってバグを生んだりデバッグ時間が長引いたりするなら本末転倒です。 可読性を気にすることで余分に 4 分 59 秒かかったとしても、1 ペナ喰らうよりは安いです。

特に ABC の C 程度までであれば複数の関数に切り分けるほどの実装量になることが稀という事情があるだけで、「競プロにおいてはなにがなんでも main にすべてを入れるのが好ましい」ということではありません。 一つのファイルで $T$ 個のテストケースが与えられるタイプの問題（マルチケースなどと呼ばれがち？）が ABC でも最近は多く見るようになってきましたが、こういう形式のときは一つのケースを解く用の関数を用意した方が見通しがいいと個人的には思っています。

そのくらいの実装量においては n a i 程度の簡素な変数名の方がむしろ可読性が高い気がします。 number_of_items array_of_inputs index_of_items_0_indexed などの長い変数名でうれしくなることがあまりなさそうです。 むしろ、紙の上での考察をするときに（数式として）$n$, $a$, $i$ などの記号を使うことが多く、それをそのまま流用できる方が読みやすいという感覚がある気がします。 もちろん、長い名前が必要なら（エディタの補完機能がある前提で）使えばいいと思っています。

また、保守性という観点においては、期間や読む人数を考えるといい気がします。 多くの場合、「AC した後も数ヶ月・数年に渡ってチームで保守する必要がある」というわけではなく「AC するまでの数十分・数時間、自分がデバッグできる必要がある」くらいだと思っていて、それを念頭においた書き方をするのがよいと思っています。 そうした前提の違いがあるので、「必ずしも業務における可読性・保守性の高さと一致するわけではない」という見方をするべきで、「競プロにおいては可読性・保守性は低くしてよい」というのは語弊がある気がしています。

テストについて

（自分が使っている言語であるところの）Rust では #[test] と書くことで簡単にテストコードが書けるので、実装に不安があるときはちょこっとテストを書くようにしています。 また、考察の過程で「こういうケースは気をつけておいた方がいいかも」と思ったら予めサンプルと同じディレクトリに追加するようにしています。

サンプルのテストは oj を用いて自動化しています。 「全部のテストを回すのが億劫だな」という状況を作らないのが重要だと思っています。

練習について

最近の人々も「精進」という呼び方をするのかはわかりませんが、コンテスト外でも過去問を解いたり、コンテストで解けなかった問題・最後に解けた問題の次の問題（たとえば C まで解けたときは D ということ）を解いたりする時間を設けないとどうしてもつらい気がします。

闇雲に時間を費やせば上達できるというわけではないと思っていますが、かけられる時間が少ないのであればどうしてもできることは限られてしまいます。 人によるところだとは思いますが、コンテストに出て「毎回参加してはいるが解けなさを実感するばかりでつらい」となるくらいなら、毎週 100 分の枠を用意して（適宜解説を読みつつ）過去問を解くのに専念する方が有益そうな気もします。

レートを上げることを目標とするならやはりコンテスト形式の練習が重要な気はしますが、始めたての人であればそうした速度重視の練習よりもまずは「時間をかければできる」の状態を作ることが大事な気がします。 コンテスト中に焦りながら（前述した）メタ読みなどをする経験を積むくらいなら、落ちついて考察する方が得られるものが多い気がします。

数学について

プログラミングの勉強をしたいと思っていたはずなのに数学をやらされていて誠に遺憾、という人もそれなりにいるのかなと予想しています。 プログラムの正当性や計算量の見積もり、あるいはそもそも計算したい対象自体が数学と関係が深いものになりがちなので、数学に触れずにいられるのはほんの一部分になってしまいそうな気がします。

AOJ にあるような「実装がんばります」系の問題が救いになる人もいるのかもしれません？ AtCoder が “TOO MATHEMATICS-ORIENTED!!!!”*6 な気がするので、別のジャッジの問題も見てみるといいかも。

onlinejudge.u-aizu.ac.jp

String Parsing などで検索すると、AtCoder ではあまり見ない類のジャンルを楽しめます*7。

競技プログラミングという呼称が misleading ですが、特に AtCoder は「競技数学・パソコン部門」のような側面が強い気がしており、基本的に「数学はあまり知らないがプログラミングは長くやっている」より「数学を長くやっているがコードは書いたことがない」の方にアドバンテージがある気がします。 よく「自分より後に始めた数学得意勢がどんどんレートを伸ばしているのを見てつらくなる」という人も見ますが、むしろそれが普通で、自分のアドバンテージを勘違いして過度に落ち込んでいるんじゃないかなという気がします。

コンテスト外の心構えなどについて

コンテスト後に Twitter でもしばしば「Union-find（など自分の知っているアルゴリズム・データ構造）で解けたのか〜」「貪欲法だったのか〜、だったら自分にも解けただろうな」と言っている人を見かけますが、「簡単でない考察の末に、何々法を使うと解ける問題に帰着される」と「何々法を知ってさえいれば解ける」の間には大きい差があります*8。

データ構造（やアルゴリズム）のお勉強に関しては、大きく二つの段階に分かれます。

• そのデータ構造を学ぶ
  • どのようにデータを管理するか・不変条件はなにか
  • どういうクエリをどういう計算量で処理できるか
  • （可能なら自分で実装してみる）
• そのデータ構造を応用して解ける問題を知る
  • そのデータ構造が処理できるクエリの形式に問題を言い換える典型テクを身につける

たとえば、セグ木について前者の段階の人でも「値の更新と区間 XOR クエリを処理してほしい」と言われたら解けるでしょうが、「この配列の転倒数を求めてほしい」に関してはやや厳しいところでしょう。 あるいは、「ソート済み配列から値を二分探索で探す」という概念を知った段階の人に、「$N^2$ マス計算で $K$ 番目に小さい値を求めてほしい (ARC 037 C)」と言っても厳しいでしょう。

Things I don't know by Um_nik という記事もあります。 この主張に賛同するわけでもないですが、多くのデータ構造について前者の段階の勉強をしたとしても、後者の段階の知識が身につくわけではないということは覚えておいた方がよさそうです。

他にも、コンテスト後の Twitter などで「何々ということに気づいたら一瞬だった」というのを見て「次回はまず何々かどうかを疑ってみることにしよう」という短絡的な学習をしてしまう人もいるのかもしれません？ 考察に関しての節でも触れましたが、問題設定を理解した上でそこに辿り着くのが重要なのであって、いきなり闇雲に試してみようとするのはナンセンスです。 それでは（仮に正しいものだったとしても）正しいことに確信が持てず、意味がないはずです。 そこに至るまでの思考過程をなぞってみるのは有用だと思います。たまたま見つけた記事を紹介します。

zenn.dev

あとがき

ポエム記事のポエムパートということで実質本編と変わらないかもしれません。あとがきです。

こういったあるべき論（だと思っているもの）を整理していると、えびちゃん自身が F, G を解けずに苦しんでいるときにそれらを実践しているのか？という気持ちになってきます。 他のやりたいこととの兼ね合いで ABC に対する取り組み方が真剣ではなくなってきていることが根本的にはあると思いますが、形だけ E や F まで解いていても意味がないような気がします。 むしろコンテストの時間中に F と G だけ本気で考えてみるとかの方がよっぽど有益なんじゃないでしょうかね。そうしてみようかな。

おなかがすきました。

おわり

おわりです。

*1:えびちゃんは、基本的に D 問題まではサンプルを見ることはほぼない気がします。E でもあんまり見てないかも。

*2:iPad と Apple Pencil とかでももちろんいいですが、脳内で完結させるのはおすすめしません。手を動かす癖をつけるのがいいと思っています。

*3:Knuth 先生もそうしたことを言っていた気がします。

*4:解候補を絞った上で、その解候補たちについて DP する場合もありますね。一旦ここでは深入りしません。

*5:それはそれで訓練が必要だとは思いますが、実装に入る準備は済んだと見なせるという意味です。

*6:cf. https://twitter.com/maroon_kuri/status/1195076295627100160

*7:楽しいと思うかは人によると思います。えびちゃん的には楽しんでいました。

*8:いわゆる “One chalk mark: $1 / Knowing where to put it: $49,999” 的なジョークに通ずるところがある気がします。