ABC 407
Table of Contents
https://atcoder.jp/contests/abc407
A. Approximation
https://atcoder.jp/contests/abc407/tasks/abc407_a
考えたこと
パット見で方針が立たなくてテンパった。
$|\frac{A}{B} - x|$ を最小化するとき、$|\frac{A - xB}{B}| = \frac{|A - xB|}{B}$ より $|A - xB|$ が最小になるような整数 $x$ を求めれば良さそうと思った。 問題が整数を求めろだったので $x \in [-1000, 1000]$ の範囲で答えを探索するという愚直な方法を取った。 よくよく考えると $A, B$ が正だから負数を考える必要はなかった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b;
cin >> a >> b;
ll mi = INF;
ll ans = 0;
for (ll x = 0; x <= 1000; x++) {
if (abs(a - x * b) < mi) {
ans = x;
mi = abs(a - x * b);
}
}
cout << ans << endl;
}
解説の解説
$\frac{A}{B}$ の小数点以下が $0.5$ 未満なら $\floor{\frac{A}{B}}$、$0.5$ より大きいなら $\lceil \frac{A}{B} \rceil$ が最適。 これは $1/2$ を足して切り捨てを行えば答えが出る。
$\floor{\frac{A}{B} + \frac{1}{2}} = \floor{\frac{2A + B}{2B}}$.
$B$ が奇数だと近い整数が一意に決まるが、偶数のときは $\frac{1}{2}$ のときのように $0, 1$ のどちらも同じ距離になるので一意に決まらない。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b;
cin >> a >> b;
// floor(a/b+1/2) = floor((2a+b)/(2b))
cout << (2 * a + b) / (2 * b) << '\n';
}
B. P(X or Y)
https://atcoder.jp/contests/abc407/tasks/abc407_b
$\text{条件に合致する個数} / 36$ を出力. どのへんが 250 点なのかよくわからない。 普通の200点で良かったのではなかろうか。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll x, y;
cin >> x >> y;
ll cnt = 0;
rep2(i, 1, 7) {
rep2(j, 1, 7) {
if (i + j >= x || abs(i - j) >= y)
cnt++;
}
}
double ans = (double)cnt / 36;
printf("%.10lf\n", ans);
}
C. Security 2
https://atcoder.jp/contests/abc407/tasks/abc407_c
考えたこと
実装方法について結構悩んだ。
末尾の数字が $S_N$ のとき、ボタンB を最低でも $S_N$ 回押したということだからまずは $S_N$ 回を計上。
0 になったら末尾を消すのに 1 回計上。
新しい末尾の数字は $S_{N-1} - S_{N} \mod 10$ になっており、この回数を計上。消すのに 1 回計上。
新しい末尾の数字は $S_{N-2} - S_{N-1} - S_{N} \mod 10$ になっており、この回数を計上。消すのに 1 回計上。
・・・というのを繰り返す。
modint で 10 で割ったときのあまりを計算するように設定すると mod を取る処理が楽になる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> S;
modint::set_mod(10);
using mint = modint;
vector<mint> A;
for (char c : S) {
A.push_back(c - '0');
}
ll ans = 0;
reverse(all(A));
int N = A.size();
rep(i, N) {
mint x = A[i] - ans;
ans += x.val();
}
ans += N; // 数字を消す操作分を足す
cout << ans << endl;
}
D. Domino Covering XOR
https://atcoder.jp/contests/abc407/tasks/abc407_d
考えたこと
ドミノということを忘れて単に1マスずつ埋める埋め方は $2^{HW}$ 通りであるが、$HW \leq 20$ よりたかだか $2^{20} = 1,048,576$ 通りである。そのマスの埋め方がドミノによって実現可能か調べ、可能であれば埋まっていないマスの数字の XOR を計算すればいいかなと思った。 しかし、埋め方の実現可能性チェックの仕方が甘くて1ペナ食らった。
左上から調べていったときに横向きの置き方ができたら横向きでおき、そうでなければ縦向きで置くという方法で実現可能性をチェックした。 サンプルは通ったが、この方法では以下のような例で失敗するとわかった。
失敗する例
x##x
x..x
x が縦置き、# が横置き、. が空きマスとする
再帰を使って全てのマスの置き方を調べることも考えたが重複する置き方を何度も数えそうだし、一つのドミノをおいたあとに次の状態への遷移方法がどうするのが最適なのか思いつかなかった。
遷移というのを考えた時点で、ドミノを置くことによってマスが埋まっている状態から、新しいドミノを置いてできた状態ははドミノの置き方として実現できる置き方だから、ドミノを一つも置いていない状態からドミノをおける場所においた新たな状態を作り出していき、その状態から新たなドミノを置くというのを繰り返していけば状態を全探索できると気づいた。 ドミノを置くことによって埋まるマスの状態は $2^20 = 1,048,576$ 通りより少ないことは明らかなので愚直にシミュレーションしても実行時間制限に間に合いそうだと思った。
サンプル3 が最大ケースだが TLE にならなかったので計算量的には問題ないと確信した。
実際にシミュレーション結果を見ると $4 \times 5$ のときにドミノの置き方に着目せずに単にマスが埋まっている状態だけに着目したときの状態数は $58830$ 通りらしい。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll H, W;
cin >> H >> W;
vvll grid(H, vll(W));
rep(i, H) rep(j, W) cin >> grid[i][j];
ll ans = 0;
auto to_index = [&](int i, int j) -> int {
return i * W + j;
};
auto has_bit = [&](int x, int i, int j) -> bool {
int id = to_index(i, j);
return (x >> id) & 1;
};
auto set_bit = [&](int x, int i, int j) -> ll {
return x | (1ll << to_index(i, j));
};
auto cal = [&](int bs) -> void {
ll ret = 0;
rep(i, H) rep(j, W) {
if (!has_bit(bs, i, j))
ret ^= grid[i][j];
}
chmax(ans, ret);
};
set<int> memo;
memo.insert(0);
queue<int> que;
que.push(0);
while (que.size()) {
int state = que.front();
que.pop();
cal(state);
rep(i, H) rep(j, W) {
if (has_bit(state, i, j))
continue;
if (j + 1 < W && !has_bit(state, i, j + 1)) {
int t = state;
t = set_bit(t, i, j);
t = set_bit(t, i, j + 1);
if (!memo.count(t)) {
memo.insert(t);
que.push(t);
}
}
if (i + 1 < H && !has_bit(state, i + 1, j)) {
int t = state;
t = set_bit(t, i, j);
t = set_bit(t, i + 1, j);
if (!memo.count(t)) {
memo.insert(t);
que.push(t);
}
}
}
}
cout << ans << endl;
}
再帰関数だと面倒と思ったが、メモ化再帰をすればいいだけだった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll H, W;
cin >> H >> W;
vvll grid(H, vll(W));
rep(i, H) rep(j, W) cin >> grid[i][j];
ll ans = 0;
auto to_index = [&](int i, int j) -> int {
return i * W + j;
};
auto has_bit = [&](int x, int i, int j) -> bool {
int id = to_index(i, j);
return (x >> id) & 1;
};
auto cal = [&](int bs) -> void {
ll ret = 0;
rep(i, H) rep(j, W) {
if (!has_bit(bs, i, j))
ret ^= grid[i][j];
}
chmax(ans, ret);
};
set<int> memo;
auto dfs = [&](auto dfs, int state) -> void {
cal(state);
rep(i, H) rep(j, W) {
if (i + 1 < H && !has_bit(state, i, j) && !has_bit(state, i + 1, j)) {
int nx_state = state | (1ll << to_index(i, j)) | (1ll << to_index(i + 1, j));
if (!memo.count(nx_state)) {
memo.insert(nx_state);
dfs(dfs, nx_state);
}
}
if (j + 1 < W && !has_bit(state, i, j) && !has_bit(state, i, j + 1)) {
int nx_state = state | (1ll << to_index(i, j)) | (1ll << to_index(i, j + 1));
if (!memo.count(nx_state)) {
memo.insert(nx_state);
dfs(dfs, nx_state);
}
}
}
};
dfs(dfs, 0);
cout << ans << endl;
}
E. Most Valuable Parentheses
https://atcoder.jp/contests/abc407/tasks/abc407_e
解説 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int N;
cin >> N;
vll A(N * 2);
rep(i, N * 2) cin >> A[i];
ll ans = 0;
ans += A[0];
priority_queue<ll> pq;
for (int i = 1; i + 1 < N * 2; i += 2) {
pq.push(A[i]);
pq.push(A[i + 1]);
ans += pq.top();
pq.pop();
}
cout << ans << endl;
};
int t;
cin >> t;
rep(i, t) {
cal();
}
}
F. Sums of Sliding Window Maximum
https://atcoder.jp/contests/abc407/tasks/abc407_f