📝

AtCoder Beginner Contest 280 レポート

2022/12/06に公開

AtCoder

Python 3

tech

摘要

ABCDEの5完でした．なかなかハイペースで解くことができたこと，F問題で差がつかなかったことから初めて青パフォーマンスを出すことができました．

ABC280

コンテスト名: デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)
順位: 709th / 8672
パフォーマンス: 1647
レーティング: 1216 → 1267 (+51) Highest更新！
段級位: 4 級
コンテスト参加回数: 65

A - Pawn on a Grid

A - 問題

$H$ 行 $W$ 列のマス目について，#の個数を求めよ．

A - 解法

特筆事項なし．

A - ACコード

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

    ans = 0
    for si in S: ans += si.count('#')

    print(ans)


if __name__ == '__main__': main()

B - Inverse Prefix Sum

B - 問題

長さ $N$ の数列 $S$ に対して， $(\sum_{i=1}^k A_i) = S_i$ となるような数列 $A$ を求めよ．

B - 解法

$A_1 = S_1$ として， $A_i = S_i - S_{i-1}$ と計算していけばよい．

B - ACコード

def main():
    N = int(input())
    S = list(map(int, input().split()))

    ans = [0]*N
    ans[0], sm = S[0], S[0]
    for i in range(1, N):  # ans[i] = S[i] - S[i-1]でよかった
        ans[i] = S[i] - sm
        sm += ans[i]

    print(*ans)


if __name__ == '__main__': main()

C - Extra Character

C - 問題

文字列 $S$ と，それに英小文字を1つ挿入した文字列 $T$ が与えられる．挿入された文字の位置を求めよ．

C - 解法

前から調べただけ．末尾に追加するケースを考慮せず1WA．

C - ACコード

def main():
    S, T = input(), input()

    for i, si in enumerate(S):
        if si != T[i]:
            ans = i+1
            break
    else: ans = len(S)+1  # 末尾に追加するケース

    print(ans)


if __name__ == '__main__': main()

D - Factorial and Multiple

D - 問題

$2$ 以上の整数 $K$ に対して， $N!$ が $K$ の倍数になるような最小の自然数 $N$ を求めよ．

D - 解法

$N!$ を素数 $p$ で割り切れる回数 $cnt$ は， $N$ を $p$ で割り続けた商の和として求められる．^[1]
よって，予め $K$ の素因数を求め，各素数の素因数の個数を満たすことができるような最小の自然数 $N$ を答え決め打ち二分探索で求める．

中受算数で散々扱ってきた問題に近いこともあり，5分で解いて最大瞬間風速黄パフォを観測できた．

D - ACコード

def main():
    K = int(input())

    facts = factorization(K)

    ans = binary_search(facts)  # max(binary_search(p, c) for p, c in facts)がbetter
    print(ans)


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def binary_search(K):
    ok, ng = 10**12, 1

    def is_ok(x, p, c):
        cnt = 0
        while x:
            x //= p
            cnt += x

        return cnt >= c

    while abs(ok-ng) > 1:
        md = (ok+ng)//2

        for p, c in K:
            if not is_ok(md, p, c):
                ng = md
                break
        else: ok = md

    return ok


if __name__ == '__main__': main()

E - Critical Hit

E - 問題

整数 $N$ に対して， $N$ を確率 $P\%$ で $2$ ， $(100-P)\%$ で $1$ 減らす操作を繰り返す． $N \leq 0$ になるまでの操作回数の期待値 $ev\mod 998244353$ を求めよ．

E - 解法

DPの利用を方針立てた．
dp = [0]*(N+2)で初期化し，次のような配る遷移を行う．

dp[i+1] += (dp[i]+1)*(100-P)/100
dp[i+2] += (dp[i]+1)*P/100

dp[N]が答えになると思ったが，うまくいかず．
dpの中身を確認した結果，dp[N-1]+1が答えになることを見つけた．
これはdp[N-1]の状態から操作を1回行うと必ず $N \leq 0$ になるためである．

解説を見ると，反復試行の確率を求めたり（これは最初に方針を立てる際に候補として考えていた）行列累乗を用いたりといろいろな方法があった．

E - ACコード

MOD = 998244353
H_inv = pow(100, MOD-2, MOD)


def main():
    N, P = map(int, input().split())

    ans = calc_ev(N, P)
    print(ans)


def calc_ev(N, P):
    ''' 要らなかった
    if P == 0: return N
    if P == 100: return -(-N//2)
    '''

    dp = [0]*(N+2)

    for i in range(N):
        dp[i+1] += (dp[i]+1)*(100-P)*H_inv
        dp[i+1] %= MOD

        dp[i+2] += (dp[i]+1)*P*H_inv
        dp[i+2] %= MOD

    return (dp[N-1]+1)%MOD


if __name__ == '__main__': main()

感想

F問題はDSUを使って連結成分を出しつつ閉路を調べるところまで大体できたのですが，
「コスト非0の閉路が存在すればinf」という条件に気づけませんでした．

とにかく，初めての青パフォは収穫でした．ここから少しずつ青パフォの感覚を掴んでいき，青色コーダーを目指していきたいと思います．

脚注

ルジャンドルの定理 ↩︎