ヘクトのメモ

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

初心者向けのABCの問題傾向とその対策

これは 「Competitive Programming (その2) Advent Calendar 2015 」の13日目の記事です。
www.adventar.org

まえがき

夏休みにAtcoder社(http://atcoder.jp/)が開催しているAtcoder Beginner Contest (ABC)を全部解いて,サークルの部誌の記事を書きました.
この時に,ABCを全部解いた知見をもとにブログを書きます.(この記事を書いた時点では,ABCは31回開催されています.)
ぶっちゃけた話,記事を8ページも書きましたがサークルの部誌の発行部数が数十部と少ない.人の目に触れる機会がないことに気づいたのがこの記事を書いた理由だったりします.

記事の構成と参考情報

Atcoder Beginner Contest (ABC)は簡単なA問題から難しいD問題までの4問からなり,難易度順に並んでいます.
そこで各問題のレベルの傾向と対策についてまとめていこうと思います.
この記事では,使用するプログラミング言語C++という前提をおいて書いています.
ライブラリやアルゴリズムの詳細はあまり書かないので他のサイトや本なども参考にしましょう.(有名な本としてはプログラミングコンテストチャレンジブックなどが挙げられます.)
また,ABCは親切な公式の解説スライドがslideshareに上がっているのでそちらも参考にしましょう.
どの問題を解いたどうかを調べるには以下のサイトが役に立ちます.
AtCoder Problems

競技プログラミングが初めてという人向け

まずは,以下のページで問題を解いてみましょう.
A: はじめてのあっとこーだー(Welcome to AtCoder) - practice contest | AtCoder

A問題

A問題はプログラミングの基本などが問われます.
問題の傾向としては次のようなものが挙げられます.

  • 簡単な演算を行う問題

A: 積雪深差 - AtCoder Beginner Contest 001 | AtCoder

  • 大小比較を行う問題

A: 正直者 - AtCoder Beginner Contest 002 | AtCoder

  • 文字列の操作を行う問題

A: ハンドルネーム - AtCoder Beginner Contest 010 | AtCoder

このレベルで必要となるプログラミングの知識は以下の内容でカバーできると思います.

  • 整数と文字列の入出力 scanf/printf cin/cout
  • 四則演算 +-*/
  • 条件分岐 if/else
  • 繰り返し for
  • 文字列の操作 std::string
    • 文字列の長さ str.size()
    • 文字列連結 str1+str2
    • (部分文字列) str.substr(pos,len);
    • (ASCIIコード)

このレベルで知っておくと良いTipsです.

計算結果の小数点以下切り捨て,小数点以下切り上げ

整数型の割り算の計算結果は使用する言語によって異なりますが,多くの言語では切り捨てです.
a÷bの計算結果を切り上げする場合には(a+b-1)/bと書くと計算結果が切り上げになります.
言語によっては,切り捨てに対応するfloor関数や切り上げに対応するceil関数などが提供されています.

B問題

B問題は簡単なプログラミングなどが問われます.
このあたりからは,アルゴリズムの効率を表す計算量やプログラムの実行時間も気にする必要があります.
問題の傾向としてはA問題を少しひねった感じだと思います.
例えば,次のようなものが挙げられます.

  • 余りを使う問題

B: トリボナッチ数列 - AtCoder Beginner Contest 006 | AtCoder

  • 大小比較を少しひねった問題

B: 投票 - AtCoder Beginner Contest 008 | AtCoder

  • 条件に合うものを数える問題 (最近のコンテストの難易度だとB問題相当だと思います)

A: Best Body - AtCoder Beginner Contest 022 | AtCoder

  • 簡単な数学が必要となる問題

B: N重丸 - AtCoder Beginner Contest 026 | AtCoder

このあたりから自分でアルゴリズムを考える必要がありますが,最初は全探索をベースに考えると良いと思います.

このレベルで知っておくと良いTipsです.

オーバーフロー アンダーフロー

答えがint型の範囲で収まるのかどうかは気を付けましょう.

文字列比較

B: 辞書式順序 - AtCoder Beginner Contest 007 | AtCoder
文字列の比較には「aa,ab,ac,...,az,ba,...」といった辞書順が用いられることが多いです.
C++において辞書順による2つの文字列aとbの比較はa < bなどでできます.
文字列の問題には条件を満たす辞書順最小の文字列を答えさせる問題もあります.

mod n

「○○を満たすものは何通りありますか?」という数え上げの問題で答えが非常に大きくなることがあります.
そうなると多倍長整数など必要になり,アルゴリズムの評価がしづらくなります.そこで答えをnで割った余りを出力させます.
こうすることで,計算途中で多倍長整数の実装する必要などがなくなります.modの世界において,足し算,引き算,掛け算はできます.しかし,割り算はできない場合もあるので注意しましょう.

小数の出力

答えで小数を出力させる問題も出てきます.この時に小数点以下の桁数が足りないとWAになる可能性があります.これを回避するため
には,小数点以下もできるだけ出力させると良いです.小数点以下20桁くらい出力しておけば大丈夫でしょう.

円周率

円周率は定数として扱いましょう.
自分はよく次の形を使います.const double PI=acos(-1.0);

C問題

C問題はアルゴリズムの基本などが問われます.
このレベルで必要になるアルゴリズムは以下の通りです.

全探索 ビット演算 再帰

B: 価格の合計 - AtCoder Beginner Contest 014 | AtCoder
C: 高橋くんのバグ探し - AtCoder Beginner Contest 015 | AtCoder
状態数がk^nとなるような全探索の問題も出てきます.
ビット演算を使ったり,再帰を用いて解いたりします.

ソート

C: AtCoderプログラミング講座 - AtCoder Beginner Contest 003 | AtCoder
競技プログラミングにおいてソートを実装する必要はあまりありません.
多くのプログラミング言語では,ライブラリとしてソート関数が提供されています.
C++におけるN個の要素をソートする関数std::sortの最悪計算量はO(NlogN)です.
問題を解くときに,入力例をソートしてみると分かることがいろいろあるかもしれません.

二分探索

C: 収集王 - AtCoder Beginner Contest 023 | AtCoder
ソートされた配列に対して効率良く値を検索するための方法です.
このアルゴリズムの計算量は,長さNの配列に対してO(log N)と高速です.
C++では,std::lower_boundやstd::upper_boundとしてライブラリが提供されています.

メモ化再帰,動的計画法

C: 123引き算 - AtCoder Beginner Contest 011 | AtCoder
小さいサイズの問題を解いて,その計算結果を記憶して,より大きなサイズの問題を解く方法です.
漸化式みたいなものをイメージすると良いです.
一番簡単な例はフィボナッチ数列です.a[0]=a[1]=1; a[n]=a[n-1]+a[n-2];
フィボナッチ数列が必要になった時に,一度a[n]を計算すれば再度計算する必要がなくなります.
詳しくは以下のスライドやサイトなどを見ると良いでしょう.
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
プログラミングコンテストでの動的計画法

データ構造
  • スタック stack
  • キュー queue
  • 優先度付きキュー priority_queue
  • 平衡二分木 set

C: 高橋くんと魔法の箱 - AtCoder Beginner Contest 019 | AtCoder
C: 数を3つ選ぶマン - AtCoder Beginner Contest 028 | AtCoder

多くのプログラミング言語でこれらのデータ構造はライブラリで提供されています.
グラフアルゴリズムの実装で使われるので知っておくべきでしょう.
また,スタックとキューに関しては実装が簡単なので自分で実装しても良いでしょう.
プライオリティキューが提供されていない言語は,skew heap(blog)を使うと実装が楽です.

グラフ理論とグラフアルゴリズム (問題例を追加しました.)

C: 壁抜け - AtCoder Beginner Contest 020 | AtCoder
C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder
C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder

ここでいうグラフ理論は棒グラフ,折れ線グラフではなく,頂点と辺で構成される関係のことを指します.
グラフ理論についてはネット上に色々な資料があるので調べてみましょう.

また,プログラムの中でグラフの表現する方法は隣接行列と隣接リストの2つがあります.
この2つはメモリ使用量と方式が違うので使い分けて違います.
以下はグラフアルゴリズムについて簡単に紹介しておきます.詳しくは他の資料を調べてみましょう.

  • 探索
    • dfs 深さ優先探索 再帰やstackなどを用いて実装  
    • bfs 幅優先探索 queueを用いて実装 重み無しグラフ上で最短経路を求めるのに使ったりもする..
  • 最短路 (Nは頂点の数,Mは辺の本数)
    • ワーシャル・フロイド 全頂点間最短路を3重ループで求められます.計算量はO(N^3)
    • ダイクストラ 単一始点最短路を求めるアルゴリズム 優先度付きキューを用いることで計算量はO(MlogN)

グラフ理論やグラフアルゴリズムの参考資料 (全探索やデータ構造や累積和なども載っています)
競技プログラミング練習会2015 Normal 第2回
競技プログラミング練習会2015 Normal 第3回

累積和,imos法 (最近のコンテストの難易度だとC問題相当だと思います)

B: 自動ドア - AtCoder Beginner Contest 024 | AtCoder
区間や矩形の塗りつぶしや,その中の和などを効率良く求める問題でよく使われるアルゴリズム (Atcoderではよく出る印象があります.)
プログラミングコンテストチャレンジブックの初級編では出てきまんせんが,この辺りのレベルで知っておくべきアルゴリズムだと思います.

しゃくとり法

C: 飛行機乗り - AtCoder Beginner Contest 030 | AtCoder
数列のインデックスを条件によって移動させて,しゃくとり虫みたいに調べていくアルゴリズム
上の問題だと,2つの数列のインデックスを交互に移動させていくと解けると思います.

D問題

D問題は発想やアルゴリズムの応用(や難しいアルゴリズム)などが問われます.
問題の全体的な傾向としては特にないと思います.(最近は,難しいアルゴリズムではなく,知っているアルゴリズムを組み合わせる形が多いかな)
D問題において重要な点は,難易度は振れ幅が大きいので解ける問題から解いてみましょう. (例えば,ABC020の問題の満点解法はSRM Div1 Medレベルにあたります.)
このあたりのレベルの問題を解けるようになるためには,ABC以外にもAtcoder Regular Contestなどたくさんの問題も解きましょう.また,競技プログラミングやアルゴリズムの本を読んだり,いろいろなサイトを見て勉強しましょう.
D問題が数問解けるようになったら,中級者レベルだと思います.

最後に

計124問解くのはなかなか大変ですが,解説も親切なので1日に数問解くなどの目標を設けて,練習していくと良いと思います.
(ARC埋めも行っていますが残り75問,いつ終わるのだろうか...)