【AtCoder】PythonでABC326を解く

はじめに

abc326のA,B,C,E問題をPython3で解きます。

A問題: 2UP3DOWN

atcoder.jp

問題の概要

ビルの階から階へ移動するとき、2階分までの上り、または、3階分までの下りであれば階段を使い、そうでないときはエレベータを使う。階段で移動するか判定せよ。

問題の考察

が範囲内に収まっているかで判定します。

コード

def main():
    x, y = map(int, input().split())
    ans = "Yes" if -3 <= (y - x) <= 2 else "No"
    print(ans)


if __name__ == "__main__":
    main()

B問題: 326-like Numbers

atcoder.jp

問題の概要

3桁の整数について、百の位のかずと十の位の数の積が一の位の数に等しいものを326-like numberと呼ぶ。整数以上の最小の326-like numberを求めよ。

問題の考察

制約を見ると分かるように326-like numberの最大値は919ですので、]の範囲で順に探索します。各位の数を取り出すには整数を文字列に変換すると楽です。

コード

def solve(N):
    for i in range(N, 920):
        a, b, c = map(int, list(str(i)))
        if a * b == c:
            return i

    return -1


def main():
    N = int(input())
    ans = solve(N)
    print(ans)


if __name__ == "__main__":
    main()

C問題: Peak

atcoder.jp

問題の概要

数直線上の座標にプレゼントが置かれている。ある座標を選ぶと半開区間にあるプレゼントを全て獲得できる。適切にを選ぶと最大でいくつのプレゼントを獲得できるか。

問題の考察

配列をソートした上で、を各で全探索しつつ高速に獲得できるプレゼント数をカウントします。二分探索で未満の数と未満の数をそれぞれ求めて差を計算すると、半開区間にあるプレゼント数をでカウントできます。前処理としてのソート、および、全探索と二分探索により、の計算量でプレゼント数の最大値を計算できました。

コード

from bisect import bisect_left


def solve(N, M, A):
    ans = 0
    for a in A:
        x = bisect_left(A, a + M) - bisect_left(A, a)
        ans = max(ans, x)

    return ans


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted(A)
    ans = solve(N, M, A)
    print(ans)


if __name__ == "__main__":
    main()

E問題: Revenge of "The Salary of AtCoder Inc."

atcoder.jp

問題の概要

そのままですので、略します。

問題の考察

をダイスでが出ているときの給料の期待値とします。ダイスでが出ているときにさらに手順を踏むと、次のダイスがからまでのときはそれぞれの確率でが支給され、からまでのときはそれぞれの確率でが支給されます。

上記の式について、の状態からの状態まで計算していけば、のときの給料の期待値が計算できます。なお、高速化のために式の最後の総和では累積和を用います。これによって、計算量で期待値が求まります。なお、答えをで計算する必要があるため、での割り算はの掛け算で実現します。

コード

def solve(N, A, MOD=998244353):
    A = [0] + A
    dp = [0] * (N + 1)
    ep = [0] * (N + 2)
    modinv_N = pow(N, -1, MOD)
    for x in range(N, -1, -1):
        dp[x] = A[x]
        dp[x] += ep[x + 1] * modinv_N % MOD
        dp[x] %= MOD
        ep[x] = dp[x] + ep[x + 1]
        ep[x] %= MOD

    ans = dp[0]

    return ans


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)


if __name__ == "__main__":
    main()