https://codeforces.com/contest/1055
A
ちょっと場合分けがあって面倒ですね。
B
幅1の区間しかたさないので、両脇見ればいいだけです。
C
GCD
D
良問。違う部分は共通じゃないと行けなくて(なぜかここにきづけなかった)、伸ばすだけ伸ばしてマッチしてほしいところより前でマッチすることを防ぐ。KMPの使い方を忘れていたのもあるのでコード張ります。
int N; string A, B; string pre, post; string S1[MAX_N], S2[MAX_N]; vector<int> KMP(string S) { int n = (int)S.size(); S += '_'; vector<int> A(n + 1); A[0] = -1; int j = -1; rep(i, 0, n) { while (j >= 0 && S[i] != S[j]) j = A[j]; j++; if(S[i + 1] == S[j]) A[i + 1] = A[j]; else A[i + 1] = j; } return A; } void no() { cout << "NO\n"; exit(0); } void solve() { cin >> N; rep(i, 0, N) cin >> S1[i]; rep(i, 0, N) cin >> S2[i]; rep(q, 0, N) { string s1 = S1[q], s2 = S2[q]; int l = sz(s1), r = -1; rep(i, 0, sz(s1)) { if(s1[i] != s2[i]) { MIN(l, i); MAX(r, i); } } if(l != sz(s1)) { if(A.empty()) { A = s1.substr(l, r - l + 1); B = s2.substr(l, r - l + 1); string tmp = s1.substr(0, l); reverse(all(tmp)); pre = tmp; tmp = s1.substr(r + 1); post = tmp; } else { if(A != s1.substr(l, r - l + 1)) no(); if(B != s2.substr(l, r - l + 1)) no(); int at = 0; while(l - 1 - at >= 0 && at < sz(pre) && s1[l - 1 - at] == pre[at]) at++; pre.resize(at); at = 0; while(r + 1 + at < sz(s1) && at < sz(post) && s2[r + 1 + at] == post[at]) at++; post.resize(at); } } } reverse(all(pre)); string ans1 = pre + A + post; string ans2 = pre + B + post; vi match = KMP(ans1); rep(i, 0, N) { int at = -1; rep(j, 0, sz(S1[i])) { at++; while(at != -1 && ans1[at] != S1[i][j]) at = match[at]; if(at == sz(ans1) - 1) { if(ans1 != S1[i].substr(j - at, sz(ans1)) || ans2 != S2[i].substr(j - at, sz(ans1))) no(); else break; } } } cout << "YES\n"; cout << ans1 << "\n" << ans2 << "\n"; }
E
よくあるにぶたんして0or1にするやつ。Dよりも簡単。