XORShiftの逆算
XORShiftされた値を逆算する機会がありましたのでメモ書きです。
y = x ^ (x << t) のとき、y ,t が分かってるとして、xを求めたい。 x << t の値は下位t桁は必ず0になっているから、 y & ((1 << t) - 1) と x & ((1 << t) - 1) は等しい。 また、x << tの t桁 ~ 2*t - 1桁目も y & ((1 << t) - 1) と等しい。 今回は x = 22, t = 3 を例として下記に示す。 x = 000010110 x << 3 = 010110000 y = 010100110 y & ((1 << 3) - 1) = ______110 x & ((1 << 3) - 1) = ______110 x << 3 の 3桁 ~ 5桁目 = ___110___ この時点で判明してるのは、y と x << t の 0桁 ~ 2*t - 1桁目までである。 x << t の判明してる部分をzと置く。XORの性質を利用すると、 z = ___110000 y = 010100110 x' = z ^ y = ___010110 よって、x の t桁 ~ 2*t - 1桁目が新たに得られた。 x' << 3 = 010110000 z' = 010110000 ; x << tの判明している部分 y = 010100110 x'' = z' ^ y = 000010110 これでxの全ての桁が復元できた。 右シフトのXORShiftもほぼ同様の処理で逆算可能である。 ただし、右シフトは算術シフトか論理シフトで値が異なる点に注意。 ちなみに、C言語の右シフトは算術シフトか論理シフトかは処理系依存。 gccではsignedでは算術シフト、unsignedでは論理シフトになる。
sample code（左シフト）
#include <stdio.h> // 1 <= t <= 31 unsigned int decodeXORLeftShift(unsigned int y, int t){ unsigned int x; unsigned int z = (y & ((1U << t) - 1)) << t; unsigned int mask = ((1U << t) - 1) << t; while( mask ){ x = z ^ y; z = z | ((x & mask) << t); mask <<= t; } return x; } unsigned int encodeXORLeftShift(unsigned int x, int t){ return x ^ (x << t); } int check(){ int i; unsigned int j; for(i=1; i<32; i++){ for(j=0; j<10000; j++){ if( j != decodeXORLeftShift(encodeXORLeftShift(j,i), i) ){ return 0; } } } return 1; } int main(){ puts(check() ? "OK" : "NO"); return 0; }
実行結果 OK
AOJ.1178 A Broken Door
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp
35msまで高速化頑張ってました。
現在1位の29msに届かなかったのが残念です。
解法はいくつかあるようですが、BFS+ダイクストラで解きました。
入口から出口までの1つの経路を考えたとき、通過するドアのうちで故障していたら最も困るケース（必要になるカード枚数が一番多い）が、その経路におけるコストになります。
どのドアが故障しているかは事前にわからないので、部屋から部屋へ移動するときに、そのドアが故障していた場合のカード使用枚数を調べる必要があります。
これは、ある部屋(x,y)から方向dirのドアが故障していた場合として、出口までの最小のカード使用枚数をBFSで計算します。
それから、入口からある部屋までの経路のうちで、もしドアが故障していた場合における入口から出口までのコストで最悪のものをworststepとし、これをダイクストラにおける比較コストにします。
見落としとしては、ある部屋(x,y)において2つの状態を考えます。
状態i : 現在のカード使用数 = a、worststep = bとします
状態j : 現在のカード使用数 = c、worststep = dとします
このとき、worststepだけで比較を行うと間違った答えになる場合があります。
仮に b < d でも、a > c の場合、状態jのほうが後になって最適解を出す場合があります。
ですので、この場合はどちらも最適解を導く可能性があるので、両方とも状態を保持する必要があります。
にしても、1位速いなぁ…。
記号
ご無沙汰です。
はてなブログに貼り付けるつもりでしたが、ハイライトがまだ効かないのでこちらに。
バイナリエディタの開発を一旦中断して、夏コミネタに向けて違うことしてました。
その結果↓
__attribute__((section(".text"))) char main[] = "%@@@@%!!!!-|||!-$*:!-/~{<`[[[[[[[%@@@@%!!!" "!-!!!!%!!!!`[[[[[[[%@@@@%!!!!-!!!!-!!!!-!|" "|]-!:`)-|:`~`[[[[[[[%@@@@%!!!!-!@!!%:+@@-`" "!@@`[[[[[[[%@@@@%!!!!-?!?!-&&:%-/?|``[[[[[" "[[%@@@@%!!!!-!!?!--:$!-??/[`[[[[[[[%@@@@%!" "!!!-]!!!-%`!,-~~\\?`[[[[[[[%@@@@%!!!!-]!?!" "-%{:`-~{|~`[[[[[[[%@@@@%!!!!-!!!!%:^\\\\-_" "\\\\\\`[[[[[[[%@@@@%!!!!-!!!!%$!!!`[[[[[[[" "%@@@@%!!!!-!!!!-@@@!%+,,[-{{{``[[[[[[[%@@@" "@%!!!!-!!!!-/*\\[-`/~{`^^^^^^^^%@@@@%!!!!-" "!!]]-$?::-`~<<`________!~,%@@@@%!!!!-!]!!-" "#:##-`<@@`________)~,____";
このままでは動きません。
スタックの実行権限許可と、書き換え許可を行う必要があります。
さらに絶対アドレスを使用しているため強く環境に依存します。
動作確認
gcc (GCC) 4.5.1 20100924 (Red Hat 4.5.1-4)
kernel 2.6.35.14-103.fc14.i686
プログラムヘッダ？の書き換え許可の変更には、
http://ph.halfmoon.jp/
trash -> 「プログラムヘッダのパーミッションをrwx にするスクリプト」
をお借りした。
$ gcc kigou.c -z execstack $ python pgm_hdr.py < a.out > b.out $ chmod 755 b.out $ ./b.out $ assembly
本来の目的は、このプログラムを書くためのプログラムを書くことでした。
作成過程を夏コミネタにしようと思います。受かれば、ですが。
参考
http://perl-users.jp/articles/advent-calendar/2010/sym/16
ζ*'ヮ')ζ＜$_
ブログの方向性が迷子なので、ちょっと考えます。
方向が定まったら、恐らく新しいブログに移行すると思います。
新ブログ予定地 : ichirin2501's diary
競技プログラミング記事 : rintpsyの日記
てすと
てすと。
