問題概要

長さ $N$ の文字列 $S$ が与えられる。次の条件を満たす 3 つ組の整数 $i, j, k$ が存在するかどうかを判定せよ。

$1 \le i \lt j \lt k \le N$
$S$ の $i$ 文字目は 'I' である
$S$ の $j$ 文字目は 'O' である
$S$ の $k$ 文字目は 'I' である

制約

$1 \le N \le 100$

解法

$1 \le i \lt j \lt k \le N$ を満たすような $i, j, k$ は次のような 3 重の for 文で走査できます。

for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
        for (int k = j + 1; k <= N; ++k) {
    
        }
    }
}

ここで、変数 j の初期値を 1 ではなく i + 1 にしていることに注意しましょう。同様に、変数 k の初期値も 1 ではなく j + 1 にしています。これによって、

$i \lt j \lt k$

という関係性が表現できます。

あとは、 $S$ の $i, j, k$ 文字目がそれぞれ I, O, I であることを判定しましょう。

コード

ここでは、0-indexed で実装しました。つまり、 $i$ を 0 以上 $N$ 未満の範囲で探索することとしました。

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    bool res = false;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            for (int k = j + 1; k < N; ++k) {
                if (S[i] == 'I' && S[j] == 'O' && S[k] == 'I') {
                    res = true;
                }
            }
        }
    }
    
    if (res) cout << "Yes" << endl;
    else cout << "No" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 一次予選 2021 (第 2 回) B - ビ太郎と IOI (6Q, 難易度 2)

問題概要

制約

解法

コード