茶色diffの傾向と、緑になるための対策

はじめに

先日、ツイッターで次のようなツイートをみました。

そこで、今回はABCで緑になるためには何をすればよいのかを、分析したいと思います。

茶色difficultyの問題の分類

対象はABC126～ABC177(現在の6問形式で開催されるABC)です。問題の解き方のネタバレが載っているので、閲覧注意でお願いします。

数え上げ
整数
貪欲
全探索
シミュレーション
確率、期待値
幾何
グラフ
その他

考察

ちゃんと検証していないのでよくわかりませんが、茶diffの問題を8～9割程度安定して正解できれば、緑に到達できると思います。
(difficultyは制限時間内に正解した人全体から算出されるので、時間に余裕を持って正解すれば、体感よりパフォーマンスは高くなります。)

数え上げ

数え上げの問題は数多く出題されていますが、DPを用いた問題は一問しか出題されていません。
それ以前に、「場合分け」「どこを固定してどこを探索するか」「高速化は可能か」などの基礎的な分析力を叩き込む必要があるのかもしれません。

整数

エラストテネスの篩が近年頻出ですが、茶diffではもう少しシンプルな問題が出題されています。

  • 範囲を絞って全探索する
  • 素因数分解した形を考える
  • modによる場合わけを考える

といった考え方は数学にも共通しています。
数え上げ、整数どちらにしても、プログラミング独特の考え方というより、高校数学の「場合の数」「整数」の考え方が使えることが多いです。
プログラミングの問題は数が限られているので、数学の参考書で勉強してみるのもそれなりに有効だと思います。

全探索

bit全探索の問題はたいてい緑diffでしたが、最近は茶色diffのことが多いです。
bit全探索の問題は、制約がN<=20など小さいのでそこから見抜きましょう。
dfs全探索などは今のところ必要なさそうです。

シミュレーション

意外と多かったのが、シミュレーション問題です。
「操作を何回かするので、操作後の状態を答えてください。」というタイプの問題です。
サンプルをもとに「操作によって状態がどのように変化していくか」をじっくり洞察する必要があります。

グラフ

グラフの問題は2問しか出題されていません。
グラフ上のアルゴリズムや探索については知らなくても緑にはなれると思います。
ただし、灰diffでグラフの問題は出題されているので、基礎的な概念(隣接リストを用いた管理など)や問題をグラフに落とし込む方法については知っておいた方がよいです。

まとめ
  • 「やりたい作業を自由に実装できる」ことは茶色では前提。
  • ○○法のようなアルゴリズムは緑になるには知らなくてもよい。
  • 考察パターンは典型といえども多岐にわたる。

AtCoder社員のりんごさんがCodeForcesのブログで、競技プログラミング(とくにAtCoder)でのスキルは

  • observation(問題に対する洞察力)
  • strategy(コンテスト時の戦略)
  • typical pattern(典型パターンの習得)
  • implement(実装)

に大別されるという趣旨のことをおっしゃっていました。

典型パターンにたどり着くための洞察は、軽視されがちですが、茶色でも多様な解き方が求められる以上必要不可欠です。
「洞察力」はじっくり問題を考えること、「典型パターン」はたくさんの問題を解くことで習得できます。
簡単な問題が解けないとき解説ACするのは知らなかった技術を習得できるので意味がありますが、難しい問題をむやみに解説ACするのはじっくり考える機会を失ってしまうかもしれません。
一つ一つの問題を無駄にせず、どういう洞察ができるか、どのような典型パターンでほかの問題とつながっているかを意識することが大事だと思います。


以上です。また加筆したいと思います。