THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318） #ABC318
2023-12-21問題 - THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318） の A/B/C 問題の解法。
実装はこちら atcoder/abc/301-400/318 · michimani/atcoder 。
A - Full Moon
何日目かを \(d\) として、 \(m \leq d \leq N\) の範囲で \(d -m\) が \(p\) の倍数となる日を探す。
#include <iostream>
using namespace std;
int main()
{
unsigned int n, m, p;
cin >> n >> m >> p;
unsigned int ans = 0;
for (unsigned int d = m; d <= n; d++)
{
ans += ((d - m) % p == 0);
}
cout << ans << endl;
return 0;
}
提出 #48698406 - THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）
B - Overlapping sheets
座標を表す bool の連想配列を \(100 \times 100 \) で用意し、各 \(A, B, C,D\) で与えられる範囲を true にする。最後に true の数を数える。ループが多くなるが制約の範囲内であれば問題ない。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<vector<bool>> grid(101, vector<bool>(101, false));
unsigned int n;
cin >> n;
for (unsigned int i = 0; i < n; i++)
{
unsigned int a, b, c, d;
cin >> a >> b >> c >> d;
for (unsigned int y = c; y < d; y++)
{
for (unsigned int x = a; x < b; x++)
{
grid[y][x] = true;
}
}
}
int ans = 0;
for (unsigned int i = 0; i <= 100; i++)
{
for (unsigned int j = 0; j <= 100; j++)
{
ans += int(grid[i][j]);
}
}
cout << ans << endl;
return 0;
}
提出 #48698148 - THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）
C - Blue Spring
各 \(F\) の入力を受けて配列 f に格納しつつ、単純に足したものを sum として保持する。
f を降順でソートし、先頭から \(D\) ずつ部分和を計算していき、都度 \(P\) との大小を比較する。
最後は \(D\) 分残っていない可能性があるので、部分和の終点は \(N\) と \(現在地 + D\) の小さい方を採用する。
部分和が \(P\) より大きい場合は sum から部分和を引いて \(P\) を足す。 部分和が \(P\) 以下になった時点で、それ以降は比較する必要がないので break する。
これを f の最後まで繰り返す。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
unsigned int n, d;
unsigned long long p;
cin >> n >> d >> p;
vector<unsigned long long> f(n, 0);
unsigned long long sum = 0;
for (unsigned int i = 0; i < n; i++)
{
cin >> f[i];
sum += f[i];
}
sort(f.rbegin(), f.rend());
for (unsigned int i = 0; i < n; i += d)
{
unsigned long long part_sum = 0;
for (unsigned int ii = i; ii < min(n, i + d); ii++)
{
part_sum += f[ii];
}
if (part_sum <= p)
{
break;
}
sum = sum - part_sum + p;
}
cout << sum << endl;
}
提出 #48694625 - THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）
comments powered by Disqus