鹿島建設プログラミングコンテスト 2024（AtCoder Beginner Contest 340）の A/B/C 問題の解法 #ABC340

2024-02-11

鹿島建設プログラミングコンテスト 2024（AtCoder Beginner Contest 340）の A/B/C 問題の解法。

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

A - Arithmetic Progression

\(D \geq 1\) なので単純増加の数列になる。なので、単に for 文で \(A\) 以上 \(B\) 以下の数を \(D\) ステップで出力すればよい。

#include <iostream>

using namespace std;
using ui = unsigned int;

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

  for (ui i = a; i <= b; i += d)
  {
    if (i != a)
    {
      cout << " ";
    }
    cout << i;
  }
  cout << endl;

  return 0;
}

提出 #50188196 - 鹿島建設プログラミングコンテスト 2024（AtCoder Beginner Contest 340）

B - Append

配列を用意して、 query 1 のときは \(x\) を配列の末尾に追加、 query 2 のときは配列の後ろから \(k\) 番目の要素を出力すればよい。

#include <iostream>
#include <vector>

using namespace std;
using ui = unsigned int;

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

  vector<ui> xv;
  for (ui i = 0; i < q; i++)
  {
    ui cmd, xk;
    cin >> cmd >> xk;

    if (cmd == 1)
    {
      xv.push_back(xk);
    }
    else
    {
      cout << xv[xv.size() - xk] << endl;
    }
  }

  return 0;
}

提出 #50149989 - 鹿島建設プログラミングコンテスト 2024（AtCoder Beginner Contest 340）

C - Divide and Divide

\(x\) に対して下記の通り再帰処理を行うことで、合計値 \(s\) を計算する。

\(x \leq 1\) のとき \(0\) を返す
\(s\) に \(x\) を加算する
\( \lfloor \frac{x}{2} \rfloor \) と \( \lceil \frac{x}{2} \rceil \) を新たな \(x\) として再帰処理を行う

これだと TLE になるので、 3. を実施する際に以下の工夫をする。

すでに計算済みの値を \(x\) を key とする map で保持する
\(x\) が偶数の場合は \( \lfloor \frac{x}{2} \rfloor = \lceil \frac{x}{2} \rceil \) となるので、片方だけ計算して 2 倍する

#include <iostream>
#include <map>

using namespace std;
using ull = unsigned long long;

ull calc(ull x, map<ull, ull> &m)
{
  if (x <= 1)
    return 0;

  ull s = x;
  if (m.count(x) > 0)
    return s + m[x];

  ull res = 0;
  if (x % 2 == 0)
    res = 2 * calc(x / 2, m);
  else
    res = calc(x / 2, m) + calc(x / 2 + 1, m);

  m[x] = res;

  return s + res;
}

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

  map<ull, ull> m;
  ull ans = calc(n, m);

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