科学の箱

科学・IT・登山の話題

AtCoder

AtCoder ABC 174D Alter Altar

投稿日:2020年9月25日 更新日:

問題

左から右へN個の石が並んでいる。石の種類は白もしくは赤のいづれかである。

石について、下記の操作を何回でも実行できる。

  • 2個の石を選んで場所を入れ替える(隣合ってなくてよい)。
  • 1個の石を選んで、色を変える。

この操作を繰り返し、赤い石の左隣に白い石がないようにする。

分析

ゴール状態

まずゴールの状態 ―赤い石の隣に白い石がない― を考える。R=赤い石、W=白い石と考える。

今赤い石を任意の場所に置く。この時、赤い石の左隣には、離れていたとしても白い石はないはずである。

1:〇〇R〇〇
2:〇RR〇〇
3:RRR〇〇

次に白い石を任意の場所に置く。この時、白い石の右隣には、離れていたとしても赤い石はないはずである。

1:〇〇W〇〇
2:〇〇WW〇
3:〇〇WWW

よってゴールの状態は以下のようになる。

RR…RW…WW

入れ替え操作

次に入れ替えの動作について考える。下記のような配列について入れ替え操作を考える。

RWWRWRWWR

入れ替えは目標となる配列が決まっていなければ、操作を決定することはできない。操作を決定できなければ回数を求めることはできない。よって、目標となる配列を固定する必要がある

初期:R W W R W R W W R
目標:R R R W W W W W W

この時すでに一致している配列については無視できる。よって下記の[]になっている位置については無視する。

初期:[R] W W R [W] R [W W] R
目標:[R] R R W [W] W [W W] W

次に操作によって目標の配列を目指す。配列の入れ替えの組み合わせとしては下記が考えられる。

パターン1: W→R
パターン2: R→W
パターン3: 入れ替える

次に入れ替えの個数を以下のように考える。

A=W→Rに入れ替える個数
B=R→Wに入れ替える個数

操作を一回実行したときに入れ替え個数の変化は以下のようになる。

パターン1: A–
パターン2: B–
パターン3: A– and B–

よってまずパターン3を実行して、その後必要に応じて、パターン1もしくは2を実行する。

上記の例ではA=2; B=3としたとき、以下の操作が最も望ましい。

A=2, B=3→[パターン3 x 2]→A=0, B=1→[パターン2 x 1]→A=0, B=0

よって操作回数はmax(A, B)となることが明らかである。

すべての配列を考える

2≤N≤200000により処理はO(N)で実施する必要がある。N^2では10^10となりTLEとなることが予測される。

考え方としては、初期状態の違いを記録しておき、一つずつ石を変化し、その変化により初期状態を更新していく。

R W W R W R W W R
W W W W W W W W W
R→W=4
W→R=0

R W W R W R W W R
R W W W W W W W W
R→W=3 (4-1)
W→R=0

R W W R W R W W R
R R W W W W W W W
R→W=3
W→R=1

これにより実行回数はO(N)となる。

実装

N=int(input())
C=input()


rw=C.count('R')
wr=0
ans=rw

for i in range(N):
    if C[i]=='R':
        rw-=1
    else:
        wr+=1
    ans=min(ans,max(rw,wr))
print(ans)

 

参考になる実装

print(s[:s.count("R")].count("W"))

 

例えばRWRWWRという配列を考える。この時Rは3個あるのでRRRWWWとなればよい。

R[W]R | WW[R]

RとWに区切りを入れた場合、右側のRと左側のWを入れ替えれば、目的となる配列を取得できる。左側のWの数は配列SについてS[:Rの個数]から’W’の個数を数えればよい。

メタ情報

inarticle



メタ情報

inarticle



-AtCoder
-

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

Xより大きな素数で最小値を求める

atcoder ABC149 C Next Primeより <span class="h2"> while any(x%i<1 for i in range(2, …

no image

AtCoder ABC 139D ModSum

問題 正の整数Nが与えられる。 {1,2,3,….N}に関する順列Pについて、Σ i mod Pi (i=1 to N)の最大値を求める。 方針 少ない値について全探索によって答えを出して …

no image

UnionFindのfindについて処理を考える。

UnionFindにおけるfind()もしくはroot()はルート(グループの根)を見つける処理である。 記述方法としては2種類ある。 whileループを回す 再帰処理 それぞれについて動きを確認して …

no image

蟻本 P42 硬貨の問題

貪欲法の基本 その時点で最善の手を尽くす 尽くした結果を目的とする値に反映させる。 次善の手になるようにする。 1に戻る 硬貨の問題 A=int(input()) *C,=map(int,input( …

2020年9月
« 8月   10月 »
 123456
78910111213
14151617181920
21222324252627
282930  

side bar top



アーカイブ

カテゴリー