みんなのプロコン 予選 C - 検索

問題概要

N個の文字列が与えられる．

ソースコード

#include<iostream>
#include<string>
#include<vector>
#include<set>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
 
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int n, k;
    cin >> n >> k;
    if(n == k){
        cout  << endl;
        return 0;
    }
    set<int> ok;
    vector<string> s(n);
    rep(k){
        int tmp;
        cin >> tmp;
        ok.insert(tmp-1);
    }
    rep(n) cin >> s[i];
    string keyword = s[*(ok.begin())];
    int key_length = (int)keyword.length();

    for(int i: ok){
        int common_length = 0;
        while(common_length < min(key_length, (int)s[i].length())){
            if(keyword[common_length] == s[i][common_length]){
                common_length++;
            }else{
                break;
            }
        }
        keyword = keyword.substr(0, common_length);
        key_length = (int)keyword.length();
    }

    vector<int> ng_length;
    rep(n){
        if(ok.find(i) != ok.end()) continue;
        int common_length = 0;
        while(common_length < min(key_length, (int)s[i].length())){
            if(keyword[common_length] == s[i][common_length]){
                common_length++;
            }else{
                break;
            }
        }
        ng_length.push_back(common_length);
    }
    
    int ans_length = *max_element(all(ng_length)) + 1;
    if(ans_length <= key_length)
        cout << keyword.substr(0, ans_length) << endl;
    else
        cout << -1 << endl;

    return 0;
}

所感

今年度も開催が決定したYahoo!主催のプロコンの，去年の予選の問題． 解けたあとに振り返ってみれば決して難しい問題ではないし，解法もかなりストレートなものだが14WAも出してしまった． 本選のAも解けていないし，私はみんプロの問題が苦手なのかもしれない(?)