第11回日本情報オリンピック本選4番解説解説: 釘 (NAILS) 第11回 日本情報オリンピック本選 今城 健太郎 (京都大学, IOI 2006 メキシコ大会) 2012年2月12日 1第11回日本情報オリンピック本選4番解説 問題の概要 正三角形で囲われた釘の数を求める問題 2012年2月12日 2 図: 大きさ5の正三角形 囲われた釘の数は 11個 第11回日本情報オリンピック本選4番解説 問題の制約 正三角形の一辺の大きさ 5000以下 囲む正三角形の数 5 105以下 2012年2月12日 3 ∼5 105 第11回日本情報オリンピック本選4番解説 解法 • 累積和による解法 • 最大値を伝搬する解法 2012年2月12日 第11回日本情報オリンピック本選4番解説 4 四角形の累積和問題 • 四角形の領域に対して加減算を行う • 2008年本選5番などで出題 • 素朴な計算方法だとO(数 面積)
