ブログのネタがなさすぎてサボっておりました（おい）。

最近競プロが楽しくてたまらないです。AtCoder のレートももうすぐ1,200となるため、一つの目標である水色レートは到達できそうです。

さて、ここ数ヶ月間は300点問題を埋めるのに時間を費やしてきました。もちろん、上を目指すならもっと配点の高い問題をやるべきなのですが、上の難易度の問題をやる前に基礎が抜け落ちていないかチェックしたいという気持ちが大きかったのでこのような練習をしています。

まだ全ては解いていないのですが、もし緑色レートあたりを目指している人に何か役立つ情報が提供できないかなとふと思ってこの記事を書きました。AtCoder 300点の問題でこれはとてもいい練習になるなと思うものをいくつかピックアップしておきました。多すぎてもアレなので、めちゃくちゃ絞っています。また、最近のコンテストの問題はあまり選ばないようにしてあります（始めたばかりの人はもう見てしまった人も多いかと思うので…）。

若干のネタバレを含む（解法の方針的な内容）のでネタバレしたくないよ〜！っていう人は後半のネタバレ注意以降の部分は読まないようにお気をつけてください！

問題集

配点はすべて300点です。ネタバレ等はこの問題集より後にまとめてあります。

C - 4/N (Tenka1 Programmer Contest 2017)
C - One-stroke Path (ABC054)
C - Digits in Multiplication (ABC057)
C - Dubious Document 2 (ABC076)
A - Getting Difference (AGC018)
C - 高橋君とカード / Tak and Cards (ARC060)
C - 白昼夢 / Daydream (ARC065)
C - Factors of Factorial (ARC067)
C - Snuke Festival (ARC084)

ネタバレの前に

この9問に含まれる要素を本番でもきちんと書けるならおそらくABCなら300点の打率（コンテスト中のAC率）は7割超えると思います。あとは writer さんや問題の内容にできるだけ偏りがないこと、300点に限らずさらに上の問題でも使えることなどいろいろ気を使ったつもりです。

主観がかなり入っているし、筆者もそこまで競プロでめっちゃ強い人！ベテラン！という訳ではありません（冒頭でも述べた通りレートにして水色手前ぐらいです）ので、「こっちの問題の方が5億倍ええやろ！」みたいな感想もあるかと思いますが、大目にみてください。お願いします。

以下ネタバレを含みます！！！！

ネタバレしてもいいよ〜！という人は進んでください。全問一気に出ます。

Σ(っºΔºc)...

ネタバレと選んだ理由的なこと

1. 4/N

200点でももちろん全探索は出てくるのですが、この問題はきちんと3500の3乗から3500の2乗に落とせば間に合うな、と時間計算量の感覚をきちんとつかめているか、全探索を考えられるかの練習にはとてもいいと思います。うっかり 0 で割らないように気をつけてほしいというのもお気持ちとして少しあります。

2. C - One-stroke Path

next_permutation 使ってO(N!)で解いてもいいし、深さ優先探索で解くのもいいし、グラフの簡単な練習にもなるのでおすすめです。いろいろな方法で解いてみましょう。

3. C - Digits in Multiplication

約数列挙がO(sqrt(N))でできるというのは300点〜400点あたりで結構出てくる印象があります。おそらく約数列挙の中ではかなりシンプルな方の問題です。

4. C - Dubious Document 2

文字列操作、辞書順最小みたいな問題は忘れた頃に出てくる感じですね…。数問は解いておいた方がいいと思います。

5. A - Getting Difference

300点で頻出なのがGCDなんですが、コンテストでちゃんとGCDと気づく鋭い勘は鍛えておいた方がいいと思います。この記事を書いた時期に近いコンテストだと、C - Monsters Battle Royale とかですかね。

Getting Differenceは入力例に対して出力がPOSSIBLEかIMPOSSIBLEのいずれかなので、入力例、出力例からメタ読みはほぼ不可能で、ちゃんと考察しないとGCDが導けません。

6. C - 高橋君とカード / Tak and Cards

部分点解法はもう大丈夫だと思うんですが、満点解法のDPはやってないとおそらく思いつかないはずです。DPは慣れないうちは本当に難しく感じるし、バグも埋め込みやすいのですが、DPの問題だけを寄せ集めたコンテスト（Educational DP Contest - AtCoderとか）もあるくらいですから感覚を養っておくと必ず役に立ちます！300点どころか400点以上も解けるようになる可能性がグーンと上がります！

この問題は最近の300点に比べたら少し難しめかもしれません…がビギナーコンテストの参加者のレベルがインフレしているのでこれくらいの問題が普通に出てもおかしくない状況です。

7. C - 白昼夢 / Daydream

Codeforces とかだと(と)が正しい入れ子になっているか解析してください、みたいな問題は出るのですが AtCoder だとなかなか見ないですね…。最近数列系の問題がやたら多いのでそろそろ出てきてもおかしくない気がします。

もちろん文字列の左側からパースしても解けるのですが、解説を見て「後ろから見るとよい」「ある文字列が他の文字列のprefixになっているかどうか」あたりの知見を得るだけで、文字列問題で打つ手が増えて嬉しい気持ちになると思います。

8. C - Factors of Factorial

素因数分解と正の約数の個数と階乗の性質がセットになっていて、さらに mod (10⁹ + 7) を正しく処理する練習もできて嬉しい問題だと思います。

9. C - Snuke Festival

数列をソートして大きい順に取るとかみたいな問題は200点問題でもやるのでそれは選ぶ必要ないなと思いました。この問題は、ソートして二分探索して数え上げするという基本要素が組み合わされただけですが、めちゃくちゃ良問だと思います。

けものみち

まったりと、きのむくままに。

300点のエッセンス

問題集