Checkpoint
数学の問題。パスカルの三角形を使って解きました。下のコードでは、len[i]に最短路のパターン数がiになる場合における始点-終点間のマンハッタン距離の最小値を格納しています。len[]が分かれば、答えはlen[j] + len[S/j]の最小値です（jはSの約数）。
const int MAX = 10000000;
const int INF = 100000000;
int comb[2][10000];
int len[MAX+1];
void solve() {
for (int i = 0; i <= MAX; i++)
len[i] = i;
memset(comb, 0, sizeof(comb));
comb[0][0] = 1;
for (int i = 0; i < 10000; i++) {
int now = i&1;
int next = (i+1)&1;
if (i > 0) {
for (int j = 0; j <= i; j++) {
int k = comb[now][j];
if (k <= MAX)
len[k] = min(len[k], i);
}
}
memset(comb[next], 0, sizeof(comb[next]));
for (int j = 0; j <= i; j++) {
comb[next][j] = min(INF, comb[next][j] + comb[now][j]);
comb[next][j+1] = min(INF, comb[next][j+1] + comb[now][j]);
}
}
int R, S;
scanf("%d", &R);
for (int i = 0; i < R; i++) {
scanf("%d", &S);
int ret = INF;
for (int j = 1; j * j <= S; j++) {
if (S % j == 0)
ret = min(ret, len[j] + len[S/j]);
}
printf("Case #%d: %d\n", i+1, ret);
}
}
Recover the Sequence
実装問題。最初にord[i] = iとした配列を用意。デバッグ情報を元にマージソートを再現します。ソート完了後のord[]を見ることで、iはもともとord[i]番目にあったんだなということが分かります。
const LL MOD = 1000003;
vector<int> merge_sort(vector<int> arr) {
int n = arr.size();
if (n <= 1)
return arr;
int mid = n/2;
vector<int> arr1(arr.begin(), arr.begin()+mid);
arr1 = merge_sort(arr1);
vector<int> arr2(arr.begin()+mid, arr.end());
arr2 = merge_sort(arr2);
unsigned int p = 0, q = 0;
for (;p < arr1.size() && q < arr2.size();) {
int c = getchar();
if (c == '1') {
arr[p+q] = arr1[p];
++p;
}
else {
arr[p+q] = arr2[q];
++q;
}
}
for (;p < arr1.size(); p++)
arr[p+q] = arr1[p];
for (;q < arr2.size(); q++)
arr[p+q] = arr2[q];
return arr;
}
void solve() {
int T;
int N;
vector<int> ord;
vector<int> pos;
cin >> T;
for (int t = 0; t < T; t++) {
cin >> N;
ord.resize(N);
for (int i = 0; i < N; i++)
ord[i] = i;
getchar();
ord = merge_sort(ord);
pos.resize(N);
for (int i = 0; i < N; i++)
pos[ord[i]] = i+1;
LL ret = 1;
for (int i = 0; i < N; i++)
ret = (31 * ret + pos[i]) % MOD;
printf("Case #%d: %I64d\n", t+1, ret);
}
}
Squished Status
DPの問題。dp[i][j]にcompressed messageのi番目まで見終わったとき最後の文字コードがjとなっているときの場合の数を格納すればOKです。
const LL MOD = 4207849484LL;
LL dp[1024][256];
void solve() {
int N;
scanf("%d", &N);
for (int t = 0; t < N; t++) {
int M;
string comp;
cin >> M >> comp;
int len = comp.length();
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < len; i++) {
for (int j = 0; j <= M; j++) {
if (dp[i][j] == 0)
continue;
int d = comp[i] - '0';
int k = 10 * j + d;
if (0 < k && k <= M)
dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % MOD;
if (k != d && 0 < d && d <= M)
dp[i+1][d] = (dp[i+1][d] + dp[i][j]) % MOD;
}
}
LL ret = 0;
for (int i = 1; i <= M; i++)
ret = (ret + dp[len][i]) % MOD;
printf("Case #%d: %I64d\n", t+1, ret);
}
}