BrownCoder

無能ですがAtCoderしてます。情報処理試験や機械学習、その他ベンダー資格時々数学など参考になった本の紹介や雑記を書いてます。

AtCoderのC問題攻略マニュアル

この記事をシェアする

最近自分がAtCoderのC問題をある程度の打率で解くことができるようになってきたので、一度勉強したアルゴリズムや勉強法をまとめて書いておこうと思いました。参考にしていただけると幸いです。


はじめに

AtCoderはB問までスラスラと解くことができますが、C問題から急に考察が必要となり、巨大な壁に行く手を阻まれる思いをします。「自分には向いてないんじゃないんだろうか」「自分には才能がないのではないだろうか」と思ってしまい、精進を辞めてしまうと一向に成長をしません。

YouTubeAtCoder解説動画を見たり、解説PDFを読んだり、他の有志の人が丁寧に解説しているブログを読んだりしてパターンを学んで行きましょう。

そして何問も何問も問題を演習しているうちに、勝手に解法が浮かんでくるようになってきます。不思議ですね。私もC問題を解き始めた時に「どの問題から手をつけたらいいか分からない」「他の人のコードを見ても理解できない」という状況になってとても辛い思いをしてました。

そのような同じ思いをして欲しくない為に今回この記事を書きました。至らぬ点も多いと思いますが、もしよければ参考にしていただけると嬉しいです。


解く上でちょっとだけ必要なこと

ちょっとだけアルゴリズムを学ぶ

qiita.com

  • Bit全探索

qiita.com

qiita.com

  • ダイクストラ
  • ワーシャルフロイド法
  • ベルマンフォード法
  • Greedy(貪欲法)
  • 1次元累積和

qiita.com

  • 1次元imos法
  • 簡単なdp

qiita.com

qiita.com

qiita.com

これらはほとんど蟻本に載っています!!!!

データ構造ちょっと学ぶ

  • データ構造
    • Union-Find

qiita.com

  • ヒープ(Priority_queue)
  • スタック
  • キュー

数学アレルギーを直して、ちょっと数学の知識を学ぶ

qiita.com

qiita.com

  • エラトステネスの篩
  • 余り(Mod)を利用したグループ分けの考察

qiita.com

  • 順列(next_permutation)
  • 期待値の線型性

qiita.com

計算量とかの補助的な知識もちょっと学ぶ

  • 計算量についての知識(時によってはそれにより解法が分かる)

qiita.com

お金 をちょっとだけ投資する

  • 蟻本

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

  • 螺旋本

解法を出すための工夫をちょっと努力する

  • 紙に書き出す(問題サンプルや自己で作成したサンプル)
  • ケアレスミスをなくす(入力とかの型とかに気をつける)
  • 問題文及び制約をよく読む(読み違えると大惨事)

今すぐには必要のないから頭の片隅に置いておくもの

qiita.com


学習フロー

1.AtCoder精選10問の類題を含めて解く

qiita.com

基本的ことは全てここにまとまっています。まずはここで類題を含めるC埋めを行い、大体の解法パターンを学びましょう。もし分からない問題があった時はコンテスト名で検索すると他の人が解説記事を書いていてくれたりするので参考にしましょう。

2.蟻本の初級編をざっと読みながら、蟻本(AtCoder版)を解く

qiita.com

ここからアルゴリズムを中心に学んで行きます。紹介されているD問題は各自でやるか、ヤラナイカを判断してください。私はD埋めの時に考察力を伸ばすついでに解きたかったので、とりあえずは保留にしています。

3.簡単なC問題を解いていく

osrehun.hatenadiary.jp

C問題にも簡単なものだったり、難しかったりする問題が存在します。その中でまだ解いていない問題で簡単なものから埋めていくようにしましょう。やっぱり少しずつ難易度を慣らしていった方が精神衛生上良いです。

ここら辺で計算量から解法が導けることにある程度気づいてくると思います。良い感じにまとめている記事がこちらです。

pyteyon.hatenablog.com

4.残っているC問題を適当に解いて埋めていく

ここからは自分が後回しにしてしまったC問題を淡々と埋めていく作業になります。一度逃げてしまった問題でも他の問題考察を行い、向上したあなたの考察力ならば解ける問題があるかもしれません。

私は電車の中で考察力だけを伸ばす為にアルゴリズムパズルを購入して少しずつ解いてみたりしました。これが結構問題によっては面白くて、感動した問題もあります。サンプルとして問題を1問抜粋しておきます。答えが知りたかったら購入またはネットで検索してみてください。

偽造硬貨の山(A Stack of Fake Coins)

10枚の硬貨を積み重ねた山が10本ある。どれも外見的には区別がつかない が、そのうちの1本の山はすべて偽造硬貨で、残りの山は本物だ。また、本物 の硬貨は10グラムで、偽造硬貨は11グラムであることが分かっている。何枚 の硬貨の重さでも正確に計ることができるデジタル式の秤があるとして、偽造 硬貨の山を見つけるには最低何回の計測が必要だろうか?

ヒント: 答えは1である。そのアルゴリズムを考えてみよ。

アルゴリズムパズル ―プログラマのための数学パズル入門

アルゴリズムパズル ―プログラマのための数学パズル入門