TCO14 Round2A - pes_magic’s blog

この記事を書いてる時に1Bの記事が事故死してしまった…。まぁいいか。

250. SixteenBricks

問題：1*1*h[i]の角柱を4×4のグリッドに並べた時の最大表面積を求める問題。

greedyかなぁと思ったけどsample2が倒せなかった。
安全にbitDPとか出来ないかなと思ったけど、思いつかず。
Challengeで人のコードを見たら、そりゃそうか、という感じだった。

以下は、本番後にbitDPしてみたコード。この解法好きです。

class SixteenBricks {
private:
    int bitCount(int t){
        int res = 0;
        for(int i=t;i;i&=i-1) res++;
        return res;
    }
    int additionalScore(int mask, int pos, int h){
        int res = 0;
        int x = pos/4, y = pos%4;
        if(x > 0 && (mask&(1<<(pos-4)))) res -= h;
        else                             res += h;
        if(x < 3 && (mask&(1<<(pos+4)))) res -= h;
        else                             res += h;
        if(y > 0 && (mask&(1<<(pos-1)))) res -= h;
        else                             res += h;
        if(y < 3 && (mask&(1<<(pos+1)))) res -= h;
        else                             res += h;
        return res;
    }
public:
    int maximumSurface(vector <int> height){
        static int dp[1<<16];
        memset(dp, 0, sizeof(dp));
        dp[0] = 16;
        sort(height.rbegin(), height.rend());
        for(int i=0;i<(1<<16)-1;i++){
            int idx = bitCount(i);
            for(int j=0;j<16;j++){
                if(i&(1<<j)) continue;
                dp[i|(1<<j)] = max(dp[i|(1<<j)], dp[i]+additionalScore(i, j, height[idx]));
            }
        }
        return dp[(1<<16)-1];
    }
};

500. NarrowPassage

問題：長さLの細い道で、n匹の狼が目的地に向かう。すれ違うにはx=0かx=Lの地点までいかないといけない。狼の移動距離の合計の最小値は？

x=0ですれ違うグループ、x=Lですれ違うグループの作り方を全探索すれば…と思った
それで通る問題が500で出るわけが無い…と思って手元で撃墜ケースを探す
x=0ですれ違い→x=Lですれ違いのパターンが最適な事もありそう
というわけで、2回出たり入ったりするのを全探索してみた。
sample3にやられる

なん…だと…。

バグかと思ってコードを見てたけどバグは見つからず。
計算量に余裕があったので、3回出たり入ったりしてみた。
sample3が倒せてしまった。
良く分からんけど250が解けてなかったので投げた。
通ったのはsample3のおかげと言わざるを得ません。

以下は本番で書いたコード。酷いコピペ実装だったし、よく通ったなと思う。

class NarrowPassage {
public:
    int minDist(int L, vector <int> a, vector <int> b) {
        int n = a.size();
        vector< pair<int,int> > vp;
        vector< pair<int,int> > p1(n), p2(n), p3(n);
        for(int i=0;i<n;i++) vp.push_back(make_pair(a[i],b[i]));
        sort(vp.begin(), vp.end());
        int res = 1000000007;
        for(int i=0;i<=n;i++){
            for(int k=0;k<n;k++) p1[k] = vp[k];
            int tmp1 = 0;
            for(int k=0;k<i;k++){
                tmp1 += p1[k].first;
                p1[k].first = 0;
            }
            sort(p1.begin(), p1.end());
            for(int j=0;j<=n;j++){
                int tmp2 = tmp1;
                for(int k=0;k<n;k++) p2[k] = p1[k];
                for(int k=0;k<j;k++){
                    tmp2 += L - p2[n-1-k].first;
                    p2[n-1-k].first = L;
                }
                sort(p2.begin(), p2.end());
                for(int l=0;l<=n;l++){
                    for(int k=0;k<n;k++) p3[k] = p2[k];
                    int tmp3 = tmp2;
                    for(int k=0;k<l;k++){
                        tmp3 += p3[k].first;
                        p3[k].first = 0;
                    }
                    sort(p3.begin(), p3.end());
                    bool ok = true;
                    for(int k=0;k+1<n;k++){
                        if(p3[k].second > p3[k+1].second) ok = false;
                    }
                    if(!ok) continue;
                    for(int k=0;k<n;k++){
                        tmp3 += abs(p3[k].first - p3[k].second);
                    }
                    res = min(tmp3, res);
                }
            }
        }
        for(int i=0;i<=n;i++){
            for(int k=0;k<n;k++) p1[k] = vp[k];
            int tmp1 = 0;
            for(int k=0;k<i;k++){
                tmp1 += L - p1[n-1-k].first;
                p1[n-1-k].first = L;
            }
            sort(p1.begin(), p1.end());
            for(int j=0;j<=n;j++){
                int tmp2 = tmp1;
                for(int k=0;k<n;k++) p2[k] = p1[k];
                for(int k=0;k<j;k++){
                    tmp2 += p2[k].first;
                    p2[k].first = 0;
                }
                sort(p2.begin(), p2.end());
                for(int l=0;l<=n;l++){
                    for(int k=0;k<n;k++) p3[k] = p2[k];
                    int tmp3 = tmp2;
                    for(int k=0;k<l;k++){
                        tmp3 += L - p3[n-1-k].first;
                        p3[n-1-k].first = L;
                    }
                    sort(p3.begin(), p3.end());
                    bool ok = true;
                    for(int k=0;k+1<n;k++){
                        if(p3[k].second > p3[k+1].second) ok = false;
                    }
                    if(!ok) continue;
                    for(int k=0;k<n;k++){
                        tmp3 += abs(p3[k].first - p3[k].second);
                    }
                    res = min(tmp3, res);
                }
            }
        }
        return res;
    }
};

1000. TreePuzzle

見てない。

結果：-- / AC / -- ，+0, 255.25pt, 101位
レーティング：2404 -> 2442

運が良かったとしか言いようのない結果です。250でbitDP思いつけなかったのが反省点。