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点?)
B: リモコン - AtCoder Regular Contest 001 | AtCoder
B: 割り切れる日付 - AtCoder Regular Contest 002 | AtCoder
B: P-CASカードと高橋君 - AtCoder Regular Contest 005 | AtCoder
B: 引越しできるかな? - AtCoder Regular Contest 013 | AtCoder
B: 格子点と整数 - AtCoder Regular Contest 018 | AtCoder
C問題
C問題はアルゴリズムの応用が問われます.
今のコンテストの得点スケールに換算すると,400点から1000点くらいでしょうか?
よく出題されていた範囲は次のあたりでしょうか.
データ構造
- セグメント木 or BIT
DP
- 多次元DP
グラフ
- DFSの応用
- BFSの応用
- ダイクストラ法の応用
DPとグラフが多く,その他の問題は多種多様なジャンルが出ていると思います.
B問題に比べると,当然ながらひねりが多くなっています.
C問題については,ARC001から順に解いていくと,難易度が徐々に上昇している傾向を感じます.
オススメ
C: 五目並べチェッカー - AtCoder Regular Contest 012 | AtCoder
C: A mod B Problem - AtCoder Regular Contest 020 | AtCoder
C: だれじゃ - AtCoder Regular Contest 024 | AtCoder
C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder
C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder
C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder
C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder
C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder
C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder
比較的簡単な問題 (推定換算で400点~500点?)
C: パズルのお手伝い - AtCoder Regular Contest 001 | AtCoder
C: コマンド入力 - AtCoder Regular Contest 002 | AtCoder
C: 節約生活 - AtCoder Regular Contest 007 | AtCoder
C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder
C: Z塗り - AtCoder Regular Contest 040 | AtCoder
普通の問題 (推定換算で600点~800点?)
C: ソーシャルゲーム - AtCoder Regular Contest 016 | AtCoder
C: 最後の森 - AtCoder Regular Contest 019 | AtCoder
C: 増築王高橋君 - AtCoder Regular Contest 021 | AtCoder
C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder
C: LCM 111 - AtCoder Regular Contest 050 | AtCoder
難しめの問題 (推定換算で900点~1000点?)
C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder
C: N!÷K番目の単語 - AtCoder Regular Contest 047 | AtCoder
C: 足の多い高橋君 - AtCoder Regular Contest 048 | AtCoder
C: 鯛焼き - AtCoder Regular Contest 054 | AtCoder
C: ABCAC - AtCoder Regular Contest 055 | AtCoder
C: 2乗根 - AtCoder Regular Contest 057 | AtCoder
D問題
D問題は最終問題であるため,当然難しいです.
また,同じD問題の中でも感じる難易度の振れ幅が非常に大きいです.
問題を解く上で必要になる要素(発想,知識,実装)も適当にバラついています.
ちなみに,今の自分が自力で解いたD問題の割合は1/4くらいでしょうか.
よく出題されていた範囲は次のあたりでしょうか.
データ構造
- セグメント木
グラフ
- 最小共通祖先
- 最大流
文字列
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 019 | AtCoder
D: バス停 - AtCoder Regular Contest 024 | AtCoder
D: アットコーダーモンスターズ - AtCoder Regular Contest 032 | AtCoder
D: カクカク塗り - AtCoder Regular Contest 040 | AtCoder
D: 辺彩色 - AtCoder Regular Contest 041 | AtCoder
D: うさぎとマス目 - AtCoder Regular Contest 046 | 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
多分一番難しい問題 (まだ解けてない)
最後に
計264問もあって解くのはなかなか大変です.
しかし,解いた分だけ実力として定着している感じはあります.
この後は,JOI春合宿,AOJ埋め,CFのVirtual Contestでもやろうかな...