ABC147

ABC147に参加しました。

自分が時間内に解けた問題プラス１問書きます。

A問題

標準入出力と足し算とif使うだけ

a1, a2, a3 = (int(i) for i in input().split())

if(a1 + a2 + a3 > 21):
    print("bust")
    exit()
print("win")

B問題

Pythonでは文字列の後ろからi番目をs[-i]とかで指定できることを知っていれば、あとは文字列の頭と尻尾から違う文字になっているものを数えて行くだけ。

s = input()

length = len(s)
ans = 0
for i in range(int(length/2)):
    if(s[i] != s[-1*i-1]):
        ans += 1
print(ans)

時間内で解けたのはここまででした。
C問題はbit全探索をすればいいのはわかったが、判定処理を無駄に難しく考えてしまって、書けなかった。

C問題

「正直者」と「不親切な人」の全パターンが高々$2^{15} = 32768$通りしかないので全探索できます。
ここでの全探索はYES/NOの選択など状態が$2^n$ある二値変数のパターンを全て列挙するのに使えるbit全探索ってやつですね。
bit全探索について詳しくはこちらが参考になるかと。

ちなみに、実行制限時間内に、全探索できるかできないかの判断はfor文なりwhile文がどれくらい回るかを考えれば大体わかって、こちらのブログによるとAtCoderの実行制限時間2秒では、$10^7$程度が限度ということなので今回は問題なく全探索できる！

n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

testimony = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if(y[i][j] == 1):
            testimony[i][x[i][j]-1] = 1
        elif(y[i][j] == 0):
            testimony[i][x[i][j]-1] = 0

ans = 0
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            for l in range(n):
                if(testimony[k][l] != 2):
                    if(testimony[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        ans = max(sum(bit_list), ans)
print(ans)

ある「正直者」と「不親切な人」のパターンに対して、正直者である人が証言していることが今の「正直者」と「不親切な人」パターンと食い違っていないかをチェックして、食い違っていなければ正直者の人数を数える。
その最大値が答え。

という流れですね。

今回のコンテストの感想

最近はC問題までは安定して解けていて、D問題が解けたり解けなかったりという感じだったので
C問題が解けないと言うのは久々だった、、、非常に悔しい。
次回は頑張りたい。