結果

問題 No.3745 Line Seats
ユーザー Nihonielse
提出日時 2026-09-22 12:25:42
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 39 ms / 2,000 ms
+ 889µs
コード長 1,410 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 63 ms
コンパイル使用メモリ 15,232 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2026-09-23 12:30:28
合計ジャッジ時間 3,930 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点 20 % AC * 47
満点 80 % AC * 60
合計 2 * 100% = 200 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# gemini-3.5-flash-lite

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    if not data:
        return
        
    N = int(data[0])
    S = data[1]
    
    # 1-indexed で扱いやすくするために先頭にダミー文字を入れる
    S = "_" + S
    
    left_dist = [float('inf')] * (N + 1)
    right_dist = [float('inf')] * (N + 1)
    
    # 1. 左から走査
    last_person = -float('inf')
    for i in range(1, N + 1):
        if S[i] == '#':
            last_person = i
        left_dist[i] = i - last_person
        
    # 2. 右から走査
    last_person = float('inf')
    for i in range(N, 0, -1):
        if S[i] == '#':
            last_person = i
        right_dist[i] = last_person - i
        
    # 3 & 4. 各空席について最も近い人までの距離の最大値を求める
    max_min_dist = -1
    best_seat = -1
    
    for i in range(1, N + 1):
        if S[i] == '.':
            # 左右の近い方の距離
            current_min_dist = min(left_dist[i], right_dist[i])
            
            # 最大値を更新（同点の場合はより左側の席を優先するため、厳密に大きい場合のみ更新）
            if current_min_dist > max_min_dist:
                max_min_dist = current_min_dist
                best_seat = i
                
    print(best_seat)

if __name__ == '__main__':
    solve()
0