AtCoder Beginners Selectionの実施記録(C++)

概要

表題のプログラミング言語でAtCoder Beginners Selectionを実施記録した際の記録です
基本文法の学習が目的です

https://atcoder.jp/contests/abs
AtCoder Beginners Selectionとは？
このコンテストは、「AtCoderに登録したけど何をしていいか分からない・・・！」という人に向けて作られた、初心者向け問題集です。
問題は、dr.kenさんの、「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」から選出しています。

基本的には以下ができれば大体の問題を解けるようになっている。

• 標準入力
• 標準出力
• 四則演算
• 条件分岐
• 文字列操作
• ループ
• 配列の操作
• 全通りの探索
• 組み込み関数等の利用
• ソート
• 集合
• 二次元配列の操作

PracticeA - Welcome to AtCoder

PracticeA - Welcome to AtCoder

問題文
高橋君はデータの加工が行いたいです。
整数 a,b,cと、文字列 s が与えられます。 a+b+c の計算結果と、文字列 s を並べて表示しなさい。

制約
1≤a,b,c≤1,000
1≤∣s∣≤100

入力
入力は以下の形式で与えられる。
a
b c
s

出力
a+b+c と s を空白区切りで 1 行に出力せよ。

基本的な標準入力、標準出力、四則演算ができればOK

main.cpp

#include <iostream>
#include <string>

using namespace std;

int main()
{
  // a,b,cをそれぞれ入力
  int a, b, c;
  cin >> a >> b >> c;

  // sを入力
  string s;
  cin >> s;

  // a+b+cとsを空白区切りで出力
  cout << a + b + c << " " << s << endl;

  return 0;
}

ABC086A - Product

ABC086A - Product

問題文
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

制約
1 ≤ a,b ≤ 10000
a,b は整数

入力
入力は以下の形式で標準入力から与えられる。
a b

出力
積が奇数なら Odd と、 偶数なら Even と出力せよ。

基本的な標準入力、標準出力、四則演算、条件分岐ができればOK

main.cpp

#include <iostream>

int main()
{
    int a, b;
    std::cin >> a >> b;

    // aとbの積を計算します
    int product = a * b;

    // 積が偶数か奇数か判定します
    if (product % 2 == 0)
    {
        std::cout << "Even" << std::endl;
    }
    else
    {
        std::cout << "Odd" << std::endl;
    }

    return 0;
}

ABC081A - Placing Marbles

ABC081A - Placing Marbles

問題文
すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。各マスには 0 か 1 が書かれており、マス i には si が書かれています。
すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約
s1 ,s2 ,s3 は 1 あるいは 0

入力
入力は以下の形式で標準入力から与えられる。
s1s2s3

出力
答えを出力せよ。

入力例 1
101

出力例 1
2

基本的な標準入力、標準出力、文字列操作ができればOK

main.cpp

#include <iostream>
#include <string>
using namespace std;
int main() {
   string s;
   cin >> s;
   int count = 0;
   for (char c : s) {
      if (c == '1') {
         count++;
      }
   }
   cout << count << endl;
   return 0;
}

ABC081B - Shift only

ABC081B - Shift only

問題文
黒板に N 個の正の整数 A1,...,AN が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
黒板に書かれている整数すべてを，2 で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約
1≤N≤200
1≤Ai≤10^9

入力
入力は以下の形式で標準入力から与えられる。
N
A1 A2 ... AN

出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ．

入力例 1
3
8 12 40

出力例 1
2

基本的な標準入力、標準出力、四則演算、ループ、条件分岐、配列の操作ができればOK

main.cpp

#include <iostream>

using namespace std;

// 配列 a の中身を全て 2 で割る関数
void div2(int a[], int n) {
  for (int i = 0; i < n; i++) {
    a[i] /= 2;
  }
}

int main() {
  // 配列 a の要素数を読み込む
  int n;
  cin >> n;

  // 配列 a を宣言し、各要素を読み込む
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  // 操作を行う回数をカウントする変数 ans を宣言し、初期値を 0 にする
  int ans = 0;

  // 操作を行う
  while (true) {
    // 配列 a の中身を順番に見ていき、偶数であれば ans をインクリメントする。また、その値を 2 で割って更新する
    bool is_all_even = true;
    for (int i = 0; i < n; i++) {
      if (a[i] % 2 == 0) {
        a[i] /= 2;
      } else {
        is_all_even = false;
      }
    }

    // 配列 a の中身がすべて偶数であるかどうかを判定する
    if (!is_all_even) {
      // 偶数でなければ操作を終了する
      break;
    }
     ans++;
  }

  // 操作を行った回数を出力する
  cout << ans << endl;

  return 0;
}

ABC087B - Coins

ABC087B - Coins

問題文
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
0≤A,B,C≤50
A+B+C≥1
50≤X≤20,000
A,B,C は整数である
X は 50 の倍数である

入力
入力は以下の形式で標準入力から与えられる。
A
B
C
X

出力
硬貨を選ぶ方法の個数を出力せよ。

基本的な標準入力、標準出力、四則演算、ループ、条件分岐、配列の操作、全通りの探索ができればOK

main.cpp

#include <iostream>

using namespace std;

int main() {
  // A, B, C, X の値をそれぞれ入力
  int A, B, C, X;
  cin >> A >> B >> C >> X;

  // 組み合わせの個数をカウントするための変数
  int count = 0;

  // A, B, C の硬貨を全て探索
  for (int a = 0; a <= A; a++) {
    for (int b = 0; b <= B; b++) {
      for (int c = 0; c <= C; c++) {
        // 硬貨の組み合わせが X 円になるかどうか判定
        if (a * 500 + b * 100 + c * 50 == X) {
          // 硬貨の組み合わせが X 円になった場合、カウントを1増やす
          count++;
        }
      }
    }
  }

  // 最終的な硬貨の組み合わせの個数を出力
  cout << count << endl;
  return 0;
}

ABC083B - Some Sums

ABC083B - Some Sums

問題文
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

制約
1≤N≤10^4
1≤A≤B≤36
入力はすべて整数である

入力
入力は以下の形式で標準入力から与えられる。
N A B

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

基本的な標準入力、標準出力、四則演算、ループ、条件分岐、配列の操作、組み込み関数の利用、ができればOK

main.cpp

#include <iostream>
using namespace std;

int main() {
  // N, A, Bを読み込む
  int N, A, B;
  cin >> N >> A >> B;

  // 答え
  long long ans = 0;

  // 1からNまでの整数を順番に調べる
  for (int i = 1; i <= N; i++) {
    // 各桁の和
    int sum = 0;

    // iを10進法で表したときの各桁を足し合わせる
    for (int j = i; j > 0; j /= 10) {
      sum += j % 10;
    }

    // sumがA以上B以下であれば答えを更新する
    if (A <= sum && sum <= B) {
      ans += i;
    }
  }

  // 答えを出力
  cout << ans << endl;
  return 0;
}

ABC088B - Card Game for Two

ABC088B - Card Game for Two

問題文
N 枚のカードがあります. i 枚目のカードには, ai という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約
N は 1 以上 100 以下の整数
ai(1≤i≤N) は 1 以上 100 以下の整数

入力
入力は以下の形式で標準入力から与えられる.
N
a1 a2 a3 ... aN

出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

基本的な標準入力、標準出力、四則演算、条件分岐、配列の操作、ループ、ソート、ができればOK

main.cpp

#include <iostream>
#include <algorithm>
#include <numeric>

// N 枚のカード
const int N = 100;

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

  // カードの数を格納する配列
  int a[N];

  // カードの数を読み込む
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  // カードを昇順にソートする
  std::sort(a, a + n, std::greater<int>());

  // Alice と Bob が取ったカードの数の合計
  int sum_a = 0;
  int sum_b = 0;

  // Alice と Bob がカードを取る
  for (int i = 0; i < n; i++) {
    // 偶数番目 (0, 2, 4, ...) は Alice が取る
    if (i % 2 == 0) {
      sum_a += a[i];
    }
    // 奇数番目 (1, 3, 5, ...) は Bob が取る
    else {
      sum_b += a[i];
    }
  }

  // Alice は Bob より何点多く取るか
  std::cout << sum_a - sum_b << std::endl;

  return 0;
}

ABC085B - Kagami Mochi

ABC085B - Kagami Mochi

問題文
X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は diセンチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約
1≤N≤100
1≤di≤100
入力値はすべて整数である。

入力
入力は以下の形式で標準入力から与えられる。
N
d1
​:
dN

​出力
作ることのできる鏡餅の最大の段数を出力せよ。

入力例 1
4
10
8
8
6

出力例 1
3

基本的な標準入力、標準出力、四則演算、ループ、配列、集合、ができればOK

main.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;

  // 餅を直径の小さいものから順番に取り出すため、餅の直径を昇順に並び替える
  int d[n];
  for (int i = 0; i < n; i++) {
    cin >> d[i];
  }
  sort(d, d + n);

  // 餅を積み重ねる
  int ans = 0; // 作ることのできる鏡餅の最大の段数
  int current_diameter = 0; // 現在の積み重ねられた鏡餅の直径
  for (int i = 0; i < n; i++) {
    // 現在の積み重ねられた鏡餅の直径よりも小さい餅を探す
    if (d[i] > current_diameter) {
      current_diameter = d[i]; // この餅を積み重ねる
      ans++; // 鏡餅の段数を1段増やす
    }
  }

  // 答えを出力
  cout << ans << endl;

  return 0;
}

ABC085C - Otoshidama

ABC085C - Otoshidama

問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
1≤N≤2000
1000≤Y≤2×10^7
N は整数である。
Y は 1000 の倍数である。

入力
入力は以下の形式で標準入力から与えられる。
N Y

出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

入力例 1
9 45000

出力例 1
4 0 5

基本的な標準入力、標準出力、四則演算、ループができればOK

main.cpp

#include <iostream>
using namespace std;

int main() {
  // 標準入力から入力値を取得
  int n, Y;
  cin >> n >> Y;
  // 10000 円札、5000 円札、1000 円札の枚数を探す
  for (int x = 0; x <= n; x++) { // 10000 円札の枚数を 0 枚から n 枚まで増やしていく
    for (int y = 0; y <= n - x; y++) { // 5000 円札の枚数を 0 枚から n - x 枚まで増やしていく
      // 1000 円札の枚数を求める
      int z = n - x - y;
      // 全てのお札の合計金額が y 円か判定
      if (10000 * x + 5000 * y + 1000 * z == Y) {
        // 枚数を出力
        cout << x << ' ' << y << ' ' << z << endl;
        // 正常終了
        return 0;
      }
    }
  }
  // 上記のループで見つからなかった場合、枚数が計算できない
  cout << -1 << ' ' << -1 << ' ' << -1 << endl;
  // 正常終了
  return 0;
}

ABC049C - 白昼夢

ABC049C - 白昼夢

問題文
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

制約
1≦∣S∣≦10^5
S は英小文字からなる。

入力
入力は以下の形式で標準入力から与えられる。
S

出力
S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

入力例 1
erasedream

出力例 1
YES

基本的な標準入力、標準出力、文字列操作ができればOK

main.cpp

#include <bits/stdc++.h>
using namespace std;

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

  string d[4] = {"dream", "dreamer", "erase", "eraser"};
  reverse(S.begin(), S.end());
  for (int i = 0; i < 4; ++i){
    reverse(d[i].begin(), d[i].end());
  }

  while (1){
    int flg = false;
    for (int i=0; i<4; i++) {
      if (S.compare(0, d[i].size(), d[i]) == 0) {
        S.erase(0, d[i].size());
        flg = true;
      }
    }
    if (flg != true) {
      break;
    }
  }
  cout << (S.empty() ?"YES" : "NO") << endl;
}

ABC086C - Traveling

ABC086C - Traveling

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻tiに 点 (xi,yi) を訪れる予定です。
AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約
1 ≤ N ≤ 10^5
0 ≤ xi ≤ 10^5
0 ≤ yi ≤ 10^5
1 ≤ ti ≤ 10^5
ti < ti+1 (1 ≤ i ≤ N−1)
入力は全て整数

入力
入力は以下の形式で標準入力から与えられる。
N
t1 x1 y1
​t2 x2 y2
:
tN xN yN

出力
旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

入力例 1
2
3 1 2
6 1 1

出力例 1
Yes

入力例 2
1
2 100 100

出力例 2
No
(0,0) にいる状態から 2 秒後に (100,100) にいるのは不可能です。

入力例 3
2
5 1 1
100 1 1

出力例 3
No

基本的な標準入力、標準出力、四則演算、ループ、二次元配列の操作、ができればOK

main.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  int t=0, x=0, y=0;
  cin >> n;
  for (int i; i<n; i++) {
    int ti, xi, yi;
    cin >> ti >> xi >> yi;
    if ( abs(xi - x) + abs(yi - y) > ti - t || (ti - t - abs(xi - x) - abs(yi - y)) % 2 != 0 ) {
        cout << "No" << endl;
        exit(0);
    }
    t = ti;
    x = xi;
    y = yi;
  }
  cout << "Yes" << endl;
}

参考