新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:ABC #083

[学習記録] ABC #083

久々にリアルタイムで参加。
C問題まで解けたが相変わらずD問題解けず。。

プログラムはこちら。
atcoder/atcoder-prg/src/abc083 at master · ueriku/atcoder · GitHub

コンテストURL

abc083.contest.atcoder.jp

A〜C問題は簡単だったので省略。

D問題

問題

0と1からなる文字列Sが与えられたとき、以下の操作を繰り返す。

  • 長さK以上の連続する区間[l, r]を選ぶ。
  • l <= i <= rになる全ての整数iに対し、Siの0と1を反転させる。

操作を好きな回数繰り返すことでSの要素をすべて0にできるような最大の整数Kを出力せよ。

解答

k文字目とk+1文字目が異なるとき、1〜k文字目かk+1〜n文字目までを反転させれば、隣り合う文字が異なる箇所を一つ減らすことができる。
これをSがすべて0になるまで繰り返せば良いが、常にkかn-kの大きい方を反転させるようにすることで、
一番最初のkかn-kの大きい方の数字=Kを減らさずに操作を行うことができる。
よって、最初の文字列Sに対して、kとk+1文字目が異なるような最小のMath.max(k, n-k)を求めれば良い。

char[] s = in.next().toCharArray();
char before = s[0];
int ans = 999999;

for (int i = 1; i < s.length; i++) {
    if (before != s[i]) {
        before = s[i];
        ans = Math.min(ans, Math.max(i, s.length - i));
    }
}

// 全部1だった場合の処理
if (ans == 999999) {
    ans = s.length;
}

out.println(ans);