AtCoder Beginner Contest 060 の A/B/C 問題の解法 #ABC060
2024-01-25AtCoder Beginner Contest 060 の A/B/C 問題の解法。
実装はこちら atcoder/abc/001-100/060 · michimani/atcoder
A - Shiritori
\(A\) の末尾と \(B\) の先頭、\(B\) の末尾と \(C\) の先頭がそれぞれ同じ文字かどうかを判定する。
#include <iostream>
using namespace std;
int main()
{
string a, b, c;
cin >> a >> b >> c;
if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0])
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
提出 #49652307 - AtCoder Beginner Contest 060
B - Choose Integers
整数 \(x,y,z\) について、「\(x\) を \(y\) で割ったあまりが \(z\) になる」ことと「\(x-z\) を \(y\) で割ったあまりが \(0\) である」ことは同値である。
今回の問題では \(x\) を \(A\) の倍数と考えるので、 \(A \times i - C\) を \(B\) で割ったあまりが 0 になる \(i\) が存在するかどうかを見つける問題となる。
\(i = 1,2,3, \dots \) と確認していく際の \(A \times i - C\) を \(B\) で割ったあまりを \(r_i\) とすると、答えが YES となるような入力についてはどこかのタイミングで \(r_i = 0\) となる。答えが NO となるような入力については、 \(r_i\) の現れ方が周期的になる。つまり、 \(r_i = r_j\) 且つ \(r_{i+1} = r_{j+1}\) となるような \(i, j (i \lt j)\) が存在する。このような \(i, j\) が現れた時点で答えは NO となる。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ui = unsigned int;
int main()
{
ui a, b, c;
cin >> a >> b >> c;
map<ui, ui> rm;
vector<ui> rv;
ui x = 1;
ui pr = 0;
bool exists = false;
while (true)
{
ui r = (a * x - c) % b;
if (r == 0)
{
cout << "YES" << endl;
return 0;
}
if (rm.count(r) > 0)
{
if (exists && rv[rm[r] - 1] == pr)
{
cout << "NO" << endl;
return 0;
}
exists = true;
}
else
{
exists = false;
}
rv.push_back(r);
rm[r] = rv.size() - 1;
pr = r;
x++;
}
return 0;
}
提出 #49652242 - AtCoder Beginner Contest 060
C - Sentou
\(t_i (1 \leq i \leq N)\) は 1 人目の人がスイッチを押してからの経過時間なので、単純に \(i\) 人目の人がスイッチを押した時刻と考えられる。
\(i+1\) 人目の人がスイッチを押した時刻と \(i\) 人目の人がスイッチを押した時刻の差が \(T\) 未満の場合、まだシャワーが出ている状態であり、 \(T\) 以上の場合はシャワーが止まっている状態となる。
シャワーが出ている状態でスイッチを押すと、既に出ているシャワーの残り時間を無視してその時点から \(T\) 秒間シャワーが出ることになるので、シャワーが出ている合計時間としては重複している分だけ短くなる。具体的には、 \(t_{i+1} - t_i\) 分だけ合計時間が加算されることになる。
スイッチが押されていない状態では、\(t_{i+1} - t_i>= T\) となるので、合計時間としては \(\min (T, t_{i+1} - t_i)\) を加算していけばよい。
#include <iostream>
#include <cmath>
using namespace std;
using ui = unsigned int;
int main()
{
ui n, t;
cin >> n >> t;
ui ans = t;
ui prev = 0;
for (ui i = 0; i < n; i++)
{
ui tt;
cin >> tt;
ans += min(t, tt - prev);
prev = tt;
}
cout << ans << endl;
return 0;
}
提出 #49634392 - AtCoder Beginner Contest 060
comments powered by Disqus