E - Four Square Tiles 解説
by 
maspy
ヒント集 → https://atcoder.jp/contests/arc197/editorial/12811
[1] 基本的な位置関係
恐らくほとんどの方は，\(4\) 枚の正方形を「左上・右上・左下・右下」という位置関係に配置するということに（定式化や証明ができなくとも）気づいたと思います．まずはこのことを証明しておきます．
通常のように行に \(1\) から \(H\)，列に \(1\) から \(W\) の番号をつけて，\(i\) 行 \(j\) 列のマスを \((i,j)\) と表します．\(i,j\) がともに \(N\) の倍数であるようなマス \((i,j)\) を黒く塗りましょう．
このとき，タイルは必ず黒く塗られたマスをちょうどひとつ含みます．制約から黒く塗られたマスは \(4\) つ以下しか存在しないため，条件を満たす配置では \(2N\leq H,W\) が成り立ち，
- \((N,N)\) を含む正方形のタイルがちょうどひとつ存在する．
- \((N,2N)\) を含む正方形のタイルがちょうどひとつ存在する．
- \((2N,N)\) を含む正方形のタイルがちょうどひとつ存在する．
- \((2N,2N)\) を含む正方形のタイルがちょうどひとつ存在する．
ことが必要です．これらのタイルを左上・右上・左下・右下のタイルと呼ぶことにします．
[2] 数え上げ
左上・右上・左下・右下のタイルの左上隅のマスをそれぞれ \((a_1,b_1)\), \((a_2,b_2)\), \((a_3,b_3)\), \((a_4,b_4)\) と書くことにします．これらが重ならないように配置されるのはどのようなときかを整理しましょう．
まず，隣同士の正方形が重ならないという条件は簡単です．これは式にすると，
- \(1\leq a_1,\quad a_1+(N-1)< a_3,\quad a_3+(N-1)\leq H\)
- \(1\leq a_2,\quad a_2+(N-1)< a_4,\quad a_4+(N-1)\leq H\)
- \(1\leq b_1,\quad b_1+(N-1)< b_2,\quad b_2+(N-1)\leq W\)
- \(1\leq b_3,\quad b_3+(N-1)< b_3,\quad b_4+(N-1)\leq W\)
のようになります．これらを満たす \(a_i,b_i\) の定め方の総数を数え上げることも出来ます．例えば \(a_3'=a_3-N\) とすればひとつめの条件は \(1\leq a_1 \leq a_3' \leq H-2N+1\) と書けるので，\((a_1,a_3)\) の数え上げは適当な二項係数で表され，全体としてはそのような二項係数 \(4\) つの積になります．
この数え上げから，条件を満たさないものを除きましょう．つまり，
- 隣同士の正方形は重ならない
- 「左上と右下」または「右上と左下」の正方形は重なる
という場合です．隣同士の正方形は重ならないという条件下で，「左上と右下」「右上と左下」の両方の対が重なることはありません．また「左上と右下」「右上と左下」の場合は明らかに同数あります．よって，「左上と右下」が重なる場合を数えればよいです．この場合の数え上げは行方向・列方向に独立な条件に分解できて，行方向については
- \(1\leq a_2,\quad a_2 +(N-1)<a_4,\quad a_4\leq a_1+(N-1),\quad a_1+(N-1)<a_3,\quad a_3+(N-1)\leq H\)
という条件になります．\(a_3' = a_3-N\), \(a_4'=a_4-N\) とすればこれは \(1\leq a_2\leq a_4'<a_1\leq a_3' \leq H-2N+1\) と書き換えられ，やはり適当な二項係数として数え上げられます．列方向の数え上げも同様です．
結局，\(2N\leq H,W\leq 3N-1\) の場合，答は \(x=H-2N, y=W-2N\) として \(x,y\) の多項式として書けて，テストケースごとに \(O(1)\) 時間で答を計算できます．
投稿日時:
最終更新: