競プロ脱超初心者のコツ（Beginners Selection解説）

Pocket

こんにちは、ふるやん（@furuya1223）です。

今回の記事では、この春多く誕生したであろう競プロ超初心者に向けて、超初心者を脱するためのコーディングのコツについて解説したと思います。

この記事を読んでコーディングすれば、初心者ぐらいにはなれると思います。

難問を解くための考え方よりもコーディングの話が中心になります。

言語はC++です。gccでコンパイルしているC言語使いの方は、

g++ -std=c++14 -o main main.cpp

みたいにコンパイルすればC++が使えるかもしれません。できなければググってください。

Visual Studio Community などを使っている場合は、そのままC++が使えると思います。

想定読者

C言語あるいはC++の基本的な書き方が分かっている

競技プログラミングを始めてみたくてAtCoderに登録したけど何をすればいいか分からない・問題がうまく解けない

AtCoder Beginners Selection

形式に慣れるための例題と、初心者向けに選ばれた10の過去問で構成された問題セットです。

とりあえずこれを解いてみましょう。

それぞれの解説のコーディングのコツを書いていきます。

はじめに：C++の書き方

C++はC言語と似ています。

C言語の書き方が完全に動くので、C言語として書いてもいいですが、C++特有の便利な機能を使ってみましょう。

まず、stdio.h ではなく iostream を include しましょう。

そして、#include のあとに using namespace std; の一行を書きましょう。これは副作用があるので業務やチーム開発では禁止されますが、競プロで使う場合は副作用が無視できて利便性が勝ります。とりあえずは気にせず書いておきましょう。

using namespace std; が行っていることと問題点について知りたい方は「C++ 名前空間」などで検索してみてください。

簡単に言うと、C++ では同じ名前の異なる変数や関数を作れないので、std::max() というように、変数や関数に対して「std」という「名字のようなもの（名前空間）」をつけることができるようになっています。こうすることで、max という名前を独自に使いたい場合に、別の名字（たとえば hoge）を用意して「hoge::max」と記述して「std::max」と区別できるようになり、両方使えるようになります。

C++ の標準機能には基本的に「std::」が付きますが、「using namespace std;」を書いておくと、「std::」を省略することができるようになり便利です。ただし、これをすると名前空間での区別ができなくなるので、すでに「std::」の中にある名前の変数や関数（例えば max）を新たに作ったときに、変な挙動をするおそれがあります。さらに、そうなったときに名前空間が原因であることに気づくのは難しいので、一般的に using namespace std; は良くないとされています。

ただし、競技プログラミングという特殊な環境においては、文字数を減らして書きやすくするために using namespace std; を用いる方が多くいます。副作用を踏むことが稀であり、完全に個人で行い競プロ以外で再利用しないコードであるため、副作用のデメリットがさくっと書けることのメリットを下回るという考え方です。

main関数はC言語と同じです。

#include <iostream>

using namespace std;

int main(void) {
    // ここに処理を書く
    return 0;
}

#include <iostream>

using namespace std;

int main(void) {

// ここに処理を書く

return 0;

}

これがコードの基本形になります。

はじめてのあっとこーだー

整数と文字列を受け取って、整数の合計と文字列を半角スペース区切りで出力する問題です。

C++においては、入力は cin >> {変数} >> {変数}; などとして、複数の入力を一気に受け取れます。cinは「標準入力ストリーム」と呼ばれるものです。（using namespace std; をしていないと std::cin と書く必要があります）

半角スペースや改行などで区切られた入力を受け取れるので、今回は整数3つと文字列1つを一気に受け取れます。

文字列には、string というクラス（型みたいなもの）を使いましょう。char配列よりも遥かに便利です。（using namespace std; をしていないと std::string と書く必要があります）

string型の変数は、s[1]などで文字にアクセスできます。また、 s.size() で文字列の長さを取得できます。便利。

出力は、入力の逆で cout << {表示する値} << {表示する値} << endl; のようにします。coutは「標準出力ストリーム」と呼ばれ、endlは「改行」です。（using namespace std; をしていないと std::cout, std::endl と書く必要があります）

今回は a+b+c と半角スペースと文字列 s と改行を出力します。

全体のコードはこんな感じですね。

#include <iostream>
 
using namespace std;
 
int main(void) {
    int a, b, c;
    string s;
 
    // 入力を一気に取得（半角スペースも改行も同じ空白文字扱いなので可能）
    cin >> a >> b >> c >> s;
 
    // 出力
    cout << a + b + c << " " << s << endl;
 
    return 0;
}

#include <iostream>

using namespace std;

int main(void) {

int a, b, c;

string s;

// 入力を一気に取得（半角スペースも改行も同じ空白文字扱いなので可能）

cin >> a >> b >> c >> s;

// 出力

cout << a + b + c << " " << s << endl;

return 0;

}

ABC086A – Product

10000以下の正整数が2つ与えられて、積が偶数かどうかを判定する問題。

C++のint型は基本的に符号付き32bit整数なので、20億ぐらいまでしか扱えません。許容上限よりも大きな値を計算しようとするとオーバーフローして変な値になります。

ただし、今回は最大でも1億なので、その心配はありません。

偶奇の判定は、2で割ったあまりが0か1かを見ればいいです。あまりを計算するには % ですね。

a, b を受け取って、積を2で割ったあまりが0か1かで条件分岐して、対応する文字列を出力すればいいです。

#include <iostream>
 
using namespace std;
 
int main(void) {
    int a, b;
    cin >> a >> b;
    if ((a * b) % 2 == 0) {
        cout << "Even" << endl;
    } else {
        cout << "Odd" << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main(void) {

int a, b;

cin >> a >> b;

if ((a * b) % 2 == 0) {

cout << "Even" << endl;

} else {

cout << "Odd" << endl;

}

return 0;

}

ABC081A – Placing Marbles

1, 0からなる3文字の文字列が与えられます。1の個数を出力しましょう。

string s;で受け取って、s[0], s[1], s[2] がそれぞれ1かどうかを確認すればいいです。

ただし、if文をいっぱい書くのは面倒なので、ループで書いてみましょう。

ループは for 文で書くのですが、バグをへらすために rep マクロというものを使いましょう。

#define rep(i, n) for(int i = 0; i < n; i++)

を using namespace std; の直後に書いておくと、for文で 0〜n まで i を増やすループが rep(i, 3){…} で書けるようになります。

string 型の s に対して添字で文字を取得するとき、s[i] の型は int ではなく char なので、s[i] == 1 としてはいけません。 s[i] == ‘1’ というように、シングルクォーテーションで囲った ‘1’ と比較します。あくまで「文字の ‘1’ と同じかどうか」です。

#include <iostream>
 
using namespace std;
 
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    string s;
    cin >> s;
    int ans = 0; // 数を数えるための変数。これが答えになる
    rep(i, 3) {
        if (s[i] == '1') {
            ans++; // '1'があればansを1増やす
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

string s;

cin >> s;

int ans = 0; // 数を数えるための変数。これが答えになる

rep(i, 3) {

if (s[i] == '1') {

ans++; // '1'があればansを1増やす

}

cout << ans << endl;

return 0;

}

中級テクニック

string はコンテナクラスなので、begin と end を持ち、イテレータによる走査ができます。また、コンテナを走査してある値と一致するものの個数を数える count が <algorithm> を include すると使えるようになります。

ということで、count(s.begin(), s.end(), ‘1’) で文字列 s に含まれる ‘1’ の個数を得られます。

#include <algorithm>
#include <iostream>
 
using namespace std;
 
int main(void) {
    string s;
    cin >> s;
    cout << count(s.begin(), s.end(), '1') << endl;
    return 0;
}

#include <algorithm>

#include <iostream>

using namespace std;

int main(void) {

string s;

cin >> s;

cout << count(s.begin(), s.end(), '1') << endl;

return 0;

}

ABC081B – Shift only

数列が与えられるので、「全部2で割る」という操作を、奇数ができるまで行うときの操作回数を出力します。

数列の長さが200以下なので、操作をシミュレートしても十分間に合います。

C++を使う場合、配列はやめて vector （可変長配列）というものを使いましょう。

vector<型> 変数名(要素数, 初期値);

というように宣言すると、配列が作れます。同じ値で埋めない場合は初期値を省略できます。要素数0の配列を作るときは、要素数を省略できます。

vectorは、末尾に要素を追加することができます。変数名.push_back(値) という書き方をします。

もちろん、通常の配列のように添字アクセスができるので、今回はそちらを使います。

vector を使うには、<vector> を include する必要があります。しましょう。

vector<int> A(N); として、ループで要素を受け取ります。

あとは、操作回数を持つ変数 ans = 0; を用意して、「配列を見て偶数なら2で割る、奇数があれば操作を終える。全部偶数だったら ans を 1 増やす」という処理を繰り返します。無限ループで実装できますね。

どんな正整数も 2 で割り続ければいつか 1 になるので、ループは必ずどこかで終わります（奇数が発生します）。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) {
        cin >> A[i];
    }
    int ans = 0;
    while (true) {
        bool all_even =
            true; // 全て偶数であればtrue, 奇数が見つかればfalseにする
        rep(i, N) {
            if (A[i] % 2 == 1) {
                // 奇数がある
                all_even = false;
                break;
            } else {
                // 偶数
                A[i] /= 2;
            }
        }
        if (all_even) {
            // 全て偶数
            ans++;
        } else {
            // 奇数があればループ終了
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

int N;

cin >> N;

vector<int> A(N);

rep(i, N) {

cin >> A[i];

}

int ans = 0;

while (true) {

bool all_even =

true; // 全て偶数であればtrue, 奇数が見つかればfalseにする

rep(i, N) {

if (A[i] % 2 == 1) {

// 奇数がある

all_even = false;

break;

} else {

// 偶数

A[i] /= 2;

}

if (all_even) {

// 全て偶数

ans++;

} else {

// 奇数があればループ終了

break;

}

cout << ans << endl;

return 0;

}

中級テクニック

この問題では、各要素を2で割れる回数の最小値が答えになります。

そのため、2で割れる回数を計算する関数を作成し、すべての要素についてその値を計算しながら最小値を計算することで答えが得られます。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
// n について何回操作できるか
int able(int n) {
    int ans = 0;
    while (n % 2 == 0) { // n が偶数である間だけループ
        n >>= 1;         // n を 2 で割る
        ans++;
    }
    return ans;
}
 
int main(void) {
    int N;
    cin >> N;
    int ans = 10000; // 答えとしてありえないくらい大きな値にしておく
    rep(i, N) {
        int a;
        cin >> a;
        ans = min(ans, able(a)); // 操作可能回数の最小値を保持
    }
    cout << ans << endl;
 
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

// n について何回操作できるか

int able(int n) {

int ans = 0;

while (n % 2 == 0) { // n が偶数である間だけループ

n >>= 1; // n を 2 で割る

ans++;

}

return ans;

}

int main(void) {

int N;

cin >> N;

int ans = 10000; // 答えとしてありえないくらい大きな値にしておく

rep(i, N) {

int a;

cin >> a;

ans = min(ans, able(a)); // 操作可能回数の最小値を保持

}

cout << ans << endl;

return 0;

}

ABC087B – Coins

500円玉、100円玉、50円玉がそれぞれ A, B, C 枚あるときに、ぴったり X 円をつくる方法は何通りあるか、という問題です。

A, B, C が小さいので、「500円玉を i 枚、100円玉を j 枚、50円玉を k 枚使う」という全パターンについて、X 円になっているかチェックするという方法で間に合います。

計算量は O(ABC) ですね。

コードは以下のようになります。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    rep(i, a + 1) {
        // 500円玉を i 枚使う
        rep(j, b + 1) {
            // 100円玉を j 枚使う
            rep(k, c + 1) {
                // 50円玉を k 枚使う
                // 合計金額が x なら ans を 1 増やす
                if (i * 500 + j * 100 + k * 50 == x) ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

int a, b, c, x;

cin >> a >> b >> c >> x;

int ans = 0;

rep(i, a + 1) {

// 500円玉を i 枚使う

rep(j, b + 1) {

// 100円玉を j 枚使う

rep(k, c + 1) {

// 50円玉を k 枚使う

// 合計金額が x なら ans を 1 増やす

if (i * 500 + j * 100 + k * 50 == x) ans++;

}

cout << ans << endl;

return 0;

}

中級テクニック

500円玉と100円玉を使う枚数を決めた時点で、使うべき50円玉の枚数が確定するので、3つ目のループは実は不要です。

500円玉と100円玉を指定数使ったときの残額について、「残額が正、50の倍数、50C以下」を満たせばansが1増えます。（今回の問題では X が50の倍数なので、50の倍数判定は不要です）

#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    rep(i, a + 1) {
        // 500円玉を i 枚使う
        rep(j, b + 1) {
            // 100円玉を j 枚使う
            // 残額を計算
            int rest = (x - 500 * i - 100 * j);
            if (rest >= 0 && rest % 50 == 0 && rest / 50 <= c) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

int a, b, c, x;

cin >> a >> b >> c >> x;

int ans = 0;

rep(i, a + 1) {

// 500円玉を i 枚使う

rep(j, b + 1) {

// 100円玉を j 枚使う

// 残額を計算

int rest = (x - 500 * i - 100 * j);

if (rest >= 0 && rest % 50 == 0 && rest / 50 <= c) {

ans++;

}

cout << ans << endl;

return 0;

}

もっと計算をすると、2番目のループも不要になります。500円玉を払ったあとの残金の払い方について、「100円玉をできる限り多く使う方法」と「100円玉をできる限り少なく使う方法」が分かれば、その間の方法でも払えることになるので、パターンの数を簡単に計算できます。今はちょっと面倒なのでやりませんが。

ABC083B – Some Sums

以上 N 以下の整数のうち、10進法での各桁の和が A 以上 B 以下であるものの総和を出力します。

N が小さいので、1から N まで全部見て桁和を計算して、条件を満たす場合に足せばいいです。

桁和は、「10で割ったあまり（一の位）を足す」「10で割る（切り捨て）」を繰り返せば得られます。

今回は、「1からNまでループ」をしたいので、0ではない好きな値から始められるループを用意してみましょう。名前の流儀はいろいろありますが、私は

#define repr(i, a, b) for (int i = a; i < b; i++)

としています。最後の r は range のつもり。範囲を設定できるという意味で。まあこの辺はお好きに。

ということで、コードはこんな感じ。

#include <iostream>
#include <vector>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
 
// 各桁の和を計算する関数
int digit_sum(int n) {
    int ans = 0;
    while (n > 0) {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}
 
int main(void) {
    int N, A, B;
    cin >> N >> A >> B;
    int ans = 0;
    repr(i, 1, N + 1) { // i=1からi=Nまでループ
        int ds = digit_sum(i);
        if (A <= ds && ds <= B) {
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = a; i < b; i++)

#define rep(i, n) for (int i = 0; i < n; i++)

// 各桁の和を計算する関数

int digit_sum(int n) {

int ans = 0;

while (n > 0) {

ans += n % 10;

n /= 10;

}

return ans;

}

int main(void) {

int N, A, B;

cin >> N >> A >> B;

int ans = 0;

repr(i, 1, N + 1) { // i=1からi=Nまでループ

int ds = digit_sum(i);

if (A <= ds && ds <= B) {

ans += i;

}

cout << ans << endl;

return 0;

}

ABC088B – Card Game for Two

数列が与えられるので、2人で交互に、合計が大きくなるように数を取っていきます。このとき、先手と後手の得点差はいくらになるでしょう、という問題です。

ちょっと試してみると分かると思いますが、常に「残っている数のうち最大のものを取る」という方策が最善です。まあそりゃそうですわな。

ということで、両者が最適な行動をとったとき、「大きい順に交互に取っていく」という動きになります。

したがって、vectorのソートが必要になります。ソートして、大きい順に交互に割り振っていきます。

C++では、vectorのソートにはsort()が使えます。<algorithm>というヘッダをincludeしましょう。

sortの中身は、ソートする範囲の始点と終点を表すものを入れます。今回は a が vector<int> の変数だとして、

sort(a.begin(), a.end());

とすると、昇順（小さい順）にソートされます。

ですが、今回は降順（大きい順）にソートしたいです。本来と逆の向きにソートしたい場合は、

sort(a.rbegin(), a.rend());

とします。r は reverse を表すのだと思います。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) {
        cin >> a[i];
    }
    sort(a.rbegin(), a.rend()); // 降順ソート
 
    int alice = 0, bob = 0;
    // 交互に振り分け
    rep(i, N) {
        if (i % 2 == 0) {
            alice += a[i];
        } else {
            bob += a[i];
        }
    }
    // 得点差を出力
    cout << alice - bob << endl;
 
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

int N;

cin >> N;

vector<int> a(N);

rep(i, N) {

cin >> a[i];

}

sort(a.rbegin(), a.rend()); // 降順ソート

int alice = 0, bob = 0;

// 交互に振り分け

rep(i, N) {

if (i % 2 == 0) {

alice += a[i];

} else {

bob += a[i];

}

// 得点差を出力

cout << alice - bob << endl;

return 0;

}

中級テクニック？

変な書き方でコード量を減らせます。

なぜこれでうまくいくか考えてみるのも面白いかもしれません。ソートが昇順（小さい順）であることに注意。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) {
        cin >> a[i];
    }
    sort(a.begin(), a.end()); // 昇順ソート
    int ans = 0;
    rep(i, N) {
        ans = a[i] - ans;
    }
    cout << ans << endl;
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

int N;

cin >> N;

vector<int> a(N);

rep(i, N) {

cin >> a[i];

}

sort(a.begin(), a.end()); // 昇順ソート

int ans = 0;

rep(i, N) {

ans = a[i] - ans;

}

cout << ans << endl;

return 0;

}

ABC085B – Kagami Mochi

数列が与えられるので、そこからいくつか選んで好きに並べ替えて「だんだん小さくなる」ように並べるときの、作れる列の最大長を出力します。

要は、「同じ数が無いように選ぶ」ということです。したがって、「数列に含まれる、相異なる数の個数」を出力すれば大丈夫です。

今回は、d[i] の値は1〜100なので、1〜100について「あるかないか」を記録すれば大丈夫です。

vector<int> exist(101, 0); で長さ101の、0で埋められた配列が得られるので、存在するものを1にして、最後に1の個数を見ればよいです。（101にしているのは、exist[100]を許容するためです）

existについて、あれば1、なければ0としているので、1の数を数えるときに、単純にexistの値を合計するだけで解けます。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main(void) {
    int N;
    cin >> N;
    vector<int> exist(101, 0);
    rep(i, N) {
        int d;
        cin >> d;
        exist[d] = 1;
    }
    int ans = 0;
    repr(i, 1, 101) { // i=1〜100までループ
        ans += exist[i];
    }
    cout << ans << endl;
 
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = a; i < b; i++)

#define rep(i, n) for (int i = 0; i < n; i++)

int main(void) {

int N;

cin >> N;

vector<int> exist(101, 0);

rep(i, N) {

int d;

cin >> d;

exist[d] = 1;

}

int ans = 0;

repr(i, 1, 101) { // i=1〜100までループ

ans += exist[i];

}

cout << ans << endl;

return 0;

}

中級テクニック

ソート済み vector に対して <algorithm>ヘッダにある unique を使用すると、重複要素を除去した vector を作ってくれます。ただし、vector の長さは変えないので、「重複要素を除去したvector+空きスペース」という vector に変えられます。

そこで、unique が「重複要素を除去した vector の終端イテレータを返す」という性質を利用して、vector.erase(始点, 終点) で vector の要素を削除する機能の組み合わせます。

そうすると、 d.erase(unique(d.begin(), d.end()), d.end()) で、重複要素を削除して長さも小さくなった vector に変えることができます。d はソート済みです。

また、vector の長さは .size() で得られるので、以下のようにして解くこともできます。

今回は、sort と unique で .begin(), .end() を書くので、マクロとして define しています。

#define all(a) a.begin(), a.end()

の部分ですね。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
 
int main(void) {
    int N;
    cin >> N;
    vector<int> d(N);
    rep(i, N) cin >> d[i];
    sort(all(d));
    d.erase(unique(all(d)), d.end());
    cout << d.size() << endl;
 
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = a; i < b; i++)

#define rep(i, n) for (int i = 0; i < n; i++)

#define all(a) a.begin(), a.end()

int main(void) {

int N;

cin >> N;

vector<int> d(N);

rep(i, N) cin >> d[i];

sort(all(d));

d.erase(unique(all(d)), d.end());

cout << d.size() << endl;

return 0;

}

cout する直前で、d の要素は重複なしの昇順になっています。

さて、これで残り3問なわけですが、残り3問は全てC問題です。つまり、今までより難しいです。つまり、解説が面倒です。

ということで、この記事は一旦ここで切り上げて公開します。

長くなったので、残り3問の記事を書いても、別の記事にすると思います。

それでは皆さん、頑張ってください。

質問があれば私（@furuya1223）に自由に聞いてくださいね。

Pocket