WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM581 Div1 Easy & Div2 Medium "SurveillanceSystem"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12588

細長い倉庫がある。この倉庫は0~N-1の番号が振られたN個のセクターに分かれている。各セクターはコンテナを置けるようになっている。現在、いくつかのセクターはコンテナが置かれておらず、いくつかのセクターはコンテナでいっぱいになっている。また、倉庫は下記で説明するような監視システムを持っている。

我々はこの倉庫に対し強盗を決行する。この作戦の前に、我々は既に倉庫に関する情報を得ている。特に、どのセクターにコンテナが積まれているか正確な情報を得ている。あなたはN個の文字で構成されるString containersを与えられる。各iでi番目のセクターにコンテナが積まれていれば、i番目の文字は'X'であり、空であれば'-'となっている。

我々は監視システムの情報も発見している。このシステムはいくつかの隠しカメラで成り立っている。あなたはこのカメラが何個の連続したセクターを監視しているかという意味のint Lが与えられる。2つカメラが監視しているセクターは、交差する事がありえるが、まったく同じセクターを監視していることはありえない。(いうならば、個々のセクターは複数のカメラによって監視されている可能性があるが、個々のカメラが監視しているセクターのセットは、互いに異なるものとなる)

最後に、我々はカメラが現在どのあたりを見ているかについての情報を得ている。あなたはint[] reportsが与えられる、reportsの各要素は1つのカメラに対応しており(特に順序は無い)。具体的には、reports[i]は対応するカメラが現在監視しているコンテナの数を表す。

これらの情報は確かなものであり、ありえないような情報が混じることはない。

あなたの仕事は上記の情報から各セクターがカメラによって監視されているか否かを推測する事である、N文字の文字列を返して欲しい。各iについて、i番目の文字は'+'、'?'そして'-'で構成させたものである。'+'の文字は、i番目のセクターは必ず1つ以上のカメラで監視されている事を示す。'-'の文字は、i番目のセクターを監視しているカメラが無い事を示す。'?'の文字はi番目のセクターが監視されている可能性とされていない可能性、どちらもあることを示す。

制約

1 <= N <= 50



考えた事

え・・むずい・・・
必ず監視されてるってどうやって判定させるんだろ・・・

あ、あるセクターは監視されていない!と仮定したときに、全てのカメラを配置する事ができるかどうかで判定できるな。

f:id:Ekaing:20130616131213j:plain



ソースコード

class SurveillanceSystem {
public:
    string getContainerInfo(string containers, vector <int> reports, int L){
        int n = containers.length();
        int m = reports.size();

        string ans( n, '-' );

        int num[55] = { 0 };
        for( int i = 0; i <= n - L; i++ ){
            for( int j = 0; j < L; j++ ){
                if( containers[i+j] == 'X' ) num[i]++;
            }
        }

        // ?か判定
        for( int i = 0; i <= n - L; i++ ){
            bool find = false;
            for( int j = 0; j < m; j++ ){
                if( num[i] == reports[j] ) find = true;
            }
            if( find ){
                for( int j = 0; j < L; j++ ){
                    ans[i+j] = '?';
                }
            }
        }

        // +か判定
        for( int b = 0; b < n; b++ ){
            int no_l = b - L + 1;
            int no_r = b;
            bool use[55] = { false };
            for( int i = 0; i <= n - L; i++ ){
                if( no_l <= i && i <= no_r ) continue;
                for( int j = 0; j < m; j++ ){
                    if( !use[j] && reports[j] == num[i] ){
                        use[j] = true;
                        break;
                    }
                }
            }
            for( int i = 0; i < m; i++ ){
                if( !use[i] ) ans[b] = '+';
            }
        }    

        return ans;
    }
};