2016-03-18

TIOJ::IOI::1885 . 【IOI2015】Scales 斯克兒悠斯-一堆天平

http://tioj.ck.tp.edu.tw/problems/1885
這是題爆搜題，可是我卻寫了一整天，還重寫了一遍才AC。
不過果然又是AC後覺得不難寫的題目…。
感覺IOI 2015 Day1的題目想要AC都要發現一些很漂亮的性質啊！

題目是這樣的，你有6個東西，你可以透過題目提供的函數來查詢，而你必須利用這些函數來排序並回傳這6個東西的順序。
想要排序不難，但是題目限制了你呼叫查詢函數的次數，正解必須在6次內排好序（6次剛好也是下界）。
如果你超過了6次，在IOI是可以得到部份分數的，但是OJ上我們就只能寫正解（special judge功能不夠完整），也就是我們必須六次完成。

如果8次的話很容易，只要先亂叫一下，然後在針對幾種狀況處理，雖然沒寫過，不過如果比賽遇到這題，這樣寫期望值應該會比較高吧？
要到6次，我們必須每一步都去考慮很多狀況，既然這樣就暴力建出決策樹吧！
所謂的決策樹，就是我如果現在做了這個查詢後，得到了不同的結果後我要怎麼繼續的一顆樹，也就是如果你建出來了，你不管遇到什麼情況都可以直接查樹來找到下一步要幹嘛。

要做到6次排序，我們希望可以有一個深度是6的決策樹，然後到底就知道答案了。
我們的4種查詢函數，回傳的結果剛好都只有三種，回傳第1個、第2個或是第3個數字，所以對於每種查詢只要找出3個結果的狀況。
一開始，假設我們有720種可能遇到的排列（六階乘，1到6的所有排列情況），然後共有120種可以做的查詢（前三種找最小、中間、最大的函數，都各有C（6,3）=20種可能的查詢法，第四種20種每種都還可以配三個不同的數字，所以60種，共120種），我們一開始就從120的隨便一種查詢開始，共有三種結果，然後拿這個去對720種分類，看那720種排列哪個符合哪一個結果，這些排列會被分進3個集合裡，我們就可以繼續遞迴，直到這個集合被刪光或是剩下唯一一個狀況，也就代表我們完成排序了，或是這是一個實際不可能遇到的情況（刪到光代表出之前的查詢中現矛盾的結果，這在實際狀況不會出現，但是在決策樹上會出現，實際上我們有729個終點，卻只有720種排列，很顯然會有9個這種終點）。
如果深度到6還剩下超過一種結果，那就無法在6次內排序，回傳失敗。每次試一種分法分成三堆，如果三堆都可以在接下來的搜尋中完成目標，就是OK的，不然就要繼續搜尋，搜不到就回傳失敗。

這樣的搜尋不夠快，要加一個很重要的剪枝，也就是，每次分成三堆的時候，每堆的大小都要小於等於 720/3的深度次方，又或者是 3的(6-深度)次方（6或是5要搞清楚，這跟每個人定義深度從0還是1開始有關係），舉例來說，720一定只能被分成3個240的堆，240只能被分成80，80可以被分成27、27、26，因為定義了一定不能大於，其實也就是定義了不能小於一定的值。
為什麼這樣會對？其實我們可以發現，每個排列不是被分進第1堆就是其他兩堆，如果有一堆太多，那很顯然他不能再接下來的步數內被分成剩下1的三堆，因為一定有人會分到大的那堆，然後你一直除三最大那堆也不會是1。
其實這也是我們最後會找到的解法會顯現的狀況，也就是每次查詢都可以分類成三堆大小差不多的狀況，這樣就能完成在6次排序。

在用查詢刪除排列的操作上，可以摹擬題目給你的查詢函數，實際看看結果是1、2、3哪個再決定分到哪堆去，剩下哪些狀態就用vector存就可以了，查詢可以用一個陣列或是struct，存函數編號、參數。再來就是注意細節。

一開始動態開點就不小心讓電腦當機兩次…，以後不要在不安全的情況下new點了…。整份code因為細節很多，最後還是到了快180行。

#include <bits/stdc++.h>
#include "lib1885.h"
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int P[721][6], C[121][5];
struct Tree{
    int fid,ans;
    Tree* ch[3];
    Tree(int dep){
        ans = -1;
        if(dep == 6)F(3)ch[i] = NULL;
        else{
            F(3)ch[i] = new Tree(dep + 1);
        }
    }
};
int getL(int *s, int *c){
    int pos[3];
    F(6)Fi(j,3)if(s[i] == c[j+1])pos[j] = i;
    if(pos[0]<pos[1]&&pos[0]<pos[2])return 0;
    if(pos[1]<pos[0]&&pos[1]<pos[2])return 1;
    return 2;
}
int getH(int *s, int *c){
    int pos[3];
    F(6)Fi(j,3)if(s[i] == c[j+1])pos[j] = i;
    if(pos[0]>pos[1]&&pos[0]>pos[2])return 0;
    if(pos[1]>pos[0]&&pos[1]>pos[2])return 1;
    return 2;
}
int getM(int *s, int *c){
    int pos[3];
    F(6)Fi(j,3)if(s[i] == c[j+1])pos[j] = i;
    if(pos[0]<pos[1]!=pos[0]<pos[2])return 0;
    if(pos[1]<pos[0]!=pos[1]<pos[2])return 1;
    return 2;
}
int getN(int *s, int *c){
    int pos[4];
    F(6)Fi(j,4)if(s[i] == c[j+1])pos[j] = i;
    int tmp = 6;
    F(3)if(pos[i] > pos[3])tmp = min(pos[i], tmp);
    if(tmp == 6){
        return getL(s, c);
    }else{
        F(3)if(s[tmp] == c[i+1])return i;
        assert(false);
    }
}
bool check(int *s, int a, int b){
    F(6){
        if(s[i] == a)return true;
        if(s[i] == b)return false;
    }
    assert(false);
}
int DP[721][121][3];
bool s_check(int p, int fid, int fres){
    int &x = DP[p][fid][fres];
    if(x)return x-1;
    if(C[fid][0] == 0){
        x = getH(P[p],C[fid]) == fres?2:1;
    }
    if(C[fid][0] == 1){
        x = getL(P[p],C[fid]) == fres?2:1;
    }
    if(C[fid][0] == 2){
        x = getM(P[p],C[fid]) == fres?2:1;
    }
    if(C[fid][0] == 3){
        x = getN(P[p],C[fid]) == fres?2:1;
    }
    return x-1;
    assert(false);
}
inline int pow3(int x){
    int res = 1;
    while(x--)res*=3;
    return res;
}
int cnt = 0;
bool DFS(Tree *now, const vector<int>&sta, int dep){
    if(dep == 6){
        if(sta.size() <=1){
            if(sta.size())now -> ans = sta[0];
            cnt++;
            return true;
        }
        return false;
    }
    vector<int> Jsta[3];
    F(120){
        now -> fid = i;
        bool ok = true;
        Fi(j,3){
            Jsta[j] = vector<int>();
            for(int p:sta)if(s_check(p, i, j)){
                Jsta[j].push_back(p);
            }
            ok &= Jsta[j].size() <= pow3(5-dep);
            if(!ok)break;
        }
        if(ok)Fi(j,3)ok &= DFS(now->ch[j], Jsta[j], dep+1);
        if(ok)return true;
    }
    return false;
}
int call(int *c){
    int res;
    if(c[0]==0){
        res = getHeaviest(c[1],c[2],c[3]);
    }
    if(c[0]==1){
        res = getLightest(c[1],c[2],c[3]);
    }
    if(c[0]==2){
        res = getMedian(c[1],c[2],c[3]);
    }
    if(c[0]==3){
        res = getNextLightest(c[1],c[2],c[3],c[4]);
    }
    F(3)if(res == c[i+1])return i;
    assert(false);
}
int* Chino(Tree *now, int dep){
    if(dep == 6){
        assert(now->ans != -1);
        return P[now->ans];
    }
    int res = call(C[now->fid]);
    return Chino(now->ch[res], dep+1);
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tmp[6];
    F(6)tmp[i] = i+1;
    int p = 0;
    do{
        F(6)P[p][i] = tmp[i];
        p++;
    }while(next_permutation(tmp,tmp+6));
    assert(p == 720);
    p = 0;
    F(3)Fi(j,6)Fl(k,j+1,6)Fl(l,k+1,6){
        C[p][0] = i;
        C[p][1] = j+1;
        C[p][2] = k+1;
        C[p][3] = l+1;
        p++;
    }
    F(6)Fl(j,i+1,6)Fl(k,j+1,6)Fi(l,6)if(l!=i&&l!=j&&l!=k){
        C[p][0] = 3;
        C[p][1] = i+1;
        C[p][2] = j+1;
        C[p][3] = k+1;
        C[p][4] = l+1;
        p++;
    }
    assert(p == 120);
    Tree *RT = new Tree(0);
    vector<int> sta;
    F(720)sta.push_back(i);
    if(!DFS(RT, sta, 0))cout<<"Build Error!!"<<endl;
    int t = Init();
    while(t--){
        orderCoins();
        answer(Chino(RT, 0));
    }
}