[c++] ABC074 #AtCoder

概要

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

• 2025.9.21 A-D

A Bichrome Cells ABC074-A

問題

$N \times N$ マス目を黒か白で塗る。$A$ マスを白色に塗る時、黒色に塗るマスはいくつかを求める。

• $1 \leq N \leq 100$
• $0 \leq A \leq N^2$

解法

1. 黒色に塗るマスを $x$ 個とすると、$$A + x = N^2$$
   これを $x$ について解くと、$$x = N^2 - A$$

サンプルコード

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

int N, A;

int main() {
  cin >> N >> A;
  
  cout << pow(N, 2) - A << endl; //黒色に塗るマスの数
  return 0;
}

B Collecting Balls (Easy Version) ABC074-B

問題

$xy$ 平面上に $N$ 個のボールがあり、その位置は $(x_i, i)$ 。ボールを回収するロボット $A$、$B$ はそれぞれ $(0, i)$、$(K, i)$ にある。ロボットは $x$ 軸方向にしか移動できず、ボールを回収した後は元の位置に戻る。全てのボールを回収した時の、ロボットの移動距離の総和で最小の値を求める。

• $1 \leq N \leq 100$
• $1 \leq K \leq 100$
• $0 < x_i < K$
• 入力値は全て整数

解法

1. ロボットとボールとの距離が小さい方を、移動距離に足していく。

サンプルコード

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

int N, K;

int main() {
  cin >> N >> K;
  
  int ans = 0; //移動距離の総和
  rep(i, N) { int x; cin >> x; ans += min(x, K-x) * 2; } //ボールまでの距離が短い方のロボットを動かす
  cout << ans << endl;
  return 0;
}

C Sugar Water ABC074-C

問題

以下の 4 種類の操作を行なって砂糖水を作る。

• 水を $100A$ [g] 入れる。
• 水を $100B$ [g] 入れる。
• 砂糖を $C$ [g] 入れる。
• 砂糖を $D$ [g] 入れる。

水 $100$ [g] 当たり砂糖は $E$ [g] 溶ける。ビーカーに入れられる質量は $F$ [g] まで。ビーカーの中に砂糖を溶け残らせてはならない。できるだけ濃度の高い砂糖水を作ったのときの、砂糖水の質量と、それに溶けている砂糖の質量を求める。

• $1 \leq A < B \leq 30$
• $1 \leq C < D \leq 30$
• $1 \leq E \leq 100$
• $100A \leq F \leq 3000$
• $A$、$B$、$C$、$D$、$E$、$F$ は全て整数

解法

動的計画法

1. 水だけをビーカーに入れた時の、作ることができる水の質量と砂糖の質量 ( $0$ )を記録する。
2. 作った水や砂糖水に砂糖を入れた時の、水の質量と砂糖の質量を記録する。
3. 作った砂糖水の中で一番濃度が高かったら、その濃度と砂糖水の質量と砂糖の質量をメモしていく。

サンプルコード

#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 A, B, C, D, E, F;
vector<vector<bool>> dp(40, vector<bool>(3010, 0)); //水の質量 : 砂糖の質量 -> この組み合わせがありうるかどうか

int main() {
  cin >> A >> B >> C >> D >> E >> F;
  
  dp.at(0).at(0) = 1; //何も入っていない状態
  rep(i, F/100+1) { //水 100i [g] である可能性
    if ((i - A >= 0 && dp.at(i-A).at(0)) || (i - B >= 0 && dp.at(i-B).at(0))) { //i - A または i - B の状態があったら、i の状態もある
      dp.at(i).at(0) = 1;
    }
  }
  
  double c = 0; int ws = 100 * A, s = 0; //一番高い濃度の、砂糖水の濃度と質量と砂糖の質量
  repu(i, A, F/100+1) repu(j, C, E*i+1) { //j は 100 [g] 当たり E を超えないようにする
    if ((j - C >= 0 && dp.at(i).at(j-C)) || (j - D >= 0 && dp.at(i).at(j-D))) { //j - C または j - D の状態があったら、j の状態もある
      int tws = 100*i + j; //砂糖水の質量
      if (tws <= F) {
        dp.at(i).at(j) = 1;
        double temp = (1.0 * j) / tws; //砂糖水の濃度
        if (temp > c) { c = temp; ws = tws, s = j; }
      }
    }
  }
  printf("%d %d\n", ws, s);
  return 0;
}

D Restoring Road Netwerk ABC074-D

問題

$N \times N$ の表 $A$ がある。$A_{u, v}$ は都市 $u$ から都市 $v$ への最短経路の長さを表したものである。都市間を繋ぐ道路は双方向で長さが異なる。この表 $A$ のような道路構造が存在するかを調べ、存在するなら道路の長さの和が最小となるようなものについて、その和を求める。存在しないなら $-1$ を出力する。

• $1 \leq N \leq 300$
• $i \neq j$ の時 $1 \leq A_{i, j} = A_{j, i} \leq 10^9$
• $A_{i, i} = 0$

解法

ワーシャルフロイド法

1. 都市 $i$ から都市 $k$ を経由して都市 $j$ に向かうとき、都市 $i$ から都市 $j$ への最短経路より経路が短い場合は、表 $A$ の道路構造は存在しない。
2. 都市 $i$ から都市 $j$ への最短経路が、都市 $k$ を経由した経路と同じ長さであったなら、都市 $i$ と都市 $j$ を繋ぐ直通の道路は必要ない。
3. 直通の道路の長さを $sum$ に足していく。

サンプルコード

#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>> A(300, vector<int>(300));

int main() {
  cin >> N;
  rep(i, N) rep(j, N) cin >> A.at(i).at(j);
  
  bool ans = true; int64_t sum = 0; //道路構造が存在するかと、道路の長さの和
  rep(i, N) repu(j, i+1, N) { //都市 i から都市 j へ
    bool road = true; //直通の道路が存在するか
    rep(k, N) { //経由する都市
      if (k == i || k == j) continue;
      int temp = A.at(i).at(k) + A.at(k).at(j); //都市 k を経由した時の経路の長さ
      if (temp < A.at(i).at(j)) { ans = false; break; } //最短経路より短い経路が存在する場合
      else if (temp == A.at(i).at(j)) road = false; //最短経路が直通でない場合
    }
    if (!ans) break; //道路構造が存在しない場合は終了
    if (road) sum += A.at(i).at(j); //直通の道路が存在する場合は sum に加算する
  }
  cout << (ans ? sum : -1) << endl;
  return 0;
}