Search on the blog

2011年6月4日土曜日

SRM508練習

本番は参加できなかったので、復習。

Div2 250 CandyShop
ある地点にキャンディ屋さんがある。しかしどこにあるかは覚えてはいない。i回目にキャンディ屋さんに行った時は、座標(x[i], y[i])からスタートして、R[i]回の平行移動(1回の移動では、上下左右のいづれかに1座標だけ移動可能)で辿りつけた。x, y, Rの情報を元に、キャンディ屋さんの場所を予想する。

え、、これDiv2の250??そんな簡単じゃない気が。簡単なときの500くらいのレベルあるんじゃ・・
x, yの範囲が比較的小さいので、各座標に対して矛盾がないかしらべる。具体的には、(x[i], y[i])からのマンハッタン距離がR[i]以内の場所のみを残していけばいい。
bool ck[512][512];

class CandyShop {
public:
int countProbablePlaces(vector<int> X, vector<int> Y, vector<int> R) {
REP(i, 512) REP(j, 512) ck[i][j] = true;

int sz = X.size();
REP(k, sz) {
REP(i, 512) REP(j, 512)
if (ABS(X[k]+256-i) + ABS(Y[k]+256-j) > R[k]) ck[i][j] = false;
}

int cnt = 0;
REP(i, 512) REP(j, 512) if (ck[i][j]) ++cnt;

return cnt;
}
};

Div2 500 DivideAndShift
N個の箱からなる列がある。一番先頭からのみ物体を取ることができる。もともと先頭からM番目にある箱を取り出すには以下の操作を最低何回行えばよいか?操作は1回につき、以下のいづれかを実施できる。
1. すべての箱を後ろにシフトする。最後尾の箱は一番前にくる。
2.すべての箱を前にシフトする。一番前の箱は最後尾に行く。
3. 箱を箱の長さNの素因数pで割る。割ったあとは好きな塊を選ぶことができる。このとき、新しい長さはN/p、Mのindexは、M % (N/p) (0-based)になることに注意。

えーっと小一時間くらいやったけど、できませんでした。深さに制限をつけたDFS、それに部分メモ化再帰を追加とやりましたが、TML回避できず。これって簡単なときの900くらいはあるんじゃ・・
LayCurse様のブログを見て解決。
解法は、1.2.3.の操作はすべて可換なので、組み合わせを全探索すること。シフト操作は最後に行うものとして、3.の操作の組み合わせを探索するようです。さすが。。。
シフトと割る操作が可換なのは、モジューロ演算の交換法則からもわかります。
(a+1) % m = a % m + 1 %m (mod m)
3.の操作の順番が関係ないのは、最終的に辿り着いた箱の長さだけをみれば、indexが一意に決まることから導け出せそうです。
あと、ちょっとしたテクニックですが、M-1を再帰関数に渡すことで、0-basedのインデックスを見れるので細かい処理(こういうの m%(n/prime[i]) ? m%(n/prime[i]) : m)が必要なくなります。
class DivideAndShift {
vector<int> prime;
public:
int solve(int n, int m, int st) {
int ret = min(m, n-m);

for (int i = st; i < (int)prime.size(); i++) {
if (prime[i] > n)
break;
if (n % prime[i] == 0)
ret = min(ret, 1+solve(n/prime[i], m%(n/prime[i]), i));
}

return ret;
}

int getLeast(int N, int M) {
int n = N;

for (int i = 2; i <= N; i++) {
if (n % i == 0)
prime.push_back(i);
while (n % i == 0)
n /= i;
}

return solve(N, M-1, 0);
}
};
この問題は、計算量を見積るのが難しい気がするのですが、どうなんでしょう?
素因数の数の上限が20くらいなので、2^20?? であってますかね?

0 件のコメント:

コメントを投稿