mean_abs_error’s blog

ソフトウェアとシステムの狭間

【AtCoder】PythonでABC319を解く

はじめに

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

A問題: Legendary Players

atcoder.jp

問題の概要

プレイヤー名とレーティングが事前に表として定義されている。あるプレイヤー名が与えられたとき、その人のレーティングを答えよ。

問題の考察

splitlinesを使うことでstr型の表の各行を読み込み、プレイヤー名をレーティングに変換するルックアップテーブル(LUT)を作っておきます。あとは入力されたプレイヤー名をLUTで変換すればよいです。

コード

def solve(S):
    text = """tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481
"""
    name2rate = {}
    for line in text.splitlines():
        name, rate = line.strip().split()
        name2rate[name] = rate

    return name2rate[S]


def main():
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

B問題: Measure

atcoder.jp

問題の概要

何をやりたいのかよくわからなかった問題なため要約が難しく、要約をサボります。

問題の考察

① Nの約数 jである、② iが N / jの倍数である、という条件2つを満たす jの集合を1～9の範囲で求めます。集合が空ならハイフンを、そうでないなら集合の最小値を結合します。

コード

def solve(N):
    ans = []
    for i in range(N + 1):
        js = [j for j in range(1, 10) if N % j == 0 and i % (N // j) == 0]
        if js:
            ans.append(str(min(js)))
        else:
            ans.append("-")

    return "".join(ans)


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


if __name__ == "__main__":
    main()

C問題: False Hope

atcoder.jp

問題の概要

B問題と違ってやりたいことは分かるのですが、そのまんますぎて省略しにくいため、要約をサボります。

問題の考察

マスを見ていく順番を全探索し、各探索毎にがっかりの有無を判定します。全探索には \mathcal{O}(9!)、がっかり判定に \mathcal{O}(9)だけ掛かり、全体としては \mathcal{O}(9 * 9!)だけ掛かります。

がっかり判定をうまく実装できればいいのですが、良い実装が思いつかなかったため愚直にマス毎のがっかり判定文を書き下しました。実装中は泣きそうになりました。

コード

from itertools import permutations
from math import factorial


def solve(C):
    def is_valid(order):
        knowns = set()
        for k in order:
            if k == 0:
                if 1 in knowns and 2 in knowns and C[1] == C[2]:
                    return False
                if 3 in knowns and 6 in knowns and C[3] == C[6]:
                    return False
                if 4 in knowns and 8 in knowns and C[4] == C[8]:
                    return False
            elif k == 1:
                if 0 in knowns and 2 in knowns and C[0] == C[2]:
                    return False
                if 4 in knowns and 7 in knowns and C[4] == C[7]:
                    return False
            elif k == 2:
                if 0 in knowns and 1 in knowns and C[0] == C[1]:
                    return False
                if 5 in knowns and 8 in knowns and C[5] == C[8]:
                    return False
                if 4 in knowns and 6 in knowns and C[4] == C[6]:
                    return False
            elif k == 3:
                if 4 in knowns and 5 in knowns and C[4] == C[5]:
                    return False
                if 0 in knowns and 6 in knowns and C[0] == C[6]:
                    return False
            elif k == 4:
                if 3 in knowns and 5 in knowns and C[3] == C[5]:
                    return False
                if 1 in knowns and 7 in knowns and C[1] == C[7]:
                    return False
                if 0 in knowns and 8 in knowns and C[0] == C[8]:
                    return False
                if 2 in knowns and 6 in knowns and C[2] == C[6]:
                    return False
            elif k == 5:
                if 3 in knowns and 4 in knowns and C[3] == C[4]:
                    return False
                if 2 in knowns and 8 in knowns and C[2] == C[8]:
                    return False
            elif k == 6:
                if 7 in knowns and 8 in knowns and C[7] == C[8]:
                    return False
                if 0 in knowns and 3 in knowns and C[0] == C[3]:
                    return False
                if 2 in knowns and 4 in knowns and C[2] == C[4]:
                    return False
            elif k == 7:
                if 6 in knowns and 8 in knowns and C[6] == C[8]:
                    return False
                if 1 in knowns and 4 in knowns and C[1] == C[4]:
                    return False
            else:
                if 6 in knowns and 7 in knowns and C[6] == C[7]:
                    return False
                if 2 in knowns and 5 in knowns and C[2] == C[5]:
                    return False
                if 0 in knowns and 4 in knowns and C[0] == C[4]:
                    return False
            knowns.add(k)

        return True

    ok = 0
    for order in permutations(range(9), 9):
        if is_valid(order):
            ok += 1

    ans = ok / factorial(9)

    return ans


def main():
    C = []
    for _ in range(3):
        line = list(map(int, input().split()))
        for c in line:
            C.append(c)
    ans = solve(C)
    print(ans)


if __name__ == "__main__":
    main()

D問題: Minimum Width

atcoder.jp

問題の概要

横幅が L_iの N個の単語について、改行または横幅1のスペースで順に繋げて M行以内のウィンドウに納めたい。ウィンドウの横幅としてありえる最小値を求めよ。

問題の考察

最大値の最小化に関する問題なため、二分探索で解けそうと分かります。

ウィンドウの横幅 Wを二分探索し、ある横幅のときに M行以内で収まるかを判定すればよいです。 Wについて、最大値としてあり得るのは N - 1 + \sum_{i=1}^N L_iで、どんなに小さくできても0以下になることはないため、 0 \lt W \le N - 1 + \sum_{i=1}^N L_iでの二分探索により、計算量は \mathcal{O} (\log (N + \sum_{i=1}^N L_i) )となります。ある横幅のときにM行以内で収まるかの判定は、先頭の単語だとスペースは不要でそれ以外だとスペースが必要なことに注意しながら愚直に実装すれば、 \mathcal{O} (N)となります。結果として、 \mathcal{O} (N \log (N + \sum_{i=1}^N L_i) )で解けました。

コード

def solve(N, M, L):
    def is_valid(W):
        m = 0
        i = 0
        w = 0
        while i < N:
            if m >= M:
                return False
            if w <= 0:
                w += L[i]
            else:
                w += L[i] + 1
            if w > W:
                w = 0
                m += 1
            else:
                i += 1

        return True

    ok = sum(L) + N - 1
    ng = 0
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if is_valid(mid):
            ok = mid
        else:
            ng = mid

    return ok


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


if __name__ == "__main__":
    main()