AtCoder Beginner Contest 343 の A/B/C/D 問題の解法 #ABC343

2024-03-03

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

実装はこちら atcoder/abc/301-400/343 · michimani/atcoder 。

A - Wrong Answer

\(i = 0, 1, \dots, 9 \) に対して、 \(i \neq A +B\) となった時点で \(i\) を出力して終了する。

#include <iostream>

using namespace std;
using ui = unsigned int;

int main()
{
  ui a, b;
  cin >> a >> b;

  for (ui i = 0; i <= 9; i++)
  {
    if (i != a + b)
    {
      cout << i << endl;
      return 0;
    }
  }

  return 0;
}

提出 #50771120 - AtCoder Beginner Contest 343

B - Adjacency Matrix

各行 \(i\) に対して各列 \(j\) として、 \(A_{i,j}= 1\) となるときの \(j\) を空白区切りで出力する

ここでは出力する行を string ans で持つようにして、毎回 j + " " を追加していき、出力する前に ans.pop_back() で末尾の空白を削除している。

#include <iostream>

using namespace std;
using ui = unsigned int;

int main()
{
  ui n;
  cin >> n;

  for (ui i = 0; i < n; i++)
  {
    string ans = "";
    for (ui j = 0; j < n; j++)
    {
      ui a;
      cin >> a;
      if (a == 1)
        ans += to_string(j + 1) + " ";
    }

    if (ans.length() == 0)
    {
      cout << endl;
      continue;
    }

    ans.pop_back();
    cout << ans << endl;
  }

  return 0;
}

提出 #50880774 - AtCoder Beginner Contest 343

C - 343

\(N \leq 10^18\) なので、 \(x^3 = K\) となるような \(x\) の最大値は \(10^6\) である。

なので \(x = 1000000\) からデクリメントしていき、初めて \(x^3 \leq N\) かつ回文となったときの \(x^3\) を出力する。

回分かどうかの判定は、文字列の先頭と末尾の両方から中央に向かって各文字を比較していく。途中で一度でも異なる文字があれば回分ではないと判定し、中央までたどり着けば回分であると判定する。

#include <iostream>
#include <cmath>

using namespace std;
using ui = unsigned int;
using ull = unsigned long long;

bool is_palindrome(string str)
{
  if (str.size() < 2)
    return true;

  ull mid = str.size() / 2;
  ull f = mid - 1, b = mid + str.size() % 2;
  ull i = 0, j = 1;
  while (i < j && i < mid)
  {
    j = str.size() - i - 1;

    if (str[i] != str[j] || str[f - i] != str[b + i])
      return false;

    i++;
  }

  return true;
}

int main()
{
  ull n;
  cin >> n;

  ull mx = 1000000;
  ull ans = 0;
  for (ull i = mx; i > 0; i--)
  {
    ull k = i * i * i;
    if (k <= n && is_palindrome(to_string(k)))
    {
      ans = k;
      break;
    }
  }

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

提出 #50811658 - AtCoder Beginner Contest 343

D - Diversity of Scores

その時点の得点の種類を key、その種類の得点を持っている選手の数を value とする map<ull, ui> sc と、各選手の得点を保持する vector<ull> a を用意する。初期値はすべての選手が \(0\) 点となるので、それぞれ

map<ull, ui> sc = {{0, n}}
vector<ull> a(n, 0)

で初期化する。

各 \(A_t, B_t (t = 1, \dots , T)\) の入力を受け取るたびに、加算前の選手 \(A_t\) の得点を key として sc の value をデクリメントする。その際、 value が 0 になった場合は sc.erase でその key を削除する。

その後、選手 \(A_t\) の得点に \(B_t\) を加算し、あらたな得点を key として sc の value をインクリメントする。

sc.size() が得点の種類の数となるので、それを出力する。

#include <iostream>
#include <vector>
#include <map>

using namespace std;
using ui = unsigned int;
using ull = unsigned long long;

int main()
{
  ui n, t;
  cin >> n >> t;

  map<ull, ui> sc = {{0, n}};
  vector<ull> a(n, 0);

  for (ui i = 0; i < t; i++)
  {
    ui ai;
    ull bi;

    cin >> ai >> bi;

    ai--;

    sc[a[ai]]--;
    if (sc[a[ai]] == 0)
      sc.erase(a[ai]);

    a[ai] += bi;
    sc[a[ai]]++;

    cout << sc.size() << endl;
  }

  return 0;
}