#1171135 (C++17) No.3587 Too Good to Swap

• 問題: No.3587 Too Good to Swap
• ユーザー: GOTKAKO
• 提出日時: 2026-07-11 12:00:36
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 8 ms / 2,000 ms
• コード長: 4,277 bytes
• コンパイル時間: 1,626 ms
• コンパイル使用メモリ: 234,528 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-11 12:00:47
• 合計ジャッジ時間: 3,890 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 49

ソースコード

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

bool solve(string s,string t){
    set<string> S;
    queue<string> Q; Q.push(s),S.insert(s);
    int N = s.size();
    bool ret = false;
    while(Q.size()){
        auto now = Q.front(); Q.pop();
        bool ng = false;
        for(int i=0; i<=N-4; i++) if(now.substr(i,4) == "good"){ng = true; break;}
        if(ng) continue;
        if(now == t) ret = true;
        for(int i=0; i<N-1; i++) if(now.at(i) != now.at(i+1)){
            swap(now.at(i),now.at(i+1));
            if(!S.count(now)) S.insert(now),Q.push(now);
            swap(now.at(i),now.at(i+1));
        }
    }
    //for(auto s : S) cout << s << "\n";
    return ret;
}

random_device rnd;
mt19937 mt(rnd());

void make(string &s,int N){
    s.resize(N,'a');
    while(true){
        for(auto &c : s){
            int kind = mt()%3;
            if(kind == 0) c = 'd';
            else if(kind == 1) c = 'g';
            else c = 'o';
        }
        bool ng = false;
        for(int i=0; i<=N-4; i++) if(s.substr(i,4) == "good"){ng = true; break;}
        if(ng) continue;
        break;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    bool submit = true;
    if(T > 100000) submit = false;
    while(T--){
        string s,t;
        if(!submit){
            make(s,8),t = s;
            while(true){
                shuffle(t.begin(),t.end(),mt);
                bool good = false;
                for(int i=0; i<=t.size()-4; i++) if(t.substr(i,4) == "good"){good = true; break;}
                if(good) continue;
                break;
            }
        }
        if(submit) cin >> s >> t;

        string memos = s,memot = t;
        auto no = [&]() -> void {
            cout << "No\n";
            if(!submit && solve(memos,memot)){
                cout << "Wrong No" << endl;
                cout << 1 << endl << memos << endl << memot << endl;
                exit(0);
            }
        };
        auto yes = [&]() -> void {
            cout << "Yes\n";
            if(!submit && !solve(memos,memot)){
                cout << "Wrong Yes" << endl;
                cout << 1 << endl << memos << endl << memot << endl;
                exit(0);
            }
        };

        int N = s.size();
        vector<int> Cs(26),Ct(26);
        for(auto c : s) Cs.at(c-'a')++;
        for(auto c : t) Ct.at(c-'a')++;
        if(Cs != Ct){no(); continue;}
        if(Cs.at('g'-'a') == 0 || Cs.at('d'-'a') == 0 || Cs.at('o'-'a') <= 1){yes(); continue;}

        int gs = 0,ds = 0,os = 0,del = 0;
        bool ng = false,end = false;
        for(int i=0; i<N; i++){
            if(s.at(i) == 'g') gs++;
            else if(s.at(i) == 'd'){
                if(i < 3 || s.at(i-2) != 'o' || s.at(i-1) != 'o') break;
                bool apg = false;
                for(int k=i+1; k<N; k++) if(s.at(k) == 'g') apg = true;
                if(apg) break;
                vector<int> Gs,Ds;
                for(int k=0; k<N; k++) if(t.at(k) == 'g') Gs.push_back(k);
                for(int k=0; k<N; k++) if(t.at(k) == 'd') Ds.push_back(k);
                
                if(Gs.size() && Ds.size()){
                    int p1 = Gs.back(),p2 = Ds.at(0);
                    if(p1+3 >= p2) ng = true; 
                }
                
                if(ng) no();
                else yes();
                end = true;
                break;

            }
        }
        if(end) continue;
        if(ng){no(); continue;}
        t.erase(t.begin(),t.begin()+del);
        gs = 0,ds = 0,N = t.size();
        for(auto c : t) gs += c=='g',ds += c=='d';
        if(gs == 0){
            for(int i=0; i<3; i++){
                if(i == N) break;
                if(t.at(i) == 'd') ng = true;
            }
            if(ng) no();
            else yes();
            continue;
        }
        bool ok = false;
        for(int i=0; i<N; i++){
            char c = t.at(i);
            if(c == 'd'){
                for(int k=i+1; k<N; k++) if(t.at(k) == 'g') ok = true;
                if(i && t.at(i-1) == 'g') ok = true; 
                if(i > 1 && t.at(i-2) == 'g') ok = true;
                break;

            }
        }
        if(ok) yes();
        else no();
        continue;
    }
}