結果

問題 No.3114 0→1
コンテスト
ユーザー moti
提出日時 2025-04-20 02:06:15
言語 C++17(clang)
(clang++ 23.1.3 + boost 1.92.0 + ACL)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 838 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
最終ジャッジ日時 2026-10-16 03:26:48
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); i++)
constexpr int INF = 1e9;

int dp[200001][2][2];

int main() {
  int N;
  string T;
  cin >> N >> T;

  int ans = INF;
  for (int q = 0; q < 2; q++) {
    string S = T;
    if (q > 1) reverse(S.begin(), S.end());
    rep(i, 200001) rep(j, 2) rep(k, 2) dp[i][j][k] = INF;
    if (S[0] == '0') {
      dp[0][1][0] = 0;
      dp[0][1][1] = 1;
    } else {
      dp[0][1][1] = 0;
    }
    rep(i, N-1) {
      dp[i+1][0][1] = dp[i][1][0] + (S[i+1] == '0');
      if (S[i+1] == '0') dp[i+1][1][0] = dp[i][1][1];
      dp[i+1][1][1] = min(dp[i][0][1] + (S[i+1] == '0'), dp[i][1][1] + (S[i+1] == '0'));
    }
    ans = min(ans, min(min(dp[N-1][0][1], dp[N-1][1][0]), dp[N-1][1][1]));
  }
  cout << ans << endl;
}
0