2020-10-10

【Python】HHKB プログラミングコンテスト 2020 解説

A - Keyboard

upper()を使うと簡単.

S = input()
T = input()
ans = T.upper() if S == 'Y' else T
print(ans)

B - Futon

B問題でgridを扱う問題が出題されるのは珍しい気がする.
grid上を全探索する.

H, W = map(int, input().split())
# H行目, W列目に番兵(#)を追加する
grid = [list(input()) + ['#'] for _ in range(H)]
grid.append(['#'] * (W + 1))

cnt = 0
for i in range(H):
    for j in range(W):
        cnt += (grid[i][j] == '.' and grid[i + 1][j] == '.')
        cnt += (grid[i][j] == '.' and grid[i][j + 1] == '.')
print(cnt)

C - Neq Min

公式解説と同じ方針.
ある整数の登場(1)・未登場(0)を管理する配列を用意して, 配列を小さい方から順に探索して最初に未登場(0)となっている整数が答えである.
毎回0から探索すると計算量が $\mathcal{O}(N^2)$ となってしまうため, 答えが単調増加となる特徴を利用して前回の答えを記憶しておくことで計算量を減らす.

N = int(input())
P = list(map(int, input().split()))

memo = [0] * (200000 + 2)  # 整数の登場(1)・未登場(1)を管理する配列.
cur = 0  # 現在の答え. 0から単調増加する.

for p in P:
    memo[p] = 1
    while memo[cur] == 1:
        cur += 1
    print(cur)

D - Squares

解説AC.
うーん、解けそうで解けなかった.

import sys

MOD = 10 ** 9 + 7

T = int(input())
for _ in range(T):
    N, A, B = map(int, sys.stdin.readline().split())
    # X4
    if N - A - B < 0:
        X4 = 0
    else:
        X4 = ((N - A - B + 2) * (N - A - B + 1)) // 2
        X4 %= MOD
    
    # X3
    X3 = 2 * X4

    # X2
    X2 = (N - A + 1) * (N - B + 1) - X3
    X2 %= MOD

    # X1
    X1 = pow(X2, 2, MOD)

    # X0
    X0 = (pow(N - A + 1, 2, MOD) * pow(N - B + 1, 2, MOD)) % MOD
    
    ans = X0 - X1
    print(ans % MOD)

E - Lamps

公式解説と同じ方針.

実装時に悩んだのが「あるマスから上下左右方向にいくつ空マスが連続するか」を数える部分.
DFSとかいろいろ考えて効率よく求めようとしたけど, 結局は愚直に1方向ずつ順に求める方法に落ち着いた.

H, W = map(int, input().split())
S = [input() for _ in range(H)]
MOD = 10 ** 9 + 7

# K: 空マスの個数
K = sum(S[i][j] == '.' for i in range(H) for j in range(W))

# Dx: あるマスから上下左右方向に連続する空マスの個数.
# Du Dr Dd Dl : 上 右 下 左
Du = [[0] * W for _ in range(H)]
Dr = [[0] * W for _ in range(H)]
Dd = [[0] * W for _ in range(H)]
Dl = [[0] * W for _ in range(H)]

# Dl, Dr を計算する
for i in range(H):
    Dl[i][0] = 0
    for j in range(W - 1):
        if S[i][j] == '.' and S[i][j + 1] == '.':
            Dl[i][j + 1] = Dl[i][j] + 1
    Dr[i][W - 1] = 0
    for j in range(W - 1, 0, -1):
        if S[i][j] == '.' and S[i][j - 1] == '.':
            Dr[i][j - 1] = Dr[i][j] + 1

# Du, Dd を計算する
for j in range(W):
    Du[0][j] = 0
    for i in range(H - 1):
        if S[i][j] == '.' and S[i + 1][j] == '.':
            Du[i + 1][j] = Du[i][j] + 1
    Dd[H - 1][j] = 0
    for i in range(H - 1, 0, -1):
        if S[i][j] == '.' and S[i - 1][j] == '.':
            Dd[i - 1][j] = Dd[i][j] + 1

# 2の累乗を事前計算しておくことで計算量を減らす.
# (これをやらなくても計算量上は間に合うはず(O(NlogN))なのだが, 
# これをやっておかないとTLEとなってしまう)
two = [0] * (K + 1)
two[0] = 1
for k in range(K):
    two[k + 1] = (two[k] * 2) % MOD

cnt = 0
D = [Du, Dr, Dd, Dl]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            k = sum(Dx[i][j] for Dx in D)  # k: マス(i,j)から上下左右方向に連続する空マスの個数
            T = K - 1 - k  # T: マス(i, j)を照らさない照明の置ける空マスの個数
            cnt += two[T]  # ここで pow(2, T, MOD) を使うとTLEとなってしまう.
            cnt %= MOD

ans = two[K] * K - cnt
print(ans % MOD)

F - Random Max

TBA