👻
【競技プログラミング】AtCoder Beginner Contest 136_D問題

2024/12/31に公開
 問題https://atcoder.jp/contests/abc136/tasks/abc136_d

 要約変数
S: マスの情報を表す文字列（'L'と'R'で構成）
N: 文字列Sの長さ（マスの数）
i: マスの位置を示す変数（左から1, 2, 3, ...）
問題
N個のマスが左右一列に並んでいる
各マスにはSの対応する文字（'L'または'R'）が書かれている
左端のマスには必ず'R'、右端のマスには必ず'L'が書かれている
初めに、各マスには1人の子どもがいる
移動ルール
子どもたちは10^100回、以下の規則に従って移動する
今いるマスに'L'が書かれていれば左隣のマスに移動
今いるマスに'R'が書かれていれば右隣のマスに移動
求めるもの
10^100回の移動後、各マスにいる子どもの人数

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

 アプローチ子どもたちが最終的に落ち着く場所を直接求める。

'R'と'L'が隣接する箇所に集まる。

各子どもの最終位置は、開始位置から最も近いRL境界までの距離と、その境界の性質（端かどうか）によって決定される

 解法手順入力文字列Sを読み込む。
RL境界の位置を特定する:
'R'の位置のリストRを作成
'L'の位置のリストLを作成
各マスについて、そこにいる子どもの最終位置を決定:
'R'のマスの場合:

a. 最も近い右側のRL境界を見つける

b. 距離が偶数か、境界が右端の場合、境界上に移動

c. それ以外の場合、境界の1つ右に移動
'L'のマスの場合:

a. 最も近い左側のRL境界を見つける

b. 距離が偶数か、境界が左端の場合、境界上に移動

c. それ以外の場合、境界の1つ左に移動
各マスの最終的な子どもの数をカウントする。
結果を出力する。

 ACコードac.py
import bisect

def io_func():
    # 入力文字列Sを読み込む
    return input()

def solve(S):
    # 'R'の位置のリストRを作成
    R = []
    # 'L'の位置のリストLを作成
    L = []

    # RL境界の位置を特定する
    for i in range(len(S)):
        if i == len(S) - 1:
            if S[i] == "R":
                R.append(i)
        elif S[i] == "R" and S[i+1] == "L":
            R.append(i)
        if i == 0:
            if S[i] == "L":
                L.append(i)
        elif S[i] == "L" and S[i-1] == "R":
            L.append(i)

    # 各マスの最終的な子どもの数を格納するリスト
    ans = [0] * len(S)

    # 各マスについて、そこにいる子どもの最終位置を決定
    for j in range(len(S)):
        if S[j] == "R":
            # 最も近い右側のRL境界を見つける
            now = bisect.bisect_left(R, j)
            if (R[now] - j) % 2 == 0 or R[now] == len(S) - 1:
                # 距離が偶数か、境界が右端の場合、境界上に移動
                ans[R[now]] += 1
            else:
                # それ以外の場合、境界の1つ右に移動
                ans[R[now] + 1] += 1
        if S[j] == "L":
            # 最も近い左側のRL境界を見つける
            next = bisect.bisect_right(L, j) - 1
            if (L[next] - j) % 2 == 0 or L[next] == 0:
                # 距離が偶数か、境界が左端の場合、境界上に移動
                ans[L[next]] += 1
            else:
                # それ以外の場合、境界の1つ左に移動
                ans[L[next] - 1] += 1

    # 結果を出力する
    print(*ans)

if __name__=="__main__":
    # メイン処理
    S = io_func()
    solve(S)

###
# S: 入力文字列
# R: 'R'の位置のリスト
# L: 'L'の位置のリスト
# ans: 各マスの最終的な子どもの数を格納するリスト
# i: RL境界を探索するためのインデックス
# j: 各マスを探索するためのインデックス
# now: 'R'の子どもに対して、最も近い右側のRL境界のインデックス
# next: 'L'の子どもに対して、最も近い左側のRL境界のインデックス

# 1. io_func関数: 標準入力から文字列Sを読み込む
# 2. solve関数: 主な処理を行う
#    2.1. RL境界の位置を特定し、RとLのリストを作成
#    2.2. 各マスについて、そこにいる子どもの最終位置を決定
#         - 'R'の子どもの場合: 最も近い右側のRL境界までの距離に基づいて移動
#         - 'L'の子どもの場合: 最も近い左側のRL境界までの距離に基づいて移動
#    2.3. 各マスの最終的な子どもの数をカウント
#    2.4. 結果を出力
# 3. メイン処理: io_func関数でSを読み込み、solve関数を呼び出す

 めも10^100回移動を繰り返すのは、最終的にどこにいるかを求めたいから。（ただし、偶奇で若干変わる）
問題

要約

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

アプローチ

解法手順

ACコード

めも

Discussion
