AOJ 0033 - Ball

問題文 : Ball

例 : smapleInputの一つ目のデータセットの図

問題概要 :

開口部Aから落とす玉の並びが与えられる。
すべてのボールは自由に筒Bか筒Cに落とすか選ぶことが出来る。
筒B,筒Cは玉が10個入るだけの十分な大きさを持っている。
筒B,筒Cの両方ともで番号の小さいの上に大きい玉を並べられる場合は YESを,並べられない場合は NOを出力する。
(玉の数は10個 それぞれに1～10までの番号がついている)

解法 :

とりあえず全探索してみる。全通りやっても2^10程度。
それぞれのボールはBに入るかCに入るかの二通りの選択肢がある。
その中でBに入るものを考える。
10ビットの2進数を考え各ビットが各ボールに対応するものとする。
そうすると筒Bについての全探索ができる。
CについてはBで考えたのと同様にする。
Bの時に考えた10ビットの2進数を反転した(補数をとった)のがCの各ボールに対応する2進数となる。
よって全てのケースについて判定できる。

#include<iostream>
#include<vector> 

using namespace std;
 
 
int data[10];
 
bool searchB (int a){
    vector<int >sea;
 
    for(int i=0;i<10;i++){
        if(a>>i & 1)sea.push_back(data[i]);
    }
    if(sea.size()>1){
    for(int i=0;i<sea.size()-1;i++){
        if(sea[i]>sea[i+1])return false;
    }
    }
    return true;
}
 
int main(){
 
    int n=0;
    cin>>n;
 
    for(int i=0;i<n;i++){
         
 
    for(int j=0;j<10;j++){
        cin>>data[j];
    }
    bool suc=false;
    for(int i=0;i<1024;i++){
        if(searchB(i) && searchB(~i)){
            cout<<"YES"<<endl;
            suc=true;
            break;
        }
    }
    if(!suc)cout<<"NO"<<endl;
    }
    return 0;
}

反省 :

解法を初めて書いたのでとても分かりにくいものになってしまいました。
最初は再帰関数を使おうとしたもののまともな知識もないままやったのでグダグダでした。

他の解法(再帰とか)がわかる方はぜひぜひコメントして頂ければ嬉しいです。