Zenn
🔥

[AtCoder]HHKB プログラミングコンテスト 2020個人的メモ[Python]

2020/10/11に公開
Python
競技プログラミング
AtCoder
tech

HHKB2020

所感

ABC3完，1032パフォ
思ったよりもパフォーマンスが出たので良かった

A - Keyboard

文字列を大文字に変換する方法を覚えてなかったのでググった

提出コード
#!/usr/bin/env python3
def main():
    S = input()
    T = input()
    print(T if S == "N" else T.upper())


if __name__ == '__main__':
    main()

B - Futon

二重のfor文で全探索
各点から，現在点と右のマスは共に布団を置けるマスか？，現在点と下のマスは共に布団を置けるか？をチェック
リストのインデックスエラーに注意

提出コード
#!/usr/bin/env python3
def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    ans = 0
    for i in range(H):
        for j in range(W):
            if i + 1 < H and S[i][j] == S[i + 1][j] == ".":
                ans += 1
            if j + 1 < W and S[i][j] == S[i][j + 1] == ".":
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

C - Neq Min

i回目の出力をxとした時，それ以降の出力がx以下になることは無い
何故なら，それ以前のpによって，x未満の数字は出禁になっているから
よって，以下のようなコードを組めばおｋ
計算量はO(N)

提出コード
#!/usr/bin/env python3
def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    num_max = 10 ** 5 * 2 + 1

    lst = [True] * num_max
    ans = 0
    for p in P:
        lst[p] = False
        while lst[ans] is False:
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

D - Squares

サンプルすらacしなかった
いろいろ考えたが，残り30分ぐらいからほぼ思考停止状態でもったいなかった
制約とか入力方法とかで，何か工夫して1クエリの計算量はO(1)になるんだろうなと考えてはいた

ほとんど公式解説と同じだが，一応説明
赤い正方形，青い正方形の全ての場合の数はそれぞれ以下の様になる

red_{all} = (N - A + 1)^2\\ blue_{all} = (N - B + 1)^2

ここから，赤と青が重複して配置される場合の数duplicateを引けばおｋ
duplicateは

(赤のx座標の範囲と青のx座標の範囲が重なる場合)\\ (赤のy座標の範囲と青のy座標の範囲が重なる場合)

の両方が同時に成り立っている場合の数
つまり，両者を掛け算すれば求まる
とはいえ，対称性により両者の場合の数は等しいから，

\begin{aligned} duplicate &= (どっちかの場合の数)^2\\ &=(dup2)^2 \end{aligned}

となる
dup2は長さA,Bの区間をNの区間に詰めた時の場合の数と言い換えられる
ということで，nodupをA,Bの区間が重ならない場合の数とすると，

dup2 = (N - A + 1)(N - B + 1) - nodup

nodupを考える
とりあえず，A,Bを区別しないとする
□を空白として，□...□赤□...□青□...□のように空白の中に長さA，Bの赤，青を挿入すると考える
すると，赤と青を区別しないと

_{N-A-B+2}C_2

通りの組み合わせがあると分かる
実際は赤と青は区別して考えるので

nodup=2(_{N-A-B+2}C_2)

となる
よって，

\begin{aligned} ans &= red_{all}blue_{all}-duplicate\\ &= red_{all}blue_{all}-{dup2}^2\\ &=red_{all}blue_{all}-{((N - A + 1)(N - B + 1) - nodup)}^2\\ &=red_{all}blue_{all}-{((N - A + 1)(N - B + 1) - 2_{N-A-B+2}C_2)}^2\\ &=(N - A + 1)^2(N - B + 1)^2-{((N - A + 1)(N - B + 1) - 2_{N-A-B+2}C_2)}^2 \end{aligned}

となる

提出コード
#!/usr/bin/env python3
def solve(N, A, B):
    MOD = 10 ** 9 + 7
    if A + B > N:
        return 0
    ab = (N - A + 1) * (N - B + 1)
    comb = (N - A - B + 2) * (N - A - B + 1)
    return (pow(ab, 2, MOD) - pow(ab - comb, 2, MOD)) % MOD


def main():
    from sys import stdin

    input = stdin.readline

    T = int(input())
    for _ in range(T):
        N, A, B = map(int, input().split())
        print(solve(N, A, B))


if __name__ == '__main__':
    main()

E - Lamps

散らかっているマスを壁，散らかっていないマスを道とする
ある1つの道のマス(i, j)に注目し，2^K通り全ての照明の置き方をした時，(i, j)が何回照らされたかをN_{(i, j)}とする
全ての道マスにおいてN_{(i, j)}を数えて，それらを合計すれば答えansが求まる

ans = \sum N_{(i, j)}

よって，N_{(i, j)}を数える方法が分かればおｋ
で，N_{(i, j)}を直接数えるのは大変なので，N_{(i, j)}の補集合を用いて以下の様に数える

\begin{aligned} N_{(i, j)}&=(全ての場合の数)-((i, j)が照らされない場合の数)\\ &=2^K - 2^{M}\\ \end{aligned}

で，Mも補集合を用いて以下の様に数える

\begin{aligned} M &= (全ての道マスの数) - ((i, j)を照らせる道マスの数)\\ &= K - cnt[i][j]\\ \end{aligned}

というわけでcntを求めればいいと分かった
で，cnt[i][j]はマス(i, j)から上下左右に壁マスに当たるまで道マスが何連続しているかを数えれば良い
しかし，各マスから4方向に連続する道マスを数えると計算量が最大でO((HW)^2)となる
なので，下図の様に各マスごとではなく，各行ごとに連続するマスを数えていくことにする
列はリストを転置することで行と同じように数えた
ただし，この方法だと各マス自身を重複して数えてしまうので，列を数える際には-1した
こうすると，計算量はO(HW)となり，十分間に合う

cntfigure

最後の2のべき乗の計算は事前計算せずに，forループの中で計算させるとTLEしたので注意

リストを回転するところがかなり時間かかっている
実際，2回転させたらTLEした
参考にさせてもらった提出 #17307568では回転させておらず実行時間が400ms
僕のは1191ms

提出コード
#!/usr/bin/env python3
def input_num_of_continuous(head, end, now_h, cnt, is_not_first):
    """
    壁にぶつかるまでに通ったマスに対して，連続していたマスの数を加算
    自分のマスを重複して数えない様に初回以外は1引く
    """
    res = 1 if is_not_first else 0
    for k in range(head, end):
        cnt[now_h][k] += end - head - res
    return cnt


def solve(H, W, S):
    MOD = 10 ** 9 + 7
    cnt = [[0] * W for _ in range(H)]
    for n in range(2):
        if n:
            # 各マスを数えた結果cnt，与えられたSを転置
            cnt = [list(x) for x in zip(*cnt)]
            S = [list(x) for x in zip(*S)]
            H, W = W, H
        for i in range(H):
            head = 0
            for j in range(W):
                if S[i][j] == "#":
                    # head == jだと#が連続しているのでheadを動かすだけ
                    if head != j:
                        cnt = input_num_of_continuous(head, j, i, cnt, n)
                    head = j + 1
            # 端に達した時の連続数で通った道に加算
            cnt = input_num_of_continuous(head, W, i, cnt, n)

    # LUT
    pow2 = [1] * (H * W + 1)
    for i in range(H * W):
        pow2[i + 1] = pow2[i] * 2 % MOD

    K = sum([row.count(".") for row in S])

    ans = 0
    for row in cnt:
        for n in row:
            ans += pow2[K] - pow2[K - n]
            ans %= MOD
    return ans % MOD


def main():
    import sys

    input = sys.stdin.readline

    H, W = map(int, input().split())
    S = [input().rstrip() for _ in range(H)]

    print(solve(H, W, S))


main()

参考資料

Discussion