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

A - Ferris Wheel

問題ページ : A - Ferris Wheel

考察

標準入出力とIF分による条件分岐ができればOK。

コード

A, B = map(int, input().split())

if A <= 5:
    print(0)
elif 6 <= A <= 12:
    print(B // 2)
elif A >= 13:
    print(B)

B- Algae

問題ページ : B - Algae

考察

漸化式 $x_{i+1} = rx_i - D$ 及び $x_{2000}$ が与えられているので、

\begin{align*}
x_{2001} &= rx_{2000} - D \\
x_{2002} &= rx_{2001} - D \\
&\vdots \\
\end{align*}

と順次for文でループを回せば良い。

コード

r, D, x = map(int, input().split())

for i in range(10):
    x = r * x - D
    print(x)

C - Prison

問題ページ : C - Prison

考察

　各IDカードが各ゲートを通過できるか全探索していくことで解にたどり着けるはずですが、計算量が$O(NM) \sim 10^{10}$となりTLEとなってしまいます。C問題では全探索で解けるがTLEとなってしまい、ACするにはデータ構造等に工夫を要する問題が多いです。
　この問題について入力例2で具体的にみてみましょう。この入力例を図示したものが下図になります。

　この図ではIDカード番号を数直線上の数値として扱い、各ゲートを通過することができるカード番号$L_i, L_i+1,\cdots, R_i$を閉区間$[L_i,R_i]$としてあらわしたものです。
　このとき、全てのゲートを通過できるIDカードは各閉区間$[L_i,R_i](i=1,2,\cdots ,M)$の共通区間です。共通区間を求めるには$L_i$の最大値$max(L_i)$と$R_i$の最小値$min(R_i)$を求め、$max(L_i) \leq min(R_i)$であれば共通区間は$[max(L_i),min(R_i)]$となります。
　なお下図のように$max(L_i) > min(R_i)$となる場合は共通区間はなく、全てのゲートを通過できるIDカードもありません（0枚です）。

コード

N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

max_L = -1
min_R = N+1
# Lの最大値、Rの最小値を求める
for L,R in LR:
    max_L = max(max_L, L)
    min_R = min(min_R, R)

ans = min_R - max_L + 1
# 全通過IDカードが一枚もない場合はansはマイナスとなるが0と回答する
if ans > 0:
    print(ans)
else:
    print(0)

D - Integer Cards

問題ページ : D - Integer Cards

考察

　この問題も、各操作毎にN枚のカードを書かれた整数順にソートし、$C_i$より小さいカードを最大{B_i}まで交換する、と愚直に実行すれば解けるはずですが処理時間が$O(MN)$となりTLEになりそうです。
　この問題を高速かつシンプルに扱うには二つの工夫が必要です。一つは$（カードに書かれた整数、そのカードの枚数）$というデータ構造をもつことです。これは各操作で整数 $C_i$ が書かれたカードを最大$B_i$枚まで交換できることから、各整数の書かれたカードが複数枚存在することになり、一枚一枚交換する処理よりも、複数枚まとめて交換する処理の方が高速になるので有効でしょう。
二つ目の工夫は、各操作毎に交換処理をせず、最初のN枚のカードに操作で使用できるカードも全て加えそこから大きい方からN枚選択すれば良い、ということです。このことは具体例をみながら考えれば理解できると思います。
この二つの工夫を導入すればコードも比較的シンプルに書けます。　

コード

from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for _ in range(M)]

# 各整数が書かれたカードの枚数
count = defaultdict(int)

# 最初のN枚の各整数がかかれたカードの枚数
for a in A:
    count[a] += 1
# 各操作で使えるカードについても足し合わせる。
for B, C in BC:
    count[C] += B

# (カードに書かれた整数、その枚数)を書かれた整数が大きい順に並べたリスト
H = [(e,count[e]) for e in count]
H.sort(reverse= True)

# カードに書かれた整数を大きい順にN毎まで足し合わせる
cnt = 0
ans = 0
for num, c in H:
    c = min(c, N - cnt)
    cnt += c
    ans += num * c
    if cnt == N:break

print(ans)

E - Cell Distance

問題ページ : E - Cell Distance

F - Absolut Minima

問題ページ : F - Absolute Minima

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