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