ABC216 A~D問題をわかりやすく解説

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;
}

競技プログラミングの最新記事4件