ABC 415
Table of Contents
https://atcoder.jp/contests/abc415
A. Unsupported Type
https://atcoder.jp/contests/abc415/tasks/abc415_a
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
ll X;
cin >> X;
int ok = 0;
rep(i, N) if (A[i] == X) ok = 1;
yesno(ok);
}
B. Pick Two
https://atcoder.jp/contests/abc415/tasks/abc415_b
void solve() {
ios base::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> S;
vll ids;
rep(i, (ll)S.size()) {
if (S[i] == '#') ids.push_back(i + 1);
}
for (ll i = 0; i < (ll)ids.size(); i += 2) {
cout << ids[i] << ',' << ids[i + 1] << endl;
}
}
C. Mixture
https://atcoder.jp/contests/abc415/tasks/abc415_c
薬品を何も混合していない状態を安全な状態とし、そこから薬品を混合して安全な状態から安全な状態への遷移を考える。 最終的に全ての薬品を混合して安全な状態にたどり着ければ Yes で、そうでなければ No となる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
ll N;
string S;
cin >> N >> S;
S = "0" + S;
vector<bool> dp((1ll << N), false);
dp[0] = true;
rep(now, 1 << N) {
if (!dp[now]) continue;
rep(i, N) {
int nx = now | (1 << i);
if (S[nx] != '0') continue;
dp[nx] = true;
}
}
yesno(dp[(1ll << N) - 1]);
};
int t;
cin >> t;
rep(i, t) cal();
}
D. Get Many Stickers
https://atcoder.jp/contests/abc415/tasks/abc415_d
自力で解けたがコンテスト中に解けなかったが自力 AC。 $B_i/A_i$ が大きい順に選ぶのがもっとも効率が良さそうだったが sample 3 でうまくいかず。 $A_i - B_i$ が小さい順に選ぶようにしたら AC した。
※ 飲むコーラの本数を最大化する場合は $B_i / A_i$ が大きい順に交換を行うのが最適なのかとおもったが、そうではらしいことを G 問題で知った。
$A_i \leq N$ のときに、$(A_i, B_i)$ の交換を行える回数を $n$ とする. $n$ は交換を繰り返して手持ちの空き瓶の数が $A_i$ 未満になる最初の数であるから
\begin{align*} N - n(A_i - B_i) < A_i \\ n > \frac{N - A_i}{A_i - B_i} \\ n = \floor{\frac{N - A_i}{A_i - B_i}} + 1 \end{align*}
struct Change {
ll A, B;
};
bool operator>(const Change& p, const Change& q) {
return p.A - p.B > q.A - q.B;
}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vll A(M), B(M);
rep(i, M) cin >> A[i] >> B[i];
priority_queue<Change, vector<Change>, greater<Change>> pq;
rep(i, M) {
pq.push({A[i], B[i]});
}
ll akibin = N;
ll ans = 0;
while (pq.size()) {
auto [A, B] = pq.top();
if (akibin < A) {
pq.pop();
continue;
}
ll x = (akibin - A) / (A - B) + 1;
akibin -= x * (A - B);
ans += x;
}
cout << ans << endl;
}
E. Hungry Takahashi
https://atcoder.jp/contests/abc415/tasks/abc415_e
自力で解けたがコンテスト中に解けなかったが自力 AC。
$H+W-1$ 日後にはマス $(H, W)$ に到達する。
初期値 $x$ を決めたときに、実際にシミュレーションを行い移動の間にコインの枚数が負数にならなければその初期値での移動が可能である。
初期値 $x$ は二分探索で求めることができる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int H, W;
cin >> H >> W;
vvll A(H, vll(W));
rep(i, H) rep(j, W) cin >> A[i][j];
vll food(H + W - 1);
rep(i, H + W - 1) cin >> food[i];
vint di = {1, 0};
vint dj = {0, 1};
auto judge = [&](ll x) -> bool {
vvll rem_power(H, vll(W, -INF));
rem_power[0][0] = x + A[0][0] - food[0];
if (rem_power[0][0] < 0) return false;
using P = tuple<ll, ll, ll>;
queue<P> que;
que.push({0, 0, rem_power[0][0]});
while (que.size()) {
auto [i, j, p] = que.front();
que.pop();
rep(d, 2) {
int ni = i + di[d], nj = j + dj[d];
if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj) continue;
ll nxp = rem_power[i][j] + A[ni][nj] - food[ni + nj];
if (nxp < 0) continue;
if (rem_power[ni][nj] >= nxp) continue;
rem_power[ni][nj] = nxp;
que.push({ni, nj, nxp});
}
}
return rem_power[H - 1][W - 1] >= 0;
};
if (judge(0)) {
cout << 0 << endl;
return;
}
ll ac = INF, wa = 0;
while (ac - wa > 1) {
ll wj = (ac + wa) / 2;
if (judge(wj)) {
ac = wj;
} else {
wa = wj;
}
}
cout << ac << endl;
}
F. Max Combo
https://atcoder.jp/contests/abc415/tasks/abc415_f