Document

Matrix Operation
原作：松本
修正：岩田
担当：野田・平澤
問題概略
• 各要素の初期値が {ar,c}=Ar+Bc (列番号と行番号の線形結合)
で与えられる正方行列に対し以下の処理を順に行い、
最終的に得られた行列からハッシュ値を計算せよ
▫
▫
▫
▫
1要素への書き込み・要素間でのコピー
2行の入れ替え・2列の入れ替え
90度回転 (時計回り・反時計周り)
上下反転・左右反転
• 制約
▫ 行列の1辺のサイズ(N)：最大40,000
▫ クエリの数(Q)：最大40,000
▫ ハッシュを計算する範囲：最大1,000×1,000
想定誤解法
• N×N行列をメモリ上に確保し、
クエリが来る度にその行列を実際に操作する
▫ Nが最大40,000なので、そもそもメモリに乗らない
• クエリを全て読み込んだ後で、
ハッシュ計算に必要なそれぞれの値を
クエリを遡っていきながら計算する
▫ ハッシュ計算に必要な値が1,000,000個あり、
クエリが40,000個なので(通常は)無理。
想定解法 (オーダー)
• 行列サイズ(N)：～40,000
• クエリ数(Q)：～40,000
• ハッシュ計算に必要な要素(K)：～1,000,000
• 各クエリをO(logN)やO(logQ)程度で実現
▫ 40,000 log(40,000) = 2,000,000
• ハッシュ計算をだいたいO(K)で実現
▫ O(K+X)とかでもXが小さければOK
想定解法 (実現方法)
• クエリの実現方法
▫ 盤面全体をどれだけ回転・反転したかを持つ
 回転・反転動作がO(1)になる
▫ 盤面の各列各行をどのように移動したかを持つ
 行・列の入れ替え動作がO(1)になる
▫ 書き込み・コピーにより上書きした要素だけ記憶
 上書き要素数は最大でQ個。
 map等で保持すればO(logQ)で検索できる
 それ以外は行番号・列番号から計算可能
• 値の取得方法
▫ mapに記録されていればその値・なければ初期値
注意点
• 操作順序に気をつける
▫ 90度回転した後に上下反転するのと
上下反転した後に90度回転するのは異なる
AB
CD
回転
CA
DB
反転
DB
CA
別物！
AB
CD
反転
CD
AB
回転
AC
BD
• 常に操作順序を統一しておけばok
クエリ
回転操作
反転操作
上書き操作
など
提出状況
• 提出チーム数:
• 受理チーム数:
• 総提出数:
• First accepted: mlTwTlm (71min)

Download Report