SRM511 Div1 Medium

500

memo[いくつ選んだ][ビット] = 必勝 or 必敗

{1, 10, 11, 500}がわかりやすいが、ORを取っても変化しない場合が存在する。
DP(orメモ化)はDAG上での計算なので、これは非常に困る。
しかも、数字は50個ある。2^50は無理。

現状のビットを作るために使える数字の個数の最大は、ORを取って変化がない数字の個数になる。
"これまで選択した数字の個数"と"使える個数の最大"を比較することで、変化しない場合を繰り返せるか分かる。
{1, 11} ⊂ {1, 10, 11}という包含関係の集合の大きさの差を思い浮かべると良いのかもしれない。

DP(orメモ化)でよくある"どこまで見た"が登場しなかったので相当悩んだ。
思い込みはいけない。

view plainprint?

1. const int L = 0, W = 1;  
2.   
3. const int N = 50 + 5;  
4. const int M = 520;  
5.   
6. vector<int> v;  
7.   
8. int memo[N][M];  
9. int rec(int nth, int memory)  
10. {  
11.   int& ret = memo[nth][memory];  
12.   if (ret != -1) return ret;  
13.   if (memory == 511) return W;  
14.   if (nth == v.size()) return L;  
15.   
16.   int inc = 0;  
17.   for (int i = 0; i < v.size(); ++i) {  
18.     if ((v[i] | memory) == memory) {  
19.       ++inc;  
20.     }  
21.   }  
22.   
23.   int mx = L;  
24.   
25.   if (inc > nth) mx = max(mx, rec(nth + 1, memory) ^ 1);  
26.   
27.   for (int i = 0; i < v.size(); ++i) {  
28.     int m = v[i] | memory;  
29.     unless (m == memory) {  
30.       mx = max(mx, rec(nth + 1, m) ^ 1);  
31.     }  
32.   }  
33.   
34.   return ret = mx;  
35. }  
36.   
37. class FiveHundredEleven {  
38. public:  
39.   string theWinner(vector <int> cards)  
40.   {  
41.     v = cards;  
42.     fill(&memo[0][0], &memo[N - 1][M - 1] + 1, -1);  
43.     return rec(0, 0) == W ? "Fox Ciel" : "Toastman";  
44.   }  

const int L = 0, W = 1;

const int N = 50 + 5;
const int M = 520;

vector<int> v;

int memo[N][M];
int rec(int nth, int memory)
{
  int& ret = memo[nth][memory];
  if (ret != -1) return ret;
  if (memory == 511) return W;
  if (nth == v.size()) return L;

  int inc = 0;
  for (int i = 0; i < v.size(); ++i) {
    if ((v[i] | memory) == memory) {
      ++inc;
    }
  }

  int mx = L;

  if (inc > nth) mx = max(mx, rec(nth + 1, memory) ^ 1);

  for (int i = 0; i < v.size(); ++i) {
    int m = v[i] | memory;
    unless (m == memory) {
      mx = max(mx, rec(nth + 1, m) ^ 1);
    }
  }

  return ret = mx;
}

class FiveHundredEleven {
public:
  string theWinner(vector <int> cards)
  {
    v = cards;
    fill(&memo[0][0], &memo[N - 1][M - 1] + 1, -1);
    return rec(0, 0) == W ? "Fox Ciel" : "Toastman";
  }