Google Kickstart 2017 Round C题解

发表于 |

C轮感觉比校招笔试轮次的DE要简单点了，这次有四道题都很有意思。

A. Ambiguous Cipher

题目就是要解一个模意义下的线性方程。由于加减乘对模运算是封闭的，所以可以直接解。注意解下来的结果还要模一下26。
用numpy搞了一波，特判下奇异矩阵，对应无穷多解的情况。
AC代码

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
import numpy as np
import scipy

def is_invertible(a):
    return a.shape[0] == a.shape[1] and np.linalg.matrix_rank(a) == a.shape[0]

ff = open("1.txt")
T = int(ff.readline())

for cas in xrange(T):
    s = str(ff.readline()).strip("\n")
    l = map(lambda x: ord(x) - ord('A'), list(s))
    length = len(l)
    ans = ""
    if length == 2:
        ans = s[::-1]
    else:
        mat = [[0 for j in xrange(length)] for i in xrange(length)]
        mat[0][1] = 1
        mat[length-1][length-2] = 1
        for i in xrange(1, length - 1):
            mat[i][i-1] = 1
            mat[i][i+1] = 1
        M = np.array(mat, dtype = int)
        if is_invertible(M):
            b = np.array(l, dtype = int).reshape(length, 1)
            x = np.linalg.solve(M, b).ravel().tolist()
            x = map(int, x)
            x = map(lambda xx: xx % 26, x)
            ans = ''.join(map(lambda xx: chr(ord('A')+xx), x))
        else:
            ans = "AMBIGUOUS"
    print "Case #{}: {}".format(cas + 1, ans)

B. X Squared

一开始找规律觉得只要除了允许其中一行和一列拥有一个叉，其他的每个行列必须有且只有两个叉。结果果断WA了，对拍下看看

5
.X..X
...XX
XX...
..X..
X..X.

上面的这个样例输出 POSSIBLE，但实际上却是 IMPOSSIBLE 的，看来我的条件只是必要条件。还能加上啥条件呢？初等变换得到的矩阵都是等价的，不过看来这性质用不上。
然后发现之前的性质挖掘不彻底，事实上矩阵在任意行列互换后位于同行/列的元素依然位于同行/列，于是矩阵中一定存在两行中的两个 X 的距离是相等的。果断又 WA 了，后来发现不仅距离要相等，而且是要平行的。
AC代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream> 
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <functional>
#include "stdlib.h" 
#include "time.h"
#include <set>
#include <map>
#include <numeric>
#include <cctype>
#include <cmath>

#define INF 0x3f3f3f3f
const int MAXN = 201;
using namespace std;
#define LL long long
#define ULL unsigned long long
#define LD long double
typedef pair<int, int> pii;

char m[MAXN][MAXN];
int a[MAXN], b[MAXN], disa[MAXN][MAXN], disb[MAXN][MAXN];
char chs[MAXN];

int main() {
	int T, cas = 0;
	freopen("1.in", "r", stdin);
	freopen("1.out", "w+", stdout);
	scanf("%d", &T);
	while (T--) {
		cas++;
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%s", &(m[i]));
		}
		memset(a, 0, sizeof a);
		memset(b, 0, sizeof b);
		memset(disa, 0, sizeof disa);
		memset(disb, 0, sizeof disb);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (m[i][j] == 'X')
				{
					a[i] ++;
					b[j] ++;
				}
				else if (m[i][j] == '.'){
				}
			}
		}
		bool flag = true;
		bool sa = false, sb = false;
		for (int i = 0; i < n; i++)
		{
			if (a[i] == 2)
			{

			}
			else if (a[i] == 1 && !sa) {
				sa = true;
			}
			else {
				flag = false;
				break;
			}
			if (b[i] == 2)
			{

			}
			else if (b[i] == 1 && !sb) {
				sb = true;
			}
			else {
				flag = false;
				break;
			}
		}
		for (int i = 0; i < n; i++)
		{
			int first_j = -1, second_j = -1;
			for (int j = 0; j < n; j++)
			{
				if (m[i][j] == 'X' && first_j == -1)
				{
					first_j = j;
				}
				else if (m[i][j] == 'X' && second_j == -1)
				{
					second_j = j;
					break;
				}
			}
			if (second_j != -1)
			{
				int index = (second_j - first_j);
				disa[index][first_j] ++;
			}
		}
		for (int i = 0; i < n; i++)
		{
			int first_j = -1, second_j = -1;
			for (int j = 0; j < n; j++)
			{
				if (m[j][i] == 'X' && first_j == -1)
				{
					first_j = j;
				}
				else if (m[j][i] == 'X' && second_j == -1)
				{
					second_j = j;
					break;
				}
			}
			if (second_j != -1)
			{
				int index = (second_j - first_j);
				disb[index][first_j] ++;
			}
		}
		for (int i = 1; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (disa[i][j] % 2 != 0)
				{
					flag = false;
					break;
				}
				else if (disb[i][j] % 2 != 0)
				{
					flag = false;
					break;
				}
			}
		}
		if (flag)
		{
			printf("Case #%d: POSSIBLE\n", cas);
		}
		else {
			printf("Case #%d: IMPOSSIBLE\n", cas);
		}
	}
	return 0;
}

C. Magical Thinking

小数据$N=1$，感觉是送分啊。直接看大数据，$N \le 2$。想了一会儿方程，发现是DP。
其实思路很简单，$dp[i][r1][r2]$表示到第$i$个题目前同学1对了$r1$条且同学2对了$r2$条时自己可能获得的最多分数。根据$N$取值可以分别分4、2种。而得分$s[0..1]$的作用就是当$r1 \ge s[0]$时他这条就不能再对了。
但是代码在小数据上都卡了很久。

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <iostream> 
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <functional>
#include "stdlib.h" 
#include "time.h"
#include <set>
#include <map>
#include <numeric>
#include <cctype>
#include <cmath>

#define INF 0x3f3f3f3f
const int MAXN = 55;
using namespace std;
#define LL long long
#define ULL unsigned long long
#define LD long double
typedef pair<int, int> pii;


char a[MAXN][MAXN];
int s[MAXN];
int dp[MAXN][MAXN][MAXN];
int dpans[MAXN];
int n, q;
int dp2[MAXN][MAXN];

void solve1() {
	char * me = a[n];
	memset(dp, 0, sizeof dp);
	memset(dpans, 0, sizeof dpans);
	for (int i = 0; i < q; i++)
	{
		dpans[i + 1] = dpans[i];
		for (int r1 = s[0]; r1 >= 0; r1--)
		{
			for (int r2 = s[1]; r2 >= 0; r2--)
			{
				if (me[i] == a[0][i] && me[i] == a[1][i])
				{
					int all_right = dp[i][r1][r2] + 1;
					int all_wrong = dp[i][r1][r2];
					dp[i + 1][r1][r2] = max(all_right, dp[i + 1][r1][r2]);
					dpans[i + 1] = max(all_right, dpans[i + 1]);
					if (r1 > 0 && r2 > 0)
					{
						dpans[i + 1] = max(all_wrong, dpans[i + 1]);
						dp[i + 1][r1 - 1][r2 - 1] = max(all_wrong, dp[i + 1][r1 - 1][r2 - 1]);
					}
				}
				else if (me[i] == a[0][i])
				{
					int me_right = dp[i][r1][r2] + 1; // r2 is wrong
					int me_wrong = dp[i][r1][r2]; // r1 and me are wrong
					if (r2 > 0)
					{
						dpans[i + 1] = max(me_right, dpans[i + 1]);
						dp[i + 1][r1][r2 - 1] = max(me_right, dp[i + 1][r1][r2 - 1]);
					}
					if (r1 > 0)
					{
						dpans[i + 1] = max(me_wrong, dpans[i + 1]);
						dp[i + 1][r1 - 1][r2] = max(me_wrong, dp[i + 1][r1 - 1][r2]);
					}
				}
				else if (me[i] == a[1][i])
				{
					int me_right = dp[i][r1][r2] + 1; // r1 is wrong
					int me_wrong = dp[i][r1][r2]; // r2 and me are wrong
					if (r2 > 0)
					{
						dp[i + 1][r1][r2 - 1] = max(me_wrong, dp[i + 1][r1][r2 - 1]);
						dpans[i + 1] = max(me_wrong, dpans[i + 1]);
					}
					if (r1 > 0)
					{
						dpans[i + 1] = max(me_right, dpans[i + 1]);
						dp[i + 1][r1 - 1][r2] = max(me_right, dp[i + 1][r1 - 1][r2]);
					}
				}
			}
		}
	}
}

int solve0() {
	char * me = a[n];
	memset(dp2, -1, sizeof dp2);
	int ans = 0;
	for (int r1 = 0; r1 <= s[0]; r1++)
	{
		dp2[0][r1] = 0;
	}
	for (int i = 0; i < q; i++)
	{
		printf("======= %d =======\n", i);
		for (int r1 = s[0]; r1 >= 0; r1--)
		{
			int me_right;
			int me_wrong;
			if (dp2[i][r1] != -1)
			{
				me_right = dp2[i][r1] + 1; // me right
				me_wrong = dp2[i][r1]; // me wrong
			}
			else {
				continue;
			}
			int right_r1 = r1 > 0 ? r1 - 1 : 0;
			if (me[i] == a[0][i])
			{
				if (r1 > 0)
				{
					// he can right
					dp2[i + 1][right_r1] = max(me_right, dp2[i + 1][right_r1]);
					if (i + 1 == q && right_r1 == 0) ans = max(ans, dp2[i + 1][right_r1]);
					printf("EQ R dp2[%d][%d]=%d %s\n", i + 1, right_r1, dp2[i + 1][right_r1], right_r1 == 0 ? "OK": "NO");
				}
				else {
					// he can't right
				}
				// he can always wrong
				dp2[i + 1][r1] = max(me_wrong, dp2[i + 1][r1]);
				if (i + 1 == q && r1 == 0) ans = max(ans, dp2[i + 1][r1]);
				printf("EQ W dp2[%d][%d]=%d %s\n", i + 1, r1, dp2[i + 1][r1], r1 == 0 ? "OK" : "NO");
			}
			else
			{
				if (r1 > 0)
				{
					// he can right
					dp2[i + 1][right_r1] = max(me_wrong, dp2[i + 1][right_r1]);
					if (i + 1 == q && right_r1 == 0) ans = max(ans, dp2[i + 1][right_r1]);
					printf("NE R dp2[%d][%d]=%d %s\n", i + 1, right_r1, dp2[i + 1][right_r1], right_r1 == 0 ? "OK" : "NO");
				}
				else {
					// he can't right
				}
				// he can always wrong
				dp2[i + 1][r1] = max(me_right, dp2[i + 1][r1]);
				if (i + 1 == q && r1 == 0) ans = max(ans, dp2[i + 1][r1]);
				printf("NE W dp2[%d][%d]=%d %s\n", i + 1, r1, dp2[i + 1][r1], r1 == 0 ? "OK" : "NO");
			}

		}
	}
	return ans;
}

// http://paste.ubuntu.com/25974690/
int main() {
	int T, cas = 0;
	freopen("1.in", "r", stdin);
	//freopen("1.out", "w+", stdout);
	scanf("%d", &T);
	while (T--) {
		cas++;
		scanf("%d%d", &n, &q);
		for (int i = 0; i < n; i++)
		{
			scanf("%s", &(a[i]));
		}
		scanf("%s", &(a[n]));
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &s[i]);
		}
		int ans;
		if (n == 2)
		{
			solve1();
			ans = dpans[q];;
		}
		else {
			ans = solve0();
		} 
		printf("Case #%d: %d\n", cas, ans);
	}
	return 0;
}

最后发现原因是出现了dp[2][6]这样的值，为什么进行到2的时候能对6个呢？将里面r1的循环改成了r1 <= min(s[0], i)，就AC了。
AC代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <iostream> 
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <functional>
#include "stdlib.h" 
#include "time.h"
#include <set>
#include <map>
#include <numeric>
#include <cctype>
#include <cmath>

#define INF 0x3f3f3f3f
const int MAXN = 55;
using namespace std;
#define LL long long
#define ULL unsigned long long
#define LD long double
typedef pair<int, int> pii;
#define IMP(X, Y) X = max(X, Y)


char a[MAXN][MAXN];
int s[MAXN];
int dp[MAXN][MAXN][MAXN];
int n, q;
int dp2[MAXN][MAXN];

#define IMP(X, Y) X = max(X, Y)

int solve1() {
	char * me = a[n];
	memset(dp, 0, sizeof dp);
	int ans = 0;
	for (int i = 0; i < q; i++)
	{
		//printf("======= %d =======\n", i);
		for (int r1 = 0; r1 <= min(s[0], i); r1++)
		{
			for (int r2 = 0; r2 <= min(s[1], i); r2++)
			{
				int me_right = dp[i][r1][r2] + 1;
				int me_wrong = dp[i][r1][r2];
				if (me[i] == a[0][i] && me[i] == a[1][i])
				{
					if (r1 < s[0] && r2 < s[1])
					{
						// all can right
						IMP(dp[i + 1][r1 + 1][r2 + 1], me_right);
						if (i + 1 == q && r1 + 1 == s[0] && r2 + 1 == s[1]) IMP(ans, dp[i + 1][r1 + 1][r2 + 1]);
						//printf("EQ[1,2] R dp[%d][%d][%d]=%d %s\n", i + 1, r1 + 1, r2 + 1, dp[i + 1][r1 + 1][r2 + 1], r1 + 1 == s[0] && r2 + 1 == s[1] ? "[OK]" : "[NO]");
					}
					else {
						// all can't right
					}
					// all can always wrong
					IMP(dp[i + 1][r1][r2], me_wrong);
					if (i + 1 == q && r1  == s[0] && r2  == s[1]) IMP(ans, dp[i + 1][r1 ][r2 ]);
					//printf("EQ[1,2] W dp[%d][%d][%d]=%d %s\n", i + 1, r1 , r2,  dp[i + 1][r1 ][r2 ], r1  == s[0] && r2  == s[1] ? "[OK]" : "[NO]");
				}
				else if (me[i] == a[0][i])
				{
					// r1 == me
					if (r2 < s[1])
					{
						// r2 can right
						IMP(dp[i + 1][r1][r2 + 1], me_wrong);
						if (i + 1 == q && r1 == s[0] && r2 + 1 == s[1]) IMP(ans, dp[i + 1][r1][r2 + 1]);
						//printf("EQ[1] R dp[%d][%d][%d]=%d %s\n", i + 1, r1 , r2 + 1, dp[i + 1][r1][r2 + 1], r1 == s[0] && r2 + 1 == s[1] ? "[OK]" : "[NO]");
					}
					if (r1 < s[0])
					{
						// r1 and me can right
						IMP(dp[i + 1][r1 + 1][r2], me_right);
						if (i + 1 == q && r1 + 1 == s[0] && r2 == s[1]) IMP(ans, dp[i + 1][r1 + 1][r2]);
						//printf("EQ[1] W dp[%d][%d][%d]=%d %s\n", i + 1, r1 + 1, r2 , dp[i + 1][r1 + 1][r2], r1 + 1 == s[0] && r2  == s[1] ? "[OK]" : "[NO]");
					}
				}
				else if (me[i] == a[1][i])
				{
					// r2 == me
					if (r2 < s[1])
					{
						// r2 and me can right
						IMP(dp[i + 1][r1][r2 + 1], me_right);
						if (i + 1 == q && r1 == s[0] && r2 + 1 == s[1]) IMP(ans, dp[i + 1][r1][r2 + 1]);
						//printf("EQ[2] R dp[%d][%d][%d]=%d %s\n", i + 1, r1 , r2 + 1, dp[i + 1][r1 ][r2 + 1], r1  == s[0] && r2 + 1 == s[1] ? "[OK]" : "[NO]");
					}
					if (r1 < s[0])
					{
						// r1 can right
						IMP(dp[i + 1][r1 + 1][r2], me_wrong);
						if (i + 1 == q && r1 + 1 == s[0] && r2  == s[1]) IMP(ans, dp[i + 1][r1 + 1][r2 ]);
						//printf("EQ[2] W dp[%d][%d][%d]=%d %s\n", i + 1, r1 + 1, r2 , dp[i + 1][r1 + 1][r2 ], r1 + 1 == s[0] && r2  == s[1] ? "[OK]" : "[NO]");
					}
				}
				else {
					// r1 == r2 != me
					if (r1 < s[0] && r2 < s[1])
					{
						// they can right
						IMP(dp[i + 1][r1 + 1][r2 + 1], me_wrong);
						if (i + 1 == q && r1 + 1 == s[0] && r2 + 1 == s[1]) IMP(ans, dp[i + 1][r1 + 1][r2 + 1]);
						//printf("EQ[] W dp[%d][%d][%d]=%d %s\n", i + 1, r1 + 1, r2 + 1, dp[i + 1][r1 + 1][r2 + 1], r1 + 1 == s[0] && r2 + 1 == s[1] ? "[OK]" : "[NO]");
					}
					else {
						// they can't right
					}
					// they can always wrong
					IMP(dp[i + 1][r1][r2], me_right);
					if (i + 1 == q && r1 == s[0] && r2 == s[1]) IMP(ans, dp[i + 1][r1][r2]);
					//printf("EQ[] R dp[%d][%d][%d]=%d %s\n", i + 1, r1, r2, dp[i + 1][r1][r2], r1 == s[0] && r2 == s[1] ? "[OK]" : "[NO]");
				}
			}
		}
	}
	return ans;
}

int solve0() {
	char * me = a[n];
	memset(dp2, 0, sizeof dp2);
	int ans = 0;
	for (int r1 = 0; r1 <= s[0]; r1++)
	{
		dp2[0][r1] = 0;
	}
	for (int i = 0; i < q; i++)
	{
		//printf("======= %d =======\n", i);
		for (int r1 = 0; r1 <= min(s[0], i); r1++)
		{
			int me_right;
			int me_wrong;
			me_right = dp2[i][r1] + 1; // me right
			me_wrong = dp2[i][r1]; // me wrong

			if (me[i] == a[0][i])
			{
				if (r1 < s[0])
				{
					// he can right
					IMP(dp2[i + 1][r1 + 1], me_right); 
					if (i + 1 == q && r1 + 1 == s[0]) IMP(ans, dp2[i + 1][r1 + 1]);
					//printf("EQ R dp2[%d][%d]=%d %s\n", i + 1, r1 + 1, dp2[i + 1][r1 + 1], r1 + 1 == s[0] ? "OK" : "NO");
				}
				else {
					// he can't right
				}
				// he can always wrong
				IMP(dp2[i + 1][r1], me_wrong);
				if (i + 1 == q && r1 == s[0]) IMP(ans, dp2[i + 1][r1]);
				//printf("EQ W dp2[%d][%d]=%d %s\n", i + 1, r1, dp2[i + 1][r1], r1 == s[0] ? "OK" : "NO");
			}
			else
			{
				if (r1 < s[0])
				{
					// he can right
					IMP(dp2[i + 1][r1 + 1], me_wrong);
					if (i + 1 == q && r1 + 1 == s[0]) IMP(ans, dp2[i + 1][r1 + 1]);
					//printf("NE R dp2[%d][%d]=%d %s\n", i + 1, r1 + 1, dp2[i + 1][r1 + 1], r1 + 1 == s[0] ? "OK" : "NO");
				}
				else {
					// he can't right
				}
				// he can always wrong
				IMP(dp2[i + 1][r1], me_right);
				if (i + 1 == q && r1 == s[0]) IMP(ans, dp2[i + 1][r1]);
				//printf("NE W dp2[%d][%d]=%d %s\n", i + 1, r1, dp2[i + 1][r1], r1 == s[0] ? "OK" : "NO");
			}

		}
	}
	return ans;
}

// http://paste.ubuntu.com/25974690/
// http://paste.ubuntu.com/25975070/
int main() {
	int T, cas = 0;
	freopen("1.in", "r", stdin);
	freopen("1.out", "w+", stdout);
	scanf("%d", &T);
	while (T--) {
		cas++;
		scanf("%d%d", &n, &q);
		for (int i = 0; i < n; i++)
		{
			scanf("%s", &(a[i]));
		}
		scanf("%s", &(a[n]));
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &s[i]);
		}
		int ans;
		if (n == 2)
		{
			ans = solve1();
		}
		else {
			ans = solve0();
		} 
		printf("Case #%d: %d\n", cas, ans);
	}
	return 0;
}

D. The 4M Corporation