注意
- 本記事はあくまで 私 がやったことを記述した資料です。受験者の 1 サンプルでしかありません。本記事を過度に一般化した主張を述べることは控えていただきますようお願いします。
- 実際に上級になりましたが、中級を意識した学習しか行っていません。上級を目指す方が本記事を参考にする場合は特にご注意ください。
はじめに
第六回 アルゴリズム実技検定 ( 以下 PAST ) を受けて、上級になりました。
これまでやってきたことを振り返ろうと思い、本記事を書きました。
目標が中級だったため、やったことの大部分が中級を目指して学習・練習したことになります。実際、アルゴリズム実技検定について の上級の出題範囲にある下記についてほとんど学習していません。
- 最小共通祖先
- 最大流問題
- 最小費用流問題
記事には私が競技プログラミング (主に AtCoder) を始めたときからやったことを書きました。私の PAST のための学習は AtCoder のコンテストのための練習の延長にあったため、競技プログラミング開始時点から書いた方が、やったことの全体を記述できると判断した次第です。
やったこと
以下はやったことの箇条書きです。
- APG4b
- 競プロ・AtCoder上達のガイドライン【初級編】
- 競プロ・AtCoder上達のガイドライン【中級編】
- 環境構築
- ライブラリの準備
- Boot camp for Beginners 埋め
- タイピング練習
- 「あさかつ」参加
- ABC 500 点寒色問題埋め (途中)
- Educational DP Contest 埋め (途中)
- PAST 対策
時期が重なっているところもあるため、正確ではありませんが、およそ下記の順序でやりました。
1. APG4b
競技プログラミングのメイン言語は C++ を選びました。レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 の「1-8. おまけ：競プロにおける C++ のすすめ」で薦められていたから、という理由で選びました。
C++ を書いた経験はあるものの、競技プログラミングでの使い方が知りたかったため、C++入門 AtCoder Programming Guide for beginners (APG4b) をやりました。
2. 競プロ・AtCoder上達のガイドライン【初級編】
競技プログラミングを始める際に レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 というガイドラインを見つけていたため、こちらに従って練習することにしました。
具体的には「1-6. 「茶色コーダー」になるためのガイドライン」に書いてあることをやりました。APG4b 終了後でしたが「1-6-1. AOJ の「Introduction To Programming I」を全部解く！」もやりました。中級編 と比べて列挙されている問題が少ないと感じたため、「1-5. 「茶色コーダー」で要求される 4 つのこと」の条件 4 で列挙されている問題など、このガイドラインにリンクがある問題を一通り解きました。
3. 競プロ・AtCoder上達のガイドライン【中級編】
初級編 を終えた後、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 に着手しました。
3.1. C++ の学習
「2-2-1. 標準ライブラリを使えるようになる！」に記載の関数のリンク先を読みました。
他には下記の使い方を覚えました。
それ以外の C++ の機能は問題を解くときに cpprefjp などで調べながら使っています。
3.2. アルゴリズムとデータ構造の学習
「2-2-2. 12 個の基本アルゴリズムをマスターする！」については、ガイドラインのリンク先の各記事を読みました。
「2-2-3. 3 個の基本データ構造をマスターする！」については プログラミングコンテストチャレンジブック (通称：蟻本) の以下を読みました。
- 2-4 データを工夫して記憶する “データ構造”
- 2-5 あれもこれも実は “グラフ”
読み終えた段階で AtCoder 版！蟻本 (初級編) の 2-4 と 2-5 の初めの数問を解きました。
3.3. 「分野別 初中級者が解くべき過去問精選 100 問」 埋め
「2-3. 分野別 初中級者が解くべき過去問精選 100 問」を 2 周しました。
別解を思いついたときは別解も実装しました。ある問題で 遅延評価セグメント木 を使った別解を思いついたため、AtCoder Library のセグメント木と遅延評価セグメント木の使い方を学習しました。
3.4. 灰色難易度のバーチャルコンテスト
「2-2-5. 早解きを鍛える！ ～バーチャルコンテストのすすめ～」で紹介されていた以下のコンテスト設定を少し変更して、バーチャルコンテストを 30 回ほど行ました。
- AtCoder Beginner Contest から、A 問題 1 問・B 問題 2 問・C 問題 3 問の合計 6 問を集める。
- これを合計 30 分でできるだけ解く。
具体的には以下のように変更しました。
- difficulty が 50 以下 1 問・50 以上 200 以下 2 問・ 200 以上 400 以下 3 問の合計 6 問を集める。
- これを合計 30 分以内を目標に解く。(コンテスト時間自体は 60 分)
difficulty をもとに問題を選ぶよう変更した理由は簡単に問題を選んでバーチャルコンテストを立てるためです。AtCoder Problems のバーチャルコンテスト作成の問題選択では difficulty の範囲と参加予定者を設定すると未 AC の問題を自動で選んでくれる機能を利用できます。この機能を使って手軽にバーチャルコンテストを立てていました。
difficulty 200 から 400 の問題を使い切ったあたりから「あさかつ」に参加し始め、この形式のバーチャルコンテストは今はやっていません。
4. 環境構築
初めの頃は iTerm2 上で以下のように AtCoder の問題を解いていました。
面倒に感じるようになったため、以下を導入しました。
これらのお陰で、サンプルのダウンロード、サンプルでの動作確認、ソースコードの提出などがコマンドでできるようになり、快適に問題を解くことができるようになりました。
5. ライブラリの準備
基本的に AtCoder Library を使っています。その他に以下をライブラリとして持っています。
- 最大公約数、最小公倍数
- chmax/chmin
- 二項係数
- よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 を参考に AtCoder Library の modint に対応した実装を用意しています。
6. Boot camp for Beginners 埋め
AtCoder Problems の Boot camp for Beginners の Medium と Hard を埋めました。
7. タイピング練習
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】 を興味本位で少し読んだとき、「3-1. 「黄色コーダー」で要求される 6 つのこと」の「条件 5」達成のためには、タイピング練習が必要だと知り、先取りしました。
いくつかのタイピングソフトを試して、今は keybr で練習しています。バーチャルコンテストの直前の数分などに練習しています。
8. 「あさかつ」参加
灰色難易度のバーチャルコンテストで difficulty 200 から 400 の問題を使い切ったあたりから、時間を意識した練習として、参加できるときは あさかつ に参加し始めました。
9. ABC 500 点寒色問題埋め (途中)
AtCoder ProblemsのHeatmapを緑色で塗りたくった話 の「AtCoderを使ったおすすめ精進プラン」の「水色以下」に「新ABC全部やる」とあったため、始めました。
いきなり 600 点の問題や黄色 difficulty 以上の問題を取り組んでも身にならない気がしたため、まずは 500 点以下かつ青色以下の問題から埋め始めました。ただ、400 点以下かつ緑色以下の問題についてはバーチャルコンテストで消化した方が練習になりそうだと考えて、放置しています。言い換えると配点と difficulty の組が下図の青線に属する問題から着手しました。
10. Educational DP Contest 埋め (途中)
Educational DP Contest / DP まとめコンテスト を埋め始めました。問題 H まで埋めました。
11. PAST 対策
2021 年 2 月末に アルゴリズム実技検定 公式テキスト［エントリー～中級編］ (以下 PAST 本) が発売することを知り、中級を目指すことにしました。発売日から試験日まであまり日がないと思い、購入後は PAST 本を軸にして学習しました。
11.1. 検定 1 か月前
PAST 本を例題を解きながら読みました。
アルゴリズムに関する知識については レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 にすでに取り組んでいたため、 8 割くらいは知っていました。しかし、知らないこともあり、復習と新しい知識の獲得をバランスよくこなすことができたと思います。
特に以下はなんとなくでやっていたため、まとまった形で勉強できて良かったです。
- 「6.8 貪欲法」
- 「6.13 クエリの処理」
アルゴリズムについての知識以上に有益だったのが「第7章 さらなる得点を狙うために」の内容でした。第 7 章では難しい問題を分解・整理する方法がいくつか解説されています。この章のお陰で、中級相当の問題の中でも難しい問題を解くための考え方が身についた気がします。
11.2. 検定 1 週間前
土曜日と日曜日に模擬試験として第四回と第五回の PAST のバーチャルコンテストを行ました。非常に疲れました。7 点の問題や 8 点の問題を解くのに (想定よりも) 時間がかかるという課題が見つかりました。そのため、バーチャルコンテスト以降は、これまでの PAST の過去問を点数の高い方から埋められるところまで埋めました。
11.3. 前日と当日
1 週間前の模擬試験の経験から、試験は非常に疲れるだろうと予想しました。疲れて集中力が低下することを避けるため、直前は以下のように疲労回復に努めました。
- 前日は早めに寝る。
- 当日の食事は朝昼しっかり食べる。
- 当日午前中は問題を考えず、軽く運動 (リングフィット アドベンチャー) する。
- 運動後、お風呂に入る。
試験中は、すぐに解法が思いつく問題を解いたあとは 1, 2 問ごとにトイレ休憩・おやつ休憩・水分補給をしました。
取り組んだ問題の量と傾向
AOJ も多少解いていますが、前述のガイドラインの初級編・中級編で紹介されている問題がほとんどのため、AtCoder を中心に見ていきます。
以下は第六回 PAST 翌日の AtCoder Problems のスクリーンショットです。
やったことには、問題の difficulty や配点を意識したこともあれば、それらをあまり意識しなかったこともあります。そのためか、以下のような、はっきりとした傾向は無いようです。
- きっちり低難易度を埋める。
- 高難易度の問題に集中する。
おわりに
PAST やコンテストを開催いただいている AtCoder に感謝いたします。また、学習の手助けになる記事、書籍、web サービスなどの作成者にも感謝いたします。
おまけ
YouTube さんに PAST 本を強く薦められました。
