michimani log

2023-12-22

AtCoder Beginner Contest 190 #ABC190

AtCoderC++
Competitive Programming

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

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

A - Very Very Primitive Game

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

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

C - Bowls and Dishes

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

A＼B123456
1-21010
2--2012
3---000
4----21
5-----0
6------

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

今回はこの条件による組み合わせの列挙を 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

Related by Tags

Related by Categories