【AtCoder】PythonでABC321を解く

はじめに

ABC321のA,B,C,D問題をPython3で解きます。

A問題: 321-like Checker

atcoder.jp

問題の概要

正整数の桁が上から順に狭義単調減少になっているとき、その正整数を321-like Numberと呼ぶ。与えられた正整数が321-like Numberかを判定せよ。

問題の考察

itertoolsのpairwiseを使うことで隣り合う2つの要素を取り出せるため、これを使って単調減少しているかを判定します。

コード

from itertools import pairwise


def solve(N):
    return all(s1 > s2 for s1, s2 in pairwise(N))


def main():
    N = input()
    ans = "Yes" if solve(N) else "No"
    print(ans)


if __name__ == "__main__":
    main()

B問題: Cutoff

atcoder.jp

問題の概要

ラウンドからなる試験の最終結果は、最高スコアのラウンドと最低スコアのラウンドを除いたラウンド分のスコアの合計となる。ラウンドまでが終了して各ラウンドのスコアがであるとき、最終結果を以上にするために最終ラウンドで取るべきスコアの最小値を求めよ。

問題の考察

最終ラウンドのスコアを]の範囲で全探索します。

コード

def solve(N, X, A):
    ans = float("inf")
    for a in range(101):
        A.append(a)
        total = sum(A) - min(A) - max(A)
        if total >= X:
            ans = min(ans, a)
        A.pop()

    if ans == float("inf"):
        ans = -1

    return ans


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


if __name__ == "__main__":
    main()

C問題: 321-like Searcher

atcoder.jp

問題の概要

番目に小さい321-like Numberを求めよ。

問題の考察

最も大きい321-like Numberは9876543210であること、および、321-like Numberである条件が厳しいことから、321-like Numberを満たす正整数の数は少なそうなため、全てを列挙しても大丈夫そうです。dequeを321-like Numberである1から9で初期化し、①dequeの先頭から正整数を取り出す、②その正整数から作れる321-like Numberをdequeの末尾に入れる、という①②をdequeが空になるまで繰り返します。

コード

from collections import deque


def solve(K):
    fifo = deque(range(1, 10))

    A = []
    while fifo:
        x = fifo.popleft()
        A.append(x)
        for d in range(x % 10):
            xx = 10 * x + d
            fifo.append(xx)

    return A[K]


def main():
    K = int(input())
    ans = solve(K - 1)
    print(ans)


if __name__ == "__main__":
    main()

D問題: Set Menu

atcoder.jp

問題の概要

価格な種類の主菜と価格な種類の副菜がある。主菜と副菜からなる定食を提供するとき、その価格はとなる。通りある定食についての価格の総和を求めよ。

問題の考察

主菜を全探索するとき、となる副菜ととなる副菜の個数が高速に分かればよさそうです。事前に副菜を価格でソートしておき、副菜の価格の累積和を取っておきます。ある主菜について二分探索でとなる副菜の数を計算すれば、ある主菜と全副菜との価格の和は累積和を使ってで計算できます。副菜のソートに、各主菜での副菜の数の計算にだけ掛かるため、全体としての計算量で価格の総和を求められました。

コード

from bisect import bisect_left
from itertools import accumulate


def solve(N, M, P, A, B):
    B = sorted(B)
    accB = list(accumulate(B, initial=0))

    ans = 0
    for a in A:
        j = bisect_left(B, P - a)
        ans += (j * a + accB[j]) + (M - j) * P

    return ans


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


if __name__ == "__main__":
    main()