AtCoder Beginner Contest 147

参加記 atcoder

はい。
https://atcoder.jp/contests/abc147
ooox-- 935(+11)だったようです。

A - Blackjack

PyPy3

l=[int(i) for i in input().split()]
print("win" if sum(l)<=21 else "bust")

21で分岐します。あとbustも知らなかったので賢くなりました。

B - Palindrome-philia

PyPy3

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

先頭からと末尾からの文字を比較して一致しなければ変更が必要な箇所ということでカウントすれば解に。

C - HonestOrUnkind2

PyPy3

n=int(input())
w=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        w[i].append((x,y))
ans=0
for i in range(1<<n):
    x="0"*15+bin(i)[2:]
    z=[int(i) for i in x[-n:]]
    f=1
    for p,q in enumerate(w):
        if z[p]==1:
            for r in q:
                if (z[r[0]-1]!=r[1]):
                    f=0
    if f:
        ans=max(ans,z.count(1))
print(ans)

これ問題文と入力の内容を理解するまで時間がかかりました。。

3 #全体の人数は3人
1 #1番目の人は証言を1件
2 1 #2番目の人は正直者と証言
1 #2番目の人は証言を1件
1 1 #1番目の人は正直者と証言
1 #3番目の人は証言を1件
2 0 #2番目の人は不親切と証言

入力の内容はこういう感じのはずです。
00...00から11...11までを作成しながら試します。作成した数列のx番目が1だとx番目の人を正直者と仮定します。x番目の人の証言内容が作成した数列の01と一致するかを確認します。証言内容の確認は正直と仮定した人だけです。不親切と仮定になる人の証言内容を見ても意味ないはずですし、全パターン試しますしなので不親切仮定の人は証言内容を確認しなくていいかな、と思います。多分。

D - Xor Sum 4

PyPy3

def sol():
    mod=1000000007
    ans=0
    n=int(input())
    a=[int(i) for i in input().split()]
    x=[[0]*61 for i in range(n+1)]
    l=[pow(2,i,mod) for i in range(61)]
 
    for i in range(n):
        d=a[i]
        cnt=0
        for j in range(61):
            if d&1:
                x[i+1][cnt]=x[i][cnt]+1
            else:
                x[i+1][cnt]=x[i][cnt]
            cnt+=1
            d=d>>1
 
    for i in range(1,n):
        for j in range(61):
            p=x[i][j]-x[i-1][j]
            if p:
                ans+=l[j]*((n-i)-(x[-1][j]-x[i][j]))
            else:
                ans+=l[j]*(x[-1][j]-x[i][j])
            ans%=mod
    print(ans)
 
if __name__=="__main__":
    sol()

よくわかりません。
l=[pow(2,i,mod) for i in range(61)] は2のi乗はlのi番目を見ればわかるようにするためです。
x=[[0]*61 for i in range(n+1)] はbitの1が立っている桁の累積和をわかるようにするためです。サンプル1の場合は、

[[0,0,0...], #0番目のリストは自分でわかりやすくするためです
 [1,0,0...], #1の2進数表記は1
 [1,1,0...], #2の2進数表記は10
 [2,2,0...], #3の2進数表記は11
...

で累積和を取ります。1xor2=3と1xor3=2の和は5です。
1番目のリスト[1,0]と3番目のリスト[2,2]に注目します。20の位は1番目で1が立っていて3番目で累積和2です。その場合は2-3番目までの区間で0の個数(1が立っていない個数)がxorで1が立つ個数、回数になります。20は1回で、(20)×1回=1ですね。
21の位は1番目では0で1が立っていなくて3番目で累積和2です。その場合は2-3番目までの区間で1が立っている個数を見ます。21は (21)×2回=4ですね。これで1xor2=3と1xor3=2の和は5と同じになります。これをもっと長い桁数、区間で処理をしています。時間は結構ギリギリです。