今回は、去年と比べて問題のレベルが上がりました。
でも上位陣は４問を１時間内に解いてしまってます。。何食べたらそんなに頭がよくなるのだろう？？
Aは境界値条件、分岐方法の正確さが求められました。Bは、データ構造方法の問題でした。
Cはビット演算の知識、Dは確率の知識が必要な問題でした。
せっかく24時間あるので、今年は3つの言語で解くという遊びにチャレンジ。
- 問題A、BはC++
- 問題CはHaskell
- 問題DはPython
で解きました。
では、それぞれの問題の解法。。もっといい解き方があったら教えてくださいーー。
Problem A. Bot Trust
[解法]
まず、お仕事リストを
vector timeline
に格納。（値は、BOBBOOなどになる。）
それとは別に、ロボットが押すべきボタンの位置をそれぞれ
vector blue;
vector orange;
に格納。
あとは、timelineをループでまわしていけばOK。
ロボットが負の方向に動く場合もあるので、正の方向と負の方向に動く場合で場合分けすると実装しやすいです。
[提出コード]
int main() {
int t, n;
scanf("%d", &t);
REP(i, t) {
scanf("%d", &n);
vector<char> timeline;
vector<int> blue;
vector<int> orange;
REP(j, n) {
int x;
char r;
scanf(" %c %d", &r, &x);
timeline.push_back(r);
if (r == 'B')
blue.push_back(x);
else
orange.push_back(x);
}
int sz = timeline.size();
int szBlue = blue.size(), szOrange = orange.size();
int p = 0, q = 0;
int bpos = 1, opos = 1;
int ret = 0;
REP(j, sz) {
if (timeline[j] == 'B') {
int pos = blue[p++];
ret += ABS(pos - bpos) + 1;
if (q < szOrange) {
int move = ABS(pos - bpos) + 1;
if (opos < orange[q])
opos = min(opos + move, orange[q]);
else
opos = max(opos - move, orange[q]);
}
bpos = pos;
} else {
int pos = orange[q++];
ret += ABS(pos - opos) + 1;
if (p < szBlue) {
int move = ABS(pos - opos) + 1;
if (bpos < blue[p])
bpos = min(bpos + move, blue[p]);
else
bpos = max(bpos - move, blue[p]);
}
opos = pos;
}
}
printf("Case #%d: %d\n", i+1, ret);
}
return 0;
}
Problem B. Magicka
[解法]
呪文合成規則を
char combine[26][26];
に、呪文組み合わせ規則を
bool opposed[26][26];
に格納。
となえる呪文をstackに詰めていき、逐次上記２つの規則をチェックする。
呪文組み合わせチェックは、26*26見ているけど、これだとLargeの場合タイムオーバーになりそうなので、
基本エレメントだけを取り出して、組み合わせチェックをするといい。（てか最初から8*8でつくれよっ。）
[提出コード]
char combine[26][26];
bool opposed[26][26];
char tmp[16];
char magic[128];
bool emerge[26];
string base = "QWERASDF";
bool isOppose(stack<char> stk) {
bool hasBase[8] = {0};
while (!stk.empty()) {
char t = stk.top();
int pos = -1;
REP(i, 8)
if (base[i] == t)
pos = i;
if (~pos)
hasBase[pos] = 1;
stk.pop();
}
REP(i, 8) REP(j, 8) {
if (!hasBase[i] || !hasBase[j])
continue;
if (opposed[base[i]-'A'][base[j]-'A'])
return true;
}
return false;
}
int main() {
int t;
scanf("%d", &t);
REP(i, t) {
int c, d, n;
memset(combine, 0x00, sizeof(combine));
memset(opposed, 0x00, sizeof(opposed));
// read combine
scanf("%d", &c);
REP(j, c) {
scanf("%s", tmp);
combine[tmp[0]-'A'][tmp[1]-'A'] = tmp[2];
combine[tmp[1]-'A'][tmp[0]-'A'] = tmp[2];
}
// read opposed
scanf("%d", &d);
REP(j, d) {
scanf("%s", tmp);
opposed[tmp[0]-'A'][tmp[1]-'A'] = 1;
opposed[tmp[1]-'A'][tmp[0]-'A'] = 1;
}
// read magic list
scanf("%d", &n);
scanf("%s", magic);
// solve
stack<char> ret;
REP(j, n) {
if (ret.empty()) {
ret.push(magic[j]);
continue;
}
int pre = ret.top()-'A';
int next = magic[j]-'A';
if (combine[pre][next]) {
ret.pop();
ret.push(combine[pre][next]);
}
else {
ret.push(magic[j]);
if (isOppose(ret)) {
while (!ret.empty())
ret.pop();
}
}
}
string res = "]";
while (!ret.empty()) {
res = ret.top() + res;
ret.pop();
if (!ret.empty())
res = ", " + res;
}
res = "[" + res;
printf("Case #%d: %s\n", i+1, res.c_str());
}
return 0;
}
Problem C. Candy Splitting
[解法]
Smallは全件探索してもO(2^15)なので間にあいます。LargeはO(2^1000)になるので全探索は不可能。
よく考えると、すべての飴玉のかたまりで排他的論理和を取って0になれば、”エセ”二等分ができることに気付きます。
排他的論理和が0以外なら、No。
0の場合は、(飴玉の総数) - (一番少ないかたまりの中にある飴玉の数)
が答え。
[提出コード]
import Data.Bits
import Text.Printf
getInt = do
n <- getLine
return (read n::Int)
getInts = do
n <- getLine
return (map (\x -> read x::Int) (words n))
gcjMain x = do
m <- getInt
nums <- getInts
printf "Case #%d: %s\n" x (solve nums)
solve nums
| foldl (xor) 0 nums /= 0 = "NO"
| otherwise = show $ solve' nums
where solve' num = (sum nums) - foldl (min) inf nums
inf = 100000000
main = do
n <- getInt
mapM_ (\x -> gcjMain x) [1..n]
Problem D. GoroSort
[解法]
これは、強烈。もっと簡単な解法があれば教えてください。。
やり方としては、
①まず数字をdisjoint（共通部分がない or 循環しない）なグループに分ける。
②それぞれのグループで期待値を求める。
③②で求めた期待値を足す。
という流れ。
サイズNのdisjoint groupに対する期待値は、
Xn = 1 + Sigma_{i=0}^n (nCi * f(i) * Xi / n! ), n >= 3
X0 = 0
X1 = 0
X2 = 2
という漸化式で表すことができる。
f(i)は、Nの中で正しい位置にいない要素の数がi個であるもののパターン数。
これは、
fn = (n-1) (f(n-1) + f(n-2)), n >= 2
f0 = 1
f1 = 0
という式で表すことが出来る。
上の式を頑張って手計算すると、ふむふむ、どうやら、
Xn = n, n >= 2
だな。と気付く。
これに気付けば、実装するだけです。
[提出コード]
import sys
n = raw_input()
n = int(n)
for i in range(n):
m = raw_input()
m = int(m)
nums = raw_input()
nums = nums.split(" ")
nums = map(int, nums)
nums = map(lambda x:x-1, nums)
grp = []
used = [0] * m
for j in range(m):
if nums[j] == j:
continue
if used[j]:
continue
cnt = 0
k = j
while used[k] == 0:
used[k] = 1
k = nums[k]
cnt = cnt + 1
grp = grp + [cnt]
print "Case #%d: %.6lf" % (i+1, sum(grp))
0 件のコメント:
コメントを投稿