zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC124-C「Coloring Colorfully」です。
ポイント
全探索を行う問題です。というのも，タイルの数は大きくても$10^5$であり，考えられる場合は「0101...」と「1010...」の2通りですので，全探索を行なっても計算量は高々$O(2\cdot10^5)=O(10^5)$だからです。
おさえるべき内容
全探索の行い方
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
string S;
int main(){
cin >> S;
int ans = 100010;
// 「0101...」の場合を考える
int cnt = 0;
rep(i, S.size()){
if (i % 2 == 0){
if (S[i] == '0') cnt ++;
}
if (i % 2 == 1){
if (S[i] == '1') cnt ++;
}
}
ans = min(ans, cnt);
// 「1010...」の場合を考える
cnt = 0;
rep(i, S.size()){
if (i % 2 == 1){
if (S[i] == '0') cnt ++;
}
if (i % 2 == 0){
if (S[i] == '1') cnt ++;
}
}
// 解は「1010...」と「0101...」の両方に対して行なった全探索のうち小さい方
ans = min(ans, cnt);
cout << ans << endl;
}
コメント