2012-02-15
Facebook Hacker Cup 2012 R1
A. Checkpoint
問題
- 始点からチェックポイントを通って終点に移動する
- チェックポイントは始点でも終点でもなく、必ず一回だけ通る
- 1マス単位で移動する。始点の方向には戻らない
- 移動のしかたがちょうどn通りになる最短経路のマンハッタン距離を求める
方針
- 始点からチェックポイントとチェックポイントから終点までを分離して考える
- 各経路においてa通りの最大値はaで、1+aが仮の最大値となる
- a通りが存在する経路であればより小さい値になる
- 図に書いてみると、場合の数(nCrとかnCmとか二項係数とかいうやつ)になっている
- 1から10000000の二項係数の表(nCrからn+rへの最小値の表)を持っておく
#define MAX_S 10000000
#define INF MAX_S*2
typedef pair<int, int> II;
typedef map<int, int> IntMap;
IntMap S_to_dist;
int i, j, k, n;
static int p[MAX_S+1];
p[0] = 1;
for (i = 1; i <= MAX_S; ++i) {
int prev = 1, next = 1;
for (j = 1; j <= (i/2); ++j) {
next = prev + p[j];
prev = p[j];
p[j] = next;
if (next > MAX_S) {
next = INF; // これがないと負になる
break;
}
if (next != i) {
int d = S_to_dist[next];
if (d <= 0 || i < d) {
S_to_dist[next] = i;
}
}
}
p[j] = next;
}
cin >> n;
for (i = 1; i <= n; ++i) {
cin >> j;
int res = j + 1;
for (k = 1; (k*k) <= j; ++k) {
if ((j % k) == 0) {
int l = k;
if (S_to_dist.find(k) != S_to_dist.end()) {
l = S_to_dist[k];
}
int m = j/k;
if (S_to_dist.find(m) != S_to_dist.end()) {
m = S_to_dist[m];
}
res = min(res, l+m);
}
}
cout << "Case #" << i << ": " << res << endl;
}
B. Recover the Sequence
問題
- マージソートのデバッグ出力が与えられる
- 元の数列を復元してチェックサムを求める
方針
- 与えられたコードをそのままシミュレーションする
- できた数列は、元の数値の位置を示しているので、元に戻す
C. Squished Status
問題
方針
- DPで足す
LL solve(int m, const char *s)
{
int len = strlen(s);
int res = 0;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int read = 0;
int write = 1;
int m2 = min(m, 99);
int a, b, c, d, e;
for (a = 1; a <= len; ++a) {
for (b = 0; b <= MAX_N; ++b) {
dp[write][b] = dp[read][b];
}
for (b = 1; b <= 9; ++b) {
if (s[a-1] == (b+'0')) {
dp[write][a] += dp[read][a-1];
}
}
if (a >= 2) {
for (b = 10; b <= m2; ++b) {
d = b/10;
e = b%10;
if (s[a-2] == (d+'0') && s[a-1] == (e+'0')) {
dp[write][a] += dp[read][a-2];
}
}
if (a >= 3) {
for (b = 100; b <= m; ++b) {
c = b/100;
d = (b-c*100)/10;
e = b%10;
if (s[a-3] == (c+'0') &&
s[a-2] == (d+'0') &&
s[a-1] == (e+'0')) {
dp[write][a] += dp[read][a-3];
}
}
}
}
dp[write][a] %= (LL)FACEBOOK;
read ^= 1;
write ^= 1;
}
return dp[read][len];
}
結果
x-o 敗退
Aはチェックポイントがn個と誤読していて時間かかりすぎ＆不正解。問題文はよく読まないと。二項係数のDPに時間かかりすぎ。
Bは思いつかなかった。だめすぎる。
Cはまあできた。よしとする。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120215
2012-02-11
Codeforces 104 Div2
A. Lucky Ticket
問題
- ラッキーナンバーかつ前半と後半の和が等しいかどうかを求める
B. Lucky Mask
問題
- aより大で、ラッキーナンバーだけ取り出した数がbと一致する最小の数を求める
方針
- せいぜい100000回
- 1文字ずつ取り出す->atoi->比較で全探索
C. Lucky Conversion
問題
- ラッキーナンバーだけからなる数aとbがある
- 交換または変更の操作によりa=bとなる最小の回数を求める
方針
- 交換のほうがコストが小さいので交換してから変更する
- まず数値毎に異なる桁数を求めて、diff_4とdiff_7とする
- min(diff_4,diff_7)が交換回数
- 残りが変更回数
D. Lucky Number 2
問題
- 4,7,47,74の回数が与えられる
- ラッキーナンバーだけからなる数を生成する
方針
- c-dの値が-1,0,1,その他で場合わけ
- abs(c-d)>1なら不可能
結果
488+932+1344+0=2764pt 145th rating 1523 -> 1597
Dは場合わけしたらバグバグだった。これをコンテスト中に通すのは困難。
4と7がラッキーナンバーってTopCoderにも出てくるがデファクトスタンダードなんだろうか。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120211
2012-02-10
Facebook Hacker Cup 2012 QR
A. Billboards
問題
- 板に文字を敷き詰める
- 上下左右の余白は不要
方針
- 上限値はすぐわかる
- 1ptずつ減らして全探索
- 一応2分探索も書いてみたが全探索でも十分間に合う
B. Auction
問題
- 最も価値がある商品をバーゲン品、最も価値がない商品を粗悪品として漸化式がなんとか
C. Alphabet Soup
問題
- 文字列からHACKERCUPを抽出
方針
- mapに入れて数える
感想
GCJとほぼ同じシステムだがsmallとlargeの区別がないので、ちょっと緊張した。GCJに比べて問題文が短く、制約条件がややわかりづらい(余白が必要かどうかとか)
Bだけ異次元。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120210
2012-02-06
SRM 530 Div2
不参加
Easy (250) GogoXBallsAndBinsEasy
問題
- N本のビンがあり、それぞれT[x]個のボールが入っている。
- Tの個数は昇順にソートされている。
- T[x]の順番をシャッフルしたものをS[x]として、ビンからビンへコスト1でボールを1個移動できる。
- 状態Sから状態Tへの移動量が最大となるSを求める。
方針
- 先頭と末尾の両端から差を取って加算
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_530/GogoXBallsAndBinsEasy.cpp
Medium (500) GogoXCake
問題
- ケーキとケーキカッターがある。
- ケーキカッターには刃が有効な部分と無効な部分があり、刃をあてるときには有効な部分にケーキがなければならない。
- 食い散らかしたケーキの結果から、ケーキカッターでその結果が生成可能か求める。
方針
- 総当りで位置をなめていって、ケーキカッターの形にフィットしたら、ケーキに戻す
- 最終的に全てがケーキに戻っていればYES
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_530/GogoXCake.cpp
Hard (1000) GogoXReimuHakurai
問題
- 小説が0から(N-1)までの全Nステージある
- あるステージAから次のステージBへのルートがあるかどうかのフラグが与えられる
- 前のステージへは戻れない
- それまでに通っていないルートを1通りとして何通りのルートがあるか求める
方針
感想
hardを誰もACしていないという珍しい回。サンプルだけ通るコードだと死。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120206
2012-02-05
Codeforces 103 Div2
不参加。
A. Arrival of the General
問題
- 最初と最後だけ並んだふりする
- 最小の交換回数を求める
方針
- 最小の位置 < 最大の位置のとき交換回数を-1する
B. Meeting
問題
- テーブルの周りに寒がりな人たち
- 半径rだけあたためるn個のストーブ
- ストーブにあたってない人数を求める
C. Anagram Search
問題
- 文字列sと文字列pが与えられる
- 文字列pの長さをlengthとする
- 文字列sの任意の位置xからlength取り出した文字列をsubstringとする
- substringがpのアナグラムである個数を求める
方針
- pの使用文字をchars[26]に入れておく
- sの使用文字を一個ずつ出し入れして、判定&ループ
感想
こどふぉにもストーリーつきのときがあるんだなと思った。
Cは題意がわからなくて悩んだ。英語弱い
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120205