513.1

問題自体は簡単です、というセット。

250

チラッと見たけれど、恐ろしく長くて放置。

500

同じものが2個ずつK組ある状態で神経衰弱。全部当てるまでの手数の期待値を答えよ、という問題。

場合分けしてDPするだけ。既に見たヤツと見てないヤツの数でやる。見たヤツを引いたら、ペア解消。見てないヤツは、見てないヤツを見付けるか、既に見たヤツ(次のターンで解消)を見付けるか、更に見てないヤツを見付けるか。

1000

一次元空間で、目的地に移動することを考える。鏡があって、鏡像位置に移動するのは1ターンで、1マス移動するのも1ターン。鏡はどれも一回しか使えない。(実際には複数回使っても意味ない。)目的地に到達するまでの最小ターン数を答えよ、という問題。

鏡の位置をMとして、現在位置をXとすると、鏡を使うと2M-Xに移動する。で、鏡を使う前に1マス移動した場合、それは鏡を使った後に反対側に1マス移動すれば同じなので、これは最後に使うことにすると、もう一枚の鏡が位置Nにあって、使うなら2N-2M+Xに移動することになる。つまり、偶数回目に使う鏡と奇数回目に使う鏡にグループ分けして探索するだけ。これだと鏡の枚数Kに対して3^Kなので終わらない。

鏡を2回使っても意味ないので、取り敢えず、K/2枚使ったときに奇数回目なら加算(偶数回目なら減算)される分をメモしておいて、それらを組み合わせて、目的地に一番近くなるような移動を考えてやれば良い。メモした値をソートしておけば、目的地にどれだけ近いかは比較的求めやすいはず。