絶滅

どうでもいい

Project Euler - Problem 577

Counting hexagons

Problem 577

$n$ を 3 以上の整数とする.
下図のように,一辺の長さ $n$ の正三角形は $n^2$ 個の一辺の長さ 1 の正三角形に分割される.
これらの正三角形の頂点集合は, $ \displaystyle \frac{(n + 1)(n + 2)}{2} $ 個の格子点を持つ三角格子を構成する.
$ H(n) $ を,三角格子点の中から 6 点選んで作ることのできる正六角形の総数とする.

f:id:my316g:20171231013642p:plain

例えば,$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} $ 個

f:id:my316g:20171231044044p:plain




  • n = 6 の場合
    • 一辺 1 の正六角形が $ \displaystyle \frac{(n-2)(n-1)}{2} = 10 $ 個
    • 一辺 2 の正六角形が 1 個
    • 一辺 √3 の正六角形が 1 個 (これに最初気付かなかった)

f:id:my316g:20171231044159p:plain




  • n = 7, 8 の場合
    • n = 6 の場合の六角形が増えるだけ

f:id:my316g:20171231044806p:plain


f:id:my316g:20171231044940p:plain

以上から,n = 3k (k = 1, 2, ...) の場合に新しい三角形が追加され,n = 3k + 1, n = 3k + 2 の場合は既存の (n = 3k の場合の) 三角形の数が増えるだけ,と予想できる.




  • n = 9 の場合
    • さらに 3 種類増える

f:id:my316g:20171231050515p:plain




  • 正六角形の分類

正六角形の中心を原点とした,x 軸と y 軸が 60° の角をなす斜交座標系において,0 ≦ θ < 60° の範囲に存在する (唯一つの) 正六角形の頂点の座標が (x, y) であるとき,その正六角形を Hex(x, y) と命名する (下図参照) .

f:id:my316g:20171231055934p:plain

これで見通しがぐっと良くなる.

n = 9 の場合の正六角形の種類を列挙すると以下のようになる.

f:id:my316g:20171231053201p:plain




  • 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 くらい.