AtCoder Beginner Contest 190 #ABC190

2023-12-23

AtCoder Beginner Contest 190 の A/B/C 問題の解法。

実装はこちら atcoder/abc/101-200/190 · michimani/atcoder 。

A - Very Very Primitive Game

高橋くんと青木くんの飴の数をサイズ 2 の配列で保持して、 0 番目を高橋くん、 1 番目を青木くんの飴の数とする。

$C$ の値は boolean で保持して、どちらかの飴の数が 0 になるまでループを回す。ループの中で $C$ が 0 の場合は高橋くんのターン、 1 の場合は青木くんのターンとして、飴の数を 1 減らす。ループの最後に $C$ を反転させる。

最後に、 $C$ が True であれば高橋くんの勝ち、 False であれば青木くんの勝ちとして出力する。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  vector<int> ab(2, 0);
  bool c;
  cin >> ab[0] >> ab[1] >> c;

  while (true)
  {
    if (ab[(unsigned int)(c)] == 0)
    {
      break;
    }

    ab[(unsigned int)(c)]--;
    c = !c;
  }

  if (c)
  {
    cout << "Takahashi" << endl;
  }
  else
  {
    cout << "Aoki" << endl;
  }

  return 0;
}

提出 #48717721 - AtCoder Beginner Contest 190

B - Magic 3

各入力に対して $X_i \lt S$ 且つ $Y_i \gt D$ であれば、 Yes を出力して終了。

条件を満たす入力がなくループを抜けたら No を出力して終了。

#include <iostream>

using namespace std;

int main()
{
  unsigned int n, s, d;
  cin >> n >> s >> d;

  for (unsigned int i = 0; i < n; i++)
  {
    unsigned int x, y;
    cin >> x >> y;

    if (x < s && y > d)
    {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
  return 0;
}

提出 #48717639 - AtCoder Beginner Contest 190

C - Bowls and Dishes

まず、条件を $N \times N$ の配列で保持する。条件は重複する場合もあるので、配列の各要素を条件の数とする。入力例 3 の場合のイメージは下記の通り。

A＼B	1	2	3	4	5	6
1	-	2	1	0	1	0
2	-	-	2	0	1	2
3	-	-	-	0	0	0
4	-	-	-	-	2	1
5	-	-	-	-	-	0
6	-	-	-	-	-	-

ボールは 1 つだけ皿に置かれていればよいので、ボールが置かれる可能性がある皿番号リストのパターンを下記のロジックで全て列挙する。

$C_k$ にまだボールが置かれていない (= リストに加えていない) 場合は、 $C_k$ をリストに加える
$D_k$ にまだボールが置かれていない (= リストに加えていない) 場合は、 $D_k$ をリストに加える
$C_k, D_k$ ともにボールが置かれている場合は、何もせず次の選択肢に進む

今回はこの条件による組み合わせの列挙を gen 関数で実装した。入力例 3 の場合、下記のような組み合わせが列挙される。

$$ \displaylines{ \lbrace 3,1,2,4,5\rbrace \\ \lbrace 3,1,2,4,6\rbrace \\ \lbrace 3,1,2,6,5\rbrace \\ \lbrace 3,1,6,4,5\rbrace \\ \lbrace 3,4,2,6,5\rbrace \\ \lbrace 3,4,6,5\rbrace \\ \lbrace 5,1,2,4,6\rbrace \\ \lbrace 5,1,2,6\rbrace \\ \lbrace 5,1,6,4\rbrace \\ \lbrace 5,4,2,6\rbrace \\ \lbrace 5,4,6\rbrace } $$

列挙した各パターンについて、対象のリスト内で皿同士の組み合わせについて $N \times N$ の条件配列から条件の数を取得し、最大値を更新していく。このとき、$A_m \lt B_m$ であるから対象の皿番号のリストは昇順にソートしておく。

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;

void gen(vector<vector<unsigned int>> &choices, vector<vector<unsigned int>> &balls_list, vector<unsigned int> balls, map<unsigned int, bool> selected, unsigned int pos)
{
  if (pos == choices.size())
  {
    balls_list.push_back(balls);
    return;
  }

  if (selected[choices[pos][0]] && selected[choices[pos][1]])
  {
    gen(choices, balls_list, balls, selected, pos + 1);
    return;
  }

  if (!selected[choices[pos][0]])
  {
    vector<unsigned int> tmp_balls = balls;
    tmp_balls.push_back(choices[pos][0]);
    map<unsigned int, bool> tmp_selected = selected;
    tmp_selected[choices[pos][0]] = true;
    gen(choices, balls_list, tmp_balls, tmp_selected, pos + 1);
  }

  if (!selected[choices[pos][1]])
  {
    vector<unsigned int> tmp_balls = balls;
    tmp_balls.push_back(choices[pos][1]);
    map<unsigned int, bool> tmp_selected = selected;
    tmp_selected[choices[pos][1]] = true;
    gen(choices, balls_list, tmp_balls, tmp_selected, pos + 1);
  }
}

int main()
{
  unsigned int n, m;
  cin >> n >> m;

  vector<vector<unsigned int>> conds(n + 1, vector<unsigned int>(n + 1, 0));
  for (unsigned int i = 0; i < m; i++)
  {
    unsigned int a, b;
    cin >> a >> b;
    conds[a][b]++;
  }

  unsigned int k;
  cin >> k;

  vector<vector<unsigned int>> choices(k, vector<unsigned int>(2, 0));
  for (unsigned int i = 0; i < k; i++)
  {
    cin >> choices[i][0] >> choices[i][1];
  }

  vector<vector<unsigned int>> balls_list;
  vector<unsigned int> balls;
  map<unsigned int, bool> selected;
  gen(choices, balls_list, balls, selected, 0);

  unsigned int ans = 0;
  for (auto &b : balls_list)
  {
    sort(b.begin(), b.end());
    unsigned int tmp_ans = 0;
    for (unsigned int i = 0; i < b.size(); i++)
    {
      for (unsigned int j = i + 1; j < b.size(); j++)
      {
        tmp_ans += conds[b[i]][b[j]];
      }
    }

    ans = max(ans, tmp_ans);
  }

  cout << ans << endl;
  return 0;
}

提出 #48717466 - AtCoder Beginner Contest 190

Tags for this post: AtCoder C++

comments powered by Disqus

Prev: AtCoder Beginner Contest 144 #ABC144

Next: AtCoder Beginner Contest 131 #ABC131