Codeforces #46 (div2) D "Game"
問題:http://codeforces.com/contest/49/problem/D
参加形式:本番.
ある一列のタイルがそれぞれ黒か白で塗られている.これをストライプ状に黒と白が交互に塗られているように塗り替える.塗り替える方法は同じ色で隣接した2つのタイルを選択して好きなように塗り替えられる.塗り替える作業が最小となる回数を求める.
最悪ケースはどんなのだろうかと考えてたら編集距離回数しか塗り替える必要が無いことに気づいたので,ストライプ状になる二つのパターンのうち編集距離が小さい方を求めた.
import java.util.*; public class D_Game { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int r1 = 0, r2 = 0; char[] a = s.next().toCharArray(); for(int i = 0; i < n;++i){ if(a[i]-'0'!=i%2){ ++r1; } if(a[i]-'0'!=1-i%2){ ++r2; } } System.out.println(Math.min(r1,r2)); } }