擬二等辺三角形（天下一プログラマーコンテスト2015予選B [C]）

概要

問題文 → ■
自分の提出 → ■
公式解説 → ■

決して難しい問題ではないのですが、「分かる」から「解ききる」までが少ししんどいです。場合によっては、しんどい数列のシグマ計算を乗り切る必要があり、公式解説でもそのような方法がとられていました。

しかしこの問題は、競技プログラミングらしい手法（主観）によって短時間で確実な実装をすることができます。

解法

とりあえず大筋として、次のような解法に至るのは難しくないでしょう。3辺を $a<b<c$ とします。

(1) $b=a+1$ となる場合を数える。
(2) $c=b+1$ となる場合を数える。
(3) $b=a+1$, $c=b+1$ となる場合を数える。

「三角不等式」「周長の上限 $L$」と、気にしなければいけない要素がいっぱいあります。例えば (1) を正確にやりきろうとすると、

・$a$ を固定すると、$c$ の範囲は $a+1<c<min(2a+1,L-2a-1)$ で与えられる。
・よって、(1) の数え上げは、$\sum _{a}max\{0,min\{2a+1,L-2a-1\}–a–2\}$。

のような格好です。$2a+1$ と $L-2a-1$ の大小関係で場合分けをしたりしながら適切に式を作る必要がありそうです。ここに、$L(\mathrm{mod}4)$ などの値も効いてくるかもしれません。$(L-2a-1)–(a+2)$ と $0$ の大小を管理するところで、$L(\mathrm{mod}3)$ の値も効いてくるかもしれません。

大体やることは分かるけれど、きちんと立式しようとすると大変

というのがこの問題です。

しかし、もろもろの場合分けが全て $L(\mathrm{mod}12)$ に依存して、計算過程に出てくるものは全て多項式になります。したがって、きちんと計算せずとも

・答を $f(L)$ とする。
・十分大きな $r$ を固定したとき、$P(n)=f(r+12n)$ は $n$ の3次多項式となる。

ことが分かります。したがって、

・十分小さな場合を全探索して答を出す
・適切な $r$ に対して、$P(0)$, $P(1)$, $P(2)$, $P(3)$ が求まっている。
・ここから $3$ 次多項式 $P(n)$ を復元することにより、十分大きな $L$ に対して $f(L)$ が求められる。

という方法で計算ができます。この方法であれば、条件が増えてきても、「全探索 → 条件を満たすものを抽出」というところの「条件」だけを管理すればよいので、実装ミス・計算ミスも起こりません。

多項式の次数に確信が持てなければ、少し高い次数の多項式と思って補間すればよいです。また、「12個おき」の部分に確信が持てない場合も、適当に数値実験をしたり、適当な倍数でとっておけばよいです。より強力な方法として、「剰余ごとには多項式」という数列は線形漸化式を持つので、Berlekamp–Masseyで殴るという方法もあると思います。

コメント

• 数学寄りの人ほど、きちんと手計算できる範囲は全部計算してしまおうと思いやすいかもしれません。このような考え方は競プロで初めて目にして、非常に感心させられました。うまく自分でも実用できてよかったです。