[c++] ABC088 #AtCoder

概要

問題の解き方をまとめました。

• 2025.9.23 A-D

A Infinite Coins #ABC088-A

問題

1 円硬貨を $A$ 枚と 500 円硬貨を無限枚持っている。これを使ってちょうど $N$ 円を払うことができるかを判定する。

• $1 \leq N \leq 10000$
• $0 \leq A \leq 1000$
• $N$ と $A$ は整数

解法

1. $N$ を $500$ で割った余りが $A$ 円以下かどうかを判定する。

サンプルコード

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

int N, A;

int main() {
  cin >> N >> A;
  
  cout << ((N%500) <= A ? "Yes" : "No") << endl;
  return 0;
}

B Card Game for Two #ABC088-B

問題

$N$ 枚のカードがある。Alice と Bob が自分の得点を最大化するようにカードを取っていった時、Alice が Bob より何点多く取るかを求める。Alice からカードを取り始める。

• $1 \leq N \leq 100$
• $1 \leq a_i \leq 100$
• $N$ と $a_i$ は整数

解法

1. カードを降順に並べる。
2. 奇数番目のカードを Alice が取り、偶数番目のカードを Bob が取る。
3. 得点の差を出力する。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N;
vector<int> A;

int main() {
  cin >> N;
  A.resize(N); rep(i, N) cin >> A.at(i);
  
  sort(A.begin(), A.end(), greater<int>{}); //カードを降順に並べる
  int Alice = 0, Bob = 0;
  for (int i = 0; i < N; i += 2) Alice += A.at(i); //奇数番目のカードを Alice が取る
  for (int i = 1; i < N; i += 2) Bob += A.at(i); //偶数番目のカードを Bob が取る
  cout << (Alice - Bob) << endl;
  return 0;
}

C Takahashi's Information #ABC088-C

問題

$3 \times 3$ のグリッドがある。マス $C_{i, j}$ には $a_i + b_j$ が書かれている。これが正しいか判定する。

• $0 \leq c_{i, j} \leq 100$

解法

1. $c_{i, j} = a_i + b_i$ を変形させる。

   \begin{align}
   c_{i, j} &= a_i + b_i\\
   &= ( a_0 + b_j ) + ( a_i + b_0 ) - ( a_0 + b_0 )\\
   &= c_{0, j} + c_{i, 0} - c_{0, 0}
   \end{align}
   

2. 上記の式を使って判定する。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repu(i, s, t) for (int i = (int)s; i < (int)t; i++)

int N;
vector<vector<int>> C(3, vector<int>(3));

int main() {
  rep(i, 3) rep(j, 3) cin >> C.at(i).at(j);
  
  bool ans = true;
  repu(i, 1, 3) repu(j, 1, 3) {
    if (C.at(i).at(j) != C.at(0).at(j) + C.at(i).at(0) - C.at(0).at(0)) { //マスの値が正しいかどうか判定する
      ans = false;
    }
  }
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

D Grid Repainting #ABC088-D

問題

$H \times W$ の白か黒に塗られたマス目がある。座標 $( 1, 1 )$ からスタートして、白いマスを通って座標 $( H, W )$ にたどり着ければゲームクリアとなる。ゲームを始める前に白いマスを黒く塗った数が得点となるので、可能性のある最高得点を求める。ゴールに辿り着けなければ $-1$ を出力する。

• $2 \leq H \leq 50$
• $1 \leq W \leq 50$
• $s_{i, j}$ は「 . 」または「 # 」
• $s_{1, 1}$ と $s_{H, W}$ は「 . 」

解法

幅優先探索、キュー

1. 座標 $( i, j )$ にたどり着くまでに通ったマスの最小の数を記録した二次元コンテナと、次に調べるマスの座標を入れるキューを用意する。
2. 上下左右の座標で、まだ訪れていないところを記録していく。
3. 座標 $( H, W )$ にたどり着くまでに通ったマスの最初の数が $0$ だったら、そもそもゴールには辿り着けていないので $-1$ を出力する。
4. 最短距離上にあるマス以外は黒く塗って良いので、盤面にある白いマスの数を調べて、その数から最短距離上にあるマスの数を引く。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int H, W;
vector<string> S;

int main() {
  cin >> H >> W;
  S.resize(H); rep(i, H) cin >> S.at(i);
  
  vector<int> I = { -1, 0, 1, 0 }, J = { 0, 1, 0, -1 };
  vector<vector<int>> P(H, vector<int>(W, 0)); P.at(0).at(0) = 1; //最短距離上のマスの数
  queue<pair<int, int>> Q; Q.emplace(0, 0); //次に調べるマス、スタートから近い順に調べる
  while (!Q.empty()) {
    int i, j; tie(i, j) = Q.front(); Q.pop();
    rep(k, 4) { //上下左右のマスを調べる
      int ti = i + I.at(k), tj = j + J.at(k);
      if (0 <= ti && ti < H && 0 <= tj && tj < W) { //H * W のマス目の範囲内にあるか
        if (S.at(ti).at(tj) == '.' && P.at(ti).at(tj) == 0) { //白いマスかつまだ行っていないマスの時
          P.at(ti).at(tj) = P.at(i).at(j) + 1; Q.emplace(ti, tj); //調べているマスから 1 つだけ移動する、次に調べるマスに追加
        }
      }
    }
  }
  
  if (P.at(H-1).at(W-1) == 0) cout << -1 << endl; //ゴールに辿り着けなかった場合
  else {
    int white = 0; //白いマスの数
    rep(i, H) rep(j, W) if (S.at(i).at(j) == '.') white++;
    cout << (white - P.at(H-1).at(W-1)) << endl; //白いマスの数から最短距離上のマスの数を引く
  }
  return 0;
}