解題區/解題區 - UVa

UVa 751 - Triangle War

Problem

兩名玩家進行放邊的操作，當其中一名玩家成功創建一個三角形，則可以再放入一邊，直到該操作無法創建一個新的三角形，則進行輪替。最大化自己與對方的分數差異。

一開始先模擬兩名玩家的操作過程。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8

Sample Output

1
2
3
4
Game 1: B wins.
Game 2: A wins.
Game 3: A wins.
Game 4: B wins.

Solution

這題很妙，總之先定義狀態 dp(盤面狀況，剩餘三角形) = 最大化差異。

那麼轉移方程要看操作是否造成輪替，如果仍然為自己，則把下一步的最大化結果累加上來，反之扣除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int dp[1<<18][11];
char used[1<<18][11] = {};
int trans[11][11], tri[10];
int countTri(int state) {
    int ret = 0;
    for (int i = 0; i < 9; i++) {
        if ((state&tri[i]) == tri[i])
            ret++;
    }
    return ret;
}
int dfs(int state, int score) {
    if (used[state][score])		return dp[state][score];
    used[state][score] = 1;
    
    int ret = 0, nstate, had = 9 - score, c, t;
    for (int i = 0; i < 18; i++) {
        if ((state>>i)&1) {
            nstate = state ^ (1<<i); // used it.
            c = countTri(((1<<18)-1)^nstate);
            if (c > had) { // create new
                t = c - had + dfs(nstate, score - (c - had));
                ret = max(ret, t);
            } else {
                t = score - dfs(nstate, score);
                ret = max(ret, t);
            }
        }
    }
    dp[state][score] = ret;
    return ret;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    trans[1][2] = 0, trans[1][3] = 1;
    trans[2][3] = 2;
    trans[2][4] = 3, trans[2][5] = 4, trans[3][5] = 5, trans[3][6] = 6;
    trans[4][5] = 7, trans[5][6] = 8;
    trans[4][7] = 9, trans[4][8] = 10, trans[5][8] = 11, trans[5][9] = 12, trans[6][9] = 13, trans[6][10] = 14;
    trans[7][8] = 15, trans[8][9] = 16, trans[9][10] = 17;
    tri[0] = (1<<0)|(1<<1)|(1<<2);
    tri[1] = (1<<3)|(1<<4)|(1<<7);
    tri[2] = (1<<2)|(1<<4)|(1<<5);
    tri[3] = (1<<5)|(1<<6)|(1<<8);
    tri[4] = (1<<9)|(1<<10)|(1<<15);
    tri[5] = (1<<7)|(1<<10)|(1<<11);
    tri[6] = (1<<11)|(1<<12)|(1<<16);
    tri[7] = (1<<8)|(1<<12)|(1<<13);
    tri[8] = (1<<13)|(1<<14)|(1<<17);
    int testcase, cases = 0;
    int n, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int state = 0, A = 0, B = 0, turn = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            if (x > y)	swap(x, y);
            int c = countTri(state|(1<<trans[x][y])) - countTri(state);
            if (c) {
                if (turn == 0)		A += c;
                else				B += c;
            } else {
                turn = !turn;
            }
            state |= 1<<trans[x][y];
        }
//		printf("score %d %d\n", A, B);
        state = ((1<<18)-1)^state; // unused: 1
        int had = A + B;
        int mx = dfs(state, 9 - had);
        if (turn == 0)	A += mx, B += 9 - had - mx;
        else			B += mx, A += 9 - had - mx;
        printf("Game %d: %s wins.\n", ++cases, A > B ? "A" : "B");
    }
    return 0;
}
/*
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8
*/
Read More +
解題區/解題區 - UVa

UVa 509 - RAID

Problem

參照《算法競賽入門經典》一書

一種磁碟儲存的機制，磁碟除了資料儲存，同時也會賦予檢查碼，來修正錯誤的資訊，即便能力相當有限，最多修正一個錯誤位元。

現在要求的工作是進行錯誤位元的復原，並且輸出 16 進制下的資料，如果資料不足 4 bits，則剩餘位元接補上 0。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 2 5
E
0001011111
0110111011
1011011111
1110101100
0010010111
3 2 5
E
0001111111
0111111011
xx11011111
3 5 1
O
11111
11xxx
x1111
0

Sample Output

1
2
3
Disk set 1 is valid, contents are: 6C7A79EDFC
Disk set 2 is invalid.
Disk set 3 is valid, contents are: FFC

Solution

這題很簡單，但是一直沒注意到陣列開太小而炸掉，我的預設記憶體不夠大而 WA。剩下的細節則注意錯誤位元如果是檢查碼就可以無視，而同時檢查碼只支持修正一個位元，如果需要修正兩個以上則表示無法復原。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
char mem[128][65536];
int main() {
    int cases = 0;
    int D, S, B;
    char kind[8];
    while (scanf("%d %d %d", &D, &S, &B) == 3 && D) {
        scanf("%s", kind);
        for (int i = 0; i < D; i++)
            scanf("%s", mem[i]);
        int n = S * B, kv = kind[0] == 'E' ? 0 : 1;
        int err = 0;
        for (int i = 0, j = 0; i < n; i += S, j++) {
            j %= D;
            for (int p = i; p < i + S; p++) {
                int broken = 0, brokenPos = 0, XOR = 0;
                for (int k = 0; k < D; k++) {
                    if (mem[k][p] == 'x')
                        broken++, brokenPos = k;
                    else
                        XOR ^= mem[k][p] - '0';
                }
                if (broken >= 2)
                    err = 1;
                else if (broken == 1) {
                    if (brokenPos == j) {
                    } else {
                        mem[brokenPos][p] = '0' + (kv^XOR);
                    }
                } else {
                    if (XOR != kv)  err = 1;
                }
            }
        }
        printf("Disk set %d is ", ++cases);
        if (err) {
            puts("invalid.");
        } else {
            char buff[65536];
            memset(buff, '0', sizeof(buff));
            int m = 0;
            for (int i = 0, j = 0; i < n; i += S, j++) {
                j %= D;
                for (int k = 0; k < D; k++) {
                    if (k == j) continue;
                    for (int p = i; p < i + S; p++) {
                        buff[m++] = mem[k][p];
                    }
                }
            }
            printf("valid, contents are: ");
            for (int i = 0; i < m; i += 4) {
                int val = 0;
                val |= (buff[i + 0] - '0') << 3;
                val |= (buff[i + 1] - '0') << 2;
                val |= (buff[i + 2] - '0') << 1;
                val |= (buff[i + 3] - '0') << 0;
                printf("%X", val);
            }
            puts("");
        }
    }
    return 0;
}
/*
 
 5 2 5
 E
 xx01011111
 0110111011
 1011011111
 1110101100
 0010010111
 5 2 5
 E
 0001011111
 0110111011
 1011011111
 1110101100
 0010010111
 3 2 5
 E
 0001111111
 0111111011
 xx11011111
 3 5 1
 O
 11111
 11xxx
 x1111
 0
*/
Read More +
解題區/解題區 - UVa

UVa 506 - System Dependencies

Problem

參照《算法競賽入門經典》一書

軟體安裝時，會同時下載所需要的插件包，而插件包的軟體也有可能繼續安裝所需要的插件包。如此遞迴下去把所需要的元件都安裝好。

當安裝一個軟體時，分成使用者安裝和系統安裝兩種，使用者只能刪除自己安裝的軟體，其相依的插件包必須由系統來進行刪除，系統刪除時，會檢查是否還有其他軟體需要相依，若不存在相依，則會將此軟體刪除。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
   Installing NETCARD
INSTALL TELNET
   Installing TCPIP
   Installing TELNET
INSTALL foo
   Installing foo
REMOVE NETCARD
   NETCARD is still needed.
INSTALL BROWSER
   Installing HTML
   Installing BROWSER
INSTALL DNS
   Installing DNS
LIST
   NETCARD
   TCPIP
   TELNET
   foo
   HTML
   BROWSER
   DNS
REMOVE TELNET
   Removing TELNET
REMOVE NETCARD
   NETCARD is still needed.
REMOVE DNS
   Removing DNS
REMOVE NETCARD
   NETCARD is still needed.
INSTALL NETCARD
   NETCARD is already installed.
REMOVE TCPIP
   TCPIP is still needed.
REMOVE BROWSER
   Removing BROWSER
   Removing HTML
   Removing TCPIP
REMOVE TCPIP
   TCPIP is not installed.
END

Solution

一道模擬，假想一張 DAG 圖，刪除時暴力檢查其逆向的依存軟體是否存在。

使用 STL 和遞迴可以讓程式更簡單易懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> getArgs(char line[]) {
    stringstream sin(line);
    vector<string> ret;
    string token;
    while (sin >> token)
        ret.push_back(token);
    return ret;
}
map<string, int> name2id;
map<int, string> id2name;
map<int, vector<int> > dependInstall, invDependInstall;
map<int, int> installStatus;
vector<int> installList;
int getId(string s) {
    int &ret = name2id[s];
    if (ret == 0) {
        ret = (int) name2id.size();
        id2name[ret] = s;
    }
    return ret;
}
string getName(int id) {
    return id2name[id];
}
int isDepended(int id) {
    vector<int> &v = invDependInstall[id];
    for (int i = 0; i < v.size(); i++) {
        if (installStatus[v[i]])    return 1;
    }
    return 0;
}
void installSoft(int id, int top) {
    if (installStatus[id] == 0) {
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            installSoft(v[i], 0);
        printf("   Installing %s\n", getName(id).c_str());
        installStatus[id] = top ? 1 : 2;
        installList.push_back(id);
    }
}
void removeSoft(int id, int top) {
    if ((top == 1 || installStatus[id] == 2) && !isDepended(id)) {
        installStatus[id] = 0;
        printf("   Removing %s\n", getName(id).c_str());
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            removeSoft(v[i], 0);
        installList.erase(find(installList.begin(), installList.end(), id));
    }
}
int main() {
    char line[2048];
    while (gets(line)) {
        vector<string> args = getArgs(line);
        puts(line);
        if (args[0] == "DEPEND") {
            vector<int> softId;
            for (int i = 1; i < args.size(); i++) {
                softId.push_back(getId(args[i]));
            }
            vector<int> &v = dependInstall[softId[0]];
            for (int i = 1; i < softId.size(); i++) {
                v.push_back(softId[i]);
                invDependInstall[softId[i]].push_back(softId[0]);
            }
        } else if (args[0] == "INSTALL") {
            if (installStatus[getId(args[1])]) {
                printf("   %s is already installed.\n", args[1].c_str());
            } else {
                installSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "REMOVE") {
            if (installStatus[getId(args[1])] == 0) {
                printf("   %s is not installed.\n", args[1].c_str());
            } else if (isDepended(getId(args[1]))) {
                printf("   %s is still needed.\n", args[1].c_str());
            } else {
                removeSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "LIST") {
            for (int i = 0; i < installList.size(); i++) {
                printf("   %s\n", getName(installList[i]).c_str());
            }
        } else if (args[0] == "END") {
            break;
        }
    }
    return 0;
}
/*
 DEPEND   TELNET TCPIP NETCARD
 DEPEND TCPIP NETCARD
 DEPEND DNS TCPIP NETCARD
 DEPEND  BROWSER   TCPIP  HTML
 INSTALL NETCARD
 INSTALL TELNET
 INSTALL foo
 REMOVE NETCARD
 INSTALL BROWSER
 INSTALL DNS
 LIST
 REMOVE TELNET
 REMOVE NETCARD
 REMOVE DNS
 REMOVE NETCARD
 INSTALL NETCARD
 REMOVE TCPIP
 REMOVE BROWSER
 REMOVE TCPIP
 END
 */
Read More +
解題區/解題區 - UVa

UVa 212 - Use of Hospital Facilities

Problem

參照《算法競賽入門經典》一書

模擬醫院的手術室和恢復室(病房)，每個病人分配到一個手術室後，手術完成後會被送至恢復室，而送病人於手術室到恢復室都需要 t1 時間，而每個病人在手術室和恢復室的時間也各有不同。

當手術室和恢復室被使用完畢後，分別需要 t2, t3 的時間進行清除整潔工作，隨後才能再給下一位病人使用，保證每一位病人在過程中都能立即使用不會延誤。

編號小的病患，會先選擇可使用的場地，場地編號也會盡可能地小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
5 12 07 5 15 10 16
Jones
28 140
Smith
120 200
Thompson
23 75
Albright
19 82
Poucher
133 209
Comer
74 101
Perry
93 188
Page
111 223
Roggio
69 122
Brigham
42 79
Nute
22 71
Young
38 140
Bush
26 121
Cates
120 248
Johnson
86 181
White
92 140

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 Patient          Operating Room          Recovery Room
 #  Name     Room#  Begin   End      Bed#  Begin    End
 ------------------------------------------------------
 1  Jones      1    7:00    7:28      3    7:33    9:53
 2  Smith      2    7:00    9:00      1    9:05   12:25
 3  Thompson   3    7:00    7:23      2    7:28    8:43
 4  Albright   4    7:00    7:19      1    7:24    8:46
 5  Poucher    5    7:00    9:13      5    9:18   12:47
 6  Comer      4    7:34    8:48      4    8:53   10:34
 7  Perry      3    7:38    9:11      2    9:16   12:24
 8  Page       1    7:43    9:34      6    9:39   13:22
 9  Roggio     4    9:03   10:12      9   10:17   12:19
10  Brigham    2    9:15    9:57      8   10:02   11:21
11  Nute       3    9:26    9:48      7    9:53   11:04
12  Young      5    9:28   10:06      3   10:11   12:31
13  Bush       1    9:49   10:15     10   10:20   12:21
14  Cates      3   10:03   12:03      8   12:08   16:16
15  Johnson    2   10:12   11:38      4   11:43   14:44
16  White      5   10:21   11:53      7   11:58   14:18
Facility Utilization
Type  # Minutes  % Used
-------------------------
Room  1     165   29.68
Room  2     248   44.60
Room  3     258   46.40
Room  4     162   29.14
Room  5     263   47.30
Bed   1     282   50.72
Bed   2     263   47.30
Bed   3     280   50.36
Bed   4     282   50.72
Bed   5     209   37.59
Bed   6     223   40.11
Bed   7     211   37.95
Bed   8     327   58.81
Bed   9     122   21.94
Bed  10     121   21.76
Bed  11       0    0.00
Bed  12       0    0.00

Solution

建議使用一種時間軸的概念，維護一個 priority_queue 來知道下一個事件發生時間，接著在那時間掃描可能發生事件，這樣維護會比較容易寫。

出題者到處打雜呢！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <sstream>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct Patient {
    string name;
    int pa, pb;
    int aBegin, aEnd, bBegin, bEnd, aid, bid;
    Patient(int a = 0, int b = 0, string s = ""):
    pa(a), pb(b), name(s) {}
} D[2048];
int main() {
    int N, M, K, ST_T, PA_T, PB_T, PAB_T;
    char s[1024];
    int x, y;
    while (scanf("%d %d %d %d %d %d %d", &N, &M, &ST_T, &PAB_T, &PA_T, &PB_T, &K) == 7) {
        for (int i = 0; i < K; i++) {
            scanf("%s %d %d", s, &x, &y);
            D[i] = Patient(x, y, s);
        }
        int aWorking[32] = {}, bWorking[32] = {};
        int aFinTime[32] = {}, bFinTime[32] = {};
        int aPid[32], bPid[32], aUsed[32] = {}, bUsed[32] = {};
        int preTime = -1, pid = 0;
        
        memset(aPid, -1, sizeof(aPid));
        memset(bPid, -1, sizeof(bPid));
        
        priority_queue<int, vector<int>, greater<int> > timeline;
        timeline.push(ST_T * 60);
        while (!timeline.empty()) {
            int now = timeline.top();
            timeline.pop();
            if (now == preTime) continue;
            preTime = now;
            vector<int> A2B;
            for (int i = 0; i < N; i++) {
                if (aWorking[i] && aFinTime[i] <= now) {
                    aWorking[i] = 0;
                    if (aPid[i] >= 0) {
                        A2B.push_back(aPid[i]);
                        aWorking[i] = 1;
                        aFinTime[i] = now + PA_T;
                        aPid[i] = -1;
                        timeline.push(now + PA_T);
                    }
                }
            }
            for (int i = 0; i < M; i++) {
                if (bWorking[i] && bFinTime[i] <= now) {
                    bWorking[i] = 0;
                    if (bPid[i] >= 0) {
                        bWorking[i] = 1;
                        bFinTime[i] = now + PB_T;
                        bPid[i] = -1;
                        timeline.push(now + PB_T);
                    }
                }
            }
            for (int i = 0; i < A2B.size(); i++) {
                int x = A2B[i];
                for (int j = 0; j < M; j++) {
                    if (bWorking[j] == 0) {
                        bWorking[j] = 1;
                        bFinTime[j] = PAB_T + now + D[x].pb;
                        bPid[j] = x, bUsed[j] += D[x].pb;
                        D[x].bid = j;
                        D[x].bBegin = now + PAB_T, D[x].bEnd = bFinTime[j];
                        timeline.push(bFinTime[j]);
                        break;
                    }
                }
            }
            for ( ; pid < K; pid++) {
                int ok = 0;
                for (int i = 0; i < N; i++) {
                    if (aWorking[i] == 0) {
                        aWorking[i] = 1;
                        aFinTime[i] = now + D[pid].pa;
                        aPid[i] = pid, aUsed[i] += D[pid].pa;
                        D[pid].aid = i;
                        D[pid].aBegin = now, D[pid].aEnd = aFinTime[i];
                        timeline.push(aFinTime[i]);
                        ok = 1;
                        break;
                    }
                }
                if (!ok)
                    break;
            }
        }
        
        int ST = 0x3f3f3f3f, ED = 0;
        puts(" Patient          Operating Room          Recovery Room");
        puts(" #  Name     Room#  Begin   End      Bed#  Begin    End");
        puts(" ------------------------------------------------------");
        for (int i = 0; i < K; i++) {
            printf("%2d  %-9s %2d  %3d:%02d  %3d:%02d    %3d  %3d:%02d  %3d:%02d\n",
                   i+1, D[i].name.c_str(), D[i].aid+1,
                   D[i].aBegin/60, D[i].aBegin%60, D[i].aEnd/60, D[i].aEnd%60, D[i].bid+1,
                   D[i].bBegin/60, D[i].bBegin%60, D[i].bEnd/60, D[i].bEnd%60);
            ST = min(ST, D[i].aBegin);
            ED = max(ED, D[i].bEnd);
        }
        puts("");
        puts("Facility Utilization");
        puts("Type  # Minutes  % Used");
        puts("-------------------------");
        for (int i = 0; i < N; i++) {
            printf("%-4s %2d %7d %7.2lf\n", "Room", i+1, aUsed[i], (double) aUsed[i]*100/(ED - ST));
        }
        for (int i = 0; i < M; i++) {
            printf("%-4s %2d %7d %7.2lf\n", "Bed", i+1, bUsed[i], (double) bUsed[i]*100/(ED - ST));
        }
        puts("");
    }
    return 0;
}
/*
 
 */
Read More +
解題區/解題區 - UVa

UVa 210 - Concurrency Simulator

Problem

模擬 CPU 排程，並且每種指令的所需時間都不同。一個程式可以使用 quantum 的時間，最多負一次執行某個指令 (quantum > 0 變成 quantum <= 0 的情況)。而當 unlock 只將一個程式從 block queue 吐出，而非所有程序。

保證每一個程序都會有一對 lock/unlock。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1
3 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b 
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end

Sample Output

1
2
3
4
5
6
7
8
9
10
1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21

Solution

作業系統排程 lock & unlock 模擬，去年某一天心血來潮寫，卻狂 WA。現在回過頭才發現對 quantum 的使用錯誤，在有限時間內，即使在有剩餘時間下，執行下一條單位操作，直到沒有剩餘時間，我卻用加法限制於 quantum 下，導致炸掉。

題目中 “When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue”，為什麼只有一個 blocked queue 元素彈出，雖然在效率考量上是這樣，誤看成全部彈出，怪不得會一直 WA。但這樣所有模擬都會完結？ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
#include <sstream>
using namespace std;
#define MAXN 1024
#define MAXM 32
#define MAXVAR 26
struct Memory {
    char s[MAXM][MAXM];
    int counter;
    void read() {
        int n = 0;
        while (gets(s[n])) {
            if (s[n][0] == 'e' && s[n][1] == 'n' && s[n][2] == 'd')
                return;
            n++;
        }
    }
} mem[MAXN];
int N, unitTime[5], quantum, locked, var[MAXVAR];
deque<int> readyQ, blockQ;
vector<string> decode(string s) {
    vector<string> ret;
    stringstream sin(s);
    while (sin >> s)
        ret.push_back(s);
    return ret;
}
int toInt(string s) {
    int ret;
    stringstream sin(s);
    sin >> ret;
    return ret;
}
void execute(int pid) {
    int q = quantum;
    while (q > 0) {
        vector<string> args = decode(mem[pid].s[mem[pid].counter]);
        if (args[0].length() == 1) {
            var[args[0][0] - 'a'] = toInt(args[2]);
            q -= unitTime[0];
        } else if (args[0] == "print") {
            printf("%d: %d\n", pid+1, var[args[1][0] - 'a']);
            q -= unitTime[1];
        } else if (args[0] == "lock") {
            if (locked) {
                blockQ.push_back(pid);
                return;
            }
            locked = 1;
            q -= unitTime[2];
        } else if (args[0] == "unlock") {
            locked = 0;
            if (!blockQ.empty()) {
                readyQ.push_front(blockQ.front());
                blockQ.pop_front();
            }
            q -= unitTime[3];
        } else if (args[0] == "end") {
            return ;
        }
        mem[pid].counter++;
    }
    readyQ.push_back(pid);
}
void run(int N) {
    for (int i = 0; i < N; i++)
        readyQ.push_back(i), mem[i].counter = 0;
    for (int i = 0; i < MAXVAR; i++)
        var[i] = 0;
    locked = 0;
    int pid;
    while (!readyQ.empty()) {
        pid = readyQ.front(), readyQ.pop_front();
        execute(pid);
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < 5; i++)
            scanf("%d", &unitTime[i]);
        scanf("%d", &quantum);
        while (getchar() != '\n');
        for (int i = 0; i < N; i++)
            mem[i].read();
        
        run(N);
        
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 */
Read More +
解題區/解題區 - 其他題目

2015 Facebook Hacker Cup Round 1

起床才發現，Facebook Hacker Cup Round 2 比賽不是比 24 小時，翻譯機的小夥伴醒了嗎？在這樣的情況下，只好自主宣告放棄，看題一直失敗，整個心情都壞了。關於 Round 2，根本沒看懂題目，就這麼結束了。

［2015 Facebook Hacker Cup Round 1］

＊Homework (10 points)

數學老師給一份質數作業，要求找到 [A, B] 之間的正整數，有多少不同質因數個數恰好等於 K 個，例如 12 = 2^2 * 3，則 f(12) = 2。寫一個程式來快速完成它。

A, B 小於等於 1000 萬，而詢問組數不超過 100 組，預估就算 O(n) 窮舉，速度來說仍然可以在時間內完成。無聊可以使用線性篩法，快速得到某個數字 x 必含的其中一個質因數來加速，f(x) = f(y) + 1, x = y * z, z power of prime nubmer。而區間查找可以針對 K 分開成數組，進行二分搜索。這樣寫太拚，有六分鐘的時間，暴力一點也無仿。

＊Autocomplete (25 points)

手機輸入單詞，會自動補上正在輸入單字的後綴，現在要求依序輸入單字，至少要敲入幾個字母，才能將所有單字完成。這題有點奇怪，照理來說要給定一個字典，接著開始鍵入，但這題是根據之前輸入的單詞，如果前綴相同就不能自動完成，怎麼補完的一點都不科學。

這題用內建 set<string>，可以使用 iterator it = map.lower_bound(word), it--; 來找到最有可能的前綴單詞，一定得輸入最大共同前綴長 +1，如果不想用內建，可以帶入 Trie 來完成，保證單詞總長不超過 100 萬，在某些題目 Trie 的速度跟泛用性相當高。

＊Winning at Sports (25 points)

在比賽中，勝利情況分成有、無壓力兩種方案，無壓力的情況是過程中，最後獲勝者的分數恆大於另一方，有壓力的情況是過程中，在另一方達到終盤分數前，最後獲勝者的分數不得大於另一方。現在給定終盤分數，請問兩種方案的比賽過程分別有多少種。

Dynamic programming 狀態 dp[a][b] 表示分別得分 a, b 的方法數，每次轉移 dp[a+1][b] += dp[a][b], dp[a][b+1] += dp[a][b] 特別小心條件範圍，分別對兩種方案做一次迭代。

＊Corporate Gifting (40 points)

每名員工都有一位上司，保證是樹狀結構，每名員工將要買禮物送給上司，禮物的花費為 $1, $2, …, $n，每個人都不想送出 $x 後，又從下屬中得到 $x 的禮物，請問該公司買禮物的總花費最小值為何？

樹狀最小帶權著色問題，套入樹形 Dp 的思路，定義狀態 dp[u][2] 表示以節點 u 當作 subtree root 的最佳解，其中 u 買 $?1,$?2 的兩種花費最小方案。合併時，窮舉 root 購入的價格，結合子樹的最小花費，防止同色即可。根據官方題解，使用的是 dp[u][log n]，可想而知數學推導得到最大購入不超過 $(log n)，但實際運作，我並沒有這麼做，而是看子樹最大著色數為何，再根據最大著色數進行窮舉。

這一題看到 N=200000 就要有點警惕，一般電腦預設 stack 大小，遞迴深度最多撐到 10 萬，呈現鏈狀很容易造成 stackoverflow，其一解決方案是編譯器調參數，其二 bfs 後的拓墣排序。

Read More +
手札日記

倒數第二次寒假

由於有一陣子沒寫，其一原因是回家去，deploy 配置設定忘了傳上去 github，而 hexo 也釋出 3.0，一直在圍觀正式版何時出場。接著回顧一下動態吧。

關於 ACM-ICPC

知乎－如何解读 ACM/ICPC 2014 各高校参赛队的队名？ http://www.zhihu.com/question/26659726

在此就選幾個吧！

萌萌哒系列

Team 69 東北師範大學－今天沒吃藥感覺萌萌哒

科南系列

Team 38 中山大學－銀翼的魔術師
Team 182 中山大學－貝克街的亡靈
Team 159 中山大學－異次元的狙擊手

對話系列

Team 80 浙江農林大學－現在問題來了
Team 90 中國科學技術大學－ 來到一個新的城市我們吃什麼
Team 59 寧波大學－吃粑粑把你

關於 ACMer

知乎－为什么 ACM 大牛都喜欢二次元喜欢扮萌妹？ http://www.zhihu.com/question/20971570

《寄生獸》要試穿個女裝，估計還挺秀色可餐的吧

聽說 ACMer 女裝後會進步神速，在此絕非講某位女裝 ACMer，當然在下還不是什麼大牛，肯定是不會女裝一下的，如果想要認識某位女裝 ACMer，歡迎自行連絡 here。這此順便提及一下，有篇《论 ACM 与妹子》值得去讀一下，真愛無所不在，不只是二次元、三次元，跨越好幾個次元的超遠次元戀愛故事，也許 ACM 裡的萌妹子 (Problem) 是屬於一次元的呢。

當然今年的 2/14 情人節，肯定也要找萌妹子囉！

情人節也要跟算法一起萌萌哒哦！

〔全局最小割〕最小割 Stoer-Wagner 算法

http://blog.sina.com.cn/s/blog_700906660100v7vb.html
http://wenku.baidu.com/view/fdb484c3bb4cf7ec4afed08b.html

主算法框架不難，隨著迭代將點數縮減，每次在 G(V, E) 找到其中一組 s-t 最小割，不管最小割 s-t 是否為答案，將 s-t 合併成一個點得到 G’(V’, E’)，繼續迭代。答案要不在剛剛求出的 s-t 要不在 G’ 中，s-t 即假設兩點位於不同的集合，如果求出的不是最小割，合併 s-t 兩點，使其強迫在同一個集合，不影響答案。

問題是卡在任意 s-t 的最小割，必須在盡可能快的時間內求出。網上都說算法神似最大生成樹 prim 算法，不過我想從遞歸中可以得到最後兩個入隊節點分別為 s-t，w[set A][s] >= w[set A][t] + w[s][t]，也就是說，s 流入 set A 的流量一定夠支持 w[set A][t]，並且約束在 w[set A][t] + w[s][t] 即為最小割。

關於生活

原來這種論文也是有的 Research paper : “Why I don’t have a girlfriend ?”，根據數學公式的計算，在條件限制下，作者發現在英國倫敦也不過 26 人會符合他的條件，在茫茫大海中也不過 26 個人會符合，那麼交不到女朋友也是情有可原的不是？

在這個寒假中迎來第 2800 個萌妹子，距離後宮佳麗三千計畫還差 200。2800 題還不到夢月 (dreamoon)大斷層的一半，然而夢月大人卻說「我改過自新了 ! 與其浪費時間去刷題，不如多去把一些不存在中文的 tutorial 中文化」一想到終點線不動的話， 終點線不移動就不 M 了啊！

靠著把 《算法競賽入門經典－劉汝佳》 前 11 章的題目都掃過，除了幾個生日賽的幾道題、化石的 World Final 題目、數論、幾何積分、機率、物理效應、不完美算法，這也足夠增加快 100 題，看來前往 3000 路途還很漫長。因為裡面挺多中文翻譯，即使沒有詳細題解，略知一二也是能解不少題，在此推薦有在刷題的各位去選購，相當划算！不過通常會被搶光，請做好心理準備 傳送門。

也因為寒假主要是靠這本書找題目來寫，感覺也不怎麼需要翻譯跟提供題解，沒有新的文章產出到是真的。不過能把上學期計算幾何的概念拿出來實用於解題方面，可說是相當感人的霎那！

寒假跟中興小夥伴一起去動漫展，而我進去參觀什麼都沒買，有趣的是一大早四點多起床，排隊到十點，這間在台北南港展覽會等了四個小時，排隊期間跟老妮可玩西洋棋，旁邊的 cosplay 的小姐也會來湊一咖，原來宅宅們都是善良的！排隊進去，結果還要排出版社，於是又排到場外去，這奇觀跟幾年前去的時候，又有一大的改變。

《四月是你的謊言》討厭自己無能

這次去動漫展之前，半夜掛急診，貌似腸胃炎失去平衡感，半夜暈眩起床而吐，在床上躺了好幾天，過了四五天平衡感才回來，至今仍然沒有完全復原，處於會影像延遲的地步。在動漫展之後，在家打掃民宿，剝床單、曬床單、拖地板，一整個早上的時間就這麼結束，免費勞工算下去，其實根本賺不了多少錢，然而實際可以分多少我也不曉得。過年中間喉嚨感冒，後來扁桃腺發炎，又好幾天痛得受不了，吞嚥上有點吃力，這寒假可是說是多苦多難啊。

開學後，選課上仍是挑戰，雖然離畢業門檻只差一學分，修什麼課都行，但是看著英文畢業門檻、外出小時數不足，心中仍然處於半放棄狀態，也許啊，該是倒數自己結束的日子，一切都玩完了。

《代筆作家》只要我寫不出來 你也會離開我的 對吧

插話一下，最近清華大學吳永輝教授，一直想要提拔台灣的程式競賽，因此辦了很多活動與訊息的提供，但是不得不說大陸式的作法在台灣能不能吸引到學生，學這個有沒有幫助先不談，能不能有飯吃比較重要。

有興趣的人，歡迎加入 Facebook ICPC 台灣參賽者交流社 關注近期比賽最新消息，而我不是很想參加比賽，因為擺在眼前的萌妹子都把不到手，更何況是期間限定的萌妹子，套一句日劇《代筆作家》的感受。

《代筆作家》如果有才能的話 早就拿獎了

所以，大家加油！我也許不是強，而是路過這裡。我不曉得這裡對你有不有趣，但希望有機會在這裡見到你的貢獻。

《問題餐廳》缺點正是魅力所在

我想如果萌妹子的英文好，那就是萌妹子的魅力。建立在自我缺點上的魅力，而另一個方面則是仇恨。

最近被邀著看兩本書，絕非跟英文多益檢定有關，很想罵髒話，不過算了。

《易讀程式碼之美學 - 提升程式碼可讀性的簡單法則》 和 《Clean Code 無瑕的程式碼：敏捷軟體開發技巧守則》 簡單來說是簡單易懂的現代魔法？但是對於練競賽編程的人而言，軟體工程的需求真的不是很大，代碼通常能在幾百行內完成，因此維護之類的項目是不怎麼需要的，在 《算法競賽入門經典－劉汝佳》 中也有提到這個缺點，易讀程式碼之美學那本書還不錯，圖文說明，例子也簡單易懂。而後那一本書還沒開始讀，所以在此不多做描述，但相信這幾本書的基礎仍然是命名能力，也就牽扯到英文 …

是不是該換行。

Read More +
學校課程/自然語言

自然語言處理 Project

Polarity Analysis for Sentiment Classification

Stop Word List

This stopword list is probably the most widely used stopword list. It covers a wide number of stopwords without getting too aggressive and including too many words which a user might search upon. This wordlist contains only 11 words.

1
2
3
4
5
6
7
8
9
10
11
the
i
it
he
she
they
we
you
-
a
an

比起其他網路上的 stop word list 少了很多介系詞，原因是這樣的，例如 who, whom, where, ... 這些詞作為描述對象的主體，這些主體通常不可省略。例如在描述『演員很不錯，但是電影劇本很糟糕。』這段話時，根據實驗的幾種模型，如果忽略主體的存在，很容易造成描述的需求面向錯誤。必然地，無法將 movie, film 過濾掉，主體是相當重要的，即使他在單一詞的極性上不夠明確。

Parsing Sentence

首先，必須把所有縮寫單位展開，當然有可能把錯誤的 Bob's 展開成錯誤的意思，實驗上不構成多大的影響，但以下的操作會更明確地把潛在的 feature 更清楚地劃分，而不會挑到已經重複的。

1
2
3
4
5
6
7
8
`can't` = `can not`
`n't` = ` not`
`'re` = ` are`
`'m` = ` am`
`'s` = ` is`
`'ve` = ` have`
`'ll` = ` will`
... maybe more

再來，必須針對符號轉英詞，有可能是在描述電影名稱會用到 &，一律將其轉換成 and 會更有效。

1
`&` = ` and`

最後，語法上的變換統一。這可能會遭遇到描述『過去的版本很好，現在這個版本很糟。』也許規則應該對時間做點細部劃分。

1
2
3
`am, are, is, was, were` = `be`
`no` = `not`
`film` = `movie`

更多的口語描述，例如 uuuuuuuugggggggggglllllllllllyyyyyyy = ugly 的可能，特別針對 long duplicate word 特別處理，查看濃縮之後，是否會在字典中。狀聲詞 oh, wow, ah, ... 可能是一個極性指標，在此就不濾掉這幾個單詞。

當使用 stop word 過濾某一個句子時，剩餘的詞應該串在一起成為新的句子，而不以 stop word 分開成新的句子。

Filter N-grams Feature

在挑選 n-grams 時，根據給定的公式，從 800 正向評論、800 反向評論中，大約會得到 50M ~ 100M 不同的 n-grams。當我們篩選 n = 3 時，bad 將可能被儲存為 (bad, null, null)。挑選時，必須保障 high order n-grams 佔有一定的數量，大約落在 n-grams : (n+1)-grams = 7 : 3。

評分時，額外增加 high order 的評分權重，以下是程式中使用的分配。

1
N-grams Bonus = {1, 1.02, 1.03, 1.04, 1.05, 1.06, 1.07};

這麼做確保實驗上有保留之前的優良，同時也增加新的元素進去。

當挑選 K-top feature 時，必須將正反兩方的 feature N-grams 分別佔有約 50%，並且去掉同時挑到的情況。

更多的策略，例如 (bad, too, null) 可以視為 (too, bad, null)，使用 dag 的方式紀錄 N-grams。

How To Decide K-top

明顯地觀察到，K 越大時，Language Model 越穩定，平均效能穩定，但最好效能可能會下降，對於 Winnow algorithm 或者是 Passive-Aggressive algorithm 來說，feature vector 會非常大，造成在找到合適的參數會消耗更多的時間，並且難在有限的迭代次數中找到好的切平面。

當 K 很大時，部分的 n-grams 甚至只出現在某些的 training set 中，這造成訓練 Winnow, Passive-Aggressive 的結果並不好，過於分配無用的權重給只出現在 training set 的 feature。在實驗中，挑選 K = 30000 與 K = 50000 的差異並不大，挑選的比例約為 5% 以內。

Improve

LM Classifier

關於論文中提到的 LM filter，試圖去替除掉一些主觀句子，根據每一個句子進行閥值的評測，實驗中測試到非常低的值作為閥值才具有較好的可能性，由於太高、太低都會使得準確度下降，估計這個閥值的調整不具有普遍性。

而其他的 Classifier 並沒有做這類的主客觀篩選，也許可以藉由主客觀句子的判斷做一套分類器，說不定可以改善另外兩個分類器的語意判斷能力。

Combine Classifier

發現到 Winnow, Passive-Aggressive (PA) 都是以閥值作為判斷標準，因此當得到靠近閥值的數據下，判斷能力是相當脆弱。雖然 PA 在平均表現最好，大約落在 85% 附近，遠比 LM 和 Winnow 多了 5% ~ 10% 的準確度，如何加強？

將四個 Classifier 串在一起，並且用八個 attribute 作為一個 feature vector，接著訓練這一個感知機。這八個 attribute 分別是每一個 Classifier 的判斷強度。

1
(LM_POS, LM_NEG, WINNOW_POS, WINNOW_NEG, PA_POS, PA_NEG, SIMPLE_POS, SIMPLE_NEG)

其中由於 Language Model (LM) 的機率不好量化，因此單純採用 0/1 的方式表示。嘗試過取 log 發現仍然並不好。

  • LM_POS : if LM.classify(x) = POS, then LM_POS = 1. Otherwise LM_POS = 0
  • LM_NEG : if LM.classify(x) = NEG, then LM_NEG = 1. Otherwise LM_POS = 0
  • WINNOW_POS : if Winnow.classify(x) = POS, the WINNOW_POS = Winnow.strongClassify(x).
  • WINNOW_NEG : if Winnow.classify(x) = NEG, the WINNOW_NEG = Winnow.strongClassify(x).

strongClassify(x) 從 training data 中得到 h(x) 的出現的最大值，然後根據將判斷的函數大小得到，strongClassify(x) = h(x) / TRAINING_MAX_H_VALUE，之所以不直接使用 strongClassify(x) = h(x) 是因為很容易造成 overflow 或者是過度的調整判斷。在實驗結果後，將後者公式調整為前者所使用的。

當然可以訓練多台，並且串在一起，但是這種串法必須盡可能有所歧異性，並不是串越多越好，可以藉較少次的迭代次數、洗牌後的訓練序列來達到歧異性。PA 具有良好的適應性，在訓練集與測資集大小、差異不大時，效能仍然可以保持著線性關係，相當具有魯棒性。

在實驗觀察中可以明白感知器在越少 feature 下，可以在越少迭代次數中訓練完成，相對地適應能力就會隨差異嚴重波動，實驗中使用的幾個感知機模型，都能在 vector 得到後的幾秒內完成訓練，不用勞費 SVM 的數個小時。Language Model 則會因為 feature 越多，展現更加穩定的效能，即便如此，LM 在負面評論的辨識率仍然不高，這一點從論文中也可以看得出具有相同的現象。

藉此把 LM 對於負面評論辨識率很差的特性，才將其判斷與其他的感知機串在一起使用。這一類的串許多的分類器的算法，可以參照 Adaboost (Adaptive Boosting) 的想法。

N-grams Score

特別小心公式的計算，雖然有很多乘除法，可以使用 Math.log 降下來，防止 overflow 的可能，但同時也會造成嚴重的浮點數誤差。所以使用恰當的 double 運算即可，即使遇到 NaN 也沒有關係。

論文中提及的公式，額外增加變成

$\chi^{2}(t, c) = \frac{N \times (AD - CB)^{2} }{(A+C)\times (B + D) \times (A + B) \times (C + D)} \times Weight[t.getSize()] \times Score(t)$

其中，Weight[t.getSize()] 正如上述的 N-grams Bonus，當最大上為 n = 5 時，部分 unigram、bigram 仍然有用。而 Score(t) 則是取額外資料中的 AFINN-111.txt 單詞正反面的絕對值權重和，有可能正負兩個詞合併成 bigram 來描述更強烈的負面，因此必須取絕對值。

Vector

選擇 K-top feature n-grams 後，感知機的 Vector 如何放置權重仍然是個困難，從實驗中，單純拿 n-grams appear times 作為一個 attribute weight 效果並不好，於是嘗試拿 Math.log(n-grams appear times)，但是效果並不好，有可能是浮點數誤差造成的差異並不大，而 Math.log 本身就很小，尤其是 n-grams appear times = 1 的時候會變成 0，額外加上一個基底 base 來補足也拿以取捨。

最後取用

$vector[i] = Score(ngrams(i)) + \sqrt{n-grams(i) \text{ appear times}}$

這部分仍然要做實驗，Score(ngrams(i)) 大約落在 1 ~ 10 之間。

Process

經過幾次的 cross validation 後，每一次會挑到不同的 feature n-grams，藉由交叉驗證得到不同的精準度 P，同時也將挑選的 n-grams 增加 P 的權重，在實驗中總共做了 5 次 cross validation，針對同一組 800 資料，進行 1 : 1 的劃分。原本預期挑選 40K 個不同的 n-grams 作為 feature，但是經過 5 次實驗，總共得到 50K 個不同的 n-grams，根據累加的 P 值進行由大排到小，挑選 1/5 的 n-grams 出來，最後挑了少於 10K 個做為 feature。

針對已知的 1600 筆資料進行 3 : 1 的劃分，先對數量較多的資料重訓練，隨後才將數量較少放在一起做第二次訓練。防止過度的訓練，導致感知器針對訓練集的已知資訊分配過多的權重，反而針對未知的元素不足以判斷。

extra data support

  • AFINN-111.txt
  • positive word list (ignore) 毫無幫助
  • negative word list (ignore) 毫無幫助
  • negation not (ignore) 目前發現只會更糟糕

程式撰寫

N-grams Storing

string 轉 integer 標記。

How to improve experiment

先用同一份資料訓練、測試，查看是否接近 P = R = 100%，接著放入未知的資料，找到挑選 feature n-grams 之間的差異。

列出幾個可能的差異後，從訓練的感知機中得到每一項的權重，由於是線性分類器，權重的大小即可作為是否具有特色，通常差距會達到 10 ~ 100 倍之間。即使從 N-grams score 得到較高的分數，從感知機中會發現到未必是較大的權重，有可能是某幾篇相關的電影所造成的一面倒。

Pseudocode

preprocess

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
gobal_record(n-grams, score)
for i  = 0 to CROSS_VALIDATION_MAX
    shuffle_order(training_data)
    (ttraining, ttest) = split(training_data, 1 : 1)
    Vectraining = n-grams_sieve(ttraining)
    (LM, Winnow, PA) = training(Vectraining)
    P = test(LM, Winnow, PA, Vectraining)
    gobal_record.add(P, Vectraining)
 
sort gobal_record(n-grams, score) by descending order.
shuffle_order(training_data)
(ttraining, tretain) = split(training_data, 4 : 1)
N-gramsTable = gobel_record.sublist(K)
Vectraining = parsingInput(ttraining,, N-gramsTable)
Vecretain= parsingInput(tretain,, N-gramsTable)
(LM, Winnow, PA) = training(Vectraining)
(LM, Winnow, PA) = retraining(Vecretain)
simpleTest(testdata, LM, Winnow, PA)
onlineTest(testdata, LM, Winnow, PA)

online test

1
2
3
4
5
6
7
GROUP_SIZE = 50
groups = splitEach(testdata, GROUP_SIZE)
foreach(group : groups)
    appear set = find(group, N-gramsTable)
    (LM, Winnow, PA) = retrainingLimited(Vectraining, appear set)
    foreach(data : group)
        classify(LM, Winnow, PA, data)

fail online test idea

1
2
3
4
5
6
7
8
GROUP_SIZE = 10
groups = splitEach(testdata, GROUP_SIZE)
foreach(group : groups)
    backtracking 210 possible solution
        training & test
        if (better performance)
            record solution.
Work, but not helpful.

Support N-grams Sieve

  • AFINN-111.txt
    The file AFINN-111.txt contains a list of sentiment scores
  • Stop word list
    Small set, |S| < 20
  • Synonymous “Not” list
    unused
  • Abbreviation list
    Rule, |R| < 10
  • No CRF, No Parsing tree, No Subjective filter

To Do

增加兩個不在 top feature 中的 attribute，但是在 pos/neg word weight 中的 n-grams 所評分的結果。在量化這些 n-grams 的分數時，不管正反面的強度，一律取絕對值進行加總，有可能一個正面單詞跟一個負面單詞合併在一起來表示一個更強烈的正面或反面資訊。

Training Classifier with 5000 subjective and 5000 objective processed sentences.

實作判斷主觀、客觀的分類器。

http://www.cs.cornell.edu/People/pabo/movie-review-data/

Github

感謝。

Read More +
學校課程/通識課程

[通識] 文明的進程 小組報告 2

文明競逐與衝突－原住民的文化問題

悠久文明－原住民文化

  • 約 15000 年以前移入台灣
  • 南島語系、祖靈信仰
  • 文化特色：屋架構築、火耕、黥面、輪舞…等
  • 音樂、工藝與神話文學
  • 各族各部落間有不同的祭典文化

根據以前讀的歷史，台灣目前出土最古老的是長濱文化，時間至少在 15000 年前。而產出的古物到底能不能證明是否是原住民的祖先？雖然在文化特質上相當相似，即便如此，能說明的是有密切關聯。

南島語族的語言高達 1200 種，相比漢語、英語可說是毫不遜色，可以說是雄霸海洋的偉大民族。其文化特色有屋架構築，常聽到的有石板屋、以竹、茅草、檜木搭建半穴居，火耕，在生活習慣上都是依靠大自然所擁有的。

  • 清領時期：
  • 封山：土牛番界
  • 開山撫番：破庄滅族、喪身滅社
  • 日治時期：
  • 理蕃：政壓、同化、皇民化

從清領時期開始，密切地接觸外來的文化與新住民。分別在清領時期有所謂的封山，避免原住民和漢人之間的衝突，或者是作為怕漢人與原住民相結反清。

而到清領後期，開山撫番主要為開闢道路，積極地經營與原住民之間的關係。其中當時最有名的是開拓的道路－八通關古道。而在隨後的日治時期也受到所謂的理番，也就是霧社事件發生的時機點，關於細節可以在電影賽德克拉萊中看到。

  • 國民政府～
    認為「 山地同胞 」遲早會被同化為與一般的漢人無異，當時並不認為原住民是個問題。如果是種不正視其存在，落入一種傲慢態度。
    • 「民族自決」
      人民可以自由決定他們的政治地位，並自由謀求他們的經濟、社會和文化的發展。對於 現代國際體系 中，處理原住民事務的原則。
    • 「原住民族基本法」
      為保障原住民族基本權利，促進原住民族生存發展，建立共存共榮之族群關係。 落實不佳 。
    • 「原住民族政策白皮書」
      民國 99 年擬定， 更凸顯漢人與原住民之間的差異 。

在國民政府遷台後，民生問題就越來越受到漢人所掌管。

一開始認為 山地同胞 ，光是這一 同胞 一詞就帶有一點點的認同感，即使原住民不這麼認為，所以並不認為原住民是個問題。這表示著什麼？如果是種不正視其存在，落入一種傲慢態度是有可能的，而不去認為是問題，也帶有一點多元文化的精神。

在 民族自決 一詞出現後，對於現代的國際體系中，民族自決對於處理原住民事務的原則，政府也依序做了幾項政策。其中「原住民族基本法」為保障原住民族基本權利，促進原住民族生存發展，建立共存共榮之族群關係。雖然基本法定義的早，但是實施上仍然沒有執行力。

而隨後在 99 年擬定「原住民族政策白皮書」，更加地區分了漢人與原住民之間的差異，也有人說擴大 漢人沙文主義 的優越意識。

為什麼這一段時間會開始注意到原住民？甚至還分給它們原住民身分？其一，為了顯示出自己國家的文明，按照民族自決的原則實施政策，其二，更可以做為執政者的政見，這一無傷大雅的政策，不就是撥點尊重認同給他們，就能討好他們，更能獲得大量的支持。這也是一種 操弄手法 ，正如同支持同志婚姻於美國，可以作為一個文明的現象。

做一點不同的舉動，就覺得文明就可以顯得更高尚。

文明衝突－蘭嶼的小七決策

  • 漢人身分－劉克襄說道
    「慎思啊！小七，別繼核廢料後，又成為漢人帶給蘭嶼的另一個惡靈！」認為小七進來勢必以物質思維、貨幣數據，取代傳統以物分享、回饋與共勞的社會結構。
  • 在「了解對方」之後，才能共同決定別人的前途，但網路自由、資訊豐富不足作為「了解對方」

小七便利商店在蘭嶼開店的時候，引起相當多的討論，其實小七一開始也不是漢人社會中的一部分，歷經好幾年的虧損才發展到現在的受人歡迎，一開始不被看好的 7-11 引入台灣，正好比討論 7-11 是否引入蘭嶼。

在這場討論中，主要由漢人身分的專家 ? 與當地人相互對話，其中以漢人身分的劉克襄為例

劉克襄：「蘭嶼和其他離島差異甚大，它並不屬於漢人社會。反而擁有一個獨特的海洋生活體系，自成複雜的生態生命觀，以及豐厚的自然知識庫。當其菲律賓的近親大量流失舊有智慧時，他們仍完整保留，足堪為世界罕見的文化遺產。可它又是如此地脆弱，如其地理位置，被台灣緊緊宰治著命運。假如小七進駐了，一定很快就會擊跨所有雜貨舖，讓它們大量消失。小七能像達悟人經營的雜貨舖那樣可以賖賬？小七的門口可以賣飛魚乾？小七會讓自己做為交換村民生活資訊的平台？小七能以企業公益的身份，融入達悟族文化？」

不屬於漢人社會又能表示什麼，罕見的文化遺產總是這麼脆弱嗎？自認漢人文化內的產物一定會取代他們原有的文化，不就是一種自視甚高的態度？以為自己所處的文明，一定可以勝過於蘭嶼文化。害怕這罕見文化遺產的消失，卻也認為自己的文化甚高，保留這文化的意義不就是做給別人看嗎？過度「替別人著想」的行為，好比要特別做出與別人不同的行為，強調自己的 階級 比較高。

過度！就是！多管閒事！

難道，漢人的眼中的蘭嶼只有碧海藍天、獨木舟的美麗風景才算是蘭嶼？而 7-11 在蘭嶼開設就這麼不堪入目嗎？

外來人希望遠離都市叢林，來蘭嶼看到的是一派天然不受現代文明汙染的淨土，但蘭嶼人本身是不是覺得有家便利商店會方便許多呢？究竟這塊海天淨土是為都市人凍結的擺飾，還是當地人必須俯仰其間的生活空間？

本島也有很多台灣美景，也在周圍建設不少旅宿啊，針對蘭嶼就不予許這樣。對蘭嶼的不信任感，是認為他們沒辦法處理這樣的文明不是，又是在強調自己有多文明了。

助教： 把大自然跟鄉土美化，「從開元港往北，沿環島公路接近朗島村時，海邊出現一間白浪板屋的雜貨舖，叫達悟超商。超商前設有一蘭嶼傳統涼亭，四五個部落的女人坐在上面吹風聊天。」然而這種美化也是不切實際的，因為他無視了當地的困苦與基本建設的匱乏。

題外話：我們可以從資訊中認識他們蘭嶼人，他們也能藉由 7-11 了解外界所有的文化資訊不是嗎 (蘭嶼小孩想吃薯條，卻不知其何物)？蘭嶼目前真的有小七，也在前一陣子九月多時，遇到鳳凰颱風，甚至便利商店的貨架被一掃而空。

  • 「一定要把我們當作稀有動物觀賞嗎？」
    文明的傲慢 ？價值不由外地人決定。
  • 關於擔憂的文化困境
    蘭嶼人表示「長久文化習慣難道經不起外來入侵？如果真經不起，可見也沒多大特色。」
  • 比起核廢料場，小七來得有誠意，何時何地到來都有說明。只有小七有文化考量，放置核廢料造成的利益關係要從何談起，決策來源仍屬於佔有多數的文化。

上山種芋頭、出海捉飛魚，這些都是蘭嶼雅美人長久以來的生活秩序。

蘭嶼小孩過得每天吃山珍海味的日子，文化習慣相當長久，有脆弱到無法自己解決外來的入侵嗎？
在蘭嶼人口中道出「一定要把我們當作稀有動物觀賞嗎？」看出，漢人的專家們不斷地評估與討論，這外界的聲音已經讓他們覺得他們成為稀有動物的存在。

這不就是傲慢嗎？要求別的文明要過什麼樣的生活、擁有什麼樣的資源 …蘭嶼人當然要小心謹慎，找出最有利於自己的生存策略，但把他們想得這麼弱，其實也是一種漢人中心的自我膨脹。

總之，是否會造成困境，還是蘭嶼人最清楚。歡不歡迎「小七」的問題，留給當地人來評論吧！

小七登陸蘭嶼雖然只為當地帶來 12 個職員的工作機會，但比起台電核廢料場，至少明明白白告訴社會：「8月8日準時開幕」，不會掛羊頭賣狗肉，硬是將核廢料場扯成魚罐頭工廠。1 萬家小七對蘭嶼的傷害，也比不上一個核廢料廠。

因一個小七引起的討論比不上過往的核廢料廠，這利益之間到底要怎麼批判，原來他們的特色價值的利益必須要因為漢人而存在？放置核廢料的利益關係又要從何談起？不正也是原住民才 50 多萬人，佔多數的漢人政府的決策，有如大我天朝般，接受恩賜吧！

說台灣多元文化，並不代表多元文化的精神在於必須要有多區隔，這區隔更顯示階級高下之分，掩飾主流文化的支配現象而已！

  • 文化入侵、破壞早已不是第一例，民宿增加、核廢料、台東農會超市 … 等，那些有造成破壞的部分，最清楚的還是當地人。
  • 漢人身分－劉克襄
    「我是為你好」論證下提供單方面意見
  • 在這事件，可以提供意見，但絕非價值的指導者。

其實台東農會超市早就進軍蘭嶼了，但至今並沒有破壞達悟族的飛魚季，或是拼板舟文化，傳統文化顯然並不會因為便利超商或超市而受到影響。

「有空調又明亮的便利商店開在陳舊灰暗的雜貨店附近，搶走客人」這個畫面對於身為現任都市人的我們來說，實在是太具體、太吸睛。作為「文化破壞」的亮點，它可能讓我們難以察覺蘭嶼文化改變的其他面相。

一位達悟大哥說：「其實最大的破壞，當觀光客大批湧入的時候，就是一種破壞了。」

在這事件，可以提供意見，但絕非價值的指導者。「我是為你好」論證，是基於對方的福祉出發，為對方指出該走的方向。在於萬一對方表示異議，論者會如何回應。

文化交流－豐年祭典的尊重

  • 阿美族豐年祭有 文化傳承 的功能，同時作為感謝上蒼保佑風調雨順，感念祖靈庇護，代表尊老敬祖 族性
  • 部落的祭典有其莊嚴與神聖性，並非官方觀光、酬庸的商品，這並非 文化交流 的本意。
  • 「有意想參訪的朋友，帶著尊重的心，我們很歡迎，帶著 高姿態 的心，獵刀很快會吻你的脖子。」－ 「豐年祭不是給觀光客看」　張震嶽發言延燒　

觀光客進入部落參觀慶典時要尊重現場的指導，不要干擾和破壞，應該秉持尊重的態度，部落的祭典不是活動，有其莊嚴和神聖性，觀光客不要因為要拍照而影響祭典進行；可以將祭典和活動分開，讓遊客可以參加活動，但是原住民也可以保有祭典的原貌，不受干擾。

大張旗鼓地為各縣市原住民宣傳他們的活動，活動與祭典之間界線越來越模糊，本意也越來越偏離。記住的是祭典並非官方觀光、酬庸的商品，這並非文化交流的本意！

在花蓮，近幾年興起的後山王東崑萁，為花蓮縣帶來龐大的觀光財。舉辦一系列的活動，展現花蓮縣特色，也因此在舉辦各種活動中給予金錢上的補助。

當然原住民活動是不可缺的一角，辦任何活動都有錢賺，甚至每一次辦活動非得要召喚外地族人回來不可，在用金錢補助活動上，是否呈現漢人認為原住民的豐年祭文化具有投資價值，是一個不錯的消費商品，花點錢，就能帶來更多的周邊利益。

他們的特色，被用「多元文化」的藉口，放置在觀光業的一環中，更是剝奪他們對自我祭典的掌握權，難道必須要因為一張海報上的活動時間而運行傳統祭典？

在某一次的活動中，不小心越界，產生出 要求舉辦祭典­的阿美族青年交互蹲跳 的荒唐行為，原住民祭典一直以來都只有年長者可以命令年輕人，沒有權力地位的身分概念，身為協辦的政府，也不能隨意地命令它們。

其實這種荒唐事情不只一例，曾經也舉辦花蓮原住民族聯合豐年祭，以文化交流的本意，召集來自大陸許多少數民族進行交流，結果大陸少路民族卻占了大多數的表演行程，中間還有特地安排 “縣長進場”，大約 10 來分鐘，難不成「縣長爬進場？」網友如此戲稱，這時間堪比一個表演節目。

當然這樣想有點對這件事情全方面的恐懼，文化交流只是按著流程跑這麼簡單？活動契機也許不錯，但是彈性限制仍有待考量。

情感受限－布農族打耳祭

  • 打耳祭從早期獵鹿、山豬，因獵物減少而以抓豬增加祭典娛樂，祭典對於他們具有團結精神的教育意義。
  • 外人情感門檻限縮下 ，原住民行為受到外部約束。
  • 立法院要求取消抓豬比賽，否則砍原民會預算，往後射耳祭活動也不予補助。「射耳祭禁抓豬 布農族抗議」

布農族早期與山林為伍，是最懂得環保及愛護動物的民族。因獵物減少而以抓豬增加祭典娛樂，其實他們一開始的活動並不是抓豬，而是真的拿弓箭射獵物的耳朵。

抓豬競賽有一定規則，一個村落抓一頭豬，時間最短的優勝，裁判看過後，這頭豬就可以扛回各部落與村民共享。抓豬不僅在訓練年輕人抓豬技巧，更重要的是傳承團結和分享的文化。

只因為政府無法看它們做出這樣野蠻的行為，就這麼限制它們。看不下去的情感，也正表示外人情感門檻限縮下，原住民連帶地受到牽連。以 Elias 的話來說而言，這種看到別人做出的行為，心中會感到難堪，用嬌貴引起的「不舒服感」，因為台灣各個角落發出「感到不舒服」，所以它們就野蠻、不文明了嗎？

當然並不是，這種極端的情感驗證了強烈追求自己階級的優越性！

  • 原住民抓豬活動、漢人供神豬，為何單獨原住民抓豬受到限制？習慣幕後隔絕的漢人文化。
    *「我們原住民的祭典不該被保留，很野蠻？那你們供神豬的就是文化？豬塞餵成那樣然後殺了供祭所以是高尚的哦？」-「射耳祭抓豬比賽被禁　紀曉君：你們的供神豬就是文化？」
  • 原住民出國表演，會被稱作 台灣之光 ；但想維護傳統儀式時，卻被指成是 野蠻 的行為。

原住民抓豬活動、漢人供神豬，為何單獨原住民抓豬受到限制？習慣幕後隔絕的漢人文化。漢人特地把打耳祭的抓豬活動拿來說嘴，就是故意挑剔的行為！

紀曉君在臉書砲轟：「我們原住民的祭典不該被保留，很野蠻？那你們供神豬的就是文化？豬塞餵成那樣然後殺了供祭所以是高尚的哦？」到底是做出別的文明所期盼的行為？還是遵循自我文明的規則發展下來？身為一個文明成長下的人，要求別的文明長成什麼樣子就是一種傲慢！

近乎病態的愛護動物 是否是崇洋媚外、為了向西方世界 (ex. 綠色和平組織) 表示我們跟他們站在同一陣線、跟他們同樣等級，而產生之好似討好、尊崇國際制度的行動，為了表示我們與西方世界一樣進步文明而寧願拋棄自己的傳統也要高規格要求 愛護動物 ？

助教： 這些傳統慶典不再具有原住民社會連繫感情與文化傳承的意義，而變成可以被漢人社會消費的商品，當這個「豐年祭」或「射耳祭」的商品形象因為「過度野蠻、血腥」，不符合漢人的文明價值(也就是失去賣相，沒辦法被消費時)我們就不再講「尊重原住民的多元文化」，而是要他們「取消抓豬比賽」。

其他地區的原住民

  • 不同地區的原住民與其處境發展
    • 日本北海道愛奴人 (Ainu)
    • 美洲印第安人
    • 澳洲土著－失竊的一代 (Stolen Generations)
    • 紐西蘭毛利人

在各國也都有原住民的存在，即使是民族精神很強烈的日本人，也存在北海道的愛奴人，直到 1986 年前都否認他們的存在。藉由很多電影宣傳、強勢文明的歷史經歷，我們也才知道有美洲印第安人（分支馬雅、阿茲特克、印加文明）、澳洲土著、紐西蘭毛利人 … 等。到底怎麼樣才算是原住民？有人認為具有演化化石才算是原住民，那事實上很多文明化石存證相當困難，這樣就稱不上原住民了？

其他地區的原住民－愛奴人

  • 日本北海道與俄羅斯境內皆存在
  • 1869 年 (明治天皇) 「蝦夷地」更名「北海道」
  • 1899 年「北海道舊土人保護法」──制度化歧視
  • 1992 年 12 月聯合國集會
    日本政府：「享有自己的文化，實踐自己的宗教，以及使用自己的語言是被我國憲法所保障的每個人的權利。但在聯合國《人權規約》中規定意義的少數民族，在我國不存在。」
  • 2008 年正式被列為日本原住民族

1869 年，愛奴人居住地被正式納入日本的行政範圍，同時被命名為習慣的「北海道」，被政府沒收的土地成了新住民的居地，逐漸地外來人口增加，使得愛奴人真的變成 “少數民族”。

隔了 30 年後，才制定對於它們的保護法，也與之前講的類似，制訂保護法等同於凸顯彼此之間的差異，是一種制度化歧視。再隔 100 年後，愛奴人在聯合國集會發表演說，要求制訂新法，但日本政府卻採用 “我國憲法” 保障每個人的權利回絕，「我國」這一詞對於少數民族存在嗎？真的是同一國嗎？「我國」這一詞呈現甚麼樣的態度？

再中間過程中，日本政府雖然修訂保護法，但是落實情況並不理想，日本長時間以「單一民族國家」的姿態現身，純粹也許很重要，更是一個進步的文明象徵。在近 2008 年，才正式將愛奴人為「日本原住民族」任何人權保護、社會地位、民族文化等內容才受到保障。

仔細想想，我們漢人對於台灣原住民的接觸與認知還不算晚。

其他地區的原住民－澳洲土著

  • 「失竊的一代 (Stolen Generations) 」
  • 1909 年至 1969 年年間（部份地方持續至 1970 年代）實行之「同化政策」長達 60 年。
  • 兒童被永久性地帶往白人家庭或政府機構「白化」自身語言和文化被剝奪。
  • 1997 年總理 約翰‧霍華德 (John Winston Howard)：「這是上一代政府的錯」
  • 2008 年 2 月 13 日，總理 陸克文(Kevin Michael Rudd) 在澳洲國會上正式道歉，承諾改善原住民 生活水平 ，提高 識字率 、平均壽命 … 等。

而澳洲土著的情況也類似，長達 60 年的同化政策，認為他們「低賤無知」及「將會消失」，必須同化，將原住民兒童永久性帶到白人家庭下照顧，迫使它們忘記原本的語言與文化。到了 1997 年時，以「這是上一代政府的錯」為理由拒絕道歉，再隔 10 年，才正式向原住民道歉。並且承諾改善當今原住民的 生活水平 。

所謂的 生活水平 又是用什麼方式？從發言的原文中看到，任何在政府機構、兒童照料的資源的提升，真的是得以求償了嗎？這一點值得省思。原住民有要求 平等 嗎？而平等的方式是用補償與另一個文明站在同一起點？

結語

  • 「原住民的問題其實是 新住民 的問題」
  • 「當沒有原住民問題時，就是沒原住民詞的時候」

「原住民的問題其實是新住民的問題」也許只是先來後到的概念，但也絕非這麼簡單，之前海協會長來台參訪時，說「中華民族同根」，原住民鬧出一句話「我們是南島語系的，誰跟你中華民族同一根，我這根跟你那根又不一樣！亂扯！」不同根的幽默言論。新住民相較於原住民晚到，因為彼此之間的文化差異，必須用原住民、新住民區隔開來，為什麼要區隔？一種認同感的需要，但這種差異性不應講究高下之分，也不該視為一個問題。

當初國民政府對山地同胞的「不視為問題所在」，最理想的方式，當然是不視為問題，並作為公民的一份子，相互協調之間的關係、經濟、資源分配。但現實中是很難達成的目標，假使一個人具有多重身分、國籍時，這顯然會有些問題，認同感應放置哪一方？即使只有單一身分的原住民，彼此之間仍有地位之差等差異，而受到不同的對待。

當我們不去討論原住民問題時，回過頭來看的就是彼此之間的階級、其他差異問題，當遇到一個更嚴重的問題時，很容易將破碎細小的差異忽略而靠攏在一起，反之當問題消失時，則因之前的靠攏引起衝突，因衝突而分化。因果關係難分難解。

報告心得

公平、正義、資本、中國

箱子

箱子

這次報告的困難度之高，感謝陳思瑀助教的指導。這份報告在兩三度討論完全被推翻重來，其一論點的背景知識不足，其二缺少足夠的批判立論，其三論點偏頗不全。本組沒有此類型的專業，以多數理工人，使用習慣的二分法在此報告相當危險。

無論如何，這篇報告應照著 Huntington 和 Elias 的論調下去觀察較為妥當。不乏會缺少多方的歷史評論，而從現代批評的歷史逆推。最後淪為心得報告。

如果單純拿別人的資料來報告，缺少自我的評論或獨特的闡述觀點，這隨處可得的資料，也不用上台報告。

日劇破案天才切利略－「事出必有因」，正是面對自己不熟識的事物時，採用的第一態度，當然根據自己的價值觀所產生的評論只好先往內心世界藏了。

中間還有談到人情網路的重要性，看人臉色的內心世界的建造，比起一學期的通識小組報告，顧及四年的人情網路的系上活動更為重要不是。而且，要求不同系的同學一起來做報告，這種要求別的文明做出我們文明所期盼的行為，就是一種傲慢。

Read More +
解題區/解題區 - 其他題目

2015 Facebook Hacker Cup 資格賽

［2015 Facebook Hacker Cup 資格賽］贖罪篇

windows 參賽，卡了一個 \r\n 問題，剛好有裝 git，使用以下指令做轉換

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt
  • Cooking the Books (15 points)

會計師要騙過稽查人員，可以把金融數值任意交換兩個位置上的數字，請問能交換得到的最大、最小值分別為何？並且數字不可起首為 0。

喵蛋，最簡單的這題 recover step 因 continue 指令而被忽略，窮舉兩個位置做交換，大部分可以看到寫法有 string compare, int compare，最方便是在字串下處理，接著看要轉數字或者直接用字典順序比較都行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    freopen("cooking_the_books.txt", "r", stdin);
    freopen("out.txt", "w+", stdout); 
    int testcase, cases = 0;
    char s[64];
    scanf("%d", &testcase);
    while (testcase--) {
        long long ret1, ret2, tmp;
        scanf("%s", s);
        sscanf(s, "%lld", &ret1);
        sscanf(s, "%lld", &ret2);
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                swap(s[i], s[j]);
                sscanf(s, "%lld", &tmp);
                if (s[0] != '0') { 
                    ret1 = min(ret1, tmp);
                    ret2 = max(ret2, tmp);
                } 
                swap(s[i], s[j]);
            }
        }
        printf("Case #%d: %lld %lld", ++cases, ret1, ret2);
        putchar('\n');
    }
    return 0;
}
  • New Year’s Resolution (30 points)

新年新希望，目標均衡飲食，要求蛋白質、澱粉、脂肪攝取剛好的量，挑選 n 個食物，只有不選、或者是只能一樣走。求是否能辦到？

在 n 不大的時候，套用 bitmask 窮舉最為方便。用 Dfs 搜索當然喜聞樂見，如果 n 很大，而要求的量很小，則可以使用三維 dp[P][C][F] 狀態來解決。如果要求倍數關係，而數量無限的話，可以轉換成幾何分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    freopen("new_years_resolution.txt", "r", stdin);
    freopen("out.txt", "w+", stdout); 
    int testcase, n, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int GP, GC, GF;
        int P[32], C[32], F[32];
        scanf("%d %d %d", &GP, &GC, &GF);
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &P[i], &C[i], &F[i]);
            
        int ret = 0;
        for (int i = (1<<n)-1; i >= 0 && !ret; i--) {
            int a = 0, b = 0, c = 0;
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1) {
                    a += P[j];
                    b += C[j];
                    c += F[j];
                }
            }
            ret |= a == GP && b == GC && c == GF;
        }
        printf("Case #%d: %s\n", ++cases, ret ? "yes" : "no");
    }
    return 0;
}
  • Laser Maze (55 points)

給予 2D 地圖，裡面的雷射裝置將會感應使用者的腳步，每踏一步則順時針換方向，並且發射出雷射，雷射只會因牆壁、雷射塔而被屏蔽，但是雷射跟雷射之間不會相消、折射。現在雷射裝置的起始方向各有不同，避開雷射，找最少步數抵達終點。(只能走上下左右四個方向，停留不能解決問題，雷射裝置因感測而行動。)

基礎的 Bfs，因為只有四個方向，根據時間做紀錄，每四次操作進行一個循環，則 int dist[time4][pos_x][pos_y]，考慮在哪一個 time mod 4 抵達某個位置。接下來麻煩的是檢查操作，檢查操作有兩種，其一，預處理每個時間下雷射發射，其二，從當前位置反搜索雷射光是否對著自己。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
char g[128][128];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dv[] = "<^>v";
int dist[4][128][128], n, m;
int valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}
char next(char c, int t) {
    static char v[] = "^>v<";
    for (int i = 0; i < 4; i++) {
        if (v[i] == c)
            return v[(i + t)%4];
    }
    assert(false);
}
int test(int t, int x, int y) {
    int tx, ty;
    for (int i = 0; i < 4; i++) {
        tx = x, ty = y;
        while (valid(tx, ty) && g[tx][ty] == '.')
            tx += dx[i], ty += dy[i];
        if (valid(tx, ty) && g[tx][ty] != '#') {
            char c = g[tx][ty];
            if (next(c, t) == dv[i])
                return 1;
//			printf("%c %c %d\n", next(g[tx][ty], t), dv[i], i);
        }
    }
    return 0;
}
void bfs() {
    memset(dist, 0, sizeof(dist));
    int sx, sy, ex, ey;
    int x, y, tx, ty, t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S')
                sx = i, sy = j, g[i][j] = '.';
            if (g[i][j] == 'G')
                ex = i, ey = j, g[i][j] = '.';
        }
    }
    dist[0][sx][sy] = 1;
    queue<int> X, Y, T;
    X.push(sx), Y.push(sy), T.push(0);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        t = T.front(), T.pop();
        int d = dist[t][x][y] + 1;
        if (x == ex && y == ey) {
            printf("%d\n", d - 2);
            return;
        }
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (!valid(tx, ty))
                continue;
            if (g[tx][ty] != '.')
                continue;
            if (test((t+1)%4, tx, ty))
                continue;
            if (dist[(t+1)%4][tx][ty] == 0) {
                dist[(t+1)%4][tx][ty] = d;
                X.push(tx), Y.push(ty), T.push((t+1)%4);
            }
        }
    }
    puts("impossible");
}
int main() {
    freopen("laser_maze.txt", "r", stdin);
    freopen("out.txt", "w+", stdout);
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", &g[i]);
        printf("Case #%d: ", ++cases);
        bfs();
    }
    return 0;
}
/*
999
2 5
##^##
S...G
2 6
###<##
S....G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G
*/
Read More +