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

A - Airplane

問題ページ : A - Airplane

考察

A問題は標準入出力と簡単な変数の処理ができれば十分なのですが、処理の部分が少しだけ考えさせられますね。
題意からはP,Q,Rのうち小さいほうから二つの数値の和が求められますが、これを$（P,Q,Rの合計値）-（P,Q,Rの最大値）$として処理しました。

コード

PQR = list(map(int, input().split()))
print(sum(PQR) - max(PQR))

B - Balance

問題ページ : B - Balance

考察

　この問題は累積和を使用して効率的に解く方法もありますが、B問題ということもあり題意どおりの愚直な全探索でも十分解くことができます。
愚直な全探索で解けるなら、その方がミスを減らしやすいので好みです。

コード

N = int(input())
W = list(map(int,input().split()))

ans = float("inf")
for T in range(N-1):
    S1 = 0
    S2 = 0
    for i in range(N):
        if i <= T:
            S1 += W[i]
        else:
            S2 += W[i]

    ans = min(ans,abs(S1-S2))

print(ans)

C - Typical Stairs

問題ページ : C - Typical Stairs

考察

DPの比較的簡単な典型。
DPテーブル（状態）は
$$dp[i] = i段目への移動方法数$$
遷移は
$$dp[i] = dp[i-1] + dp[i-2]$$
という貰う形式の方がイメージしやすいですが、コード中はいわゆる配る形式で記述しました。

\begin{array}{l}
dp[i+1] = dp[i+1] + dp[i] \\
dp[i+2] = dp[i+2] + dp[i] \\
\end{array}

床が壊れている段の扱いは、床の壊れている段からは進まないという風に読み替えて処理しています。
ある段が壊れている段に含まれるか否かの探索は壊れている段をset()に登録しておいた方が高速に処理できます。

コード

mod = 10 ** 9 + 7

N, M = map(int, input().split())
A = set()                           # 含まれているかの探索高速化のためsetで受ける
for _ in range(M):
    A.add(int(input()))

# dp[i] : i段目への移動方法
dp = [0] * (N + 2)
dp[0] = 1

# 遷移
for i in range(N):
    if i in A:continue     #　床が壊れている段からは移動しない
    dp[i + 1] = (dp[i + 1] + dp[i]) % mod
    dp[i + 2] = (dp[i + 2] + dp[i]) % mod

print(dp[N])

D - Lamp

問題ページ : D - Lamp

考察

二分法典型。
各行、各列毎に障害物の位置を列記したリストを作成。この時マップ外枠も障害物として位置-1,H or Wとしてリストに記載しておくと処理が楽になります。
あとは全マス探索で障害物でないマスなら、行内、列内で双方向にもっとも近い障害物位置を2分法で検出し照らされるマスの数を計算します。
計算量$O(HW\dot \log(max(H,W))$で処理できます。
二分法はbisectをインポートすれば簡単に使用できます。

コード

from bisect import bisect_left

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

gyo = [[-1,W] for _ in range(H)]        # i行目にある障害物の位置   
retsu =[ [-1,H] for _ in range(W)]      # i列目にある障害物の位置

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            gyo[i].append(j)
            retsu[j].append(i)

# 二分法にかけるためソート
for i in range(H):
    gyo[i].sort()
for i in range(W):
    retsu[i].sort()

# 全マスク探索
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            pos1 = bisect_left(gyo[i],j)
            pos2 = bisect_left(retsu[j],i)

            len1 = gyo[i][pos1] - gyo[i][pos1 - 1] -1 
            len2 = retsu[j][pos2] - retsu[j][pos2-1] -1

            ans = max(ans, len1 + len2 -1)

print(ans)

E - Sum Equals Xor

問題ページ : E - Sum Equals Xor

考察

　この問題を見たときにまずDPにて解くことが思いつきました。下位から$k \ bit$までの組数を求めることができれば、下位から$k+1 \ bit$までの組数を求めることができる、という点からでしょうか。
　DPで解くとしたとき、DPテーブル（状態）の明確化と状態遷移の数式化が必要になります。まずDPテーブルは求めたい解でもありますので以下のように設定します。
$$dpL[i] : 下位からi\ bit$目まででa+b=a\ XOR\ b かつ a+b \leq Lを満たす(a,b)の組数$$
次に遷移を考慮すると
$$dpU[i] : 下位からi\ bit目まででa+b=a\ XOR\ b かつ a+b > Lを満たす(a,b)の組数$$
も必要になります。$a$の$i+1 \ bit$目と$b$の$i+1 \ bit$目との和が$L$の$i+1 \ bit$目より大きい場合には、$dpU[i]$からの遷移も必要となるからです。
　次に$a + b = a \ XOR \ b$との条件から、$a,b$の各$i \ bit$目は$(a[i],b[i]) = (0,0),(0,1),(1,0)$のいずれかの組み合わせになります。
　これらを元に$dpL[i],dpU[i]$から$dpL[i+1],dpU[i+1]$への遷移を考えます。これは$L[i+1]$が$0$か$1$かによって場合分けされます。

L[i+1] = 0の場合

dpL[i+1]への遷移

$dpL[i]$からの遷移は$(a[i+1],\ b[i+1]) = (0,0)$の1個
$dpU[i]$からの遷移は存在しない

dpU[i+1]への遷移

$dpL[i]$からの遷移は、$(a[i+1],\ b[i+1]) = (0,1),(1,0)$の2個
$dpU[i]$からの遷移は、$(a[i+1],\ b[i+1]) = (0,0),(0,1),(1,0)$の3個
数式化すると

\begin{array}{l}
dpL[i+1] = dpL[i] \\
dpU[i+1] = dpL[i] \times 2\ + \ dpU[i] \times 3 \\
\end{array}

L[i+1] = 1の場合

dpL[i+1]への遷移

$dpL[i]$からの遷移は、$(a[i+1],\ b[i+1]) = (0,0),(0,1),(1,0)$の3個
$dpU[i]$からの遷移は、$(a[i+1],\ b[i+1]) = (0,1),(1,0)$の2個

dpU[i+1]への遷移

$dpL[i]$からの遷移は存在しない
$dpU[i]$からの遷移は、$(a[i+1],\ b[i+1]) = (0,1),(1,0)$の2個
数式化すると

\begin{array}{l}
dpL[i+1] = dpL[i] \\
dpU[i+1] = dpL[i] \times 2\ + \ dpU[i] \times 3 \\
\end{array}

以上を実施すると$dpL[Lのbit長]$が解となります。

コード

mod = 10 ** 9 + 7

L = list(input())
L.reverse()
N = len(L)

# dpL[i] : i-bit目まで　a + b = a xor b かつ a + b <= L
# dpU[i] : i-bit目まで　a + b = a xor b かつ a + b > L
dpL = [0] * (N + 1)
dpU = [0] * (N + 1)
dpL[0] = 1

for i in range(N):
    if L[i] == "0":
        dpL[i + 1] = dpL[i]                           # dpLからの遷移 (a,b)=(0,0)   dpUからの遷移 なし
        dpU[i + 1] = (dpL[i] * 2 + dpU[i] * 3) % mod  # dpLからの遷移 (a,b)=(0,1),(1,0) dpUからの遷移 (a,b) = (0,0),(0,1),(1,0)
    elif L[i] == "1":
        dpL[i + 1] = (dpL[i] * 3 + dpU[i]) % mod      # dpLからの遷移 (a,b)=(0,0),(0,1),(1,0)   dpUからの遷移 (a,b) = (0,0)
        dpU[i + 1] = dpU[i] * 2                       # dpLからの遷移 なし  dpUからの遷移 (a,b) = (0,1),(1,0)

print(dpL[N])

'''
# debug確認
for i in range(num+1):
    print(dpL[i],dpU[i])
'''

F - Takahashi's Basics in Education and Learning

問題ページ : F - Takahashi's Basics in Education and Learning

青色diff以上は後日挑戦