ABC 345
Table of Contents
https://atcoder.jp/contests/abc345
A. Leftrightarrow
https://atcoder.jp/contests/abc345/tasks/abc345_a
B. Integer Division Returns
https://atcoder.jp/contests/abc345/tasks/abc345_b
C. One Time Swap
https://atcoder.jp/contests/abc345/tasks/abc345_c
D. Tiling
https://atcoder.jp/contests/abc345/tasks/abc345_d
2026/1/17 小手先の高速化を何回か試みたら AC してしまったがデータサイズが小さかったのでたまたまと思われる。なのでほぼ解説 AC 相当
上の方から順に左詰めでタイルをおいて隙間を埋めていくことを考える。上から見ていって空いているマスのうち一番左のマスにタイルを置く。このときタイルの置き方は $\text{(まだ置かれていないタイルの個数) \times 2}$ 通りの置き方がある。
これを繰り返すので空きマスの探索に $O(HW)$、タイルの置き方に $O(N! 2^N)$ かかるので計算量は $O(HW N! 2^N)$ となる。 $HW \times N! \times 2^N = 10 \times 10 \times 7! \times 2^7 = 6.45 \times 10^7$ なので十分間に合う。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, H, W;
cin >> N >> H >> W;
vll A(N), B(N);
rep(i, N) cin >> A[i] >> B[i];
vvint grid(H, vint(W, -1));
auto dfs = [&](auto dfs, int used, int curi, int curj) -> bool {
while (grid[curi][curj] != -1) {
curj++;
if (curj == W) {
curi++;
curj = 0;
}
if (curi == H) break;
}
if (curi == H)
return true;
rep(k, N) {
if (used >> k & 1) continue;
ll a = A[k], b = B[k];
rep(_, 2) {
int ok = 1;
rep(i, a) rep(j, b) {
int ni = curi + i, nj = curj + j;
if (ni < H && nj < W && grid[ni][nj] < 0) {
grid[ni][nj] = k;
} else {
ok = 0;
}
}
if (ok && dfs(dfs, used | 1ll << k, curi, curj))
return true;
rep(i, a) rep(j, b) {
int ni = curi + i, nj = curj + j;
if (ni < H && nj < W && grid[ni][nj] == k) {
grid[ni][nj] = -1;
}
}
swap(a, b);
}
}
return false;
};
yesno(dfs(dfs, 0, 0, 0));
}
E. Colorful Subsequence
https://atcoder.jp/contests/abc345/tasks/abc345_e
F. Many Lamps
https://atcoder.jp/contests/abc345/tasks/abc345_f