Pythonで二色に塗り分けた正多角形の頂点から同色の二等辺三角形を数えるプログラム

問題の概要

n 個の頂点を持つ正多角形を考えます。この多角形は長さ n の 2 進数文字列で表され、各頂点には時計回りの順に青(0)または赤(1)のいずれかの色が割り当てられています。ここで求めるのは、正多角形の頂点だけを頂点とし、かつ 3 つの頂点がすべて同じ色で構成されている二等辺三角形の個数です。

たとえば polygon = "111010" が入力された場合、条件を満たすのは三角形 ACE と AFE の 2 つなので、出力は 2 になります。

解法のアプローチ

この問題は「作れる二等辺三角形の総数」から「同色で構成されていない二等辺三角形の数」を差し引くという発想で、線形時間 O(n) で効率よく解くことができます。

ステップ 1:二等辺三角形の総数を求める(all 関数)

• n が奇数の場合:no = n × (n − 1) / 2
• n が偶数の場合:no = n × (n / 2 − 1)
• さらに n が 3 の倍数の場合は、正三角形が対称性により重複して数えられるため、no から n / 3 × 2 を減算します

ステップ 2:同色にならない二等辺三角形を数える(non 関数)

n が奇数の場合:

• 文字列を 1 回走査し、'0' の個数 s0 と '1' の個数 s1 を数えます
• 異なる色の組み合わせに基づく基本値を s = s0 × s1 × 6 とします
• n が 3 の倍数のときは、n/3 個隣および 2n/3 個隣の頂点と色を比較し、一致しないごとに s から 2 を引いて調整します

n が偶数の場合:

• 偶数番目のインデックスと奇数番目のインデックスに分け、それぞれについて '0' と '1' の個数(s00、s01、s10、s11)を集計します
• これらの積を係数付きで合算し(s += s00×s01×8、s10×s11×8、s00×s11×4、s10×s01×4)、基本値を構成します
• n/2 個離れた対称位置の頂点同士の色を比較し、不一致なら s から 2 を減算します
• さらに n が 3 の倍数の場合は、奇数の場合と同様に n/3・2n/3 離れた位置との比較で調整を行います

non 関数は最後に s / 2 を返します。これは、同じ三角形が対称性によって 2 回数えられるためです。

ステップ 3:答えを組み合わせる

• n を文字列 polygon の長さとします
• 答え = all(n) − non(polygon, n) / 2

Python 実装例

以下のコードで実際の動作を確認できます。

def all(n):
   if n % 2 == 1:
      no = n*(n-1)/2
   else:
      no = n*(n/2-1)
   if n % 3 == 0:
      no -= n/3*2
   return no

def non(a,n):
   if n % 2 == 1:
      s0 = s1 = 0
      i = 0
      while i < n:
         if a[i] == '0':
            s0 += 1
         else:
            s1 += 1
         i += 1
      s = s0*s1*6
      if n % 3 == 0:
         n1 = n/3
         n2 = n1*2
         i = 0
         while i < n:
            if a[i] != a[int((i+n1)%n)]:
               s -= 2
            if a[i] != a[int((i+n2)%n)]:
               s -= 2
            i += 1
   else:
      s00 = s01 = s10 = s11 = s = 0
      i = 0
      while i < n:
         if a[i] == '0':
            s00 += 1
         else:
            s01 += 1
         i += 2
      i = 1
      while i < n:
         if a[i] == '0':
            s10 += 1
         else:
            s11 += 1
         i += 2
      s += s00 * s01 * 8
      s += s10 * s11 * 8
      s += s00 * s11 * 4
      s += s10 * s01 * 4
      n1 = n/2
      i = 0
      while i < n:
         if a[i] != a[int((i + n1)%n)]:
            s -= 2
         i += 1
      if n % 3 == 0:
         n1 = n/3
         n2 = n1*2
         i = 0
         while i < n:
            if a[i] != a[int((i+n1)%n)]:
               s -= 2
            if a[i] != a[int((i+n2)%n)]:
               s -= 2
            i += 1
   return s/2

def solve(polygon):
   n = len(polygon)
   no = all(n) - non(polygon,n)/2
   return int(no)

polygon = "111010"
print(solve(polygon))

入力

polygon = "111010"

出力

2

このアルゴリズムの計算量は O(n) であり、頂点数が大きい正多角形でも高速に答えを求められます。全数を数えてから条件を満たさないものを差し引く補集合の考え方は、組合せ最適化の問題で頻出するテクニックなので、覚えておくと役立ちます。