ABC356参加後振り返り

前書き

2024/3からAtCoderを始めました。
現職は、2年目の新人インフラSEです。
業務中では、実際に手を動かすとなると時間がかかるという場面が多く、
AtCoderを通して高パフォーマンスを出せるように実装力を磨きます。
使用言語はPython3です。

ABC 356 振り返り

全体を通しての感想

今回はA, B の2完でした。
C問題では全探索が間に合わないという思い込んだまま時間を使い切ってしまいました。全探索での実装は難しくなかったので、最初に思い付いた方法の計算量をざっくりとでも一度見積もっておくと良いと反省しました。
（今回のC問題のように指数時間の解法でも案外間に合うかもしれないし、間に合わない場合はどれくらい高速化すればよいか見積もることができる。）
また、bit演算を使う問題は経験がなく、今回が初めてでした。
復習して慣れていきたいと思います。

A問題 -Subsegment Reverse

問題
A - Subsegment Reverse (atcoder.jp)

答案①（AC）
1~L-1（昇順）とR~L (降順)とR+1からN（昇順）を結合すればよいです。（約6分）

#input
N,L,R = map(int,input().split())

#process
ans = list(range(1,L))+list(range(R,L-1,-1))+list(range(R+1,N+1))

#output
print(*ans)

B問題 - Nutrients

問題
B - Nutrients (atcoder.jp)

答案（AC）
WAを出してしまっていることに気が付かず、実時間では28分かかりました。修正込みで8分+1WAぐらいで解けていたので反省です。（約28分+1WA）

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

# process
for i in range(N):
    Xi = list(map(int,input().split()))
    for j in range(M):
        A[j] = A[j]- Xi[j]

ans = len([a for a in A if a > 0 ])

# output
print("Yes" if ans == 0 else "No")

C問題 -Keys

問題
C - Bingo 2 (atcoder.jp)

答案①（AC ※コンテスト後）
主な制約は$${2\leq N \leq 15, M \leq 100}$$であるため、$${O(N\cdot (M\cdot 2^N))}$$程度の処理は制限時間内で実行可能です。

コンテスト中は全探索で間に合う気がせず、かといって良い方法も見つけることができずに時間を使い果たしてしまいました。
思い込みで進めずに全探索の計算量を一度確認するべきというのは良い教訓になったと思います。以下の解答例は単に全探索を実装したものです。

# input
N,M,K = map(int,input().split())

C=[0]*M
A=[]
R=['o']*M

for i in range(M):

    temp = list(input().split())
    C[i] = int(temp[0])
    R[i] = temp[len(temp)-1]

    # A は2進表現を用いてテストで使う鍵の組み合わせを表現する。（1->使う/0->使わない）
    temp2 = 0
    for j in list((map(int,temp[1:len(temp)-1]))):
        temp2 += 2**(j-1)
    A.append(temp2)

# process
ans = 0

for pattern in range(2**N):
    flag = 0
    for test in zip(A,R):
        #Aを真の鍵のパターンpatternでマスクすることで受け入れられた正しい鍵の本数を求める
        accepted_keys = bin(test[0]&pattern).count("1")

        #テストの結果（'o', 'x'）に合わせて解か解でないか判定する
        if test[1] == 'o':
            if accepted_keys < K:
                flag = 1
                break
        else:
            if accepted_keys >= K:
                flag = 1
                break
                
    if flag == 0:
        ans += 1
            
# output
print(ans)

後書き

D問題については、平日に時間があれば取り組みます。