文字列集合 [Kyoto University Programming Contest 2020 Spring M]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/M

解説

根性構築。 N=1,2のときはサンプルにあるやつを答えればいい。 3≦Nのときは、00, 010, 0110, 01110, ...と構築していけばN-1個を達成できる。 なぜN-1が上限（最適解）であることが言えるかというと、N個を達成するには長さ1の文字列を作る必要がある。 長さ1の文字列を作ってしまうと、その文字は今後使えなくなる。 なので、2番目の文字列はある1つの文字列となり、複数個作ると必ず部分列となってしまうためである。

どうやって思いつくかであるが、構築問題はシンプルな構築方法を模索するのがポリシーである。 正直これくらいしか言うことがない。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<string> ans;
    if (N == 1) ans.push_back("0");
    else if (N == 2) ans.push_back("0"), ans.push_back("11");
    else {
        rep(i, 0, N - 1) {
            string ones = "";
            rep(j, 0, i) ones += "1";
            ans.push_back("0" + ones + "0");
        }
    }

    int n = ans.size();
    printf("%d\n", n);
    fore(s, ans) printf("%s\n", s.c_str());
}