Official

B - Electric Board Editorial by E869120

この問題は A 問題より難しく、コンテスタントの半分以上が苦戦しています。しかし実装量は非常に軽く、適切な考察ステップを踏めばたったの 400 バイト程度で解くことができるのです。そこで本解説では、

  • B 問題「Electric Board」の解説
  • どのような考察ステップで解法に至るか
  • サンプルコード

の 3 つに分けて紹介します。


1-1. この問題の解法

まず、文字列 \(S\) と \(T\) に存在する 0 の個数が違う場合、目的を達成することが不可能であるため、答えは \(-1\) です。

そうでない場合の答えは次の通りになります。

文字列 \(S\) の \(a_1, a_2, \cdots, a_K\) \((a_1 < a_2 < \cdots < a_K)\) 文字目が 0 であるとする。
文字列 \(T\) の \(b_1, b_2, \cdots, b_K\) \((b_1 < b_2 < \cdots < b_K)\) 文字目が 0 であるとする。
そのとき、\(a_i \neq b_i\) となっているような \(i\) \((1 \leq i \leq K)\) の個数が答えである。

時間計算量は \(O(N)\) です。


1-2. 具体例

一応、解法の理解のために、2 つの具体例を載せておきます。

具体例1 　\(S = \)111100、\(T = \)111000 の場合

\(S\) に含まれる 0 の個数は \(2\) 個である。
\(T\) に含まれる 0 の個数は \(3\) 個である。
個数が違うため、答えは \(-1\) である。

具体例2　\(S = \)0110110、\(T = \)0010111 の場合

\(S, T\) に含まれる 0 の個数はいずれも \(3\) 個であり、同じである。
次に、\(S\) における 0 の位置を左から並べると \((a_1, a_2, a_3) = (1, 4, 7)\) である。
また、\(T\) における 0 の位置を左から並べると、\((b_1, b_2, b_3) = (1, 2, 4)\) である。
そして、\(a_i \neq b_i\) であるものは \(i = 2, 3\) の \(2\) 個なので、答えは \(2\) である。


2. どうやって解法を思いつくか？

この章では、正解に至るまでの考察ステップについて記します。


2-1. ステップ 1｜少ない方である「0」に着目する

まず、この問題で行える操作は、端的に書くと次のようになります。

パターンA　連続する部分文字列のうち 011111…111111 であるものを 111111…111110 に変える
パターンB　連続する部分文字列のうち111111…111110 であるものを 011111…111111 に変える

どちらのパターンでも、操作する部分文字列の長さ \(r-l+1\) が大きい場合、部分文字列内の大部分が 1 であり、0 は僅か \(1\) 個しかありません。

そこで、競技プログラミングでは「数が少ない方を考えると考察が進む場合がある」という典型テクニックがあります。

では、数が少ない 0 の位置に着目して考えてみましょう。


＜参考＞ステップ 1 の補足・類題

例えば、

など、余事象を考える問題は、このテクニックの一種です。


2-2. ステップ 2｜問題を言い換える

次に、文字列 \(S\) の \(a_1, a_2, \cdots, a_K\) \((a_1 < a_2 < \cdots < a_K)\) 文字目が 0 であるとすると、文字列に対する \(1\) 回の操作は次のように言い換えられます。

パターンA　整数 \(i\) \((1 \leq i \leq K)\) を選び、\(a_i\) の値を \(x\) \((a_{i} < x < a_{i+1})\) に変更する。
パターンB　整数 \(i\) \((1 \leq i \leq K)\) を選び、\(a_i\) の値を \(x\) \((a_{i-1} < x < a_i)\) に変更する。
※ここでは便宜上 \(a_0 = 0, a_{K+1} = N+1\) とする。

そこで、文字列 \(T\) の \(b_1, b_2, \cdots, b_K\) \((b_1 < b_2 < \cdots < b_K)\) 文字目が 0 であるとすると、

最小何回の操作で \((a_1, a_2, \cdots, a_K)\) を \((b_1, b_2, \cdots, b_K)\) に一致させることができますか？

という問題に言い換えられます。


2-3. ステップ 3｜自明な下界を考える

問題の言い換えによって、確かに考えるべき問題は単純になりましたが、それでも最小の操作回数を求めることは難しいです。

そんなときは、操作回数の下界を考える、つまり

  • 「絶対に〇〇回未満の答えにはならない」といったことを考えてみる

という典型テクニックを導入してみましょう。（詳しくはこちらの記事をお読みいただければと思います）

今回の問題の場合、自明なものとして、次のような下界が考えられます。

下界　\(a_i \neq b_i\) となっている \(i\) \((1 \leq i \leq K)\) の個数
理由　\(1\) 回の操作では、数列 \((a_1, a_2, \cdots, a_K)\) の要素のうち \(1\) つしか変更できないため。


＜参考＞ステップ 3 の補足・類題

このような「上界・下界を考えるテクニック」は、例えば

などでも使えます。


2-4. ステップ 4｜下界を実現する方法を考える

最後に、操作回数の自明な下界が答えになるかどうかを考えてみましょう。

下界を実現させるためには、毎回の操作で次のことが行われている必要があります。（逆に、これができれば操作回数が自明な下界になります）

\(1\) 回の操作で、\(a_i \neq b_i\) となっている \(i\) \((1 \leq i \leq K)\) の個数が \(1\) つ減る。
つまり、\(1\) 回の操作で、元々 \(a_i \neq b_i\) であったものを \(a_i = b_i\) にする。

これはいくつかのパターンを手で試しながら考えてみると、実現可能であることが分かります。実際、

\(a_i > b_i\) となる \(i\) が存在する場合
\(a_i > b_i\) となる最小の \(i\) を \(p\) とするとき、\(a_p\) の値を \(b_p\) に変更する

全て \(a_i \leq b_i\) である場合
\(a_i < b_i\) となる最大の \(i\) を \(q\) とするとき、\(a_q\) の値を \(b_q\) に変更する

という操作を行うことができます。


＜参考＞ステップ 4 の補足・具体例

例えば、\((a_1, a_2, a_3, a_4) = (1, 5, 6, 9), (b_1, b_2, b_3, b_4) = (1, 4, 7, 8)\) の場合、\(a_i > b_i\) となる最小の \(i\) は \(i = 4\) です。
したがって、下図の通り \(a_4\) の値を \(b_4 = 8\) に変更することができます。
そのとき、「\(a_i \neq b_i\) となる \(i\) の個数」は \(3\) 個から \(2\) 個に減ります。

また、\((a_1, a_2, a_3, a_4) = (1, 5, 6, 8), (b_1, b_2, b_3, b_4) = (1, 4, 7, 8)\) の場合、\(a_i > b_i\) となる \(i\) は存在せず、\(a_i < b_i\) となる最大の \(i\) は \(i = 3\) です。
したがって、下図の通り \(a_3\) の値を \(b_3 = 7\) に変更することができます。
そのとき、「\(a_i \neq b_i\) となる \(i\) の個数」は \(2\) 個から \(1\) 個に減ります。


2-5. まとめ

このように、競技プログラミングの問題を解くにあたって、

  • 数が少ない方を考える（余事象など）
  • 操作回数の自明な下界を見積もったうえで、それを実現される方法を考える

などが大切です。


3. サンプルコード

まず、C++ での解答例は次のようになります。（リンク）
std::vector の仕様についてはこちらをお読みください。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int N;
string S, T;

int main() {
	// Step #1. 入力
	cin >> N;
	cin >> S;
	cin >> T;

	// Step #2. a[i], b[i] を求める
	vector<int> a, b;
	for (int i = 0; i < N; i++) {
		if (S[i] == '0') a.push_back(i);
		if (T[i] == '0') b.push_back(i);
	}

	// Step #3. 場合分け
	if ((int)a.size() != (int)b.size()) {
		cout << "-1" << endl;
		return 0;
	}

	// Step #4. 答えを計算し、出力する
	int Answer = 0;
	for (int i = 0; i < (int)a.size(); i++) {
		if (a[i] != b[i]) Answer += 1;
	}
	cout << Answer << endl;
	return 0;
}

他のプログラミング言語でのサンプルコードは、次の通りです。

posted:
last update: