[c++] ABC082 #AtCoder

概要

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

• 2025.9.22 A-D

A Round Up the Mean ABC082-A

問題

$a$ と $b$ の平均値の、小数点以下を切り上げた整数を出力する。

• $a$ 、$b$ は整数
• $1 \leq a, b \leq 100$

解法

1. $a + b + 1$ を $2$ で割る。

サンプルコード

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

int a, b;

int main() {
  cin >> a >> b;
  
  cout << (a + b + 1) / 2 << endl;
  return 0;
}

B Two Anagrams ABC082-B

問題

文字列 $s$ 、$t$ をそれぞれ並べ替えて、$s' < t'$ にできるかどうかを判定する。

• $1 \leq |s|, |t| \leq 100$
• $s$ 、$t$ は英小文字のみからなる

解法

1. $s$ を昇順に並べ替えて、$t$ を降順に並べ替える。
2. $s$ と $t$ を比べる。

サンプルコード

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

string s, t;

int main() {
  cin >> s >> t;
  
  sort(s.begin(), s.end()); //s は昇順 -> 辞書順で一番前
  sort(t.begin(), t.end(), greater<char>()); //t は降順 -> 辞書順で一番後ろ
  cout << (s < t ? "Yes" : "No") << endl;
  return 0;
}

C Good Sequence ABC082-C

問題

長さ $N$ の数列からいくつかの要素を取り除き、数列を良い数列にする。良い数列とは、要素 $x$ がちょうど $x$ 個あるもののことをいう。取り除くべき要素の個数の最小値を求める。

• $1 \leq N \leq 10^5$
• $a_i$ は整数
• $1 \leq a_i \leq 10^9$

解法

1. 数列にある要素の、それぞれの個数を数える。
2. 要素 $x$ が $x$ 個より多かったら、差分を $ans$ に加算する。要素 $x$ が $x$ 個より少なかったら、要素 $x$ の個数を $ans$ に加算する。( 要素 $x$ がちょうど $x$ 個だったら何もしない。 )

サンプルコード

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

int N;
map<int, int> M;

int main() {
  cin >> N;
  
  rep(i, N) { int a; cin >> a; M[a]++; } //それぞれの要素の個数を数える
  int ans = 0;
  for (auto t : M) {
    if (t.first < t.second) ans += t.second - t.first; //要素 x が x 個より多かったら差分を加算する
    else if (t.first > t.second) ans += t.second; //要素 x が x 個より少なかったら要素 x の個数を加算する
  }
  cout << ans << endl;
  return 0;
}

D FT Robot ABC082-D

問題

原点にいるロボットが座標 $( x, y )$ に到達できるかを判定する。ロボットは F の時前進して、T の時に 90 度、右か左に向きを変える。

• $s$ は「 F 」、「 T 」のみからなる
• $1 \leq |s| \leq 8000$
• $x$ 、$y$ は整数
• $|x|, |y| \leq |s|$

解法

1. $x$ 軸方向に進んだ時と、$y$ 軸方向に進んだ時の移動距離を調べる。
2. 最初の移動は $x$ 軸方向の正の向きだから、先に到達点の $x$ 座標から引いておく。
3. $x$ 軸方向の移動と $y$ 軸方向の移動はそれぞれ分けて考える。到達点に到達可能かどうかの関数を作る。
   1. これまでの移動で可能性のある座標から、$i$ 回目の移動で正の方向へと移動した時と、負の方向へと移動した時の座標を加える。
   2. 可能性のある座標の中に、到達点があれば到達可能である。

サンプルコード

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

string s;
int x, y;

bool reachable(deque<int> &T, const int &G) { //座標 0 から座標 G に到達可能かどうか
  set<int> S; S.insert(0); //これまでの移動で可能性のある座標
  for (int t : T) { //移動距離
    set<int> S2; for (int s : S) { S2.insert(s + t); S2.insert(s - t); } //正の方向に移動した時と、負の方向に移動した時の座標を追加
    S = S2;
  }
  for (int s : S) if (s == G) return true; //座標 G になる可能性がある場合は true
  return false;
}

int main() {
  cin >> s >> x >> y;

  deque<int> X, Y; bool judge_x = true; int count = 0;
  for (char c : s) {
    if (c == 'F') count++;
    else { //方向転換する時
      if (judge_x) X.push_back(count); else Y.push_back(count); //x 軸方向を向いていたら X に追加、y 軸方向を向いていたら Y に追加
      judge_x = !(judge_x); count = 0; //向きを 90 度変える、移動距離リセット
    }
  }
  if (judge_x) X.push_back(count); else Y.push_back(count); //最後の移動
  
  x -= X.front(); X.pop_front(); //最初の移動だけは x 軸の正の方向へ移動するのが決まっているので、到達座標 x からあらかじめ引いておく
  cout << ((reachable(X, x) && reachable(Y, y)) ? "Yes" : "No") << endl; //x 座標と y 座標にそれぞれ到達できるなら Yes
  return 0;
}