---
tags: Programming Contest
---
# HHKB Programming Contest 2020 題解
[題目連結](https://atcoder.jp/contests/hhkb2020/tasks)
## 心得
B 一直搞錯題意，花了二十分鐘才解出來。
E 太晚去看，應該要是能解出來的，時間都花在第四題上，但就是做不出來。
｡:ﾟ(;´∩`;)ﾟ:｡
## A
```python
S = input()
T = input()
print(T.upper() if S == 'Y' else T)
```
## B. Futon
他問的是有多少種放置的方式，而不是有多少種不同的位置可以放……。
```python
H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for r in range(H):
for c in range(W):
if S[r][c] == '.':
if r + 1 < H and S[r + 1][c] == '.':
ans += 1
if c + 1 < W and S[r][c + 1] == '.':
ans += 1
print(ans)
```
## C. Neq Min
開個陣列，記錄哪些數字還沒出現過，amortized 時間仍是 $O(N)$。
```python
N = int(input())
P = [int(x) for x in input().split()]
vis = [False for _ in range(200000 + 10)]
val = 0
for p in P:
vis[p] = True
while vis[val]:
val += 1
print(val)
```
## D. Squares
在研究完 [官方題解](https://atcoder.jp/contests/hhkb2020/editorial/229) 與 [Spheniscine 題解](https://codeforces.com/blog/entry/83623) 後我終於解出這題了。
也太困難了吧，竟然進行了兩次用反面來算正面。
基本上這兩個題解都寫得很好，除了 $X_4$ 到底怎麼算，我這邊提供利用重複組合的想法。$X_4$ = 在長度為 N 的線段中，放入長度為 A 與長度為 B 的線段（A 在 B 左邊），且這兩個線段不重疊的方法數：
其中 $C_1, C_2, C_3 \ge 0$ 是空格的長度。我們可以得出
$$
C_1 + A + C_2 + B + C_3 = N \implies C_1 + C_2 + C_3 = N - A - B
$$
$X_4$ 等價於問 $C_1, C_2, C_3$ 的非負整數解個數，即
$$
X_4 = H^3_{N-A-B} = {N - A - B + 3 - 1 \choose N - A - B} = {N - A - B + 2 \choose 2}
$$
```python
TC = int(input())
for _ in range(TC):
N, A, B = map(int, input().split())
M = 10 ** 9 + 7
if A + B > N:
print(0)
else:
X4 = (N - A - B + 2) * (N - A - B + 1) // 2
X3 = 2 * X4 % M
X2 = (N - A + 1) * (N - B + 1) % M - X3 % M + M
X1 = X2 ** 2 % M
ans = (N - A + 1) ** 2 % M * (N - B + 1) ** 2 % M - X1 + M
print(ans % M)
```
## E. Lamps
看各個 tidy square 對答案貢獻了多少，即有多少種放置的方法能使這一格亮起來。
假設某個 tidy square 會被 $cnt$ 個 tidy squares 影響（含自己），那該 tidy square 能貢獻 $2^k - 2^{k - cnt}$ 到答案中，$k$ 是所有 tidy squares 的數量。因為在這 $cnt$ 個 tidy squares 中有**任一個位置或多個**被放了燈，該 tidy square 就會是亮的，至於這總共會有多少種情況？我們可以用扣的：**「任一個或多個被放的方法數」=「所有放置的方法數」-「這些 tidy squares 都沒有被放置燈的方法數」**，也就是 $2^k - 2^{k - cnt}$。
實作上，`cnt` 可以用 4 個 $O(HW)$ 求出。以下程式碼使用 AtCoder Library，submit 前記得先用 expander 將之轉換（公告說下個比賽開始就不用了，nice）。
```cpp
#include <algorithm>
#include <atcoder/modint>
#include <iostream>
#include <vector>
using namespace std;
using mint = atcoder::modint1000000007;
int solve() {
int H, W;
cin >> H >> W;
auto S = vector<string>(H);
for (int r = 0; r < H; r++) {
cin >> S[r];
}
int n_tidy = 0;
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
if (S[r][c] == '.') {
n_tidy++;
}
}
}
auto cntL = vector<vector<int>>(H, vector<int>(W, 0));
auto cntR = vector<vector<int>>(H, vector<int>(W, 0));
auto cntU = vector<vector<int>>(H, vector<int>(W, 0));
auto cntD = vector<vector<int>>(H, vector<int>(W, 0));
for (int r = 0; r < H; r++) {
for (int c = 1; c < W; c++) {
if (S[r][c] == '.') {
cntL[r][c] = ((S[r][c - 1] == '.') ? cntL[r][c - 1] + 1 : 0);
}
}
for (int c = W - 2; c >= 0; c--) {
if (S[r][c] == '.') {
cntR[r][c] = ((S[r][c + 1] == '.') ? cntR[r][c + 1] + 1 : 0);
}
}
}
for (int c = 0; c < W; c++) {
for (int r = 1; r < H; r++) {
if (S[r][c] == '.') {
cntU[r][c] = ((S[r - 1][c] == '.') ? cntU[r - 1][c] + 1 : 0);
}
}
for (int r = H - 2; r >= 0; r--) {
if (S[r][c] == '.') {
cntD[r][c] = ((S[r + 1][c] == '.') ? cntD[r + 1][c] + 1 : 0);
}
}
}
mint ans = 0;
mint all = mint(2).pow(n_tidy);
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
if (S[r][c] == '.') {
int cnt = cntR[r][c] + cntL[r][c] + cntU[r][c] + cntD[r][c] + 1;
ans += all - mint(2).pow(n_tidy - cnt);
}
}
}
return ans.val();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << solve() << endl;
return 0;
}
```
:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::
Sign in with Wallet
Connect another wallet