Zenn
📖

【競技プログラミング】AtCoder Beginner Contest 268_C問題

2025/01/01に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc268/tasks/abc268_c

要約

  1. N人の人が回転テーブルの周りに反時計回りに並んでいる。
  2. 各人の前には料理が置かれている。
  3. テーブルを反時計回りに1/N回転させる操作を何度でも行える。
  4. 操作後、人iは料理iが自分の左隣、自分の前、または右隣にあると喜ぶ。
  5. 喜ぶ人数の最大値を求める。
  • N: 人数と料理の数
  • i: 人の番号（0からN-1まで）
  • pi: 最初に人iの前にある料理の番号

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

各人が喜ぶ条件を満たす回転回数を特定し、その回数ごとに喜ぶ人数をカウントする。

解法手順

  1. 入力からNと料理の初期配置Pを受け取る。

  2. 各回転回数に対して喜ぶ人数をカウントするためのデフォルトディクショナリCNTを作成する。

  3. 各人iについて以下の処理を行う：
    a. 料理iが人iの前に来る回転回数を計算し、CNTに加算する。
    b. 料理iが人iの左隣に来る回転回数を計算し、CNTに加算する。
    c. 料理iが人iの右隣に来る回転回数を計算し、CNTに加算する。

  4. 回転回数の計算は、(P[i] - i) % Nを基本とし、左隣は-1、右隣は+1する。

  5. すべての人について処理が終わったら、CNTの値の最大値を出力する。

ACコード

ac.py
from collections import defaultdict

def io_func():
    # 人数Nを入力として受け取る
    N = int(input())
    # 料理の初期配置Pをリストとして受け取る
    P = list(map(int, input().split()))
    return N, P

def solve(N, P):
    # 各回転回数に対して喜ぶ人数をカウントするためのデフォルトディクショナリを作成
    CNT = defaultdict(int)

    for i in range(N):
        # 料理iが人iの前に来る回転回数を計算
        front_rotation = (P[i] - i) % N
        # 料理iが人iの左隣に来る回転回数を計算
        left_rotation = (P[i] - i - 1) % N
        # 料理iが人iの右隣に来る回転回数を計算
        right_rotation = (P[i] - i + 1) % N

        # 各回転回数に対して喜ぶ人数をカウント
        CNT[front_rotation] += 1
        CNT[left_rotation] += 1
        CNT[right_rotation] += 1

    # 最も多くの人が喜ぶ回転回数の人数を返す
    return max(CNT.values())

if __name__=="__main__":
    # メイン処理
    N, P = io_func()
    result = solve(N, P)
    print(result)

###
# N: 人数と料理の数
# P: 料理の初期配置を表すリスト
# CNT: 各回転回数に対して喜ぶ人数をカウントするデフォルトディクショナリ
# front_rotation: 料理iが人iの前に来る回転回数
# left_rotation: 料理iが人iの左隣に来る回転回数
# right_rotation: 料理iが人iの右隣に来る回転回数

# 1. io_func関数で標準入力から人数Nと料理の初期配置Pを受け取る
# 2. solve関数で主な処理を行う
#    a. defaultdictを使用して各回転回数に対する喜ぶ人数をカウントするCNTを初期化
#    b. 各人iについて、料理iが前、左隣、右隣に来る回転回数を計算
#    c. 計算した回転回数に対して、CNTのカウントを1増やす
#    d. すべての人について処理が終わったら、CNTの値の最大値を返す
# 3. メイン処理でio_func関数とsolve関数を呼び出し、結果を出力する

Discussion