Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2013-09-01

Typical DP Contest 10:07 Typical DP Contest - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Typical DP Contest - nodchipのTopCoder日記 Typical DP Contest - nodchipのTopCoder日記 のブックマークコメント

http://tdpc.contest.atcoder.jp/

A - コンテスト

  • 点数の合計が小さいので幅優先探索
int main() {
	std::ios::sync_with_stdio(false);

  set<int> score;
  score.insert(0);

  int N;
  cin >> N;
  REP(n, N) {
    set<int> next;
    int p;
    cin >> p;
    for (set<int>::iterator it = score.begin(), itEnd = score.end(); it != itEnd; ++it) {
      next.insert(*it);
      next.insert(*it + p);
    }
    swap(score, next);
  }
  cout << score.size() << endl;
}

B - ゲーム

  • ゲーム木
  • 状態数はO(AB)
  • MinMax慣れてないので手間取った
int as[1024];
int bs[1024];
int dp[1024][1024];
int dfs(int a, int b, int A, int B) {
  if (dp[a][b] != 0) {
    return dp[a][b];
  }

  if (a == A && b == B) {
    return 0;
  } else if (a == A) {
    return bs[b] - dfs(a, b + 1, A, B);
  } else if (b == B) {
    return as[a] - dfs(a + 1, b, A, B);
  }

  return dp[a][b] = max(as[a] - dfs(a + 1, b, A, B), bs[b] - dfs(a, b + 1, A, B));
}

int main() {
	std::ios::sync_with_stdio(false);
  int A, B;
  cin >> A >> B;
  int sum = 0;
  REP(a, A) {
    cin >> as[a];
    sum += as[a];
  }
  REP(b, B) {
    cin >> bs[b];
    sum += bs[b];
  }

  int diff = dfs(0, 0, A, B);
  cout << (sum - diff) / 2 + diff << endl;
}

C - トーナメント

  • 各プレイヤーの勝率を更新していくDP
  • ビット演算面倒
double eroRating(double p, double q) {
  return 1.0 / (1.0 + pow(10.0, (q - p) / 400.0));
}

int main() {
	std::ios::sync_with_stdio(false);

  double R[1024];
  int K;
  cin >> K;
  REP(k, 1 << K) {
    cin >> R[k];
  }

  static double ero[1024][1024];
  REP(left, 1 << K) {
    REP(right, 1 << K) {
      ero[left][right] = eroRating(R[left], R[right]);
    }
  }

  static double p[2][1024];
  int back = 0;
  int front = 1;
  REP(i, 1 << K) {
    p[back][i] = 1.0;
  }

  for (int round = 0; round < K; ++round) {
    fill_n(p[front], 1024, 0);

    for (int battle = 0; battle < 1 << (K - round - 1); ++battle) {
      for (int left = 0; left < (1 << round); ++left) {
        for (int right = 0; right < (1 << round); ++right) {
          int leftPlayer = battle * (1 << (round + 1)) + left;
          int rightPlayer = battle * (1 << (round + 1)) + (1 << round) + right;
          p[front][leftPlayer] += p[back][leftPlayer] * p[back][rightPlayer] * ero[leftPlayer][rightPlayer];
          p[front][rightPlayer] += p[back][leftPlayer] * p[back][rightPlayer] * ero[rightPlayer][leftPlayer];
        }
      }
    }

    swap(front, back);
  }

  REP(k, 1 << K) {
    printf("%.20f\n", p[back][k]);
  }
}

D - サイコロ

  • 素因数に2,3,5がどれくらい含まれるか着目する
  • TLEがきつくて色々枝刈りした
  for (hash_map<int, double>::iterator it = back.begin(), itEnd = back.end(); it != itEnd; ++it) {
    int dtwo, dthree, dfive;
    decode(it->first, dtwo, dthree, dfive);
    if (two <= dtwo && three <= dthree && five <= dfive) {
       answer += it->second;
    }
  }
  for (hash_map<int, double>::iterator it = fixed.begin(), itEnd = fixed.end(); it != itEnd; ++it) {
    int dtwo, dthree, dfive;
    decode(it->first, dtwo, dthree, dfive);
    if (two <= dtwo && three <= dthree && five <= dfive) {
       answer += it->second;
    }
  }

  printf("%.20lf\n", answer);
}

E - 数

  • dp[先頭から何桁目][mod Dした数字の個数]のDP
  • N以下の値を各桁でDP表に反映させるのが面倒だった
const int MOD = 1000000007;

void add(int& a, int b) {
  a = (a + b) % MOD;
}

int main() {
	std::ios::sync_with_stdio(false);

  string N;
  int D;
  cin >> D >> N;

  // [back / front][fixed / free][倍数]
  static int dp[2][128];
  int back = 0;
  int front = 1;
  int digitSum = 0;
  REP (n, N.size()) {
    fill_n(dp[front], 128, 0);
    int digit = N[n] - '0';
    REP(from, D) {
      REP(to, 10) {
        add(dp[front][(from + to) % D], dp[back][from]);
      }
    }
    REP(to, digit) {
      add(dp[front][(digitSum + to) % D], 1);
    }

    digitSum = (digitSum + digit) % D;
    swap(back, front);
  }
  add(dp[back][digitSum], 1);

  cout << (dp[back][0] + MOD - 1) % MOD << endl;
}

F - 準急

  • 解けませんでした
  • なんでみなさんこんなに解けているのでしょう・・・

G - 辞書順

  • 解けませんでした
  • 順列組み合わせ苦手です

H - ナップザック

  • 各色ごとでナップザックをして、全体のナップザックに反映させるDP
  • TLEがきつくて色々枝刈りした
int main() {
	std::ios::sync_with_stdio(false);

  int N, W, C;
  cin >> N >> W >> C;
  // C, w, v
  map<int, vector<pair<int, int> > > items;
  REP(n, N) {
    int w, v, c;
    cin >> w >> v >> c;
    items[c].push_back(MP(w, v));
  }

  static int dp[2][64][16 * 1024];
  fill_n((int*)dp, sizeof(dp) / sizeof(int), -1);
  int back = 0;
  int front = 1;
  dp[back][0][0] = 0;
  for (map<int, vector<pair<int, int> > >::iterator it = items.begin(), itEnd = items.end(); it != itEnd; ++it) {
    copy((int*)dp[back], (int*)dp[back+ 1], (int*)dp[front]);

    static int dp2[16 * 1024];
    fill_n((int*)dp2, sizeof(dp2) / sizeof(int), -1);
    dp2[0] = 0;

    for (vector<pair<int, int> >::iterator jt = it->second.begin(), jtEnd = it->second.end(); jt != jtEnd; ++jt) {
      if (jt->first > W) {
        continue;
      }
      for (int w = W - jt->first; w >= 0; --w) {
        if (dp2[w] == -1) {
          continue;
        }
        MAX_UPDATE(dp2[w + jt->first], dp2[w] + jt->second);
      }
    }

    // w
    static int compressed[16 * 1024];
    int compressedSize = 0;
    REP(w, W + 1) {
      if (dp2[w] == -1) {
        continue;
      }
      compressed[compressedSize++] = w;
    }

    REP(c, C) {
      REP(w, W) {
        if (dp[back][c][w] == -1) {
          continue;
        }

        for (int compressedIndex = 0; compressedIndex < compressedSize && compressed[compressedIndex] + w <= W; ++compressedIndex) {
          int wAdd = compressed[compressedIndex];
          MAX_UPDATE(dp[front][c + 1][wAdd + w], dp[back][c][w] + dp2[wAdd]);
        }
      }
    }

    swap(back, front);
  }

  int answer = 0;
  REP(c, C + 1) {
    REP(w, W + 1) {
      MAX_UPDATE(answer, dp[back][c][w]);
    }
  }
  cout << answer << endl;
}

I - イウィ

  • 分かりませんでした
  • 行列の積の計算回数的なDPだと思ったのですが、詳細を詰められませんでした

J - ボール

  • 分かりませんでした
  • 期待値の連立方程式を立てるのだと思うのですが、確率DP苦手です

K - ターゲット

  • 分かりませんでした

L - 猫

  • 分かりませんでした
  • O(N^2)でやる方法ってあるんでしょうか・・・

M - 家

  • 前半はTSPのDPの形である部屋からある部屋への行き方のパターン数を求める
  • 後半は隣接グラフのH乗
  • 一番典型DPっぽい問題だと思いました
int main() {
	std::ios::sync_with_stdio(false);

  int H, R;
  cin >> H >> R;
  int g[16][16];
  REP(from, R) {
    REP(to, R) {
      cin >> g[from][to];
    }
  }

  GMatrix mat(R);
  REP(start, R) {
    static GG dp[16][1 << 16];
    fill_n((GG*)dp, sizeof(dp) / sizeof(GG), 0);
    dp[start][1 << start] = 1;
    REP(visited, 1 << R) {
      REP(from, R) {
        if (dp[from][visited] == 0) {
          continue;
        }
        REP(to, R) {
          if (!g[from][to] || (visited & (1 << to)) != 0) {
            continue;
          }
          dp[to][visited | (1 << to)] += dp[from][visited];
        }
      }
    }

    REP(goal, R) {
      REP(visited, 1 << R) {
        mat[start][goal] += dp[goal][visited];
      }
    }
  }

  GMatrix m = mat.pow(H);
  cout << m[0][0].x << endl;
}

N - 木

  • 分かりませんでした
  • ある頂点から先のパターン数のDPだと思ったのですが、計算式と解法に自信がありませんでした

O - 文字列

  • 分かりませんでした

P - うなぎ

  • 分かりませんでした

Q - 連結

  • 分かりませんでした

R - グラフ

  • 分かりませんでした

S - マス目

  • 分かりませんでした

T - フィボナッチ

  • 分かりませんでした
  • K<300なら行列のN乗なのですが・・・

System Test

順位ユーザ名コンテストゲームトーナメントサイコロ準急辞書順ナップザックイウィボールターゲット文字列うなぎ連結グラフマス目フィボナッチ得点 / Total
44nodchip2 13:303 32:244 56:394 (4) 97:324 123:35--5 (1) 173:58----5 213:00-------27 (5) 238:00

苦手な分野だったのですが、普通の順位でした。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20130901
 |