C++でABC216のA~D問題を解説します。
本番ではA~CまでしかACできませんでしたが、翌日D問題に取り組み答えを見ずにAC出来ました。
では解説していきます。
A – Signed Difficulty
問題概要
実数\( X.Y \)が与えられる。\( Y \)は一桁。
- \( 0 \le Y \le 2 \)ならば、\( X- \)
- \( 3 \le Y \le 6 \)ならば、\( X \)
- \( 7 \le Y \le 9 \)ならば、\( X+ \)
と出力
制約
- \( 1 \le X \le 15 \)
- \( 0 \le Y \le 9 \)
- \(X\)と\(Y\)は整数
解説
入力を\(X\)と\(Y\)に分けて、\(Y\)の条件によって\(X\)に演算子を追加して出力します。
#include <bits/stdc++.h>
int main() {
std::string s; std::cin >> s;
int s_len = s.size();
std::string x = s.substr(0, s_len-2); // 右端の2文字を除いたものがx
int y = s[s_len-1] - '0'; // 末尾がy
std::string ans;
if (y >= 0 && y <= 2) ans = x + '-';
else if (y >= 3 && y <= 6) ans = x;
else ans = x + '+';
std::cout << ans << std::endl;
return 0;
}7行目はchar型の数字をintの数字に変換しています。char型の数字の文字コードは’0’ー’9’まで連続して大きくなっていきます。char型の’0’からの差分を計算することでint型の数字に変換することが出来ます。
B – Same Name
問題概要
\(N\)人の人が居ます。\(i\)番目の人の性が\(S_i\)、名が\(T_i\)のとき同性同名の人が居るかどうか判定してください。
制約
- \( 2 \le N \le 1000\)
- \(N\)は整数
- \(S_i , ~ T_i\)は英子文字のみからなる長さ\(1\)以上\(10\)以下の文字列
解説
2重for文で異なる2人の組み合わせをすべて試して、同姓同名の人が居るかどうか判定します。
組み合わせのfor文のイメージはこんなかんじです。外側のfor文が添え字\(i\)で、内側が\(j\)です。\(i\)をある値に固定して\(j\)を\((i+1) \sim (N-1)\)まで動かす。\(i\)をインクリメントする。これらを繰り返すことで、すべての異なる\(2\)人の組み合わせを作ることができます。
#include <bits/stdc++.h>
int main() {
// 入力
int n; std::cin >> n;
std::vector<std::string> last_name(n), first_name(n);
for (int i = 0; i < n; ++i)
std::cin >> last_name[i] >> first_name[i];
// 人の組み合わせをすべてチェックし、同姓同名の存在判定
bool same_name_exists = false;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (last_name[i] == last_name[j] && first_name[i] == first_name[j])
same_name_exists = true;
if (same_name_exists) std::cout << "Yes" << std::endl;
else std::cout << "No" << std::endl;
return 0;
}C – Many Balls
問題概要
2種類の魔法
- 魔法\(A\): 箱の中のボールを\(1\)つ増やす
- 魔法\(B\): 箱の中のボールの数を\(2\)倍にする
を繰り返し合計\(120\)回以内にボールの数を\(N\)個にする方法を出力してください。
制約
- \( 1 \le N \le 10^{18} \)
- 入力はすべて整数
解説
\(N\)個のボールを0個にする方法を求め、それを逆にすることで\(0\)個のボールを\(N\)個にする方法を求められます。
魔法\(A\)の逆の操作はボールを\(1\)つ減らし、魔法\(B\)の逆の操作はボールの数を半分にします。魔法\(B\)の逆の操作が使える時、つまりボールの数が偶数の時はそれを使い、奇数の時は魔法\(A\)の逆の操作をします。
ソースコードは下のようになります。
6行目はnが0になった時点で偽と評価され、while文を抜けます。
8行目と12行目では後に使う魔法ほど右側に来るようにしています。
#include <bits/stdc++.h>
int main() {
long long n; std::cin >> n;
std::string magics;
while (n) {
if (n%2 == 0) {
magics = 'B' + magics;
n /= 2; // Bの逆操作を行う
}
else {
magics = 'A' + magics;
--n; // Aの逆操作を行う
}
}
std::cout << magics << std::endl;
return 0;
}D – Pair of Balls
問題概要
\(2N\)個のボールに\(1\)以上\(N\)以下の整数が書かれている。各数字が書かれたボールはちょうど2個づつ存在する。これらのボールが\(M\)本の筒に入れられていて、\(i\)番目の筒には\(k_i\)個のボールが入っている。異なる2本の空でない筒を選び、2つの筒の一番上のボールが同じ数字の場合、それらの筒から一番上のボールを捨てる。この操作を繰り返し\(M\)本の筒をすべて空にできるか判定してください。
制約
- \( 1 \le N \le 2 \times 10^5 \)
- \( 2 \le M \le 2 \times 10^5 \)
- \( 1 \le k_i ~ (1 \le i \le M) \)
- \( 1 \le a_{i,j} \le N ~ (1 \le i \le M, ~ 1 \le j \le k_i) \)
- \( \sum_{i=1}^M = 2N\)
- 入力はすべて整数
解説
ボールを取り出すときに毎回、\(M\)個の筒をチェックしていると計算量が\(O(MN)\)となり間に合いません。ボールを取り出す操作を\(N\)回、取り出すときに毎回\(M\)個の筒をチェックするので\(O(MN)\)となります。
そこで\(top[i] := \)(筒の一番上の球について、書かれている番号が\(i\)である筒の番号)とし、\( pairs :=\) (筒の一番上にある球について、同じ番号が書かれた球が2つあるような球の番号)とします。
例えば下のような状況の場合(0-indexedにしています)、\(top\)と\(pairs\)はこのようになります。
\(0、1\)番目の筒の一番上の球番号が1なので、\(top[1] = \{0, 1\} \)、\(2、3\)番目の筒の一番上の球番号が3なので\( top[3] = \{2, 3\} \)となります。
それぞれの筒の一番上の球番号について\(1\)と\(3\)が書かれた球がそれぞれ2つあるので、\( pairs = \{1, 3\} \)となります。
あとは筒の状態を表現するために、要素がqueueであるvectorを用意して、筒から取り出せる球を順番に取り出していきます。筒が空になれば\(Yes\)、そうでなければ\(No\)を出力します。
どのように球を取り出していくのかについてはソースコード中にコメントで説明しています。
#include <bits/stdc++.h>
int main() {
int n, m; std::cin >> n >> m;
std::vector<std::queue<int>> pipes(m); // M個の筒の状態
std::vector<std::vector<int>> tops(n); // tops[i] := 筒の一番上の球番号がiである筒の番号
std::vector<int> pairs; // 筒の一番上の球について同じ番号が2つある球の番号
for (int i = 0; i < m; ++i) {
int k; std::cin >> k;
// i個目の筒の状態を読み込む
for (int j = 0; j < k; ++j) {
int a; std::cin >> a;
pipes[i].push(a-1); // 0-indexedにする
}
// i個目の筒の一番上の球番号をtopに記録
tops[pipes[i].front()].push_back(i);
}
// 筒の一番上に同じ番号が2つある球番号
for (int i = 0; i < n; ++i)
if (tops[i].size() == 2)
pairs.push_back(i);
// pairsが空になるまで
while (!pairs.empty()) {
// 筒から取り出す球番号取得
int pop_num = pairs.back(); pairs.pop_back();
// 球を取り出す筒番号取得
int pipe_idx_1 = tops[pop_num].back(); tops[pop_num].pop_back();
int pipe_idx_2 = tops[pop_num].back(); tops[pop_num].pop_back();
// 筒の一番上の球を取り出す
pipes[pipe_idx_1].pop();
pipes[pipe_idx_2].pop();
// 新しく筒の一番上に位置する球でtopsとpairsを更新
if (!pipes[pipe_idx_1].empty()) {
int new_top = pipes[pipe_idx_1].front();
tops[new_top].push_back(pipe_idx_1);
if (tops[new_top].size() == 2)
pairs.push_back(new_top);
}
if (!pipes[pipe_idx_2].empty()) {
int new_top = pipes[pipe_idx_2].front();
tops[new_top].push_back(pipe_idx_2);
if (tops[new_top].size() == 2)
pairs.push_back(new_top);
}
}
// 筒がすべて空になっているかどうかを判定
bool empty = true;
for (int i = 0; i < m; ++i)
if (!pipes[i].empty())
empty = false;
if (empty) std::cout << "Yes" << std::endl;
else std::cout << "No" << std::endl;
return 0;
}