読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Typical DP Contest

Programming Contest

というのをAtCoderでやってたので、初級ラテン語リーディングの後で途中から(全5時間のところを後半3時間半ぐらい?)参加。
http://tdpc.contest.atcoder.jp/



5問解けて58位。時間足りない割にはまあそこそこ。
http://tdpc.contest.atcoder.jp/standings#page_3

というかこれ面白かった。AtCoderイイネ!!!

以下、解いた問題(5問)についてあれこれ

A. コンテスト

10分ぐらい?
AC (2点)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)

main(){
  int N; cin >> N; // 1-100
  vector<int> p(N); rep(i,N) cin >> p[i]; // 1-100

  int dp[2][10001];
  rep(i,2)rep(j,10001) dp[i][j] = 0;

  dp[0][0] = 1;
  int jmax = 0;
  rep(i,N){
    int pi = p[i], next_jmax = jmax + pi;
    int i0=i%2, i1=1-i0;
    rep(j,1+next_jmax) dp[i1][j]=0;
    rep(j,1+jmax) {
      dp[i1][j] += dp[i0][j];
      dp[i1][j + pi] += dp[i0][j];
    }
    jmax = next_jmax;
  }
  int ans = 0;
  rep(j,1+jmax) if (dp[N%2][j]) ++ans;

  printf("%d\n", ans);
  return 0;
}

B. ゲーム

敬遠

こういうのめちゃ苦手意識ある。
というかこういうのの克服のためのコンテストだと思うのだれけど…

C. トーナメント

25分ぐらい?
k回戦で当たるかもしれない相手候補を全部出すのにビット演算が活躍するね

AC (4点)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)

double win(int rp, int rq){
  return 1.0 / (1.0 + pow(10.0, 0.0025*(rq - rp)));
}
main(){
  int K; cin >> K;
  int M = 1 << K;

  vector<int> R(M);
  rep(i,M) cin >> R[i];

  vector<vector<double> > rate(2, vector<double>(M, 1.0));

  for (int k=0,f=1; k<K; ++k,f<<=1) {
    int k0=k%2, k1=1-k0;
    rep(i,M) rate[k1][i] = 0;

    int m=f-1;
    rep(i, M){ // 1024
      int i_ = (i ^ f) & (~m);
      double u = 0;
      rep(j, f){
        int a = i_ + j;
        u += rate[k0][a] * win(R[i], R[a]);
      }
      rate[k1][i] = rate[k0][i] * u;
    }
  }
  rep(i,M){
    printf("%11.9f\n", rate[K%2][i]);
  }
  return 0;
}

D. サイコロ

35分ぐらい?
素因数分解する(というか2,3,5以外が素因数に出てきたらアウト)というのはProject Eulerとかやってると普通に出てくる考え(←これはトイレ往復の間に思いついた)
AC (4点)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)

double dp[2][201][101][101];

main(){
  int N; cin >> N;
  ll D; cin >> D;

  int p2=0, p3=0, p5=0;

  while (!(D % 2)) { D /= 2; ++p2; }
  while (!(D % 3)) { D /= 3; ++p3; }
  while (!(D % 5)) { D /= 5; ++p5; }

  // printf("N=%d, D=2^%d 3^%d 5^%d\n", N, p2, p3, p5);
  if (D > 1 || N < p5 || N < p3 || N*2 < p2) {
    printf("0\n");
    return 0;
  }

  rep(i,201) rep(j,101) rep(k,101) dp[0][i][j][k] = 0;
  dp[0][0][0][0] = 1.0;

  rep(n,N){
    int i0=n%2, i1=1-i0;
    for (int i=0; i<=n*2+2; ++i)
      for (int j=0; j<=n+1; ++j)
        for (int k=0; k<=n+1; ++k)
          dp[i1][i][j][k] = 0;

    for (int i=0; i<=n*2; ++i)
      for (int j=0; j<=n; ++j)
        for (int k=0; k<=n; ++k) {
          double o = dp[i0][i][j][k] / 6;
          dp[i1][i][j][k] += o; // 1
          dp[i1][i+1][j][k] += o; // 2
          dp[i1][i][j+1][k] += o; // 3
          dp[i1][i+2][j][k] += o; // 2^2
          dp[i1][i][j][k+1] += o; // 5
          dp[i1][i+1][j+1][k] += o; // 2.3
        }
  }

  double ans = 0.0;
  int N_ = N%2;
  for (int i=p2; i<=N*2; ++i)
    for (int j=p3; j<=N; ++j)
      for (int k=p5; k<=N; ++k) {
        ans += dp[N_][i][j][k];
      }

  printf("%11.9f\n", ans);

  return 0;
}

E. 数

1時間ちょい?
Project Eulerの前半にありそうな問題。

TLE -> AC (4点)

TLEの原因は「DPしていなかったからwww」
30桁のサンプルが通って満足してた><
10000桁分の何かをDPしておくことで計算量を減らした。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)

#define MOD 1000000007LL

ll dp[10001][101];
int D;

main(){
  cin >> D;

  string s; cin >> s;
  int slen = s.size();

  rep(i,D) dp[0][i] = 0;
  dp[0][0] = 1;

  rep(t, 10000) {
    rep(i,D) dp[t+1][i] = 0;
    rep(i,D) {
      ll d0 = dp[t][i] % MOD;
      rep(j, 10) {
        int ix = (i + j) % D;
        dp[t+1][ix] += d0; // % MOD;
      }
    }
  }

  ll sum = 0LL;
  int cum = 0;
  rep(i, slen){
    int h = (int)(s[i] - '0');

    if (i == slen-1) {
      rep(j, h+1) {
        int ix = (cum + j) % D;
        sum += dp[0][(D - ix)%D];
        sum %= MOD;
      }
    } else {
      rep(j, h) {
        int ix = (cum + j) % D;
        sum += dp[slen-i-1][(D - ix)%D];
        sum %= MOD;
      }
    }
    cum = (cum + h) % D;
  }

  sum += (MOD - 1);

  cout << (sum % MOD) << endl;
  return 0;
}

F. 準急さん

1時間
WA -> AC (4点)
WAの原因は、modulo取ってるのに配慮せずに引き算してる箇所が1つあった所。

最初vectorで1つずつdp[st+1][k+1]的な所に加算してた
→全部1つずつ移動するだけだから1次元でよくね?dp[k+1]に加算だ
→いや他から来ないから単純代入でおk。K駅目でこぼすだけ
→100万×100万だとTLEしちゃう。シフトしてる計算量減らしたい
vectorでキューを自作→計算量は減らせたが結果おかしい。デバッグめどい
→deque使いますよはい→(当然ながら答えも合ったし)十分速い

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)

#define MOD 1000000007LL

main(){
  int N, K; cin >> N >> K;

  vector<ll> q(3, 0);
  q[1] = 1;

  deque<ll> dq;
  rep(i, K-2) dq.push_front(0);

  ll sum = 0;

  rep(st, N-1){
    q[0] = q[1];
    q[1] = q[2];

    dq.push_front(q[0] % MOD);
    sum = (sum + q[0]) % MOD;

    q[2] = (q[2] + sum) % MOD;

    sum = (sum + MOD - dq.back()) % MOD; /// ここでMODを足してなかったのでWAった
    dq.pop_back();
  }

  int goal = N - 1;

  ll ans = q[1];
  while (!dq.empty()) {
    ans = (ans + dq.back()) % MOD;
    dq.pop_back();
  }

  cout << (ans % MOD) << endl;
}

ここまでやって残り15分だったので、他の問題を解くのは諦めて試合終了にした。

その他

I. イウィ

開いてません