JOI 2021/2022 二次予選 C 「国土分割 (Land Division)」
問題ページ
私が取った解法
$H=1$ の場合（小課題 $1$）
この場合は簡単です。
$S=\displaystyle \sum_{i=1}^{W} A_{i}$ として、$S$ の約数 $d$ を列挙したうえで、$\displaystyle \frac{S}{d}$ 個に分割出来るか判定すればよいです。これは、左から貪欲に取っていけばできます。
一般の場合
小課題 $1$ の解法を応用することを考えます。
$i$ 行目の要素の総和を $R_i$、$j$ 列目の要素の和を $C_j$ とします。また、$S=\displaystyle \sum_{i=1}^{H} \sum_{j=1}^{W} A_{i,j}$ とおきます。
$R, C$ それぞれについて、$H=1$ の時の手法を適用します。すると、「縦方向に入れて大丈夫な切れ込みの組み合わせ」と「横方向に入れて大丈夫な切れ込みの組合せ」が列挙できます。
よって、縦方向と横方向のそれぞれから切り方を $1$ つずつ取ってきて、全通りについて「和が全て等しいか」を判定すればよいです。これは頑張ればできます（説明箒🧹）。
計算量は、
$n$ 以下の整数の約数の個数のうち最大のものを $d(n)$ として、$O(\sqrt{S} + d(S) HW)$ となります。$50 \times 50 \times 100000 = 250000000$ 以下で最大の高度合成数は $245044800245044800$ で、その約数の個数は $1008$ です。よって、計算回数は最大でも $2.5 \times 10^{9}$ 回程度であることが分かりました。
あれ？
助けてください
実際は $H=1$ の時の答えがそんなに大きくならないので爆速で通ってると思うんですが、どうやったらうまく抑えられるか分かりませんでした
助けてください
追記
「$d$ 個分割する方法は高々 $1$ つで、$d$ の取り得る値は $1$ から $W$（ないし $H$）なので結局 $H^2 W^2$ では？」みたいな指摘を受けました ありがとうございます 僕がバカでした
AC コード
感想
難しすぎる、難易度 7 は最低でもある 8 でもいい でもパンケーキほどではないし……うーん
体感的には低めの青 diff くらい？
おわりに
D 問題についても書くかは未定です（こっちは解法が想定と異なったから書いていますが、D は想定とそう変わら無さそうなので）
