---
# System prepended metadata

title: HHKB Programming Contest 2020 題解
tags: [Programming Contest]

---

---
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 左邊），且這兩個線段不重疊的方法數：

![](https://i.imgur.com/8kbDao0.png =400x)


其中 $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/)
:::