[c++] ABC083 #AtCoder

概要

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

• 2025.9.24 A-D

A Libra #ABC083-A

問題

左の天秤に $A$ と $B$ の重りを、右の天秤に $C$ と $D$ の重りを置くと、どちらに傾くかを求める。

• $1 \leq A, B, C, D \leq 10$
• 入力は全て整数

解法

1. $A + B$ と $C + D$ を比べる。

サンプルコード

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

int A, B, C, D;

int main() {
  cin >> A >> B >> C >> D;
  
  int l = A + B, r = C + D;
  cout << (l > r ? "Left" : (l == r ? "Balanced" : "Right")) << endl;
  return 0;
}

B Some Sums #ABC083-B

問題

$1$ 以上 $N$ 以下の整数のうち、10 進法での各桁の和が $A$ 以上 $B$ 以下であるものの総和を求める。

• $1 \leq N \leq 10^4$
• $1 \leq A \leq B \leq 36$
• 入力は全て整数

解法

全探索

1. 各桁の和が $A$ 以上 $B$ 以下なら $ans$ に足す。

サンプルコード

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

int N, A, B;

int main() {
  cin >> N >> A >> B;
  
  int ans = 0;
  rep(i, N+1) {
    int sum = 0, t = i; //各桁の合計
    while (t > 0) { sum += t % 10; t /= 10; } //各桁を足す
    if (A <= sum && sum <= B) ans += i; //sum が A 以上 B 以下なら ans に i を足す
  }
  cout << ans << endl;
  return 0;
}

C Multiple Gift #ABC083-C

問題

数列 $A$ は $X$ 以上 $Y$ 以下の整数からなる。$A_{i+1}$ は $A_i$ の倍数で、$A_i$ より真に大きい。この数列の長さの最大値を求める。

• $1 \leq X \leq Y \leq 10^{18}$
• 入力は全て整数

解法

1. $t = X$ から初めて、$t$ を二倍にしていく。$t$ が $Y$ を超えたら終了する。$Y$ を超えない値の個数が答え。

サンプルコード

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

int64_t X, Y;

int main() {
  cin >> X >> Y;
  
  int ans = 0; int64_t t = X; //数列の要素の個数、要素の値
  while (t <= Y) { ans++; t <<= 1; } //Y を超えない t がいくつあるかを求める
  cout << ans << endl;
  return 0;
}

D Wide Flip #ABC083-D

問題

0 と 1 からなる文字列 $S$ を、長さ $K$ 以上の区間を反転させる操作をして、全ての要素を 0 にする。この時の最大の整数 $K$ を求める。

• $1 \leq |S| \leq 10^5$
• $S_i$ は 0 または 1

解法

1. 左から順に見ていって、0 と 1 が切り替わる時に、左側と右側の長い方を反転させて 0 と 1 を揃える。
2. $ans$ には反転させた長さの一番短いものを記録しておく。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

string S;

int main() {
  cin >> S;
  
  int n = S.size(), ans = n; //ans には反転させた一番短い長さを記録しておく
  bool one = true; //0 と 1 の切り替わりを検知、切り替わりの位置が分かれば良い
  rep(i, n) {
    if ((one && S.at(i) == '0') || (!one && S.at(i) == '1')) { //0 と 1 が切り替わる時、左側と右側のどちらかを反転させて合わせる
      chmin(ans, max(i, n-i)); one = !one; //長い方を反転させる
    }
  }
  cout << ans << endl;
  return 0;
}