【AtCoder】ABC 393 B - A..B..C | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 44

問題概要
制約
考察
実装例
コメント

問題概要

文字列 $S$ が与えられるので、 $S$ の中にA, B, Cがこの順に等間隔に並んでいる場所が何箇所あるか求めよ。

厳密には、3つの整数の組 $(i,j,k)$ であって、以下の条件をすべて満たすものの個数を求めよ。

$1\leq i \lt j \lt k\leq |S|$
$j-i = k-j$
$S_i=$ A
$S_j=$ B
$S_k=$ C

制約

$S$ は英大文字からなる長さ $3$ 以上 $100$ 以下の文字列

考察

問題文の前半だけだとどう実装しようか悩むかもしれないが、この問題の本質は「厳密には...」より後ろに書かれている。

つまり、挙げられている5つの条件を全て満たす整数組 $(i, j, k)$ を全探索によって求めればよいのだ。

本問は $|S|$ の制約が小さいので、 $i, j, k$ について3重forループを回すという $O(|S|^3)$ の解でも十分 AC できる。

だが、せっかくなので公式解説の「Bonus」の解法(計算量 $O(|S|^2)$ )についても考えてみよう。

条件の2つ目の式を整理すると、 $2j - i = k$ と書ける。

したがって、 $i, j$ を決めた時点で $k$ も勝手に定まる。これで $k$ についてループを回す必要がなくなった。

ただし、 $k$ が条件の第1式を満たしているかのチェックは必要なので注意しよう。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    string S;
    cin >> S;

    int l = S.size();
    int ans = 0;
    rep(i, 0, l) rep(j, i + 1, l)
    {
        int k = 2 * j - i;
        if (k >= l)
            continue;

        if (S[i] == 'A' && S[j] == 'B' && S[k] == 'C')
            ans++;
    }

    cout << ans << endl;

    return 0;
}