AtCoder Beginner Contest 356 - あるぱかのブログ

A - Subsegment Reverse
B - Nutrients
C - Keys

A - Subsegment Reverse

概要：配列 $A$ の一部分を逆順にしたものを出力してね

配列 $A$ 全体を逆順にするには

A[::-1]

と書きます。

$x$ から $y$ の間を逆順にするには

A[x:y+1][::-1]

と書きます（1-indexedの場合）。

並びを反転する場所としない場所を組み合わせて出力します。

（以下のコードは0-indexedで表記しています）

#ABC356 A - Subsegment Reverse
N, L, R = map(int, input().split())
A = [(i+1) for i in range(N)]
B = A[:L-1] + A[L-1:R][::-1] + A[R:]
print(*B)

提出リンク：提出 #54078819 - AtCoder Beginner Contest 356

B - Nutrients

リンク：B - Nutrients (atcoder.jp)

概要： $N$ 種類の食材から $M$ 種類の栄養をとったとして各栄養が基準値 $A$ 以上であるか判定してね

二次元配列を縦に足し算します。

$X_{1,j},X_{2,j},$ ・・・ $X_{N,j}$ の足し算が $A_j$ 以上であればOKです。

#ABC356 B - Nutrients
N, M = map(int, input().split())
A = list(map(int, input().split()))
X = []
eiyo = [0]*M
for i in range(N):
    xi = list(map(int, input().split()))
    for j in range(M):
        eiyo[j] += xi[j]
for i in range(M):
    if eiyo[i] < A[i]:
        print('No')
        exit()
print('Yes')

提出リンク：提出 #54087209 - AtCoder Beginner Contest 356

C - Keys

リンク：C - Keys (atcoder.jp)

概要：鍵の真偽の組み合わせで考えられる組み合わせ数を出力してね

制約が $N \leq 15$ 、 $M \leq 100$ と小さいので全探索します。

（ $2^{15} \times 100=3,276,800$ ）

真とする鍵の組み合わせを仮決めしてテスト結果と照合し、矛盾がなければ数え上げていきます。

仮決めした鍵のうち各テストで使用した本数を調べて以下の判定を行います。

テスト結果が〇かつ使用本数が $K$ 本以上ならOK
テスト結果が×かつ使用本数が $K$ 未満ならOK
その他（〇かつ $K$ 本未満、×かつ $K$ 本以上）ならNG

仮決めした鍵の組み合わせとテストに使用した鍵の照合を高速にしたいので、それぞれset()として積集合（&演算子）を使用しました。

・・・が20/60ケースでWAになりました。

#ABC356 C - Keys
from math import comb
from itertools import combinations
N, M, K = map(int, input().split())
zen = 0 #N本中K本以上のカギが正解となる組み合わせ数
for i in range(K, N+1):
    zen += comb(N, i)
test = []
for _ in range(M):
    ip = input()
    c, *a = map(int, ip[:-2].split())
    r = ip[-1]
    a = set(a)
    test.append([c, a, r])
keys = set((i+1) for i in range(N))
for i in range(K, N+1):
    for j in combinations(keys, i):
        now = set(j)
        count = 0
        for k in range(M):
            if test[k][2] == 'o' and len(now&test[k][1]) >= K:
                continue
            if test[k][2] == 'x' and len(now&test[k][1]) < K : 
                continue
            else:
                count += 1
        if count > 0:
            zen -= 1
print(zen)

提出リンク：提出 #54129635 - AtCoder Beginner Contest 356

（WA×20）

公式解説を参考に組み合わせの生成と使った鍵の本数のカウントだけbit演算するとACしました。

$1$ ~ $2^{N}$ の生成

for mask in range(1<<N)

正解の鍵を使った本数の数え上げ（上から $A[i][k]-1$ 桁目のビットが1ならカウント）

use += 1 & (mask >> (A[i][k]-1))

OK/NGの判定は元々のコードでいいようですが、組み合わせと本数カウントもやってること変わらないと思うんですけど・・・

念のため入力受け取り部分も変えてみましたが結果変わらず。bit全探索ﾅﾆﾓﾜｶﾗﾝ

#ABC356 C - Keys
from itertools import combinations
N, M, K = map(int, input().split())
C, A, R = [], [], []
for _ in range(M):
    CAR = list(input().split())
    C.append(int(CAR[0]))
    A.append(list(map(int, CAR[1:-1])))
    R.append(CAR[-1])
ans = 0
for mask in range(1<<N):
    judge = True
    for i in range(M):
        use = 0
        for j in range(C[i]):
            use += 1 & (mask >> (A[i][j]-1))
        if R[i] == 'o' and use >= K:
            continue
        if R[i] == 'x' and use < K:
            continue
        else:
            judge = False
    if judge:
        ans += 1
print(ans)

提出リンク：提出 #54136987 - AtCoder Beginner Contest 356