主題

ZeroJudge - e562: 11401 - Triangle Counting　解題心得（2019 / 12 / 14 更新）

Not In My Back Yard | 2019-12-13 23:52:43 | 巴幣 0 | 人氣 403

題目連結：

題目大意：

給定一正整數 n （3 ≦ n ≦ 1000000，當 n ＜ 0 時代表輸入結束），有各自長度 1 ～ n 的木棍（也就是有 n 根木棍）。

試問用這 n 根木棍可以組出多少個不同的三角形？

範例輸入：

範例輸出：

解題思維：

這題目雖然可以用動態規劃（DP，Dynamic Programming）解出。設 Dn 是 n 根棍子的方法數，則 Dn+1 ＝ Dn ＋ H × (n － 2 － H) ，其中 H ＝ floor((n － 2) ÷ 2) 。

因為可以看到用長度為 n 的棍子當作三角形最長邊時：

若以長度 n － 1 作為第二長邊，則最短邊只能挑長度 2 以上，共有 n － 3 種。

若以長度 n － 2 作為第二長邊，則最短邊只能挑長度 3 以上，共有 n － 5 種。

若以長度 n － 3 作為第二長邊，則最短邊只能挑長度 4 以上，共有 n － 7 種。

……

以此類推。所以用第 n 根作為最長邊的方法數為 n － 3 ＋ n － 5 ＋……，化簡後即是 H × (n － 2 － H) 那部分的由來。

但是也可以用一個數學式子解出。~~（推導過程忘記了，待補）~~

根據 H × (n － 2 － H) 那條式子，我們可以將該式子重寫為：

以下用較不正規的數學歸納法證明：

當 n ＝ 2 、 3 、 4 、 5 時，命題成立。

設當 n ＝ k 、 k ＋ 1 、 k ＋ 2 、 k ＋ 3 時命題也成立，則

當 n ＝ k ＋ 4 時，等式左邊：

等式右邊：

因此，等式左邊＝等式右邊，等式依然成立。同理，n ＝ k ＋ 5 、 k ＋ 6 、 k ＋ 7 時，等式也依然成立。

所以根據數學歸納法，命題成立。

因此，我們的所求為

其中 ERROR 為誤差項（會多加，因此要減掉）。因此，我們觀察 i ^ 2 ：

當 i 為 4 的倍數＋ 1，即 i ≡ 1 （mod 4），則 i ^ 2 ≡ 1；

當 i 為 4 的倍數＋ 2，即 i ≡ 2 （mod 4），則 i ^ 2 ≡ 0；

當 i 為 4 的倍數＋ 3，即 i ≡ 3 （mod 4），則 i ^ 2 ≡ 1；

當 i 為 4 的倍數，即 i ≡ 0 （mod 4），則 i ^ 2 ≡ 0；

所以，我們只需關注 i ≡ 1 和 i ≡ 3 ，因為這兩種情形會導致誤差（i ^ 2 不被 4 整除）。

而這兩種情形在 1 ～ n － 2 會發生幾次呢？答案是 floor( (n － 1) ÷ 2 ) 。於是，所求可寫為一個可在 O(1) 時間求出的數學式：

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

ETH官方钱包