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

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

A - New Scheme

問題ページ

考察

$100 \leq S[i] \leq 675$ の判定と $S[i]$ が25の倍数かどうかの判定をまとめて先にしてしまいます。下のコードはandをつかってまとめてるけれど、ややこしかったら、andをつかわずにfor文を2回に分けて書いても大丈夫です。
最後に $S[i] \leq S[i+1]$ が $0 \leq i \leq 7$ で成り立ってるかどうかを判定します。

コード

S = list(map(int, input().split()))

for el in S:
    if not (100 <= el <= 675 and el % 25 == 0):
        print("No")
        exit()

for i in range(7):
    if S[i] > S[i + 1]:
        print("No")
        exit()

print("Yes")

B - Default Price

問題ページ

考察

お皿の色が分かったらすぐに値段が分かるような構造があると、とても楽に解けそうです。
これは、Pythonだと辞書dictで書けます。
具体的には、サンプル1だと、$blue → 1600, red → 2800$になればいいので、

dic = dict()
dic["blue"] = 1600
dic["red"] = 2800

のようにしたいです。下のコードではfor文を用いて1つ1つ辞書にお皿の色と値段を登録しています。
もしこの辞書に登録されていない色のお皿が来たら、値段は $P[0]$ にしてあげればいいです。

コード

N, M = map(int, input().split())
C = list(input().split())
D = list(input().split())
P = list(map(int, input().split()))

dic = dict()
for i in range(M):
    dic[D[i]] = P[i + 1]

ans = 0
for c in C:
    if c in dic:
        ans += dic[c]
    else:
        ans += P[0]
print(ans)

C - Standings

問題ページ

考察

問題文の通りに数値を求めてソートすると、WAになります。
これは小数点以下の誤差が原因で、できれば小数点の出る計算はやめて整数しか出てこない計算に置き換えられるととてもうれしいです。
とても大きい数字を事前にかけておくことで、整数同士の比較に持ち込みます。
下のコードではコイントスの成功率に $10^{20}$ をかけることで無理やり整数同士の比較に持ち込んでいます。

コード

INF = 10 ** 20

N = int(input())
P = []
for i in range(N):
    a, b = map(int, input().split())
    val = INF * a // (a + b)
    P.append((val, -i))
P.sort(reverse=True)
for v, i in P:
    print(-i + 1, end=" ")

D - Snuke Maze

問題ページ

考察

迷路をゴールできるかどうかの問題は、幅優先探索BFSで解けることが多いです。
今回もBFSで解きます。
s→n, n→u, u→k, k→e, e→s の$5$種類のどれかなら先のマスへ進めて、それ以外なら先のマスへは進めない。という条件をつけ加えたBFSを書けばACです。
BFSの中にこの条件を書くとネストが深くなって気持ち的にしんどいので、関数にしてsnuke判定の部分を分けちゃうのがおすすめです(下のコードのis_next関数)。

コード

from collections import deque


def is_next(e1, e2):
    T = "snuke"
    if e1 not in T or e2 not in T:
        return False
    i1 = T.index(e1)
    i2 = T.index(e2)
    if i2 == (i1 + 1) % 5:
        return True
    return False


H, W = map(int, input().split())
S = [input() for _ in range(H)]

que = deque()
que.append((0, 0))
seen = [[False] * W for _ in range(H)]
seen[0][0] = True

while que:
    oi, oj = que.popleft()
    oe = S[oi][oj]
    for ni, nj in [(oi + 1, oj), (oi - 1, oj), (oi, oj + 1), (oi, oj - 1)]:
        if not (0 <= ni < H and 0 <= nj < W):
            continue
        if seen[ni][nj]:
            continue
        ne = S[ni][nj]
        if is_next(oe, ne):
            seen[ni][nj] = True
            que.append((ni, nj))
if seen[-1][-1]:
    print("Yes")
else:
    print("No")

E - MEX

問題ページ

考察

bitDPっぽく解きます。
状態 $bit$ を次のように決めます。

• $(A_i,A_j,A_k)$ に対して、$bit$ の $2^{A_i}$ の桁を $1$ にする。 $A_j,A_k$ でも同じように該当する桁を $1$ にする。

例えば $(A_i,A_j,A_k)=(0,0,1)$ なら $bit=(011)_2=3$ 、 $(A_i,A_j,A_k)=(2,2,2)$ なら $bit=(100)_2=4$ です。
そして、$dp$ を次のように決めます。

• $dp[i][bit]$ : "MEX"の $i$ 文字目まで見て、状態 $bit$ になる選び方の数

左から順番に見ていきます。数列 $A$ での値を $a$ とすると、

• 文字が"M"のとき、 $dp[0][1<<a]$ の値を $1$ だけ増やす。
• 文字が"E"のとき、 $0 \leq bit \leq 7$ それぞれについて、 $dp[1][bit|(1<<a)]$ の値を
  $dp[0][bit]$ だけ増やす。( $a|b$ はor演算です)
• 文字が"X"のとき、 $0 \leq bit \leq 7$ それぞれについて、 $dp[2][bit|(1<<a)]$ の値を
  $dp[1][bit]$ だけ増やす。

と遷移すればいいです。
これで状態が $bit$ になるような $(i,j,k)$ の選び方の数がすべて分かります。
状態 $bit$ のときのmexを計算してあげて(下のコードのmex_bit関数)、それと選び方の数をかけたものの総和が答えになります。

コード

N = int(input())
A = list(map(int, input().split()))
S = input()


def mex_bit(bit):
    if bit & 1 == 0:
        return 0
    if bit & (1 << 1) == 0:
        return 1
    if bit & (1 << 2) == 0:
        return 2
    return 3


dp = [[0] * 8 for _ in range(3)]
for a, s in zip(A, S):
    if s == 'M':
        dp[0][1 << a] += 1
    elif s == 'E':
        for bit in range(8):
            nbit = bit | (1 << a)
            dp[1][nbit] += dp[0][bit]
    elif s == 'X':
        for bit in range(8):
            nbit = bit | (1 << a)
            dp[2][nbit] += dp[1][bit]

ans = 0
for bit in range(8):
    ans += mex_bit(bit) * dp[2][bit]
print(ans)

F - Vouchers

問題ページ

考察

つかえたはずの割引額の大きなクーポンがつかえないのはもったいないので、割引額の大きなクーポンからつかいたいです。
また、クーポンが $L$ 円以上の品物にしかつかえないとき、 $L$ 円以上の中でもなるべく安い品物につかいたいです(まだつかっていないクーポンのために、値段の大きな品物はなるべく残しておきたくなります)。
これをそのまま実装します。

コード

'''
tatyamさん作の、SortedMultisetです。
使わせていただき、ありがとうございます！
https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py

SortedSetの多重集合版。同じ要素を複数入れることができる。
SortedSetから、s.add(x), s.discard(x) が変更され、s.count(x)が追加されている。

・使い方(個人的まとめ)
s=SortedMultiSet()
s.a: SortedMultiSetの中身を返す。
len(s), x in s, x not in s: リストと同じ要領で使える。
s.add(x): xを追加する。sにxが含まれているかどうかは関係ない。
s.discard(x): xを1つだけ削除してTrueを返す。もし存在しないなら、Falseを返す。
s.count(x): sに含まれるxの個数を返す。
s.lt(x): xより小さい最大の要素を返す。もし存在しないなら、Noneを返す。
s.le(x): x　以下の　最大の要素を返す。もし存在しないなら、Noneを返す。
s.gt(x): xより大きい最小の要素を返す。もし存在しないなら、Noneを返す。
s.ge(x): x　以上の　最小の要素を返す。もし存在しないなら、Noneを返す。
s.index(x): xより小さい要素の数を返す。
s.index_right(x): x以下の要素の数を返す。

・使い方URL
https://github.com/tatyam-prime/SortedSet
'''
# (コード省略。上のURLからコピペしてね。)

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

K = []
for l, d in zip(L, D):
    K.append((d, l))
K.sort(reverse=True)

ans = sum(P)
ss = SortedMultiset(P)

for d, l in K:
    el = ss.ge(l)
    if el is not None:
        ss.discard(el)
        ans -= d

print(ans)