🍣

ARC 110 | B - Many 110

1 min read

問題

https://atcoder.jp/contests/arc110/tasks/arc110_b

考えたこと

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

T1のときは1101が2つあり、それが{10^{10}}個あるので答えは2 \times 10^{10}である。
T0のときは1100が1つあり、それが{10^{10}}個あるので答えは10^{10}である。

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

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

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

例えばT1101とすると、以下のように先頭の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で、T1のときを考慮できていなくてWAしてしまいました。

参考

https://atcoder.jp/contests/arc110/editorial/383

Discussion

ログインするとコメントできます