問題
https://codeforces.com/contest/1352/problem/F
問題概要
'0'と'1'で構成された文字列を考える。その文字列の隣接した2文字を数値として足して和が0, 1, 2になる区間の合計数がそれぞれ与えられる。
例えば文字列1110011110の場合、11, 11, 10, 00, 01, 11, 11, 11, 10に分けることができて、0となる区間は1つ、1となる区間は3つ、2となる区間は5つであり、この3つの数が与えられる。
与えられた条件を満たす文字列を復元せよ。ただし復元できることは保証される。
考察
場合分けをしてみます。簡単な方から考えてみましょう。
0となる場合のみがある場合
0を並べるだけです。与えられた数+1の0を並べると条件を満たせます。
1となる場合のみがある場合
0と1を交互に並べるだけです。これも文字列の長さが与えられた数+1になるように並べればよいです。
2となる場合のみがある場合
1を並べるだけです。与えられた数+1の1を並べます。
すべてが0でない場合
最初のサンプルの`(1, 3, 5)'で考えてみましょう。
0となる場合が1なので、1 + 1 = 2つの1を並べて00とします。
また、2となる場合が5なので、同様に1を並べて111111とします。
これを繋げてみます。0の場合と2の場合はすべて消費した状態で00111111となります。
ここで、連結部分が'01'であるため1の場合が一つ消費されて残りは2つです。あとはその2つを消費できるように末尾に0と1を交互に並べます。
0011111101となります。これで完成です。すべて0ではない場合は、与えられた数字がなんであれこの考え方で復元することができます。
0となる場合のみが0の場合
`(0, 3, 5)'で先ほどと同じように考えてみます。
0はないので最初の手順は不要です。次に2となる場合が5なので111111とできます。
最後に1となる場合ですが、先程と違ってまだ0と1の連結がないので、末尾には3つの1ができるよう交互に連結します。
111111010となり、これで完成です。
1となる場合のみが0の場合
このケースはありえません。0を作るためには2つの0が、2と作るためには2つの1が必要で、これを繋げるとどうしても01または10の区間ができてしまうためです。
2となる場合のみが0の場合
`(5, 3, 0)'で考えてみます。
0となる場合が5なので000000とします。2となる場合はないので作成不要です。最後に、1を作るために交互に並べます。
000000101です。実装上は、このケースでは末尾が0の状態で最後の手順になるので、そこで1から交互に並べないといけないことに気をつけます。
すべてが0の場合
このケースは制約がn0 + n1 + n2 > 0なのでありえません。
とここまでをコードにすると完成です。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n0, n1, n2; cin >> n0 >> n1 >> n2; string ans = ""; if (n0 > 0) ans += string(n0 + 1, '0'); if (n2 > 0) ans += string(n2 + 1, '1'); if (n1 > 0) { if (n0 > 0 and n2 > 0) { for (int i = 0; i < n1 - 1; i++) ans += (i % 2 == 0 ? '0' : '1'); } else if (n0 > 0) { for (int i = 0; i < n1; i++) ans += (i % 2 == 0 ? '1' : '0'); } else if (n2 > 0) { for (int i = 0; i < n1; i++) ans += (i % 2 == 0 ? '0' : '1'); } else { for (int i = 0; i < n1 + 1; i++) ans += (i % 2 == 0 ? '0' : '1'); } } cout << ans << endl; } }
