予選B-C 「擬二等辺三角形」
問題文はこちら。
部分点解法（O(L)）
次の条件を満たす正整数 a,b,c の組が何通りあるかを数えます。
- a \lt b \lt c …(1)
- a+b+c \leq L …(2)
- a+b \gt c …(3)
- a+1=b または b+1=c …(4)
- a+1=b
- (1),(2),(3)より、各 a について c のとりうる値の範囲は a+2 \leq c < {\rm min}(2a+1,L-2a) です。
- a+1 \lt b かつ b+1=c
- 1.と同様に、(1),(2),(3)より、各 b について a のとりうる値の範囲は 2 \leq a < {\rm min}(b-1,L-2b) です。
これらを足し合わせれば、周長が L 以下となる擬二等辺三角形の個数が求まります。
満点解法（O(1)）
まず、部分点解法における、a と c それぞれがとりうる値の範囲にふくまれる \rm min を除去します。
2a+1 \leq L-2a より a \leq (L-1)/4, a+2 \leq L-2a より a \leq (L-2)/3 なので、 s = {\rm floor}((L-1)/4), t = {\rm floor}((L-2)/3) として、 Σ_{a=1..s} (2a+1)-(a+2) と Σ_{a=(s+1)..t} (L-2a)-(a+2) を解きます。
b-1 \leq L-2b より b \leq (L+1)/3, 2 \leq L-2b より b \leq (L-2)/2 なので、 u = {\rm floor}((L+1)/3), v = {\rm floor}((L-2)/2) として、 Σ_{b=3..u} (b-1)-2 と Σ_{b=(u+1)..v} (L-2b)-2 を解きます。
まとめると、答えは
(s-1)s/2 + (t-s)(2L-3s-3t-7)/2 + (u-2)(u-3)/2 + (v-u)(L-u-v-3) となります。 ただし、s, t, u, v の大小関係には注意する必要があります。