🍣

ARC 110 | B - Many 110

2020/12/06に公開

競プロ

tech

問題

考えたこと

$N$ が1のときを考えます。

$T$ が1のときは110に1が2つあり、それが ${10^{10}}$ 個あるので答えは $2 \times 10^{10}$ である。
$T$ が0のときは110に0が1つあり、それが ${10^{10}}$ 個あるので答えは $10^{10}$ である。

$N$ が2以上のときを考える。

まずそもそも文字列が部分文字列となるか確認する。ならない場合は0を出力する。

部分文字列の場合は何回含まれるか確認する。
$S$ が大きすぎると理解しにくいので110が4個連携した $S$ を簡単のため考える。

例えば $T$ を1101とすると、以下のように先頭の110の1文字目にがっちする。最小文字列が110なので110の中で1文字目と2文字目に合致するといった複数の文字に合致することはない。

次に1101が何個あるか考える。以下のように文字列が110の2つの連結部分にわたっているので $N - 2 + 1$ で3個の部分文字列がある。

このように考えればいくつ部分文字列が含まれているか求められる。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  string t;
  cin >> n >> t;
  string b = "110";
  if (n == 1) {
    if (t[0] == '1') {
      cout << 20000000000 << endl;
    } else {
      cout << 10000000000 << endl;
    }
    return 0;
  }

  // そもそも合致するか確かめる
  ll diff = -1;
  for (int i = 0; i < 3; i++) {  // 開始位置
    bool ng = false;
    for (int j = 0; j < n; j++) {
      if (t[j] != b[(i + j) % 3]) {
        ng = true;
        break;
      }
    }
    if (!ng) {
      diff = i;
      break;
    }
  }
  if (diff == -1) {  // 合致しない
    cout << 0 << endl;
    return 0;
  }
  ll l = ceil((ld)(diff + n) / 3);  // 必要なブロック数
  cout << 10000000000 - l + 1 << endl;
}

コンテスト中

$N = 1$ で、 $T$ が1のときを考慮できていなくてWAしてしまいました。

ARC 110 | B - Many 110

問題

考えたこと

コード

コンテスト中

参考

Discussion