ARC224 B - Adjacent Tiles

考え方

まず、角度が異なる正方形が存在することは考えなくてよい。
というのは、そのような並べ方は以下の方法で、同じスコアのまま角度を揃えられるため。

• その並べ方を同じ角度のものごとに分離する
• 分離成分ごとにまとめて回転し、正方形の向きを同じにそろえる

また、同様に、中途半端に辺を共有している正方形が存在することも考えなくてよい。
ということで、全て格子点を頂点にもつ正方形のみで考える。

$N$ 個の正方形には、左辺が $N$ 個、上辺が $N$ 個ある。
このうち隣接に使われている個数が、隣接ペア数である。
そして、隣接ペア数が最大というのは、非隣接辺数が最小ということ。
つまり、この $2N$ 個の辺から、なるべく非隣接辺を生まない並べ方を考えればよい。

正方形の存在範囲が、縦幅 $H$、横幅 $W$ であるとする。
$2N$ 個の辺のうち、少なくとも $H$ 個の左辺と少なくとも $W$ 個の上辺は必ず非隣接である。
そして、例えば存在範囲の左上から貪欲に詰めていけば、非隣接が $H+W$ 個で済む解が構成できる。
よって、縦幅 $H$、横幅 $W$ である物の中では、非隣接辺最小値は $H+W$ である。

ここまで来れば、あとは「$HW \geq N$ である $H,W$ の中で $H+W$ の最小値は？」という問題。
$H+W$ が同じ値を取る中では $|H-W|$ が小さい方が積 $HW$ は大きくなる。
よって、$|H-W|$ が $0$ か $1$ のもののみ考えればよい。
$H \geq W$ としてもよいので、この問題は結局以下の順で解ける。

• $H^2 \geq N$ となる最小の $H$ を探す
• $H(H-1) \geq N$ ならば $W=H-1$、そうでなければ $W=H$ とする。
• 非隣接辺の個数の最小値 $H+W$ を出す

最後に、忘れずに $2N$ からそれを引けば、元の問題の答え。
計算量はテストケース当たり $O(1)$、全体で $O(T)$。

動作例

$N=18$ の場合を考える。

n: 18

まず、h を $\sqrt{n}$ 以上の最小の整数にする。

$\sqrt{18}$ の整数部分は $4$ であり、$4^2<18$ なので、$h = 5$ とする。

次に、$5 \times 4 = 20$ が $18$ 以上なので、$w = h-1 = 4$ とする。

各タイルの左辺と上辺を数えると、全部で $2n = 36$ 本ある。
そのうち、隣接に使われない辺は合計 $h+w = 9$ 本である。

したがって、隣接に使われる辺の本数は、$2n-h-w = 36-5-4 = 27$ となる。

以上より、答えは $27$ である。

注意点

$N$ や答えは、int 型からはみ出る。
long long 型を用いること。

別解

特になし。