ABC319をPythonで解いてみたよ。(A～E問題)

AtCoder Beginners Contest 319 (ABC319) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。

A - Legendary Players

問題ページ

考察

気合いでif文(条件分岐)や辞書をつくってもACできますが、時間がかかるしタイプ量が多くてしんどいです。
問題文にある上位10人の情報をコピーします。シングルクォーテーションだとコピペしてもエラーが出てしまいますが、トリプルクォーテーションだと改行コードもそのまま受け取れます。これを利用して辞書をあらかじめつくっておくことでACできます。

コード

top10_str = """tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481"""

top10_dict = dict()
for info in top10_str.split('\n'):
    name, rate_str = info.split(' ')
    top10_dict[name] = rate_str

S = input()

ans = top10_dict[S]
print(ans)

B - Measure

問題ページ

考察

$1$ 以上 $9$ 以下の $N$ の約数のリストをつくります(下のコードの j_lst)。
問題文の「 $i$ が $N/j$ の倍数である」というのは、「 $i$ を $N/j$ で割ったあまりが $0$ になる」というのと同じです。
$i=0,1,2, \cdots ,n$ それぞれについて、j_lst の中で「 $i$ を $N/j$ で割ったあまりが $0$ になる」を満たすような最小の $j$ を求めます。

コード

N = int(input())

j_lst = [j for j in range(1, 10) if N % j == 0]  # Nの約数のリスト
s = ['-'] * (N + 1)
for i in range(N + 1):
    for x in j_lst:
        if i % (N // x) == 0:
            s[i] = str(x)
            break
ans = ''.join(s)
print(ans)

おまけ

コードの3行目について

上のコードの3行目

j_lst = [j for j in range(1, 10) if N % j == 0]  # Nの約数のリスト

これは「リスト内包表記」と呼ばれます。
次のコードとやっていることは同じです。

j_lst = []
for j in range(1, 10):
    if N % j == 0:
        j_lst.append(j)

大したことはしてない割に4行もつかってネストも深くなっているので、リスト内包表記をつかって1行で書くのに慣れてみるのもいいかもしれないです。

C - False Hope

問題ページ

考察 1

高橋くんが見るマスの順番は、全部で $9 \times 8 \times \cdots 2 \times 1 = 362880$ 通りあります。
これなら全パターン試してもよさそうです。順列全探索で解きます。

まず、見ないといけないラインを整理します。
$i$ 行 $j$ 列 ( $0 \leq i,j \leq 2$ ) のマスを、マス $i \times 3 + j$ とします。

0	1	2
3	4	5
6	7	8

縦のラインは全部で $3$ つあります。

• $(0, 3, 6)$
• $(1,4,7)$
• $(2,5,8)$

横のラインも全部で $3$ つあります。

• $(0,1,2)$
• $(3,4,5)$
• $(6,7,8)$

斜めのラインは全部で $2$ つあります。

• $(0,4,8)$
• $(2,4,6)$

この計 $8$ つのタプルをリスト $A$ に入れておきます。

考察 2 (つづき)

順列全探索は、itertools.permutations() をつかうと便利です。

from itertools import permutations

# 0～8の順列を全部列挙する
for perm in permutations(range(9)):
    print(perm)

$perm[i]$ : マス $i$ を何番目に見たか

ということにします。
処理がごちゃごちゃになるのを防ぐために、まずは「見る順番は $perm$ で分かってて、見るラインが $tpl$ のとき、高橋くんががっかりしてしまうならFalseを返し、がっかりしないならTrueを返す」という関数 is_ok_tuple(tpl,perm)をつくります。
これは、 そのラインの中で最初に見た数と2番目に見た数が同じときにFalseを返して、それ以外はすべてTrueを返せばいいです(詳細は下のコードを見てください)。

この関数をつかえば、「見る順番が $perm$ のとき、リスト $A$ の中にあるライン全部について高橋くんががっかりしないかどうか」は、for文をつかえば判定できます。
これを見る順番 $362880$ 通りそれぞれで行い、高橋くんががっかりしなかった回数を求めます。

問題文で聞かれていたのはパターン数ではなくて確率だったので、全パターンの数 $362880$ で割るのを忘れないようにしましょう。

コード

import math
from itertools import permutations

c = [list(map(int, input().split())) for _ in range(3)]

A = [(0, 4, 8), (2, 4, 6)]
for i in range(3):
    tpl = tuple(i * 3 + j for j in range(3))
    A.append(tpl)
for j in range(3):
    tpl = tuple(i * 3 + j for i in range(3))
    A.append(tpl)


def is_ok_tuple(tpl, perm):
    T = []
    for pos in tpl:
        i, j = divmod(pos, 3)
        T.append((perm[pos], c[i][j]))
    T.sort()
    return T[0][1] != T[1][1]


ok_cnt = 0
for perm in permutations(range(9)):
    is_ok = True
    for tpl in A:
        if not is_ok_tuple(tpl, perm):
            is_ok = False
            break
    if is_ok:
        ok_cnt += 1

ans = ok_cnt / math.prod(range(1, 10))
print(ans)

D - Minimum Width

問題ページ

考察

答えを二分探索します。
つまり、「横幅が $x$ のとき、 $M$ 行以内におさまりますか？( $M$ は問題で与えられています)」という問題を考えて、この問題の答えがYesになるような最小の $x$ が答えです。

横幅は $max(L)$ より小さくならないので、最初から二分探索の下限を $max(L)$ にしたり、二分探索に使う関数の中で $max(L)$ 未満の値はすぐにFalseを返すようにしたりすると、バグらせにくいと思います。

コード

N, M = map(int, input().split())
L = list(map(int, input().split()))

max_L = max(L)


def judge(m):
    if max_L > m:
        return False
    now_width = 1 << 63
    cnt = 0
    for l in L:
        if now_width + l + 1 > m:
            cnt += 1
            now_width = l
        else:
            now_width += l + 1
    return cnt <= M


ok = 1 << 63
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if judge(mid):
        ok = mid
    else:
        ng = mid
print(ok)

E - Bus Stops

問題ページ

考察

$1$ ～ $8$ の数の最小公倍数は $840$ です。
これはmath.lcm()をつかうと簡単に求められます。

import math

print(math.lcm(1, 2, 3, 4, 5, 6, 7, 8))  # 840

つまり、$q_i$ ($1 \leq q_i \leq 10^9$) は実は $840$ で割ったあまりだけが重要です。
たとえば、 $q_i=10$ のときの各バス停での待ち時間と、 $q_i=850$ のときの各バス停での待ち時間は全く一緒になります。
$q_i$ がたくさん飛んでくる前に、 $q_i=0,1,2, \cdots ,839$ のときの答えを先に用意しておき、その後に $q_i$ を受け取って答えを出していきます。
たとえば $q_i=1840$ のときは、 $1840=2 \times 840+160$ なので、 $q_i=160$ のときと同じ動き方をします。答えは、 $(q_i=160のときの答え) +(2 \times 840)$ になります。

コード

import math

LCM = math.lcm(1, 2, 3, 4, 5, 6, 7, 8)  # 840


# aの倍数でb以上の数
def f(a, b):
    x = ((b - 1) // a + 1) * a
    return x


N, X, Y = map(int, input().split())
Bus = [list(map(int, input().split())) for _ in range(N - 1)]

ans_lst = [None] * LCM
for t in range(LCM):
    nt = t + X
    for bp, bt in Bus:
        nt = f(bp, nt) + bt
    nt += Y
    ans_lst[t] = nt

Q = int(input())
for _ in range(Q):
    q = int(input())
    p, mod = divmod(q, LCM)
    print(ans_lst[mod] + p * LCM)