📝

AtCoder Beginner Contest 280 レポート

2022/12/06に公開約4,400字

摘要

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

ABC280

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

https://atcoder.jp/users/ryuichiueda/history/share/abc280

A - Pawn on a Grid

A - 問題

HW列のマス目について,#の個数を求めよ.

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()

https://atcoder.jp/contests/abc280/submissions/36947665

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()

https://atcoder.jp/contests/abc280/submissions/36951435

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()

https://atcoder.jp/contests/abc280/submissions/36955390

D - Factorial and Multiple

D - 問題

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

D - 解法

N!を素数pで割り切れる回数cntは,Npで割り続けた商の和として求められる.[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()

https://atcoder.jp/contests/abc280/submissions/37000297

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()

https://atcoder.jp/contests/abc280/submissions/36976680

感想

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

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

脚注
  1. ルジャンドルの定理 ↩︎

Discussion

ログインするとコメントできます