2025.04.29 2025.04.30

【C++】AtCoder Programming Practice 問題解説まとめ

mintson

Contents

基礎練習問題

– PracticeA: Welcome to AtCoder

記事での解説は →https://mintsonh.com/archives/1368

– ABC086A: Product

この問題では整数a,bを掛け合わせた数が偶数(Even)か奇数(Odd)のどっちかを判断する問題です。

#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;
    
    if ((a * b) % 2 == 0) {
        std::cout << "even";
    } else {
        std::cout << "odd";
    }

    return 0;
}

今回は、if文を用いて、掛け合わせた結果を剰余演算子（%）で2による余りを求めて処理します。

0だったらEven、1(それ以外)だったらOddという感じです。

– ABC081A: Placing Marbles

三つのマスに0か1が書かれていて、それをs1,s2,s3をそのままインプットする形の問題です。

#include <iostream>
#include <string> 

int main() {
    std::string s;
    std::cin >> s;
    int count = 0;

    if (s[0] == '1') count++;
    if (s[1] == '1') count++;
    if (s[2] == '1') count++;

    std::cout << count << std::endl;

    return 0;
}

入力される文字に区切りがないためそのまま文字列(string)の形で取得してから各位が1,0のどっちかを判断していく戦略を取りました。

if文で1だったら、countに1プラスしていきます。

– ABC081B: Shift only

この問題は全文の数字が共通で何回まで2で割れるかを解いている問題です。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    int min = INT_MAX;

    for (int i = 0; i < n; ++i) {
        int count = 0;
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            ++count;
        }
        min = std::min(min, count);
    }

    std::cout << min << std::endl;
    return 0;
}

まずはたくさんの数字を配列(vector)を使ってインプットをします。

今回は一つ一つ2で何回割れるのかをカウントします。
その割った回数を<algorithm>ライブラリのstd::minを使用して、割れた数の中で最小の数を求めることができます。

– ABC087B: Coins

この問題は500円(A)と100円(B)、50円(C)の四つの貨幣を使って、X円に丁度なる方法は何通りあるのかについて解いている問題です。

#include <iostream>

int main() {
    int A, B, C, X;
    std::cin >> A >> B >> C >> X;

    int count = 0;

    for (int i = 0; i <= A; ++i) {
        for (int j = 0; j <= B; ++j) {
            for (int k = 0; k <= C; ++k) {
                if (500 * i + 100 * j + 50 * k == X) {
                    ++count;
                }
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}

本日はforループを使用して問題を解いていきました。

0枚からその貨幣の枚数までを複数層のループにより、すべての金額の可能性を足し合わせた結果Xになるのをカウントします。

– ABC083B: Some Sums

この問題は1からNの整数の中から各桁の数字を足し合わせた数字がAより大きくて、Bより小さくなるのはなん通りあるのかを求める問題です。

#include <iostream>

int main() {
    int N, A, B;
    std::cin >> N >> A >> B;

    int sum = 0;

    for (int i = 1; i <= N; ++i) {
        int x = i;
        int digit_sum = 0;

        while (x > 0) {
            digit_sum += x % 10;
            x /= 10;
        }

        if (digit_sum >= A && digit_sum <= B) {
            sum += i;
        }
    }

    std::cout << sum << std::endl;
    return 0;
}

今回の場合はforループでi=1からNまでの整数を一つ人つ試していきました。

whileループではその数字が0かそれ以下になるまで実行していきました。
例えば1１1の数字の10で割ったあまりは1になり、それをdigit_sumにたし合わせます。
その101を最後に1１で割り10します。

その次に11を10で割ったあまり1をまたdigit_sumに足し合わせて、これを繰り返すと3になります。

最後にdigit_sum が A ≤ x ≤ Bであれば何通りの合計(sum)にカウントしていきます。

– ABC088B: Card Game for Two

この問題はN枚あるカードをAliceとBobが1人ずつカードを取っていき、そのカードを取る法則はお互いがその時々の最善策を取ることが求められています。

つまりたくさんのカードから常に最大の数字を取るということです。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int N;
    std::cin >> N;
    std::vector<int> a(N);

    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end(), std::greater<int>()); 

    int alice = 0, bob = 0;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            alice += a[i];  
        } else {
            bob += a[i];   
        }
    }

    std::cout << (alice - bob) << std::endl;

    return 0;
}

この問題は先ほどの問題同様vector配列を使ってまずはN枚の数字を入力します。

そして最適になるように大きい数字から小さい順に並び替えていきます。
これによりAliceとBobが交互に取る時にきちんと最大を取れるようになりました。

– ABC085B: Kagami Mochi

この問題は鏡餅を並べる問題です。
大きいのから小さいのを上に重ねていくのが何段になるのかを求めていきます。

#include <iostream>
#include <map>

int main() {
    int N;
    std::cin >> N;

    std::map<int, int> mochi;
    for (int i = 0; i < N; i++) {
        int d;
        std::cin >> d;
        mochi[d]++; 
    }

    std::cout << mochi.size() << std::endl;

    return 0;
}

今回の重要なポイントは、「同じ直径の餅は重ねられない（＝重複する餅は加算しない）」という点です。

そのため、今回は <map> ライブラリを使用して餅の直径を管理しました。
map は キー（直径）を自動的に重複なしで保持してくれるため、入力された餅の直径が何回出てきたかも同時に記録できます。

これにより、vector を使ってソートや重複削除を行うよりも簡単に、
map のサイズを出力するだけで、重複のない直径の種類数（＝最大段数）を求めることができます。

– ABC085C: Otoshidama

この問題はお年玉の10000 円札、5000 円札、1000 円札の枚数は決まっている状態で合計金額がその枚数下であり得るのかを問います。

#include <iostream>

int main() {
    int N, Y;
    std::cin >> N >> Y;

    for (int x = 0; x <= N; ++x) {
        for (int y = 0; y <= N - x; ++y) {
            int z = N - x - y;
            int total = 10000 * x + 5000 * y + 1000 * z;
            if (total == Y) {
                std::cout << x << " " << y << " " << z << std::endl;
                return 0;
            }
        }
    }

    std::cout << "-1 -1 -1" << std::endl;
    return 0;
}

今回の問題は合計が枚数と一致する場合が複数の場合でも一つだけでいいのでtotal==Yになった瞬間にループをretrun 0;終わらせます。

そしてもしその枚数がありえない場合は-1 -1 -1を出力すれば完成です。

– ABC049C: 白昼夢（Daydream）

この問題はdream dreamer erase eraserを組み合わせてた文字列Tと与えらてた文字列Sと一致できるかを問いている問題です。

#include <iostream>
#include <string>
#include <regex>
using namespace std;

int main() {
    string S;
    cin >> S;

    regex re("(dream|dreamer|erase|eraser)*");

    cout << (regex_match(S, re) ? "YES" : "NO") << endl;

    return 0;
}

正規表現(regex)を使う回答がものすごく良かったので、これを採用しました。
これにより、文字列Sと比較をしてマッチするかどうかを判断してくれます。

–ABC086C – Traveling

この問題は(0,0)のマスから移動をして、数秒後には別の目的地につきたいと思っている方が、果たして辿り着ける時間と距離が設定されているのかについてです。

移動の方法は左右上下のどちらかに必ず一秒に1マス移動しないといけないのでその場に止まれないところに注意しましょう。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    int prev_t = 0, prev_x = 0, prev_y = 0;
    bool possible = true;
    
    for (int i = 0; i < N; ++i) {
        int t, x, y;
        cin >> t >> x >> y;
        
        int time_diff = t - prev_t;
        int dist = abs(x - prev_x) + abs(y - prev_y);
        
        if (dist > time_diff || (time_diff - dist) % 2 != 0) {
            possible = false;
            break;
        }
        
        prev_t = t;
        prev_x = x;
        prev_y = y;
    }
    
    if (possible) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

今回の場合は条件分でもし移動距離が移動可能時間より大きかったら、そこまで辿り着けないことになります。

それと同じところに入れないので、もしも時間が余っていたとしても奇数の場合往復までの時間がないため辿り着けないことになります。

最後に

今回はAtcoderの初心者向けの問題を解いていきました。

感想としてはAtcoderの入門なので難しいアルゴリズムや数学が求められていないため非常に初心者に優しい問題だと思われます。

この記事で書いた解き方以外にももっとスマートでいい回答があったりするので、色んな人が書いたコードを見ることも非常に勉強になってためになります。

競技プログラミングなので問題が解ければいい条件下なので、例えばusing namespace std;でstdを省略したり、include <bits/stdc++.h>で必要なライブラリーを全て取り入れたりするなどができたりします。

答えが人それぞれで、みんな違うコードになるのはやはり競プロの面白さだと思うので、ぜひこれからもコードをエンジョイしていきましょう！

ABOUT ME

基礎練習問題

– PracticeA: Welcome to AtCoder

最後に

【C#/C++/C】PracticeA - Welcome to AtCoder解説してみた！【競技プログラミング】