WARush

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

SRM582 Div2 Hard "ColorTheCells"

問題

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

N個のマスが一列に並んでいる。左から右へとマスには0~N-1と番号が振られている。魔法少女であるレイナはマジカルパワーを使って全てのマスにマジカル色で色を塗りたい。レイナはタイム0の時、マス0にいる。彼女は以下の3つのアクションをとる事ができる。

1. 彼女は好きな時間だけ、今いるマスで待機する事ができる。
2. 彼女は隣りのマスに移動する事ができる。時間は1かかる。
3. 彼女は隣りのマスに色を塗る事ができる。時間は1かかる。
  (彼女は今立っているマスに色を塗る事ができず、
  隣りのマスのみそれができることに注意せよ)

さらに1つ、次のような制限がある。レイナは乾ききっていない塗りたてのマスに移動する事はできない。あなたはN個の要素を持つint[] dryingTimeを与えられる。dryingTime[i]はi番目のマスが、レイナが色を塗ってから乾くまでの時間を表す。レイナは乾ききっていないマスへと移動を始める事はできない。

例えば、レイナが今マス3にいて、dryingTime[2]=7と仮定する。時間12の時にレイナはセル2を塗り始めたとしよう。時間12 + 1 = 13の時、塗り終わる。時間13 + 7 = 20の時、その塗ったマスが乾く。そして、レイナがマス2に再び移動できる時間は最も早くて21である。(時間20の時、マス2に移動を始め、移動には時間1かかるため)

レイナはなるべく早くNマス全てを塗りたい。彼女は好きな順番でマスを塗る事ができる。全てのマスを塗り終わる、最も早い時間を返せ。

制約

2 <= N <= 7
1 <= dryingTime[i] <= 10^5


考えた事

N <= 7か・・・BitDPかな?
dp[塗ったマス(Bit)][今いるマス]みたいな。

・・・

できね

塗るマスの順番は7!通り。端っこ以外のマスは左に立って塗るか右に立って塗るか選べるため、それが2^5通り。7回ずつ計算するから計算量は7! * 2^5 * 7= 約120万。

これや

ソースコード

class ColorTheCells {
public:

    int n;
    vector<int> dtime;
    int oktime[7];
    int cell[7];
    int flg;

    int solve(){
        for( int i = 0; i < n; i++ ) oktime[i] = 0;
        int res = 0;
        int pos = 0;
        for( int i = 0; i < n; i++ ){
            // 移動マス取得
            int target = cell[i]; // 次塗るマス
            int npos = -1;        // 次行くマス
            if( target == 0 ){
                npos = 1;
            }else if( target == n - 1 ){
                npos = n - 2;
            }else{
                int mask = 1 << (target - 1);
                if( flg & mask ){
                    npos = target - 1;
                }else{
                    npos = target + 1;
                }
            }

            // 移動
            while( pos != npos ){
                if( pos < npos ){
                    res = max( res + 1, oktime[pos+1] + 1 );
                    pos++;
                }else{
                    res = max( res + 1, oktime[pos-1] + 1 );
                    pos--;
                }
            }

            // 塗る
            res++;
            oktime[target] = res + dtime[target];
        }
        return res;
    }

    int minimalTime(vector <int> dryingTime){
        n = dryingTime.size();
        dtime = dryingTime;
        for( int i = 0; i < n; i++ ){
            cell[i] = i;
        }
        int ans = 100000000;

        // 塗るマスの順番と、左右どっちに立つかを全部試す
        do{
            for( flg = 0; flg < 1 << (n - 2); flg++ ){
                ans = min( ans, solve() );
            }
        }while( next_permutation( cell, cell + n ) );

        return ans;
    }
};