似非プログラマーの雑多な日記

似非プログラマーの雑多な日記

「継続は力なり」の実証実験してます

【競プロ(AtCoder)】第二回全国統一プログラミング王決定戦本戦:B - NIKKEI String《C++ ver.》

f:id:captaindream0502:20210810000601p:plain
C++_logo

第二回全国統一プログラミング王決定戦本戦:B - NIKKEI StringをC++で解いたときの解答。

1. 問題

問題文
高橋君は英小文字からなる文字列Sを持っています。
高橋君はSをNIKKEI型に分割する方法が何通りあるか気になっています。Sを6つの空でない連続する文字列に分割する方法であって、次の条件を満たすものの個数を求めてください。
  • Sを分割してできた文字列を前から順にS1,S2,S3,S4,S5,S6としたとき、S2とS6が等しく、かつS3とS4が等しい。
制約
6 ≦ |S| ≦ 500
Sは英小文字から成る

2. 解答

#include <iostream>
using namespace std;

int main(){
    string S;
    cin >> S;
    int output = 0;

    for(int i = 1; i <= S.length(); i++){
        for(int j = 1; 2*j <= S.length()-i; j++){
            for(int k = 1; 2*k+1 <= S.length()-i-2*j; k++){
                int l = S.length()-i-2*j-2*k;
                string S2 = S.substr(i, j);
                string S3 = S.substr(i+j, k);
                string S4 = S.substr(i+j+k, k);
                string S6 = S.substr(i+j+2*k+l, j);
                if(S2 == S6 && S3 == S4) output++;    
            }
        }
    }
    cout << output << endl;
}

3. 所感

一瞬簡単に思えたけど普通に難しい。全探索すると当然のごとくTLE (時間切れ)になる。
解説は気が向いたら...

以上