Official

B - Split? Editorial by KoD


解説では主に C++ のコードを用いて説明しますが、最後に Python での実装例も掲載しています。


\(S\) の一文字目が 1 なら答えは No です。以下では \(S\) の一文字目が 0 の場合を考えます。

まず、全ての列について、その列に立っているピンが存在するかどうか求めます。C++ での実装は以下のようになります。

string s;
cin >> s;

array<bool, 7> column = {};
column[0] = (s[6] == '1');
column[1] = (s[3] == '1');
column[2] = (s[1] == '1') or (s[7] == '1');
column[3] = (s[0] == '1') or (s[4] == '1');
column[4] = (s[2] == '1') or (s[8] == '1');
column[5] = (s[5] == '1');
column[6] = (s[9] == '1');

問題文ではピンの番号は 1-indexed ですが、コードでは 0-indexed になっているので混乱してしまう人がいるかもしれません。その場合は、次のようにするとミスを防ぐことができます。

string s;
cin >> s;
s = '$' + s // s の先頭に適当な一文字を追加する

array<bool, 7> column = {};
column[0] = (s[7] == '1');
column[1] = (s[4] == '1');
column[2] = (s[2] == '1') or (s[8] == '1');
column[3] = (s[1] == '1') or (s[5] == '1');
column[4] = (s[3] == '1') or (s[9] == '1');
column[5] = (s[6] == '1');
column[6] = (s[10] == '1');

その後、問題文の条件を満たすような二つの列を全探索します。
これは二重 for-loop を用いて書くことができます。

for (int i = 0; i < 7; ++i) {
    for (int j = 0; j < i; ++j) {
        if (column[i] and column[j]) {
            // それぞれの列に立っているピンが存在するなら、
            // その間にピンが全て倒れている列があるかどうか調べる
        }
    }
}

二つの列の間にピンが全て倒れている列があるかどうか調べるには、三つ目の for 文を if ブロックの中に追加します。

for (int k = j + 1; k < i; ++k) {
    if (!column[k]) {
        cout << "Yes\n";
        return 0;
    }
}

C++ において return 0; という文は main() 関数での処理を終了し 0 を返すという意味を持ちます。これにより、条件を満たす二つの列が一組見つかった段階で Yes を出力し実行を終了することができます。これがなければ、Yes が複数回出力される可能性があります。

最後に、条件を満たす二つの列が見つからなかった場合に No を出力するコードを追加します。全てをまとめると次のようなコードになります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    s = '$' + s;
    if (s[1] == '1') {
        cout << "No\n";
    } else {
        array<bool, 7> column = {};
        column[0] = (s[7] == '1');
        column[1] = (s[4] == '1');
        column[2] = (s[2] == '1') or (s[8] == '1');
        column[3] = (s[1] == '1') or (s[5] == '1');
        column[4] = (s[3] == '1') or (s[9] == '1');
        column[5] = (s[6] == '1');
        column[6] = (s[10] == '1');
        for (int i = 0; i < 7; ++i) {
            for (int j = 0; j < i; ++j) {
                if (column[i] and column[j]) {
                    for (int k = j + 1; k < i; ++k) {
                        if (!column[k]) {
                            cout << "Yes\n";
                            return 0;
                        }
                    }
                }
            }
        }
        cout << "No\n";
    }
    return 0;
}

実装例 (Python) :

def search(column):
  for i in range(7):
    for j in range(i):
      if column[i] and column[j] :
        for k in range(j + 1, i):
          if not column[k]:
            return 'Yes'
  return 'No'

s = input()
s = '$' + s

if s[1] == '1':
  print('No')
else:
  column = [False] * 7
  column[0] = (s[7] == '1');
  column[1] = (s[4] == '1');
  column[2] = (s[2] == '1') or (s[8] == '1');
  column[3] = (s[1] == '1') or (s[5] == '1');
  column[4] = (s[3] == '1') or (s[9] == '1');
  column[5] = (s[6] == '1');
  column[6] = (s[10] == '1');
  print(search(column))

posted:
last update: