ABC 401 D - Logical Filling
まず、
oの隣の?は.で確定できるSにK個の
oがすでにある場合は、すべての?は.で確定できるSの
oの個数がK-1個以下の場合Sが奇数長で
?からなる、例えば???であり、K=(N+1)/2であるならo.oというふうに確定できるSが偶数長で
?からなる、例えば????のときは、Kをどのように取っても、oの位置を確定できないただし、K=0の場合は先ほどの考察から
....に確定できる
この考察を、
?を部分文字列として持つSに適用すると「奇数長の
?のみからなる部分文字列」ではoが(N+1)/2回出現し、かつ、「偶数長の
?のみからなる部分文字列」ではoがN/2回出現し、かつ、?中のoと元からあるoの個数の合計がKに一致するならば「奇数長の
?のみからなる部分文字列」におけるoと.の位置を確定できる「偶数長の
?のみからなる部分文字列」はoを消費するだけで、?の確定はできない
void answer() {
llong N, K;
std::string S;
read(N, K, S);
for (llong i = 0; i < N; i++) {
if (S[i] == '?') {
if (i - 1 >= 0 && S[i - 1] == 'o' || i + 1 < N && S[i + 1] == 'o') {
S[i] = '.';
}
}
}
llong oCount = 0;
for (llong i = 0; i < N; i++) {
oCount += S[i] == 'o';
}
if (oCount == K) {
for (llong i = 0; i < N; i++) {
if (S[i] == '?') {
S[i] = '.';
}
}
}
std::string SCopy = S;
llong begin = -1;
for (llong i = 0; i <= N; i++) {
if (i < N && S[i] == '?') {
if (begin == -1) {
begin = i;
}
} else if (begin != -1) {
if ((i - begin) % 2 == 0) {
K -= (i - begin) / 2;
} else {
for (llong j = begin; j < i; j++) {
S[j] = (j - begin) % 2 == 0 ? 'o' : '.';
}
K -= (i - begin + 1) / 2;
}
begin = -1;
}
K -= i < N && S[i] == 'o';
}
writeln(K == 0 ? S : SCopy);
}