ABC351参加後振り返り

前書き

先月（2024/3）からAtCoderを始めました。
現職は、現場配属されて半年程度の新人SEです。
業務では、分かっていても実際に手を動かすのに時間がかかるという場面が多く、これを改善するために高パフォーマンスで3完できるように精進していきます。
AtCoderでは、Python3を使用しています。

ABC 351 振り返り

A問題 - The bottom of the ninth

問題

A - The bottom of the ninth (atcoder.jp)

• チーム高橋が先攻、チーム青木が後攻で野球をしている。

• 9回表終了時点でチーム高橋が$${\displaystyle\sum_{i=1}^9 A_i}$$点、チーム青木は$${\displaystyle\sum_{i=1}^8 B_i}$$獲得している。

• チーム青木が9回裏でサヨナラ勝利を決めるのに必要な最低点数は何点か。

答案（AC）
素直に$${\left(\displaystyle\sum_{i=1}^9 A_i+1\right) - \sum_{i=1}^8 B_i}$$を計算すればよい。以下のように実装してAC（約2分）。

##入力
A = list(map(int,input().split()))
B = list(map(int,input().split()))

#解答＆出力
print(sum(A)+1-sum(B))

B問題 - The bottom of the ninth

問題

• 各成分が英子文字であるサイズ$${N}$$の正方行列$${A, B}$$がある。

• ある唯一の$${(k,l)}$$を除き、$${A_{i,j}=B_{i,j}}$$である。

• $${(k,l)}$$はどれか？

答案①（AC）
Pythonの高次元の配列を良く知らなかったので、線形リストに格納してから
不一致する$${(k,l)}$$を計算する方針で実装。
以下のように実装してAC（約8分+1WA）。

#入力
N = int(input())

A = ""
for i in range(N):
    A = A + input()

B = ""
for i in range(N):
    B = B + input()

#解答＆出力
for i in range(N*N):
    if A[i] != B[i]:
        print(str(i // N + 1)+" "+str(i % N + 1))

答案②（AC / 公式解説の模写）
コンテスト中は敬遠してしまった、二次元配列を使った解法も実装してみました。
l.6などの、str→listのキャストはしなくても動作します。

#入力
N = int(input())

A = []
for i in range(N):
    A.append(list(input()))

B = []
for i in range(N):
    B.append(list(input()))

#解法
def spot(A, B):
    for i in range(N):
        for j in range(N):
            if A[i][j] != B[i][j]:
                return str(i+1)+" "+str(j+1)
#出力
if __name__ == '__main__':
    print(spot(A, B))

C問題 - Merge the balls

問題

C - Merge the balls (atcoder.jp)

• N個のボールがあり、それぞれの大きさは$${2^{A_i}}$$である。

• 次の操作を$${N}$$回行う：

  • $${i}$$個目のボールを列の右端に付け加える

  • 以下の手順を繰り返す：

    • 右端から2つのボールの大きさが同じならボールを合成する。合成されたボールの大きさは、合成前のボールそれぞれの大きさの和である。

• 上記の操作の終了後、列にあるボールの個数はいくつか？

答案①（TLE）
ボールを付け加える操作、合成する操作はいずれも高々$${N}$$回なので、素直に実装して$${O(N)}$$の十分速いアルゴリズムになる、、、と思っていたのですがそうはいかないようです。以下がTLEとなってしまった実装例です。（約17分）

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

B = []

for i in range(N):
    B = B+[A[i]] #末尾にA_iを追加

    while len(B) != 1 and B[-1] == B[-2]:
        B[-2] = B[-2] + 1
        B = B[:-1]

print(len(B))

答案②（AC）
リストの末尾の操作が遅いことを疑ってdequeを使って書き換えたところ、ACとなりました。（約76分+4WA/TLE）
後から調べたところ、スライス操作とポップ操作では結果が同じでも実行時間が異なり、今回の実装ではポップ操作を使う必要がありました。

■長さ$${N}$$のリストに対する操作の計算量

• （末尾の）スライス操作：$${O(N)}$$

• ポップ操作：　　　　　　$${O(1)}$$

つまり、listをdequeに書き換えたことが本質ではなく、スライス操作をポップ操作に置き換えたことが高速化に寄与していました。

■参考
pythonの高速化のために、用途別にcollection型(list/tuple/dictionary/set)の計算量をまとめる #Python - Qiita

ACした実装例は以下のようになります。

コンテスト中に提出したもの：

from collections import deque

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

B = deque()

for i in range(N):
    B.append(A[i])

    while len(B) != 1 and B[-1] == B[-2]: #1. ボールが一つならば操作を終了 # 2.3. ボールの後ろ二つが同じ大きさのときだけ次の操作をして1.に戻る
        B[-2] = B[-2] + 1
        B.pop()

print(len(B))

コンテスト後にlistで実装してみたもの：

#入力
N = int(input())
A = list(map(int,input().split())) 

B = []

#解法
for i in range(N):
    B.append(A[i])

    while len(B) != 1 and B[-1] == B[-2]:
        B[-2] = B[-2] + 1
        B.pop()

#出力
print(len(B))

コンテスト中に提出した問題のふりかえりは以上です。
D~F問題についても、今後ちょうどいい問題があれば触れていきたいと思います。