【競プロ精進ログ】ABC120-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC120-C「Unification」です。

ポイント

だるま落としの問題です。ぷよぷよを連想させます。少し考察が必要な問題でしたが，重要なのは「キューブを取り除く順番は関係ない」という点です。なぜなら，最終的なキューブは00...0や11...1のように0だけのカタマリか1だけのカタマリになるからです。最後に同じ色のキューブしか残らないのであれば，キューブを消す順番は関係ありませんよね。

証明としては，背理法チックな方法が使えます。つまり「もし最後に2つの色のキューブが混在していたら」という場合を考えます。すると，どこかで必ず異なる色のキューブが隣り合っているので，そこでキューブを取り除くことができます。したがって，最後に2つの色のキューブが混在していることはあり得ません。

以上を踏まえると，答えは与えられたキューブの色のうち少ない色のキューブの数を2倍したものになります。

実装

#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 cnt_0, cnt_1;

int main(){
  cin >> S;
  // 0の数と1の数を数える
  rep(i, S.size()){
    if (S[i]=='0') cnt_0++;
    else cnt_1++;
  }
  // 答えを出力する
  cout << 2 * min(cnt_0, cnt_1) << endl;
}