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]以内の場所のみを残していけばいい。

view plainprint?

1. bool ck[512][512];  
2.   
3. class CandyShop {  
4. public:  
5.    int countProbablePlaces(vector<int> X, vector<int> Y, vector<int> R) {  
6.        REP(i, 512) REP(j, 512) ck[i][j] = true;  
7.   
8.        int sz = X.size();  
9.        REP(k, sz) {  
10.            REP(i, 512) REP(j, 512)  
11.                if (ABS(X[k]+256-i) + ABS(Y[k]+256-j) > R[k]) ck[i][j] = false;  
12.        }  
13.   
14.        int cnt = 0;  
15.        REP(i, 512) REP(j, 512) if (ck[i][j]) ++cnt;  
16.   
17.        return cnt;  
18.    }  
19. };  

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）が必要なくなります。

view plainprint?

1. class DivideAndShift {  
2.    vector<int> prime;  
3. public:  
4.    int solve(int n, int m, int st) {  
5.        int ret = min(m, n-m);  
6.   
7.        for (int i = st; i < (int)prime.size(); i++) {  
8.            if (prime[i] > n)  
9.                break;  
10.            if (n % prime[i] == 0)  
11.                ret = min(ret, 1+solve(n/prime[i], m%(n/prime[i]), i));  
12.        }  
13.   
14.        return ret;  
15.    }  
16.   
17.    int getLeast(int N, int M) {  
18.        int n = N;  
19.   
20.        for (int i = 2; i <= N; i++) {  
21.            if (n % i == 0)  
22.                prime.push_back(i);  
23.            while (n % i == 0)  
24.                n /= i;  
25.        }  
26.   
27.        return solve(N, M-1, 0);  
28.    }  
29. };  

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??　であってますかね？