B - Let's Get a Perfect Score Editorial by math_hiyoko
行列積を用いた解法\(Boolean型のN \times N\)行列\(NG\)を
\(NG[i][j] = (参加者iが問題jを解けないならTrue、解けるならFalse)\)
とします。
このとき
\(NG[i][k]\;and\;NG[j][k] = (参加者iとjの組が問題kを解けないならTrue、解けるならFalse)\)
となるので、\(NG\)と\(^t\!NG\)の行列積(\(N×N\)行列)の(\(i, j\))成分は、参加者iとjの組に解けない問題があるかどうかを表していることになります。
求める答えは\(NG\)と\(^t\!NG\)の行列積のうち、\(False\)となるような(\(i, j\))成分(\(i \lt j\))の個数となるので、これを求めることでこの問題を解くことができます。
(実装例では上記の行列の各成分を反転したものについて、\(True\)となるような要素数を数えています。)
import sys
import numpy as np
# 入力
S = np.array([list(line.rstrip()) for line in sys.stdin.readlines()[1:]])
# NG[i][j] = (参加者iが問題jを解くことができないかどうか) N×M行列
NG = S == 'x'
# OK[i][j] = (参加者iと参加者jの組で全ての問題を解けるかどうか) N×N行列
OK = ~(NG @ NG.T)
# 答え = (OKのi < jとなる(i, j)成分のうち、Trueのものの個数)
answer = np.triu(OK, 1).sum()
print(answer)
posted:
last update: