ABC409のC問題 Equilateral Triangle

ABC409のC問題 Equilateral Triangleにチャレンジした。一周以上回った場所の指定されることがあるので円周で割った余り\(\mod{L}\)を点の位置として使い、辺の長さが\(\frac{L}{3}\)となっている点を探すことで正解できた。

問題 Equilateral Triangle

C - Equilateral Triangle

• 円周\(L\) (正L角形と考えられる)の円上に点が\(N\)個配置されている。
• 点の位置は、前の点からの距離\(d\)で与えられる。
• 円周上の点が正三角形になる組み合わせの数を答える。

方法

正三角形ができるのは、円周の長さ\(L\)が3の倍数のときに限定されれる。例えば正方形では、どう頑張っても頂点を結んで正三角形を作ることは出来ない。これは正五角形も同じ。そこで、\(L\)が3の倍数では無いときには、答えは\(0\)に決まります。

点の位置は、円周を一回り以上するすることがあります。そこで、円周で割った余り\(\mod{L}\)を点の位置として使うことで、一周以上する問題を解決できます。

正三角形ができるかは、点の間隔が\(\frac{L}{3}\)になっている場合です。そのため最初の点の位置を\(P_0\)とすると、他の２点は、\(P_0 + \frac{L}{3}\)と\(P_0 + 2 \times \frac{L}{3}\)に位置するはずです。

正三角形の数は、点の組み合わせなので、正三角形の条件を満たす各点の数を全て掛ければ求められます。

技術的工夫

• 円周で割った余り\(\mod{L}\)を点の位置として使うため、複数の点が同じ場所に来ることがあります。そこでDict型で点の数を管理しますが、keyが存在しない時の煩雑さを避けるため、defaultdictを使用します。
• 正三角形の頂点の１つは、必ず\(0, \cdots , \frac{L}{3}\)のいずれかを使用します。そこで、これらの点を起点として正三角形の条件を満たす点があるかを探します。

from collections import defaultdict

n, l = map(int, input().split())
d = list(map(int, input().split()))

points = defaultdict(lambda: 0)
points[0] = 1

# 余りを考える時は、0スタートが吉。
prev = 0
for x in d:
    y = (prev + x) % l
    points[y] += 1
    prev += x

# should 3の倍数
if (l % 3) != 0:
    print(0)
    exit()

total = 0
delta = l // 3
for i in range(0, delta):
    if (i in points) and ((i + delta) in points) and ((i + 2*delta) in points):
        # print(points[i], points[i + delta], points[i + 2*delta])
        total += points[i] * points[i + delta] * points[i + 2*delta]
print(total)