Pythonで循環トラック上のレースにおける最も訪問されたセクターを見つける方法

数字 n と配列 rounds があるとします。ここで、1 から n までの番号が付けられた n 個の異なるセクターで構成される円形トラックを考えます。このトラックでレースが開催され、レースは m ラウンドで構成されています。i 番目のラウンドはセクター rounds[i - 1] から開始し、セクター rounds[i] で終了します。たとえば、第 1 ラウンドはセクター rounds[0] から始まり、rounds[1] で終わります。

私たちのタスクは、最も多く訪問されたセクターを昇順で求めることです。(トラックの番号は反時計回りの方向でセクター番号の昇順に配置されているものとします)

たとえば、入力が n = 4、rounds = [1, 3, 1, 2] の場合、出力は [1, 2] になります。

その理由は以下の通りです。レースはセクター 1 から開始され、訪問されるセクターの順序は次のようになります。

[1, 2, 3(第 1 ラウンド終了)、4, 1(第 2 ラウンド終了)、2(第 3 ラウンド終了)]

このとき、セクター 1 とセクター 2 はそれぞれ 2 回訪問されており、これらが最も訪問回数の多いセクターです。一方、セクター 3 と 4 は 1 回しか訪問されていません。

解決のためのアルゴリズム

この問題を解くために、以下の手順に従います。

• d を新しいマップ(辞書)として作成する
• j を 1 から n までループする:
  • d[j] := 0 と初期化する
• d[rounds[0]] := 1 とする(スタート地点を 1 回としてカウント)
• i を 1 から rounds のサイズ - 1 までループする:
  • rounds[i] > rounds[i-1] の場合(ラップ内で進む場合):
    • j を rounds[i-1]+1 から rounds[i]+1 までループし、d[j] を +1 ずつ加算する
  • それ以外の場合(周回をまたいで進む場合):
    • j を rounds[i-1]+1 から n までループし、d[j] を +1 ずつ加算する
    • j を 1 から rounds[i] までループし、d[j] を +1 ずつ加算する
• curr := d[rounds[0]] とする
• out := [rounds[0]] とする
• i を 1 から n までループする:
  • i が rounds[0] と異なる場合:
    • d[i] > curr の場合:
      • curr := d[i] と更新し、out := [i] とする
    • そうでなく d[i] == curr の場合は、out に i を追加する
• out をソートして返す

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]

コードのポイント

このアルゴリズムのポイントは、各ラウンド間の移動を「順方向」と「周回をまたぐケース」に分けて処理している点です。rounds[i] が rounds[i-1] より大きい場合は単純にその区間のセクターをカウントし、小さい場合はトラックの終端までと先頭から目的地までの両方をカウントすることで、円形トラックの一周を正しく表現しています。

計算量は O(n × m)(m はラウンド数)となり、n と m がそれほど大きくない場合には十分に効率的なアプローチです。