脳log[20220517]

2022年05月17日 (火) [AtCoder] 精進。Code Formula 2014 本選-F「100個の円」(水 diff)。■AtCoder ではなかなか類題が見つからない問題。まずは面積の比較。敷き詰める範囲が 1500×1500 = 2250000。そこに置く円の面積の合計が約 1062958 (48 %)。円が四角形だとすると 1353400 (61 %)。それほど厳しくはないのかな。空き領域と置く円をすべて正方形として扱うことにする。大きい正方形ほど置く場所に困るから、一辺が 200 の正方形から順番に置いていくことにする。■提出 #31770604 (AC / 325 Byte / 60 ms)。ブログや提出一覧を見るといろいろな考え方があることがわかる。自分の解答のできがいいとは思わないけど、許容範囲の広い制約だったのだ。