SRM 695 div2 medium BearPasswordAny

問題

問題概要

x = {4, 2, 1, 0}のとき、長さ4の文字列で、その中に、1文字の連続文字列が4つ(b, a, a, a)、2文字の連続文字列が2つ(aa, aa)、3文字の連続文字列が1つ(aaa)、4文字の連続文字列が0つである文字列を出力すればいい。文字列が作れないなら、空文字を出力すればいい。

解法

考察として、例えば、aaaという連続文字列(ex a, b, aa, bb, aaa)があるとき、3連続文字列が1つ、2連続文字列が2つ、1連続文字列が3つとなる。これは、n連続文字列があるとき、n連続文字列が1つ、n-1連続文字列が2つ... 2連続文字列がn-1個、1連続文字列がn個できることになる。よって、文字列を作る条件として必要な連続文字列のなかで、1番長いものから順に作っていけば、それより小さい連続文字列の必要な数も自動的に決まっていく。
実装は、必要ななかで長いものから順に見ていき、必要な数をxから引いていく。その操作をおこなった後に、xのすべての要素が0であればよい。また、文字列の長さもx[0]と一致していなければならない。

ミス

誤読というか読み忘れしてた。
x = {1, 0}みたいな時も、aかbを出力すればよいと思ってたけど、答えとなる文字列はN(=x.size())でなければならないことを忘れていた。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

class BearPasswordAny{
public:
    bool hantei(vector<int> &t){
        rep(i, t.size()){
            if(t[i] != 0) return false;
        }
        return true;
    }

    string findPassword(vector <int> x){

        vector<int> ans;
        int len = x[0];
        while(len > 0){
            for (int i = x.size() - 1; i >= 0; --i){
                if(x[i] > 0){
                    len -= (i + 1);
                    ans.push_back(i + 1);
                    int d = 1;
                    for (int j = i; j >= 0; --j){
                        x[j] -= d;
                        d++;
                    }
                    break;
                }
            }
        }

        string ret = "";
        //x[0]と長さが同じであるかと、すべての長さの連続列を指定された個数作れているかを確認
        if(len == 0 && hantei(x)){
            rep(i, ans.size()){
                rep(j, ans[i]){
                    if(i % 2 == 0){
                        ret += 'a';
                    }else{
                        ret += 'b';
                    }
                }
            }
        }

        //長さが　n　か見る
        //v = {1, 0}の時などに、ret = "a"となっているので、それをはじく。
        if(ret.size() == x.size()){
            return ret;
        }else{
            ret = "";
            return ret;
        }
    }
};

はじめから、x[0]の値とnが異なれば文字列ができないことがわかる

class BearPasswordAny{
public:
    bool hantei(vector<int> &t){
        rep(i, t.size()){
            if(t[i] != 0) return false;
        }
        return true;
    }

    string findPassword(vector <int> x){

        vector<int> ans;
        int len = x[0];
        //1文字の連続列はどんな文字列を作っても、文字列の長さと同じになる
        if(len != x.size()){
            return "";
        }

        while(len > 0){
            for (int i = x.size() - 1; i >= 0; --i){
                if(x[i] > 0){
                    len -= (i + 1);
                    ans.push_back(i + 1);
                    int d = 1;
                    for (int j = i; j >= 0; --j){
                        x[j] -= d;
                        d++;
                    }
                    break;
                }
            }
        }

        string ret = "";
        //x[0]と長さが同じであるかと、すべての長さの連続列を指定された個数作れているかを確認
        if(len == 0 && hantei(x)){
            rep(i, ans.size()){
                rep(j, ans[i]){
                    if(i % 2 == 0){
                        ret += 'a';
                    }else{
                        ret += 'b';
                    }
                }
            }
        }
        return ret;
    }
};