Document

G: Pixel Shuffle
出典 Southwestern Europe 2005
担当牟田、野村
解説野村
1
問題概要
• 画像のピクセルを置換する変換を施す
• 変換は id、rot、sym、bhsym、bvsym、div、
mix およびこれらの逆変換の合成
• 何回適用すると元に戻るか？
– 画像サイズ～2^10×2^10
– 変換合成数～32
2
とりあえずは
• 合成した変換を求めてみる
– 2^10×2^10×32 ≒ 3300万
• 注意点
–
–
–
–
変換を逆方向に実装していないか
置換テーブルの意味を逆にしていないか
変換の合成は適切か
全部合わせて大混乱していないか
3
周期を求める
無理。
• 元に戻るまで一回ずつ適用していく
– 答は～2^31
– 2^10×2^10×2^31
• ある１点のみに着目
– 何回で元の位置に戻ってくるか
– 答はその値の倍数
• 各点の周期の最小公倍数
– 点AがA→B→C→AならB,Cはもう調べなくてよい
– 周期によらずピクセル数のオーダーで終了
4
結局
4と5と7の
最小公倍数
5
解答状況
• Submit / Accept
– combat
– coaches
– echizen
10 / 4
203 (1)
215 (1)
243 (5)
• サブミットは一番乗りだったが…
• バグとりに大苦戦
– GNC
293 (3)
• ランダム！？
6
合成を計算しないで出来るか？
• 安易な仮定はアウト
１２３
X↓ 周期2
２１３
１２３
Y↓ 周期3
２３１
１２３
X・Y↓ 周期2
３２１ (≠LCM(2,3))
• 適当なルール（○と○が可換など）で
扱いやすい式に変形できれば・・・
– 良いアイデア募集中
• ちなみに
– divの周期
2^x=1 mod n-1 なる最小のX
7

Download Report