AtCoder Beginner Contest 131 #ABC131
2023-12-28AtCoder Beginner Contest 131 の A/B/C の解法。
実装はこちら atcoder/abc/101-200/131 · michimani/atcoder 。
A - Security
文字列の各文字を前から順に見ていき、前の文字と同じであれば Bad を出力して終了する。
#include <iostream>
using namespace std;
int main()
{
char prev = '.';
for (unsigned int i = 0; i < 4; i++)
{
char c;
cin >> c;
if (c == prev)
{
cout << "Bad" << endl;
return 0;
}
prev = c;
}
cout << "Good" << endl;
return 0;
}
提出 #48887992 - AtCoder Beginner Contest 131
B - Bite Eating
\(L+i-1\) の絶対値が最小になるような \(i\) を、食べるりんごとして選べばよい。 そのような \(\hat{i}\) を探す過程で、全部のりんごを使った場合の合計を計算しておき、最後にその値から \(L+\hat{i}-1\) を引けばよい。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
unsigned int n;
int l;
cin >> n >> l;
int min_abs = 300;
int min_n = 0;
int all = 0;
vector<int> apples(n, 0);
for (unsigned int i = 0; i < n; i++)
{
apples[i] = l + int(i + 1) - 1;
all += apples[i];
if (abs(apples[i]) < min_abs)
{
min_abs = abs(apples[i]);
min_n = i;
}
}
int ans = all - apples[min_n];
cout << ans << endl;
return 0;
}
提出 #48887944 - AtCoder Beginner Contest 131
C - Anti-Division
答えの初期値を \(A\) 以上 \(B\) 以下の数の個数とする。 \(A\) から \(B\) までの範囲で、 \(C\) と \(D\) それぞれで割り切れる数を数える。ただし、それぞれの個数には重複があるので、重複している数を引く必要がある。
重複している数は \(A\) から \(B\) までの範囲で \(C\) と \(D\) の最小公倍数で割り切れる数を数えればよい。
答えの初期値から \(C\) と \(D\) で割り切れる数を引き、 \(C\) と \(D\) の最小公倍数で割り切れる数を足せばよい。
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
unsigned long long gcd(unsigned long long a, unsigned long long b)
{
if (a % b == 0)
{
return b;
}
else
{
return gcd(b, a % b);
}
}
unsigned long long lcm(unsigned long long a, unsigned long long b)
{
return a * b / gcd(a, b);
}
int main()
{
unsigned long long A, B, C, D;
cin >> A >> B >> C >> D;
unsigned long long ans = B - A + 1;
unsigned long long dc = B / C - (A - 1) / C;
unsigned long long dd = B / D - (A - 1) / D;
// duplications
unsigned long long cd_lcm = lcm(C, D);
unsigned long long dup = 0;
if (cd_lcm <= B)
{
dup = B / cd_lcm - (A - 1) / cd_lcm;
}
ans -= (dc + dd - dup);
cout << ans << endl;
return 0;
}
提出 #48887698 - AtCoder Beginner Contest 131
comments powered by Disqus