Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2012-01-31

SRM531 Div1 Medium: MonsterFarm

| 02:29 | SRM531 Div1 Medium: MonsterFarm - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM531 Div1 Medium: MonsterFarm - naoya_t@topcoder SRM531 Div1 Medium: MonsterFarm - naoya_t@topcoder のブックマークコメント

なんかEasyより簡単そうに思えたんだけど、やってみて5回目でSystem Test通った程度の体たらくなのでまあEasy頑張っておいてよかった的な。

〈1投目〉ナイーブにシミュレーション。step by stepで100万回ぐらいしか見てない。収束するまでやれてなくてアウト。

〈2投目〉ちまちまstep by stepしてくんじゃなくて自乗を繰り返してみる。まあそれは良いとして。1000000007 周期のやつなんて無いとか高をくくってたのかアウト。

〈3投目〉mod 1000000007系とmod 1000000009系を回して両方で収束を確認できなければ-1、としてみる。2501回回して51回不変、という条件では(手元のcore i7では余裕なのだが)TLEでアウト。

〈4投目〉1001回回して51回不変、にしてみるがまだTLEでアウト

〈5投目〉101回回して51回不変、にしてやっと通った。

最終的なコード:

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }
  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

const ll MOD7 = 1000000007LL;
const ll MOD9 = 1000000009LL;

class MonsterFarm {
 public:
  int numMonsters(vector<string> transforms) {
    int N = sz(transforms); // 1-50
    vector<vector<ll> > ta(N,vector<ll>(N,0)); // 1-50
    vector<vector<ll> > tb(N,vector<ll>(N,0)); // 1-50
    rep(a,N) {
      vector<int> ns = map_atoi(split(transforms[a],' '));
      tr(ns,it){
        int b=*it - 1;
        // ta[a][b]++;
        ta[b][a]++; // TR
        tb[b][a]++; // TR
      }
    }

    ll sum7_ = 1, sum9_ = 1, staying=0;
    rep(j,101) {
      vector<vector<ll> > taa(N,vector<ll>(N,0)), tbb(N,vector<ll>(N,0));
      rep(x,N) rep(y,N) {
        rep(i,N) taa[x][y] = (taa[x][y] + ta[x][i]*ta[i][y]) % MOD7;
        rep(i,N) tbb[x][y] = (tbb[x][y] + tb[x][i]*tb[i][y]) % MOD9;
      }

      ll sum7 = 0; rep(i,N) sum7 = (sum7 + taa[i][0]) % MOD7;
      ll sum9 = 0; rep(i,N) sum9 = (sum9 + tbb[i][0]) % MOD9;
      
      ta = taa;
      tb = tbb;
      
      if (sum7 == sum7_ && sum9 == sum9_) {
        staying++;
        if (staying==51) return (int)(sum7 % MOD7);
      } else {
        staying=0;
      }
      sum7_ = sum7;
      sum9_ = sum9;
    }
    return -1;
  }
};

SRM531 - 1年3ヶ月ぶりのTopCoder参戦

00:00 |  SRM531 - 1年3ヶ月ぶりのTopCoder参戦 - naoya_t@topcoder を含むブックマーク はてなブックマーク -  SRM531 - 1年3ヶ月ぶりのTopCoder参戦 - naoya_t@topcoder  SRM531 - 1年3ヶ月ぶりのTopCoder参戦 - naoya_t@topcoder のブックマークコメント

http://naoyat.hatenablog.jp/entry/2012/01/31/235459 からの転載)

1/31 21:05〜

久しぶりすぎて緊張する

300-500-1000だ

Easy300点は不吉

Div1 Easy(300) : NoRepeatPlaylist

  • DPで解けるか?…なんか可能なstateの数が多すぎて手に負えない
  • M曲ずつブロックにして…違うな。それだと連続するかもしれない
  • とりあえずM=0の場合を考えよう。
  • N=4なら、毎回4曲の中から好きなのを選べるからまず4^pがあって
  • 3曲のみのplaylist, 2曲のみのplaylist, 1曲のみのplaylist を引けばよさげ
  • \displaystyle4^p - 3^p - 2^p - 1^p みたいな?
  • P=4 だと 256 - 81 - 16 - 1 = 158 だおかしい24になるはずだから
  • いやそれだと4曲の中のどのn曲かが考慮されてない。それぞれ4C3, 4C2, 4C1掛けないと駄目だろ
  • \displaystyle4^p - {_4}C_33^p - {_4}C_22^p - {_4}C_11^p みたいな?
  • 256 - 4*81 - 6*16 - 4*1 = 256-324-96-4 = -168 …マイナスありえないw おかしいな24になるはずなんだけどww 計算の材料はこれで全てな気がする
  • お? 256-324+96-4=24 になるじゃん?あ、そうか包除原理か
  • \displaystyle4^p - {_4}C_33^p + {_4}C_22^p - {_4}C_11^p ね。プラスとマイナスが交互に。
  • \displaystyle\sum_{i=0}^{n-1}(-1)^i{_n}C_{n-i}(n-i)^pで行けそう
  • M>0の場合は?1曲目はN曲どれでも、2曲目は1曲目のを外したN-1曲の中から、3曲目はN-2曲の中から…M曲目はN-(M-1)曲の中から好きに選べて、M+1曲目以降はN-M曲の中から
  • \displaystyle\sum_{i=0}^{n-1}\{(-1)^i{_n}C_{n-i}\prod_{j=0}^{p-1}(n-i-min(j,m))\}で行けそう
  • あれ?これってM=0の場合も成り立つじゃん
  • {_n}C_{n-i} mod 1000000007 の計算どうするんだっけ。+ - x については自明なんだけど割り算のmod ...
  • フェルマーの小定理だったっけ
  • 前にどこかで書いたのを探す
  • 出来た!!

てなわけでここまで辿り着くのに70分。やはりブランクを感じる。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

#define rep(var,n)  for(int var=0;var<(n);var++)
#define sz(a)  int((a).size())
#define found(s,e) ((s).find(e)!=(s).end())

const ll MOD = 1000000007LL;
typedef pair<ll,ll> ll2;
map<ll2,ll> cmm;

ll add(ll x, ll y) { return (x + y) % MOD; }
ll sub(ll x, ll y) { return (x - y) % MOD; }
ll mul(ll x, ll y) { return (x * y) % MOD; }
ll pow(ll x, ll y) {
  ll v = 1;
  for(;y;x=mul(x,x),y>>=1)
    if(y&1) v = mul(v, x);
  return v;
}
ll divi(ll x, ll y) { return mul(x, pow(y, MOD-2)); }
ll C(ll n, ll k) { // nCk
  ll2 p(n,k);
  if (found(cmm,p)) return cmm[p];
  ll v = 1;
  for(ll i=1; i<=k; ++i) 
    v = divi(mul(v, n-i+1), i);
  return cmm[p]=v;
}
ll solve(ll n, ll m, ll p) {
  if (n==0) return 0;
  ll x=1;
  rep(i,p) {
    ll u = m; if (i<m) u=i;
    x = (x * (n-u)) % MOD;
  }
  return x;
}

class NoRepeatPlaylist {
 public:
  int numPlaylists(int N, int M, int P) {
    ll n = (ll)N, m = (ll)M, p = (ll)P;
    ll sum = 0LL, del = 0LL;
    for(int i=0; i<n; ++i) {
      int n_=n-i;
      if (i&1) {
        del = (del + C(n,n_)*solve(n_, m, p)) % MOD;
      } else {
        sum = (sum + C(n,n_)*solve(n_, m, p)) % MOD;
      }
    }
    sum = (sum + MOD - del) % MOD;
    return (int)sum;
  }
};

とりあえずテストケース全部通ったし、可能なN,M,Pの全組み合わせを投げてTLEにならないことを確認する辺りまで試してからsubmit。

Div1 Medium(500) : MonsterFarm

  • 残り2, 3分だったけれど開いた
  • 「解いてみた」編は次のエントリ

Challange Phase

  • あ、{_n}C_{n-i}はパスカルの三角形だからmod 1000000007があってもDPで書けるのね(そりゃそうだ)nも高々100だし…
  • 何人かのコードを開いてみたけど手出しせず
  • Div2 Easyを開いてみた。なにこのsortしてnext_permutationして終わりな感じ...

System Test

passed. (o - -)

110.38 point, 364/872位(部屋では13/20位だったけれどなぜか真ん中より上)

1649 → 1652 (+3) 自己ベストを微更新

f:id:n4_t:20120131235321p:plain]

おまけ

Practice RoomでDiv2 Easyをやってみた。

#include <vector>
using namespace std;
#define all(c)  (c).begin(),(c).end()

class UnsortedSequence {
 public:
  vector<int> getUnsorted(vector<int> s) {
    sort(all(s));
    if (!next_permutation(all(s))) return vector<int>();
    return s;
  }
};

next_permutation()の返り値を使えば空vectorを返すべきケースも簡単!

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20120131