Project Euler - Problem 577
Counting hexagons
$n$ を 3 以上の整数とする.
下図のように,一辺の長さ $n$ の正三角形は $n^2$ 個の一辺の長さ 1 の正三角形に分割される.
これらの正三角形の頂点集合は, $ \displaystyle \frac{(n + 1)(n + 2)}{2} $ 個の格子点を持つ三角格子を構成する.
$ H(n) $ を,三角格子点の中から 6 点選んで作ることのできる正六角形の総数とする.
例えば,$H(3) = 1, \ H(6) = 12, \ H(20) = 966.$
$ \displaystyle \sum_{n = 3}^{12345} H(n) $ を求めよ.
下図のように,一辺の長さ $n$ の正三角形は $n^2$ 個の一辺の長さ 1 の正三角形に分割される.
これらの正三角形の頂点集合は, $ \displaystyle \frac{(n + 1)(n + 2)}{2} $ 個の格子点を持つ三角格子を構成する.
$ H(n) $ を,三角格子点の中から 6 点選んで作ることのできる正六角形の総数とする.
例えば,$H(3) = 1, \ H(6) = 12, \ H(20) = 966.$
$ \displaystyle \sum_{n = 3}^{12345} H(n) $ を求めよ.
例によって Difficulty rate の一番低い問題 (20%) をとってきて解いてみた.
考察がそこそこ重く実装は 2 秒というイメージ.
- n = 3 ~ 5 の場合
- 一辺 1 の正六角形が $ \displaystyle \frac{(n-2)(n-1)}{2} $ 個
- n = 6 の場合
- 一辺 1 の正六角形が $ \displaystyle \frac{(n-2)(n-1)}{2} = 10 $ 個
- 一辺 2 の正六角形が 1 個
- 一辺 √3 の正六角形が 1 個 (これに最初気付かなかった)
- n = 7, 8 の場合
- n = 6 の場合の六角形が増えるだけ
以上から,n = 3k (k = 1, 2, ...) の場合に新しい三角形が追加され,n = 3k + 1, n = 3k + 2 の場合は既存の (n = 3k の場合の) 三角形の数が増えるだけ,と予想できる.
- n = 9 の場合
- さらに 3 種類増える
- 正六角形の分類
正六角形の中心を原点とした,x 軸と y 軸が 60° の角をなす斜交座標系において,0 ≦ θ < 60° の範囲に存在する (唯一つの) 正六角形の頂点の座標が (x, y) であるとき,その正六角形を Hex(x, y) と命名する (下図参照) .
これで見通しがぐっと良くなる.
n = 9 の場合の正六角形の種類を列挙すると以下のようになる.
- H(n) を求める
以上の考察から H(n) の式を求める.
サイズ n の三角格子に存在する Hex(x, y) の個数 H(n, x, y) は,三角数 T(n) = n(n + 1)/2 を用いれば,
H(n, x, y) = T(n - 3(x + y)m + 1)
によって求められる.
m = floor(n / 3) とおく.
k = 1, ..., m に対して,Hex(x, y) (x + y = k) は k 種類存在するので,
$ \displaystyle H(n) = \sum_{k = 1}^{m} k \ T(n - 3km + 1) $
が求める答え.
typedef long long lint inline lint triangle(lint n) { return n * (n + 1) / 2; } lint hexagons(lint n) { lint ret = 0; for (lint k = 1; k * 3 <= n; k++) ret += k * triangle(n - 3 * k + 1); return ret; } int main() { clock_t start, end; start = clock(); lint ans = 0; for (lint n = 3; n <= 12345; n++) ans += hexagons(n); cout << ans << endl; end = clock(); printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC); return 0; }
0.42 sec くらい.