[c++] ABC079 #AtCoder

概要

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

• 2025.9.27 A-D

A Good Integer #ABC079-A

問題

3 つ以上の数字が連続して並んだ 4 桁の整数を良い整数とする。4 桁の整数 $N$ が良い整数かどうかを判定する。

• $1000 \leq N \leq 9999$
• 入力は整数からなる

解法

1. 1 番目と 2 番目と 3 番目が等しかったら良い整数。2 番目と 3 番目と 4 番目が等しかったら良い整数。

サンプルコード

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

int main() {
  char a, b, c, d; cin >> a >> b >> c >> d;
  
  if ((a == b && b == c) || (b == c) && (c == d)) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

B Lucas Number #ABC079-B

問題

$N$ 番目のリュカ数を求める。

• $1 \leq N \leq 86$
• 答えは $10^{18}$ より小さい
• 入力は整数

解法

動的計画法、再帰関数

1. リュカ数をメモしておくコンテナを用意する。
2. リュカ数を返す関数を用意する。
3. $N$ 番目のリュカ数を出力する。

サンプルコード

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

int N;
vector<int64_t> dp(100, -1); //リュカ数をメモする

int64_t lucas_number(int i) { //i 番目のリュカ数を返す
  if (dp.at(i) != -1) return dp.at(i);

  //終了条件
  if (i == 0) return 2;
  else if (i == 1) return 1;
  
  return dp.at(i) = lucas_number(i-1) + lucas_number(i-2);
}

int main() {
  cin >> N;
  
  cout << lucas_number(N) << endl; //N 番目のリュカ数を出力
  return 0;
}

C Train Ticket #ABC079-C

問題

4 つの整数 $A$ 、$B$ 、$C$ 、$D$ の間に + か - を入れて式を作り、7 にできるものの一例を求める。

• $0 \leq A, B, C, D \leq 9$
• 入力は整数
• 答えが存在しない入力は与えられない

解法

全探索

1. 全ての組み合わせで 7 になるかを試す。
2. 7 になる時、式を整形して出力する。

サンプルコード

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

int main() {
  vector<int> A(4); rep(i, 4) { char c; cin >> c; A.at(i) = c - '0'; }
  //数字を一文字ずつの整数にする、例えば (char)'5' - '0' = (int)5
  
  rep(tmp, (1<<3)) { //間に入れる + と - の組み合わせ、1 の時 + 、0 の時 -
    bitset<3> B(tmp);
    int sum = A.at(0); //式の計算結果
    rep(i, 3) { if (B.test(i)) sum += A.at(i+1); else sum -= A.at(i+1); }
    if (sum == 7) { //計算結果が 7 だったら出力して終了
      rep(i, 3) cout << A.at(i) << (B.test(i) ? '+' : '-');
      cout << A.at(3) << "=7" << endl;
      break;
    }
  }
  return 0;
}

D Wall #ABC079-D

問題

$H \times W$ のマス目に 0 以上 9 以下の整数が書かれている。-1 の時は何も書かれていないということ。1 つの数字を $i$ から $j$ に書き換えるには魔力 $c_{i, j}$ が必要である。この壁に書かれている数字を最終的に全て 1 に変えるのに必要な魔力の最小値を求める。

• $1 \leq H, W \leq 200$
• $1 \leq c_{i, j} \leq 10^3 (i \neq j)$
• $c_{i, j} = 0 (i = j)$
• $-1 \leq A_{i, j} \leq 9$
• 入力は整数
• 壁には一つ以上の整数が書かれている

解法

1. 数字を $i$ から $j$ に変える時の最小魔力を求める。
2. 全ての数字を 1 に変えた時の魔力を出力する。

サンプルコード

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

int H, W;
vector<vector<int>> C(10, vector<int>(10));

int main() {
  cin >> H >> W;
  rep(i, 10) rep(j, 10) cin >> C.at(i).at(j);
  vector<vector<int>> A(H, vector<int>(W));
  rep(i, H) rep(j, W) cin >> A.at(i).at(j);
  
  rep(k, 10) rep(i, 10) { //変換する時の最小魔力を求める
    if (k == i) continue;
    rep(j, 10) { //数字を i から k に変えて、 k から j に変えたときの必要魔力を求めて、i から j に変える時の必要魔力の最小値を求める
      if (k == j || i == j) continue;
      int t = C.at(i).at(k) + C.at(k).at(j);
      if (t < C.at(i).at(j)) C.at(i).at(j) = t;
    }
  }
  
  int ans = 0; //全ての数字を 1 に変えた時の必要魔力
  rep(i, H) rep(j, W) { //全ての数字を 1 に変える
    int t = A.at(i).at(j);
    if (t != -1 && t != 1) ans += C.at(t).at(1);
  }
  cout << ans << endl;
  return 0;
}