鹿島建設プログラミングコンテスト 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;
}
提出 #50188699 - 鹿島建設プログラミングコンテスト 2024(AtCoder Beginner Contest 340)
comments powered by Disqus