7/24 解いた問題 - yamake's blog

$(x,y)$ の色が白（黒）い場合と $(x,y+K)$ の色が黒（白）い場合は同値です。

従って適当な白マス左下の位置が $0\leq i \lt K,0 \leq j \lt 2K$ となる $i,j$ について探索を行えばよいです。

次に、探索の手法についてです。愚直にやっていたら間に合わないので高速化をする必要があります。

市松模様を動かして、希望を叶えることができる領域もまた市松模様になります。

探索する領域について希望を叶えられる部分を1,叶えられない部分を0としてプロットしたあとの、領域の最大値が答えとなります。

市松模様のプロットは二次元累積和を用いることで高速に行うことができます。

入力無しという面白い形式の問題でした。

$k$ 番目の円の半径が $k$ となる100個の円を1500*1500の正方形の中に敷き詰めるという問題です。

まず1~50番目の円を

$1400\leq x\cup1400\leq y$

の領域に詰めます。

すると50個の円が残ります。

ところで、 $1400*1400$ の領域は一辺が200の正方形49個に分けられます。

また、一辺が200の正方形は残された50個の円を1つずつ含むことができます。

残された50個の円を49個の正方形に置くことができれば円を詰め切ることができます。

51番目の円と52番目の円について考えます。これら2つの円を一つの正方形の中におさめられれば円を詰め切れます。

51番目と52番目の円を $(51,51)$ と $(147,147)$ を置くことができるかどうか考えてみましょう。この二つが $(0,0),(199,199)$ を対角線とする正方形からはみ出ないことは明らかです。

次に、この二つが正方形内で重なっていなければ正方形内に収められていると言えます。重なっているかの判定については二つの円の中心間の距離と二つの円の半径の和を比較すればよいです。

$\sqrt{(147-51)^2+(147-51)^2}\fallingdotseq 135.7\geq51+52$

より収められることがわかりました。

したがって51, 52番目の円はそれぞれ $(51,51),(147,147)$ に置くことができます。

53~100番目までの48個について、

$0\leq i\leq6, 0\leq j\leq 6, i\neq 0 \cap j\neq 0$

を満たす

$(100+200i,100+200j)$

に置きます。これで完成です。

余談ですが、51番目の円を $(1449,1449)$ に置けば49個の円をそれぞれ

$(100+200i,100+200j)$

に割り振るだけでもできそうです。

どちらの方が実装が軽いかについては意見が分かれるかもしれませんが。。。