Pythonを使用して循環トラックで最も訪問されたセクターを見つけるプログラム

数nとroundsという配列があるとします。 1からnまでのラベルが付いたn個の異なるセクターで構成される円形のトラックがあります。ここで、このトラックでレースが開催されることを考えてみましょう。レースはm個の異なるラウンドで構成されています。 i番目のラウンドはセクターラウンド[i-1]で始まり、セクターラウンド[i]で終わります。たとえば、ラウンド1がセクターラウンド[0]で始まり、セクターラウンド[1]で終わる場合です。したがって、最も訪問されたセクターを昇順でソートする必要があります。 （トラック番号は、反時計回りにセクター番号の昇順です）

したがって、入力がn =4ラウンド=[1,3,1,2]の場合、出力は[1、2]

レースはセクター1から始まるためです。訪問したセクターの順序は次のとおりです：[1,2,3（第1ラウンドの終了）、4,1（第2ラウンドの終了）、2（第3ラウンドの終了）]。ここでは、セクター1と2の両方が2回訪問され、最も訪問されたセクターです。そして、セクター3と4は一度だけ訪問されます。

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

• d：=新しいマップ

• 1からnの範囲のjについては、次のようにします

  • d [j]：=0

• d [rounds [0]]：=1

• 範囲1からラウンドのサイズまでのiの場合-1、実行

  • rounds [i]> rounds [i-1]の場合、

    • 範囲ラウンド[i-1]+1からラウンド[i]+1のjの場合、実行

      • d [j]：=d [j] + 1

  • それ以外の場合

    • 範囲ラウンド[i-1]+1からnのjの場合、実行

      • d [j]：=d [j] + 1

    • 範囲1からラウンド[i]のjの場合、実行

      • d [j]：=d [j] + 1

• curr：=d [rounds [0]]

• out：=[rounds [0]]

• 1からnの範囲のiの場合、実行します

  • iがrounds[0]と同じでない場合、

    • d [i]> currの場合、

      • curr：=d [i]

      • out：=[i]

    • それ以外の場合、d [i]がcurrと同じである場合、

      • なしでiを追加

• 並べ替え後に戻る

例（Python）

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

def solve(n, rounds):
   d = {}
   for j in range(1,n+1):
      d[j] = 0
   d[rounds[0]] = 1
   for i in range(1, len(rounds)):
      if rounds[i] > rounds[i-1]:
         for j in range(rounds[i-1]+1, rounds[i]+1):
            d[j] += 1
      else:
         for j in range(rounds[i-1]+1,n+1):
            d[j] += 1
         for j in range(1,rounds[i]+1):
            d[j] += 1

   curr = d[rounds[0]]
   out = [rounds[0]]
   for i in range(1,n+1):
      if i != rounds[0]:
         if d[i] > curr:
            curr = d[i]
            out = [i]
         elif d[i] == curr:
            out = out + [i]
   return(sorted(out))

n = 4
rounds = [1,3,1,2]
print(solve(n, rounds))

入力

4, [1,3,1,2]

出力

[1, 2]