【Atcoder解法検討】ABC128 A~D Python

A - Apple Pie

問題ページ : A - Apple Pie

考察

標準入力と整数の四則演算、標準出力を利用すれば簡単に実装できます。

コード

A, P = map(int, input().split())
print((A * 3 + P) // 2)

B- Guidebook

問題ページ : B - Guidebook

考察

$(市名, 得点, 店番号)$をデータ単位としてリストを作成してソートすることでまず市名順、同じ市名なら得点順に並べることができます。ただし、このままソートすると得点は小さい順にソートされてしまいますので、$(市名, 得点 \times (-1), 店番号)$をデータ単位とすることで得点も高い順に並べることができます。

コード

N = int(input())

# (市名, 得点 x (-1), 番号)のリストを作成
G = []                              
for i in range(N):
    city, score = input().split()
    G.append((city, -int(score), i + 1))

# 市名,　得点 x (-1)でソートして順に番号を出力
G.sort()
for c, p, num in G:
    print(num)

C - Switches

問題ページ : C - Switches

考察

　スイッチの個数が高々10個なので、全てのスイッチのON/OFFの組み合わも高々$2^{10} \sim 10^3$となり全探索が可能となります。
　またスイッチのON/OFFのようなN個の二者択一の組み合わせの全探索にはbit全探索が適しており、本問題にも適用します。

コード

N, M = map(int, input().split())
KS = [map(int, input().split()) for _ in range(M)]
P = list(map(int, input().split()))

k = [0]* M
switch = [[] for _ in range(M)]
for i in range(M):
    k[i],*switch[i] = KS[i]

ans = 0
for i in range(1<<N):            # N個のスイッチのON,OFの全組合せ（2^N)
    flag = True                  # 上記各組合せで電球が全て点灯してればTrue、そうれでなければFalse
    for bulb in range(M):        # bulb(=0~M)番目の電球にたいして
        tmp = 0                  # つながっていてONになっているswitchの数
        for s in switch[bulb]:
            if (i >> (s-1)) & 1 == 1:
                tmp += 1
        if tmp % 2 != P[bulb]:
            flag = False
    if flag:
        ans += 1

print(ans)

D - equeue

問題ページ : D - equeue

考察

　一見複雑ですが適切に整理すると全探索が可能となります。まず操作A~Dを任意の順番でK回実施することができるのですが、操作内容をよく見ると、実は左側から任意の回数（変数名$left$と設定）取り出し、次に右側から任意の回数（変数名$right$と設定）取り出し、最後に任意の回数（変数名$back$と設定）価値の小さいものからDに戻す（右側・左側どちらでも良い）、というパターンだけ計算すれば良いことがわかります。
　ここで文中にて設定した各変数の取れる範囲を適切に設定し全探索することで解が得られます。各変数の取れる範囲は以下のようになります。

\begin{array}{l}
0 \leq \text{left} \leq \min(N,K) \\
0 \leq \text{right} \leq \min(N-L, K-L) \\
0 \leq \text{back} \leq \min(K-(L+R), L+R) \\
\end{array}

コード

N, K = map(int, input().split())
D = list(map(int,input().split()))

ans = 0
for left in range(min(N,K)+1):                  # left   : Dの左から何個とるか
    for right in range(min(N-left,K-left)+1):   # righth : Dの右から何個とるか
        g = [D[i] for i in range(left)]         # g      : 手元に持っているもののリスト
        for i in range(right):
            g.append(D[-(i+1)])
        g.sort()

        for back in range(min(K-(left + right),left + right) + 1):  # back : 手元からDに返す個数
            ans = max(ans,sum(g[back:]))

print(ans)

E - Roadwork

問題ページ : E - Roadwork

F - Frog Jump

問題ページ : F - Frog Jump

　　
青diff以上の問題は後日トライ