https://atcoder.jp/contests/abc147
解説
numpyを利用できるかよ！今度注意する。
AとBを書くまでもない。
###C - HonestOrUnkind2
bit全探索で解く。
3
1
2 1
1
1 1
1
2 0
を例としてやりましょう。
n = 3で、全員のH(Honest)(Unkind)状況は、$2^{3}=8$つ可能性がある。
例えば、101は、人1と人3が正直者、人2が不親切者である状況を示す。
ならば正直者の証言に矛盾があるかどうか、それをチェックすればいい。
人1の「人2が1です」証言は、101に矛盾するので、101が不可能であることがわかる。
n = int(input())
lst = [] # 証言list
for _ in range(n):
a = int(input())
lst.append([[int(i) for i in input().split()] for _ in range(a)])
m = 0
for i in range(2 ** n):
a = True # bin(i)が示す状況をTrueと仮定する。
for j in range(n):
if i >> j & 1:
'''
bin(i)のどの位が1か、現時点では私がこれをしか利用できない
101の場合、j=0,2の時条件を満たす(101>>0=1, 101>>1=10, 101>>2=1)
'''
for x, y in lst[j]: # 人jの証言をチェックする。ここでlst[0] = [2, 1]
if (i >> (x - 1) & 1) != y: # 101>>1&1=0, y=1, 矛盾
a = False # iがだめだ
break
'''
011の場合、j=0,1：
j=0: [x,y]=[2,1], 011>>1&1=1, y=1, OK
j=1: [x,y]=[1,1], 011>>0&1=1, y=1, OK
aがTrueのまま
'''
if a:
m = max(m, sum(map(int, bin(i)[2:])))
# 011に1が幾つあるか、現時点では私がこれをしか利用できない
print(m)
###D - Xor Sum 4
10
3 1 4 1 5 9 2 6 5 3
を例として計算しよう。
3 = 0011
1 = 0001
4 = 0100
1 = 0001
5 = 0101
9 = 1001
2 = 0010
6 = 0110
5 = 0101
3 = 0011
各数字の各bitが、他の数字とN-1回XOR算しなければならない。
XOR算は、
1 xor 1 = 0 xor 0 = 0, 1 xor 0 = 0 xor 1 = 1
です。
1位を見ると、７つ'1'と３つ'0'があることがわかる。
つまり、全部45回のXOR算に、結果の1位が1になったのは21回。
2、3、4位には、別々24回、24回、9回ある。
つまり、最後の結果は、
21 * 1 + 24 * 2 + 24 * 4 + 9 * 8 = 237
です。
よって、
import numpy as np
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0
for i in range(60):
c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
s += 2 ** i * c1 * (n - c1)
arr >>= 1
print(s % mod)
###E - Balanced Path
自分ができないから他人のコードを拝見し参考した。
https://atcoder.jp/contests/abc147/submissions/8874312
先ずはarrayを作る。
import numpy as np
H, W = map(int, input().split())
lst1 = []
lst2 = []
for _ in range(H):
lst1.append([int(i) for i in input().split()])
for _ in range(H):
lst2.append([int(i) for i in input().split()])
arr1, arr2 = np.array(lst1), np.array(lst2)
arr = np.abs(arr1 - arr2)
'''
2 3
1 10 80
80 10 1
1 2 3
4 5 6
を例として、
arr = array([[0, 8, 77], [76, 5, 5]])
'''
つぎにbitを使う。
0<=A,B<=80ので、偏りは最大で80(H+W)まで考える必要がある。(by解説、実は80(H+W-1)まででも構わない)
d = [[0] * W for _ in range(H)]
m = 80 * (H + W) # 400
d[0][0] = 1 << m # 最初の「位置」
for h in range(H):
for w in range(W):
x = arr[h][w] # 現在地の偏りを取る
if h > 0:
d[h][w] |= d[h - 1][w] # 前回のすべて可能な位置を継承する
if w > 0:
d[h][w] |= d[h][w - 1] # 前回のすべて可能な位置を継承する
d[h][w] = d[h][w] << x | d[h][w] >> x
'''
今回可能な移動を記録する。
例えば前回の記録は、
00010(0,ここは最初の位置)01000で、
xは2の時、偏りは2と-2の二つ可能性がある。
ならば今回の記録は、
01000(1,ここは最初の位置)00000 | 00000(1,ここは最初の位置)00010
= 01000(1,ここは最初の位置)00010
になる。
これは、「偏りが4,0,-4の３つ可能性がある」を表示する。
最後、d[H - 1][W - 1]がすべて可能な偏りを記録したことがわかる。
'''
x, y= 1 << m, 1 << m # 最初の「位置」で偏りが0
for i in range(m + 1): # 最小のx,yを見つけ出す。
if d[H - 1][W - 1] & x or d[H - 1][W - 1] & y:
print(i)
quit()
x<<=1
y>>=1