SRM 340 div1 level3

難しい。覚えることたくさん。

まず、囲む系の問題は範囲チェックのロジックを思い出す。「ある一方方向」に向かって端まで進むのに境界を何回越えるかを数える。奇数なら内側、偶数なら外側。

このとき、実はある一方だけでよい。2次元空間でも1つの軸だけでよい。1軸についても正か負のどちらかだけでよい。ただし、範囲が閉じていることが保障されていなければならない。なぜなら、閉じているので軸の向きに関係が無く、ある軸においては閉じた空間で切れば必ず境界は偶数ある。だから片方が偶数ならもう片方は偶数、奇数なら奇数と反対側の境界線数も決まってしまう。

チェックすべきものが最大で10なので、総当りでも2^10=1024しかないのでモノをビットで見立てて、それらの境界線数のパリティをintのビットで表しておく。また、各セグメントを通った時にそれぞれのモノの境界線のカウントに含まれるかどうかもintのビットで表しておく。 ＸＯＲを取り続けると、その結果がパリティになるので、境界線パリティのintと通ったセグメントのintをＸＯＲしていけば、その時の境界線パリティが更新され続ける。

同じ場所を通って同じ境界線パリティであれば全く同じ状態と思っていいので、int[51][51][1<<n]（nはチェックすべきモノの数）をメモライズすればよく、最小コストの枝だけを残していけばｂｓｆで～2,500,000程度のループになる。常に到達可能なセグメントを進んでいき、進むたびに境界線パリティをＸＯＲで計算して、memしてあるx,y,パリティのステップ数より小さい時だけ進んでいく。x=y=0になったら止める。ぎりぎりいける。

• 境界の内外問題は、閉じた空間であることを保障して1軸1方向に進んだ時の境界のパリティで内外を判断する（1軸1方向でよければ状態数は激減する）
• ＢＳＦなどサーチの問題のループ数はmemのサイズのオーダーだと思えばよい
• やはりＬｉｎｋｅｄＬｉｓｔを使え
• 境界を作成するループは普通にやれば無限だが、その地点にいるときの意味が同じものを除いてしまえば状態数は激減する。この場合、各モノが数える境界線パリティの状態が同じものは同じ意味を成すので、常にパリティを数えながら移動して行けばよい