部活14

部活です。

前回の欠陥について。

正解は、「かぶりを考えていない」です。

例として233点の場合を挙げます。

233点になるパターンは、以下の2パターンあります。

Sa = { 15^1 + 14^4 + 13^9 + 12^4 + 11^1 }

Sb = { 15^1 + 14^4 + 13^8 + 12^6 }

Saから導ける232点の組は、以下の3パターンです。

15, 14, 13がすべて使い切られているため、15, 14は減らせません。

Sa1 = { 15^1 + 14^4 + 13^8 + 12^5 + 11^1 }

Sa2 = { 15^1 + 14^4 + 13^9 + 12^3 + 11^2 }

Sa3 = { 15^1 + 14^4 + 13^9 + 12^4 + 10^1 }

一方Sbから導ける232点の組は、以下の3パターンです。

Sb1 = { 15^1 + 14^3 + 13^9 + 12^6 }

Sb2 = { 15^1 + 14^4 + 13^7 + 12^7 }

Sb3 = { 15^1 + 14^4 + 13^8 + 12^5 + 11^1 }

ここで、Sa1とSb3は同じ組になっていますが、前回のように単純に実装してしまうと既に実施した計算を再度行ってしまうことになります。

せっかく計算量を減らしているのに、これではもったいないので、同じものがあるかを確認する必要があります。

今日はここまで。