SRM508 div2 - Set::prototype

easy
実はこのコードは間違い。-100 <= X <= 100, -100 <= R <= 100ならとりうる点として、{150, 200}とかもあり得るんじゃない？？

	int countProbablePlaces(vector <int> X, vector <int> Y, vector <int> R) {
    int sz = X.size();
    int cnt = 0;
    for(int i = -100; i <= 100; i++) {
      for(int j = -100; j <= 100; j++) {
        bool flag = true;
        for(int k = 0; k < sz; k++) {
          if(abs(X[k]-i)+abs(Y[k]-j) > R[k]) {
            flag = false; break;
          }
        }
        if(flag) cnt++;
      }
    }
    return cnt;
	}

この手のミスはケアレスミスではないから注意！

    int sz = X.size();
    int cnt = 0;
    //ここを訂正する
    for(int i = -200; i <= 200; i++) {
      for(int j = -200; j <= 200; j++) {
        bool flag = true;
        for(int k = 0; k < sz; k++) {
          if(abs(X[k]-i)+abs(Y[k]-j) > R[k]) {
            flag = false; break;
          }
        }
        if(flag) cnt++;
      }
    }
    return cnt;
	}

medium
素数ということに気を取られがちだが、要するになんかの数で割って、Mを余り1の個所に移動させる最小の手順を求めればよい。
56 --> 14 --> 15(15%14==1)
56/14 = 4 = 2*2より、DIVIDEの操作は2回、SHIFTの操作は1回で３回となる。
SHIFTは右にも左にもシフトできるので、
M=7のとき、
1 7 15 //left shift:6回 right shift:8回でleft shiftした方が早く目的の値に到達できる。

問題の意味を読み取るのに時間がかかったので反省。

#define INF (1<<30)
  
class DivideAndShift {
	public:
	int getLeast(int N, int M) {
    int ans = INF;
    //i = 1から始まっている
    for(int i = 1; i <= N; i++) {
      if(N%i == 0) {
        int num = i;
        int tmp = N/i;
        int mod = M%tmp;
        int shift = min( abs(mod-1), tmp+1-mod);
        //M=iのとき分割した後の個数が1になるので、shiftの回数は必ず0になる。直前のコードの例外を補う。
        if(tmp == 1) shift = 0;
        int cnt = 0;
        int j = 2;
        //DIVIDEの回数を調べる（素因数分解した後の掛け算の個数)
        while(num != 1) {
          if(num%j == 0) {
            cnt++; num /=j;
          } else {
            j++;
          }
        }
        ans = min(cnt+shift, ans);
      }
    }
    return ans;         
	}

difficult
どう見てもDPで解くしかなさそうな問題．
dp[N+1][R+1]として、iまでが範囲のときの総数を直接求めようとすると詰まる．
なぜかというと、n+k == n|k でnが違えば結果が違ってくるから．漸化式にできない．
だから、dp[N+1][R+1]で総和がexactly iのときのn個選んだときの場合の数を　DPにすればよい。

//これはだめな例
  int countSequences(int N, int R) {
    int dp[N+1][R+2];
    memset(dp, 0, sizeof dp);
    for(int i = 0; i <= R; i++) {
      dp[1][i] = 1;
    }
    for(int i = 1; i < N; i++) {
      //これではR+1以降でsumされないので、だめ。例ではうまいこと2^n-1になっているので通ってしまう．
      for(int j = R; j >= 0; j--) {
	for(int k = 0; k <= R; k++) {
	  if(j + k == (j|k) ) {
	    int index = (j+k > R) ? R+1 : j+k;
	    dp[i+1][index] += dp[i][j];
	  }
	}
      }
    }
				     				 
    int ans = 0;
    //R+1もたすことに注意
    for(int i = 0; i <= R+1; i++) {
      ans += dp[N][i];
    }
    return ans;
  }

//こっちが正しい
  int countSequences(int N, int R) {
    const int MAX = (1<<14); //例えば、R=2^10+2:(100_0000_0010)とかのときは最終的な和が2^11-1:(111_1111_1111)になる可能性があるので、配列をここまでのばす。
    int dp[N+1][MAX]; //0~2^13
    memset(dp, 0, sizeof dp);
    for(int i = 0; i <= R; i++) {
      dp[1][i] = 1;
    }
    for(int i = 1; i < N; i++) {
      //n個足したときの和がdp[i][j]となる
      for(int j = MAX; j >= 0; j--) {
        //さらに数を足す．0~Rの範囲なので必ずこの範囲でループさせる．
	for(int k = 0; k <=R ; k++) {
	  if(j + k == (j|k) && dp[i][j] != 0) {
            //dp[i+1][j]とかで作ってしまうと、j=R+..の時に計算できなくなるorまた新たに条件を加えてけいさんしなければならなくなる．
	    dp[i+1][j+k] = (dp[i][j]+dp[i+1][j+k])%MOD;
	  }
	}
      }
    }
				     				 
    int ans = 0;
    //全体の和は1~Rまで、ではないことに注意．
    for(int i = 0; i < MAX; i++) {
      ans = (ans + dp[N][i])%MOD;
    }
    return ans;
  }

//全体の流れとしては、
R=4
(今までの和j:5) + (新たに足す数k:2)  --条件が真--> (j+k:7)
i = ?? //いままで足した回数
j = 5  新たに足す数:k = [0~R]まで試してみる． k =2でヒットしたところ．
R=4だけど、j=5のときにも上の例のように普通になりたつので、気をつける。