[BOJ]死の星(no.118111)

質問する
若い絶地武士の任務は死の星を浸透させ破壊することだ.死の星を破壊するには、長さNの音ではなく整数数列aiが必要だ.しかし、イヴァンにはこの数列はありません.しかし、彼は古い友达のダス・ヴィッドから受け取ったメモを持っています.このメモにはその数列が満たさなければならない条件が書かれています.
この用紙にはNサイズの正方形マトリクスがあり、i行jの1列目の数字はaiとajでビット演算andを実行した結果である.しかし残念なことに、光剣はメモを壊し、イヴァンはマトリクスの主対角線の数字を読み取ることができなかった.元の案を再組織し、任務を遂行するイヴァンを助ける.
答えは唯一ではないかもしれませんが、いつも存在しています.
入力
入力された第1行は、行列のサイズN(1≦N≦1000)を与える.
次のN行は、行列内の各要素のN個の数mij(1≦mij≦109)を与える.
しゅつりょく
問題条件を満たすN個以外の音の整数を1行に正しく出力する.各整数は109以下でなければなりません.複数の回答がある場合は、いずれかを印刷します.
🤔 の意見を打診

AND演算が交差していると思う場合は、

数列は各行の和集合の数列と見なすことができる.

OR演算を2回繰り返すだけで、

行列は主対角線に対して対称であるからである.

繰り返し回数を減らすために,行列対角線の半分に限定して繰り返す.

📌 説明する

from itertools import islice
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    ans = [0]*n

    for x in range(n):
        grid = map(int, input().split())
        for i,y in enumerate(islice(grid, 0, x)):
            ans[x] |= y
            ans[i] |= y

    print(*ans)

if __name__ == '__main__':
    sys.exit(main())

なぜtupleをsliceにしないでislice関数を?

tuple化も思ったより時間がかかります.小さいなら小さいけどランキングにこだわります.

mapの戻り型もiterableです.データ型を変更せずにスライドできる関数はisliceで40ミリ秒程度節約できます.

レビュー

sliceのデータ型を変更するよりもislice関数を積極的に利用したほうがいい!

の主要な動作の速度が速いことを指定します.(Pypyは逆のようです)