今週も参加して参りましたAtCoder Beginner Contest
A,B,Cとトントン拍子で正解し、「今日こそは４完だ！！」と次の問題へ！
D問題を見て素朴な解法しか思いつかず、「よし、絶対TLEだな」。
確信したのでE問題に手を出した。
結果E問題ではWAが取れず、コンテスト終了。
成績はまたもや3完。
３完がデフォになりつつあるのほんとにまずい、、
E問題はセグ木でACLをインストールしてなかった私が解けるはずもなかったが
D問題の二分探索（ちょうど最近勉強していたところ）は正解したかった、、
A問題 Print 341
#include <iostream>
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
int main() {
int N;
std::cin >> N;
for (int n = 0; n < N; n++) std::cout << 10;
std::cout << 1 << std::endl;
}B問題 Foreign Exchange
#include <iostream>
#include <vector>
int main() {
int N;
std::cin >> N;
std::vector<long long> A(N), S(N - 1), T(N - 1);
for (int n = 0; n < N; n++) std::cin >> A[n];
for (int n = 0; n < (N - 1); n++) std::cin >> S[n] >> T[n];
for (int n = 0; n < (N - 1); n++) {
long long time = (A[n] / S[n]);
A[n + 1] += T[n] * time;
}
std::cout << A[N - 1] << std::endl;
}C問題 Takahashi Gets Lost
#include <iostream>
#include <vector>
#include <queue>
int main() {
int H, W, N;
std::string T;
std::cin >> H >> W >> N >> T;
std::vector<std::string> Grid(H);
for (int h = 0; h < H; h++) std::cin >> Grid[h];
auto dfs = [&](auto self, int r, int c) {
std::queue<std::pair<int, int>> q;
q.push({ r,c });
for (int t = 0; t < N; t++) {
if (q.size() <= 0) return false;
std::pair<int, int> tmp = q.front(); q.pop();
int new_r = tmp.first;
int new_c = tmp.second;
switch (T[t]) {
case 'L':
new_c -= 1;
break;
case 'R':
new_c += 1;
break;
case 'U':
new_r -= 1;
break;
case 'D':
new_r += 1;
break;
}
if ((new_r < 0) || (H <= new_r)) return false;
if ((new_c < 0) || (W <= new_c)) return false;
if (Grid[new_r][new_c] == '#') return false;
q.push({ new_r , new_c });
}
return true;
};
int ans = 0;
for (int h = 0; h < H; h++) {
for (int w = 0; w < W; w++) {
if (Grid[h][w] == '#') continue;
if (dfs(dfs, h, w) == true) ans++;
}
}
std::cout << ans << std::endl;
}D問題 Only one of two
#include <iostream>
#include <limits.h>
int main() {
long long N, M, K;
std::cin >> N >> M >> K;
auto gcd = [](auto self, long long a, long long b) -> long long //2数の最大公約数を求める関数
{
//ユークリッドの互除法
if (b < a) std::swap(a, b); //bよりaの方が大きい時は入れ替える（常にa<bの構図を作っておく） ※不要説あり
if ((b % a) == 0) return a; //bがaで割り切れるとき、aはbの約数になる
return self(self, a, (b % a));
};
auto lcm = [&](long long a, long long b) {return (a * b) / gcd(gcd, a, b); }; //2数の最小公倍数を求める関数
long long lower = 0;
long long upper = LLONG_MAX/2;
while ((lower + 1) < upper) {
long long tmp = (lower + upper) / 2;
long long N_divisible_cnt = (tmp / N); //K以下の整数のうち、Nで割り切れる数の個数
long long M_divisible_cnt = (tmp / M); //K以下の整数のうち、Mで割り切れる数の個数
long long NM_divisible_cnt = (tmp / lcm(N, M)); //K以下の整数のうち、NでもMでも割り切れる数の個数
long long only_one_divisible_cnt = N_divisible_cnt + M_divisible_cnt - (2 * NM_divisible_cnt);
if (K <= only_one_divisible_cnt) upper = tmp;
else lower = tmp;
}
std::cout << upper << std::endl;
}数学的考察（というか知識）が必要な問題でしたね。
「AとBのどちらかで割り切れる数の個数」＝「Aで割り切れる数の個数＋Bで割り切れる数の個数ー2×（AとBの両方で割り切れる数の個数）」は忘れちゃいけない大事なポイント。
義務教育で似たような問題をやったことがあるけど、忘れちゃってました。。
最小公倍数の求め方も地味に大事なポイント。
最小公倍数を求めるためには最大公約数が必要で、最大公約数はユークリッドの互除法を使って求める。
E問題 Alternating String
#include <iostream>
#include <vector>
#include <atcoder/segtree.hpp>
int op(int a, int b) { return (a + b); };
int e() { return 0; };
int main() {
int N, Q;
std::string S;
std::cin >> N >> Q >> S;
atcoder::segtree<int, op, e> seg(N+1);
for (int n = 1; n < N; n++) if (S[n-1] != S[n]) seg.set(n, 1); //前の値と違う場合に１にする（このデータ変換を思いつけるかが勝負）
for (int q = 0; q < Q; q++) {
int type, l, r;
std::cin >> type >> l >> r;
switch (type) {
case 1:
l--;
seg.set(l, (1 - seg.get(l)));
seg.set(r, (1 - seg.get(r)));
break;
case 2:
/*for (int i = l; i <= r; i++) std::cout << seg.get(i);
std::cout << std::endl;*/
std::cout << ((seg.prod(l, r) == (r - l)) ? "Yes" : "No") << std::endl; //「Al~Arの総和」＝「R-L」となればいい文字列
break;
}
}
}ポイントは２つあり、
1つ目のポイントは与えられたデータを「1つ前の値との差のフラグ」に変換すできるかという点。
２つ目のポイントは「Al～Arの総和」＝「R-L」となればいい文字列となることに気付けるかという点。
せっかく取り組んだので考え方の引き出しの一つとして持っておきたいですね。
コメント