読者です 読者をやめる 読者になる 読者になる

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

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
  • 連結成分
数論
  • 最大公約数
  • 最小公倍数
文字列
  • 辞書順最小の貪欲
  • 回文の性質

C問題

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

データ構造
  • セグメント木 or BIT
DP
  • 多次元DP
グラフ

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

D問題

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

データ構造
  • セグメント木
グラフ
  • 最小共通祖先
  • 最大流
文字列
DP
  • 期待値DP
その他
  • 経路数の性質

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

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

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

最後に

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