Pythonで色付きの頂点正多角形から二等辺三角形の数を数えるプログラム

サイズnのバイナリ文字列として表されるn個の辺を持つ1つの正多角形があるとします。頂点は、青（0）または赤（1）のいずれかで色付けできます。時計回りに色付けされています。頂点が正多角形の頂点であり、色が同じである二等辺三角形の数を数える必要があります。

したがって、入力がpolygon ="111010"のような場合、出力は2になります。

ACEとAFEの2つの三角形があります。

これを解決するには、次の手順に従います-

• 関数all（）を定義します。これにはnがかかります
• n mod 2が1と同じ場合、no：=n *（n-1）/ 2
• それ以外の場合、いいえ：=n *（n / 2-1）
• n mod 3が0と同じ場合、no：=no --n / 3 * 2
• 返品しない
• 関数non（）を定義します。これにはa、nが必要です
• n mod 2が1と同じ場合、
  • s0：=0、s1：=0
  • i：=0
  • i
  • a[i]が'0'と同じ場合、s0：=s0 + 1
  • それ以外の場合、s1：=s1 + 1
  • i：=i + 1
• s：=s0 * s1 * 6
• n mod 3が0と同じ場合、
  • n1：=n / 3
  • n2：=n1 * 2
  • i：=0
  • i
  • a[i]がa[（i + n1）mod n]と同じでない場合、
    • s：=s-2
  • a[i]がa[（i + n2）mod n]と同じでない場合、
    • s：=s-2
  • i：=i + 1

例

理解を深めるために、次の実装を見てみましょう-

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))

入力

1, 1000

出力

2