441.1

0点連続中。

250

N個の数字からなるPermutationが与えられるので、それと一番差分が少ないPermutationのうち、Permutationを導出可能なものとの差分の数を答えよ、という問題。導出については式が与えられる。

良くある問題らしいが、初出なので全く分からない。上の方ではコピペ問題だったらしい。

500

見てない。

1000

紙を適当に追って、特定の矩形内に含まれる部分に色を塗り(下にも貫通させる)、元に戻す、という処理を複数回行った後で、色の塗られていない領域の大きさを答えよ、という問題。

登場するx座標が200個で、y座標が100000個なので、全部についてうまいこと計算するだけで良さそう？

上のルーチンはかなり遅くてダメそうなので、最初にやった実装を修正した。方針としては、x座標200個をソートして、どの折り方に関与しているかを配列で持つ。関与する折り方について出現するy座標100000個をソートして、関与するかしないかのflipを覚えておく。関与する個数が0個の領域を下から求めていくだけ。

これで3倍くらい遅かったので、(y座標について出てくるものは完全一致するので)x座標から分かる関与する折り方集合についてメモしてみたら、間に合った。もっと悪いケース作れるような気もするが、システムテストに気合いは足りないようだった。