naoya_t@topcoder

SRM532 - 寝倒した先日の問題を見てみた

01:54 |

（http://naoyat.hatenablog.jp/entry/2012/02/16/184337 からの転載）

300 - 450 - 1000 ってまた気持ち悪い配点だけれど、本番じゃないしMediumから手をつけてみようかと。

Div1 Medium(450) DengkleBuildingRoads

まあどう見てもDPなんだけど

BAD END

• 必ず偶数、ってことはオイラー路だよね…
• なんか輪ゴムを釘に巻いていくパターンで考えてた（多分こないだJOI本選の問題を見たせい）
• 家aと家a+d (0<d≦K) を含む輪ゴムの巻き方パターンを数え上げてた</li>
• 輪ゴムの輪の頂点の数と同じだけの道路を消費
• f(d, m) = f(d-1, m) + ΣΣ f(d-1, m-j)*g(i, j) みたいな。DP。
• サンプルケースで答えが合わない…
• ああそうか、経路の組み合わせがf(d-1,..)の時とかぶるからこれはDPには使えない

BETTER END

• 1本ずつ引くDPにできるかな。とりあえず奇数なら奇数のままで（後に期待すれば）いいじゃん
• 高々8つ前までしか道路を引けないので、自分を含め9bitの偶奇（高々512）、あとこれまでに引いた道路の数（高々30）を持ち回るDPで書けそう。直前の結果がわかればいいので dp[2][31][512] とかその位。
• さてDP。
• 道路の本数ではなく偶奇のパターンを総なめ（と言っても8つ前までなら256通り）。例えば2つ前の家への道路が奇数本で ...101, 偶数本で ...000
• それぞれのパターンについて、同じ奇数（ないし偶数）でもそれぞれの家に何本の道路を引くのか、全パターンを数え上げて足していく。k軒に向けて道路を合計n本敷くパターンは(n+k-1)C(k-1)通り。
• １つ前の結果のパターンを左に１ビットシフトしたものに対しこのパターンをXORしたのが新パターン
• 最後の家まで回って dp[N-1][M][0] にある数値 (mod 1000000007) が答え
• とか書いてサンプルは通るようになった。
• が最悪ケース（30,30,8）でTLE…ローカルでは1.3秒ぐらいで終わるのに何それ…

TRUE END

• 8つ前までのパターンを持つ必要がないのでは？パターン数を減らしループを半分にしよう
• nCk を逐一計算してると遅い。メモ化したとしても遅い。nが高々30前後なので最初にDPで配列に用意してしまおう。（そうすればフェルマーの小定理とかしなくて済むあれ）
• __builtin_popcount() を毎回呼ぶのをやめて結果を配列にキャッシュしておこう
• → 0.3秒ぐらいになった。でもまだTLE
• dp[n][] += (nCk * dp[n-1][]) % 1000000007 のMODをループから外して、次のnの時にMODすることにする
• → ローカルで0.2秒切った。これで最悪ケースも通るようになってAC。

変なトリックないし黒魔術を必要としているわけではないが、計算の無駄をきちんと省かないとTLEになるぎりぎりのパラメータで問題設計してある感じ。

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

const ll MOD = 1000000007LL;

class DengklekBuildingRoads {
 public:
  int numWays(int N, int M, int K) { // 1-30, 0-30, 1-8
    int P = 1 << K;
    int bc[256];
    rep(i,256) bc[i] = __builtin_popcount(i);
 
    ll dp[2][31][256];
    rep(m,M+1) rep(p,P) dp[0][m][p] = 0;

    ll c[40][40];
    rep(i,40) c[i][0] = c[i][i] = 1;
    for (int i=1; i<40; i++) {
      for (int j=1; j<i; j++) {
        c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
      }
    }

    dp[0][0][0] = 1LL;
    for (int b=1; b<N; ++b) { // 30
      int i0=(b-1)%2, i1=b%2;

      rep(m,M+1) rep(p,P) dp[i1][m][p] = 0;
      int dmax = min(b,K);

      int D = 1 << dmax;
      rep(m,M+1) { // 30
        rep(p,D) {
          ll bmp = dp[i0][m][p]; if (!bmp) continue;
          bmp %= MOD;  // ここで mod
          int p_ = p << 1;
          rep(ma,D) {
            int bits = bc[ma];
            int p_m = p_ ^ ((ma << 1) | (bits & 1));
            if (p_m >= P) continue;
            for (int u=m+bits,jj=dmax-1,j=0; u<=M; u+=2,jj++,j++) { // 15
              dp[i1][u][p_m] += c[jj][j] * bmp;  // ここで mod するのをやめる
            }
          }
        }
      }
    }
    return (int)(dp[(N-1)%2][M][0] % MOD);
  }
};

Div1 Easy(300) DengklekMakingChains

• とりあえずチェーンを８種類に分類。数字がある箇所のビットを1、錆びてる箇所のビットを0としよう
  • 0 "..."（これは捨てて良い）
  • 1 "..1" / 3 ".11" これは一番左に来る。一番大きなものを残して捨てて良い
  • 2 ".1." 繋げることはできないが、この数字より大きなチェーンが出来ない場合にこれが最大値をとる場合がある
  • 4 "1.." / 6 "11." これは一番右に来る。一番大きなものを残して捨てて良い
  • 5 "1.1" これは右にも左にも来るので有利なところに置きたい。左右どちらに配するのがよいか考えるのが面倒くさいからDPで決めよう。
  • 7 "111" いくつでも繋げられる
• 最初5型をsetで持つコードを書いてて失敗。なぜ失敗するかというと例えば同じものが2つ以上あった時に左右両方に置くことができるはずなのに片方分しか持ってないから。（2つあれば十分とも言える）

書いたのはこんなコード。

laycurseさんの所を見たらDPとかしてなくて単に左右全パターン総当りしてた。高々50x50だしそれが賢いね。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class DengklekMakingChains {
 public:
  int maxBeauty(vector<string> chains) {
    int N = chains.size();
    vector<pair<int,int> > pat5;  // これはsetではNG
    int sum = 0, max1 = 0, max2 = 0, max4 = 0;
    rep(i,N){
      string s = chains[i];
      int pat = 0;
      for (int j=2,m=1; j>=0; j--,m<<=1) {
        if (s[j] != '.') pat |= m;
      }
      int n = 0, m = 0;
      switch (pat) {
        case 0: // ...
          break;
        case 3: // .11
          n += (s[1]-'0');
          // fall thru
        case 1: // ..1
          n += (s[2]-'0');
          if (n > max1) max1 = n;
          break;
        case 2: // .1.
          n = (s[1]-'0');
          if (n > max2) max2 = n;
          break;
        case 6: // 11.
          n += (s[1]-'0');
          // fall thru
        case 4: // 1..
          n += (s[0]-'0');
          if (n > max4) max4 = n;
          break;
        case 5: // 1.1
          n = (s[0]-'0'); m = (s[2]-'0');
          pat5.push_back(make_pair(n,m));
          break;
        case 7: // 111
          n = (s[0]-'0') + (s[1]-'0') + (s[2]-'0');
          sum += n;
          break;
      }
    }

    vector<vector<vector<bool> > > dp(2, vector<vector<bool> >(19, vector<bool>(19, false)));
    dp[0][max4][max1] = true;

    int pat5n = pat5.size(), i=0;
    tr(pat5,it) {
      int f4 = it->first, f1 = it->second;
      int i0=i%2, i1=(i+1)%2;
      dp[i1].assign(19, vector<bool>(19, false));
      rep(a,19) rep(b,19) {
        if (!dp[i0][a][b]) continue;
        if (f4 > a) dp[i1][f4][b] = true;
        if (f1 > b) dp[i1][a][f1] = true;
        dp[i1][a][b] = true;
      }
      i++;
    }

    int abmax = 0;
    rep(a,19) rep(b,19) {
      i = pat5n%2;
      if (!dp[i][a][b]) continue;
      if (a+b > abmax) abmax = a+b;
    }
    sum += abmax;

    return max(sum, max2);
  }
};