ARC過去問の難易度レビュー

これは「Competitive Programming Advent Calendar 2016 」の22日目の記事です。
Competitive Programming Advent Calendar 2016 - Adventar

まえがき

去年はAtcoder社(http://atcoder.jp/)が開催しているAtcoder Beginner Contest (ABC)を全部解いて，ブログの記事を書きました．
初心者向けのABCの問題傾向とその対策 - ヘクトのメモ
この記事の最後に，(ARC埋めも行っていますが残り75問,いつ終わるのだろうか...)
と書いてありますが，2016年にARC047~ARC066まで追加されたので+80問です．
これは(学生のうちに)ちゃんと解かないと，もう埋められないのでは? ということでほぼ埋めました．

2016年にAtcoderにレーティングがつき，問題傾向も多少変わりましたが，過去問を解くことは有益と思われます．
そこで，過去問を埋める人向けに役立つ何かを書いていきたいと思います．(あくまで自分の感覚で)

記事の構成

ARCの問題の難易度とジャンルについて書いていきます．
どの問題を解いたどうかを調べるには以下のサイトが役に立ちます．
AtCoder Problems
多くのコンテストには，公式の解説があります．そうでないものは，検索すれば解法が載っているブログがヒットするはずです．
あと，今年のアドベントカレンダーに機械学習を用いた過去のAtcoderコンテストの難易度推定の記事があります．
どの問題を解くかを決める時に参考になると思います．
AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間 - TopCoder部
全ての問題について書くのは大変なので，問題を適当にピックアップしていきます．

A問題

A問題はプログラミングの基本などが問われます．
今のコンテストの得点スケールに換算すると，100点から200点くらいです．
ですので，ABCのA問題とB問題くらいでしょうか．
しかし，問題文の読解に少し知識が必要な場合もあります．
また，計算量に気をつけないとTLEする問題もあります．

B問題

B問題は基本的なアルゴリズムの運用が問われます．
ここから先の問題は難易度の幅が非常に広いです．
今のコンテストの得点スケールに換算すると，200点から500点くらいです．
よく出題されていた範囲は以下の通りです．
これらの知識が身につけば，比較的解ける問題が多いと思います．

ソート

多項式オーダーでない全探索

二分探索

データ構造

Union-Find

DP

2次元DP
数え上げ

グラフ

DFS
BFS
連結成分

数論

最大公約数
最小公倍数

文字列

辞書順最小の貪欲
回文の性質

オススメ

B: Your Numbers are XORed... - AtCoder Regular Contest 021 | AtCoder (難しい)
B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder
B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder (難しい)
B: 同一円周上 - AtCoder Regular Contest 047 | AtCoder (難しい)
B: 互除法 - AtCoder Regular Contest 051 | AtCoder

比較的簡単な問題 (推定換算で200点~300点?)

普通の問題 (推定換算で400点~500点?)

難しめの問題 (推定換算で600点くらい?)

B: 高橋君と禁断の書 - AtCoder Regular Contest 029 | AtCoder
B: せんべい - AtCoder Regular Contest 055 | AtCoder
B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder

C問題

C問題はアルゴリズムの応用が問われます．
今のコンテストの得点スケールに換算すると，400点から1000点くらいでしょうか?
よく出題されていた範囲は次のあたりでしょうか．

データ構造

セグメント木 or BIT

DP

多次元DP

グラフ

DFSの応用
BFSの応用
ダイクストラ法の応用

DPとグラフが多く，その他の問題は多種多様なジャンルが出ていると思います．
B問題に比べると，当然ながらひねりが多くなっています．
C問題については，ARC001から順に解いていくと，難易度が徐々に上昇している傾向を感じます．

オススメ

比較的簡単な問題 (推定換算で400点~500点?)

普通の問題 (推定換算で600点~800点?)

難しめの問題 (推定換算で900点~1000点?)

D問題

D問題は最終問題であるため，当然難しいです．
また，同じD問題の中でも感じる難易度の振れ幅が非常に大きいです．
問題を解く上で必要になる要素(発想，知識，実装)も適当にバラついています．
ちなみに，今の自分が自力で解いたD問題の割合は1/4くらいでしょうか．
よく出題されていた範囲は次のあたりでしょうか．

データ構造

セグメント木

グラフ

最小共通祖先
最大流

文字列

Suffix Array

DP

期待値DP

その他

経路数の性質

D問題ははっきり言って，どれも難しいので

比較的簡単な問題 (推定換算で600点~800点?)

D: シャッフル席替え - AtCoder Regular Contest 003 | AtCoder
D: 表現の自由 ( Freedom of expression ) - AtCoder Regular Contest 004 | AtCoder
D: アルファベット探し - AtCoder Regular Contest 006 | AtCoder
D: 破れた宿題 - AtCoder Regular Contest 007 | AtCoder
D: grepマスター - AtCoder Regular Contest 014 | AtCoder
D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder

(自分が)類題を見たことがないオススメ

D: お菓子の国の旅行 - AtCoder Regular Contest 020 | AtCoder
D: 注文の多い高橋商店 - AtCoder Regular Contest 028 | AtCoder
D: 見たことのない多項式 - AtCoder Regular Contest 033 | AtCoder
D: ナナメクエリ - AtCoder Regular Contest 047 | AtCoder
F: 文字列大好きいろはちゃん / Iroha Loves Strings - AtCoder Regular Contest 058 | AtCoder

オススメ

D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder
D: インフレゲーム - AtCoder Regular Contest 034 | AtCoder
D: 旅行会社高橋君 - AtCoder Regular Contest 039 | AtCoder
D: みんな仲良し高橋君 - AtCoder Regular Contest 045 | AtCoder
F: AtCoDeerくんとグラフ色塗り / Painting Graphs with AtCoDeer - AtCoder Regular Contest 062 | AtCoder

考察

知識+重実装?

D: 僕は友達が少ない - AtCoder Regular Contest 018 | AtCoder
D: コンセント - AtCoder Regular Contest 025 | AtCoder (重実装)
D: ぴょんぴょんトレーニング - AtCoder Regular Contest 027 | AtCoder
D: グラフではない - AtCoder Regular Contest 030 | AtCoder

幾何?

D: レースゲーム - AtCoder Regular Contest 001 | AtCoder (想定解で解いていない)
D: 情報伝播 - AtCoder Regular Contest 010 | AtCoder (想定解で解いていない)
D: きつねさんからの挑戦状 - AtCoder Regular Contest 011 | AtCoder

多分一番難しい問題 (まだ解けてない)

D: スプリンクラー - AtCoder Regular Contest 022 | AtCoder

最後に

計264問もあって解くのはなかなか大変です．
しかし，解いた分だけ実力として定着している感じはあります．
この後は，JOI春合宿，AOJ埋め，CFのVirtual Contestでもやろうかな...

まえがき

記事の構成

A問題

グラフの連結成分

素数判定

計算量

B問題

ソート

多項式オーダーでない全探索

二分探索

データ構造

DP

グラフ

数論

文字列

オススメ

比較的簡単な問題 (推定換算で200点~300点?)

普通の問題 (推定換算で400点~500点?)

難しめの問題 (推定換算で600点くらい?)

C問題

データ構造

DP

グラフ

オススメ

比較的簡単な問題 (推定換算で400点~500点?)

普通の問題 (推定換算で600点~800点?)

難しめの問題 (推定換算で900点~1000点?)

D問題

データ構造

グラフ

文字列

DP

その他

比較的簡単な問題 (推定換算で600点~800点?)

(自分が)類題を見たことがないオススメ

オススメ

考察

知識+重実装?

幾何?

多分一番難しい問題 (まだ解けてない)

最後に