CTT 2018 Day 2 B 面国建设

問題リンク (QOJ)
想定解がなんなのかよくわからない。

問題概要

正整数 $S,C$ が与えられる。正整数 $(a,b)1<=a<=S,1<=b<=C$ についてそれぞれ以下の問題を考えて、答えが Yes であるような組の個数を求めよ。

• 各辺の長さが正整数であるような長方形の多重集合であって、面積の和が $a$ で周長の和が $b$ であるようなものはあるか。

制約
$S\le 2\times {10}^5,C\le 4\times {10}^5$

解法

とりあえず、周長ではなく縦と横の長さの和ということにする。

もちろん dp[i][j] := 面積 i で周長 j にできるか などとすれば多項式時間で解けるが、もう少しまともな考察をする。

まず、周長 l について実現可能な最大面積と最小面積はそれぞれ ${\displaystyle \lfloor \frac{l}{2}\rfloor \times \lfloor \frac{l+1}{2}\rfloor ,\lfloor \frac{l+1}{2}\rfloor }$ 。である。これらはそれぞれ、最大の長方形を $1$ つ置くパターンと、 $1\times 1$ の長方形をたくさん置くパターン。
最大と最小の間で、実現不可能な要素はかなり疎で、しかも最大近くに偏っているだろうということはなんとなく予想がつく。或いは愚直な解法の実装が簡単なので部分点と同時に実験できる。こういう考察をもう少し形式的に落とせば具体的に計算量改善になる。

まず、ある数 $n$ を $n=m^2+c(0\le c\le 2m)$ と表して、面積が $m^2,c$ になる長方形をそれぞれ作るような構築方法が考えられる。すると、ある $O(\sqrt{S})$ の数 $X$ があって、 $X\ge b$ であれば $(a,b)$ についての答えは全て Yes となる。(自明な最小面積の条件を満たしたうえで)
それならば周長 $b$ が $X$ より大きい部分は考えなくてよいので、実際に dp で答えを求める必要がある $(a,b)$ の個数は $O(S^{\frac{3}{2}})$ になる。遷移に $O(S)$ かかるので合計で $O(S^{\frac{5}{2}})$ になる。

例えばもらう dp として実装するとき、そんなに大きな周長を使う必要がないだろうというのもなんとなく予想がつく。雰囲気としては、面積が大きい長方形を $2$ 個以上作る意味はなさそうという感じ。
これもちゃんと考察すれば、使う周長の上限を $O(S^{\frac{1}{4}})$ で抑えられる。

ここまで考察すればオーダー上は $O(S^{\frac{7}{4}})$ に落ちている。評価がガバガバなのは間違いなくて、実際のコードでは適当にしきい値のパラメータを設定すれば余裕で通った。あるいは、うまく更新の順番を設定すれば、ある意味での枝狩りはできてもっと速くなると思う。

自分の提出

なんて長々と書いていたら、他の人のコードがみんな短いし $O(S^{\frac{3}{2}})$ でびっくりした。これはどういうことかというと、辺の長さが $x,y(x\le y)$ の長方形を $(x,y)$ と表すことにすると、

• $(x,y),(x,z)$ は $(x,y+z-1),(1,x)$ に
• $(1,x),(1,y)$ は $(1,x+y-1),(1,1)$ に

それぞれ置き換えられるので、結局 $(1,1)$ を除いて、ある $x$ について長方形 $(x,y)$ は $1$ つしか使わないということらしい。この考察は全くしていなかった…