くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 174 D - Alter Altar

Python3で解く AtCoder Beginner Contest 174 D - Alter Altar

AtCoder 競プロ ABC-D 線形探索 状態考察

{\displaystyle n+1}個存在する状態をを目指すようにして、それぞれの状態における最小の手数を数えて、全状態の中で最小値をみつければいい。状態をどう考えるか、その時の最小の手数はどう考えればいいかというのがポイント。

概要

問題

  1. {\displaystyle W}か{\displaystyle R}と書かれた石が並んでいる。次の２つの行動が取れる。（１つで手数として+1）
    1. 石を２つ選んで位置を入れ替えられる。
    2. 石を１つ選んで色を{\displaystyle W}から{\displaystyle R}もしくは逆ができる。
  2. {\displaystyle W}の左側に{\displaystyle R}がない状態にしたい。
  3. 上記の状態を作るためにかかる最小の手数は？

解くときに考えた内容

  • 全部WにするのがいいのかRのするのがいいのか、それともRRRWWWWのようにするのがいいのかは{\displaystyle C}状況によってかわるため、取りうる状態の最小手数を考えなくてはいけない。
  • たとえば、7文字あるとして 与えられた現状（とりあえずRWRWRWRとすると）から、以下の状態の全てを最小手数で目指す。
RWRWRWR → WWWWWWW  
RWRWRWR → RWWWWWW  
RWRWRWR → RRWWWWW  
      ・・・・・・  
RWRWRWR → RRRRRRW  
RWRWRWR → RRRRRRR
  • 各状態の手数の中の最小値が条件を満たす最小値になる。
  • ここで重要なのは、それぞれの状態というのは区切り（|）があるようなイメージで、|より右はW、左はRにするように行動する。
|RWRWRWR  → WWWWWWW
R|WRWRWR  → RWWWWWW 
RW|RWRWR  → RRWWWWW 
RWR|WRWR  → RRRWWWW 
RWRW|RWR  → RRRRWWW 
RWRWR|WR  → RRRRRWW 
RWRWRW|R  → RRRRRRW 
RWRWRWR|  → RRRRRRR
  • その時にかかる最小手数は、区切りよりも左側の{\displaystyle W}の数を{\displaystyle w}、区切りよりも右側の{\displaystyle R}の数を{\displaystyle r}とすると{\displaystyle max(w, r)}になる。理由は、区切りの左側と区切りの右側の{\displaystyle w}か{\displaystyle r}の大小によって、最小手数が変わるためで、以下のように考える。
    • {\displaystyle w \leqq r}のとき、区切りの左側にある{\displaystyle W}を{\displaystyle R}と入れ替えるので{\displaystyle w}回。残りの区切りの右側にある{\displaystyle R}は{\displaystyle r-w}個であるのでそれらを全部{\displaystyle W}に変える。全部で{\displaystyle r}回になる。
    • {\displaystyle w > r}のとき、区切りの左側にある{\displaystyle W}を{\displaystyle R}と入れ替えるので{\displaystyle r}回。残りの区切りの左側にある{\displaystyle W}は{\displaystyle w-r}個であるのでそれらを全部{\displaystyle R}に変える。全部で{\displaystyle w}回になる。
  • あとはこれを実装する。
    1. {\displaystyle w}の初期値は0とする。
    2. 最初に与えられた{\displaystyle r}を数えて{\displaystyle r}の初期値とする。
    3. あとは与えられる石の並び{\displaystyle C}の一つ目から{\displaystyle W}だったら{\displaystyle w += 1}として、{\displaystyle R}だったら{\displaystyle r -= 1}とすれば、各区切りの状態の{\displaystyle w, r}となるので、最後の文字までやれば、区切りを一番最後の状態まで見たことになる。

反省点

ごちゃごちゃ、場合分けするのではなくて、目指す方向性を決めて、全部数えてから最小値を見つけるっていう流れにしなければいけなかった。
まぁむずいなぁ。。。問題を言い換えて、最小手数をともかく大きい方っていう形に変えられるかがポイントだった。

コード

n = int(input())
C = input()
r_all = C.count('R')
# CをRWRWRWRとした時に、
# どの状態にするのが最小手数かがわからないので全パターンである以下の状態における最小手数を計算する。
# ある場所を境に右側をW左側をRとするイメージ。
# |RWRWRWR→WWWWWWW
# R|WRWRWR→RWWWWWW
# RW|RWRWR→RRWWWWW
# .......
# RWRWRW|R→RRRRRRW
# RWRWRWR|→RRRRRRR
# 最小手数をリストに入れておく。パターンはn+1
move = [0] * (n+1)
# 実際の並びにおいて、|の左のW右のRの数をw, rとする
# 初期値はw=0, r=CのうちRの数
w = 0
r = r_all
# moveの初期値はすべてWを目指すので
move[0] = max(0, r_all)
# forで１文字ずつ見ていくのは区切りを一つずつずらしているイメージ
# Cの文字をみてWならwを1増やしてRならrを1減らす
# （区切りの左のWの数がwで右のRの数がrなので）
for idx, c in enumerate(C):
    if c == 'W':
        w += 1
    else:
        r -= 1 
    move[idx+1] = max(w, r)
ans = min(move)
print(ans)