NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） #ABC253

2024-01-13

NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）の A/B/C/D 問題の解法。

実装はこちら atcoder/abc/201-300/253 · michimani/atcoder 。

A - Median?

入力される値は 3 つなので、 \(a \leq b \leq c\) または \(c \leq b \leq a\) である場合に Yes 、それ以外の場合に No を出力する。

#include <iostream>

using namespace std;

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

  if ((a <= b && b <= c) || (c <= b && b <= a))
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }

  return 0;
}

提出 #49236403 - NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）

B - Distance Between Tokens

2 つの o が表示されている位置をそれぞれ \((h1, w1)\) と \((h2, w2)\) として、 \( \vert h1 - h2 \vert + \vert w1 - w2 \vert \) を計算すればよい。

#include <iostream>

using namespace std;
using ui = unsigned int;

int main()
{
  ui h, w;
  cin >> h >> w;

  int h1, w1, h2, w2;
  ui sc = 0;
  for (ui hi = 0; hi < h; hi++)
  {
    for (ui wi = 0; wi < w; wi++)
    {
      char s;
      cin >> s;
      if (s == 'o')
      {
        sc++;
        if (sc == 1)
        {
          h1 = int(hi), w1 = int(wi);
        }
        else
        {
          h2 = int(hi), w2 = int(wi);
        }
      }
    }
  }

  cout << abs(h1 - h2) + abs(w1 - w2) << endl;
  return 0;
}

提出 #49236403 - NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）

C - Max - Min Query

多重集合 \(S\) を map<ui, ui> s で記録する。各 \(query_i\) に対して、次の処理を行う。

1 x の場合
- s[x] の値をインクリメントする。
2 x c の場合
- s[x] の値から、 \(min (c, \vert S_x \vert)\) を引く。ここで \(\vert S_x \vert\) は s[x] の値、つまり \(S\) に含まれる \(x\) の個数を表す。
- s[x] の値が 0 になった場合は、 s.erase(x) で map から \(key\) を削除することで \(S\) から \(x\) がすべて削除されたことを表現する。
3 の場合
- s[x].begin()->fist で最小値を取得する。
- s[x].rbegin()->first で最大値を取得する。
- 最大値と最小値の差を出力する。

3 の場合の処理が成立するのは、 C++ の std:map のイテレータの仕様によるもの。 std:map のイテレータは、 \(key\) の昇順で値が取り出されるため、begin および rbegin を使うことで先頭（=最小）と末尾（=最大）を取得することができる。

#include <iostream>
#include <map>
#include <cmath>

using namespace std;
using ui = unsigned int;

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

  map<ui, ui> s;
  for (ui i = 0; i < q; i++)
  {
    ui cmd, x, c;
    cin >> cmd;

    switch (cmd)
    {
    case 1:
      cin >> x;
      s[x]++;
      break;

    case 2:
      cin >> x >> c;
      s[x] -= min(c, s[x]);
      if (s[x] == 0)
      {
        s.erase(x);
      }
      break;

    case 3:
      cout << s.rbegin()->first - s.begin()->first << endl;
      break;

    default:
      // noop
      break;
    }
  }

  return 0;
}

提出 #49237889 - NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）

D - FizzBuzz Sum Hard

まず、 \(1\) から \(N\) までの総和を求める。これは、 \(\frac{N (N + 1)}{2}\) で求めることができる。

ここから \(A\) と \(B\) の倍数を引いていく。 \(A\) と \(B\) それぞれについて倍数を引いていく際に、 \(A\) と \(B\) の公倍数を 2 回引いてしまわないように注意する。また、そもそも \(A = B\) の場合は \(A\) の倍数のみ引けばよい。

#include <iostream>
#include <cmath>

using namespace std;
using ull = unsigned long long;

int main()
{
  ull n, a, b;
  cin >> n >> a >> b;

  ull ans = (1 + n) * n / 2;
  for (ull i = a; i <= n; i += a)
  {
    ans -= i;
  }

  if (a != b)
  {
    for (ull j = b; j <= n; j += b)
    {
      ans -= j * ull(j % a != 0);
    }
  }

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