naoya_t@topcoder

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

00:00 |

（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曲の中から好きなのを選べるからまずがあって
• 3曲のみのplaylist, 2曲のみのplaylist, 1曲のみのplaylist を引けばよさげ
• みたいな？
• P=4 だと 256 - 81 - 16 - 1 = 158 だおかしい24になるはずだから
• いやそれだと4曲の中のどのn曲かが考慮されてない。それぞれ4C3, 4C2, 4C1掛けないと駄目だろ
• みたいな？
• 256 - 4*81 - 6*16 - 4*1 = 256-324-96-4 = -168 …マイナスありえないw おかしいな24になるはずなんだけどww 計算の材料はこれで全てな気がする
• お？ 256-324+96-4=24 になるじゃん？あ、そうか包除原理か
• ね。プラスとマイナスが交互に。
• で行けそう
• M>0の場合は？１曲目はN曲どれでも、２曲目は1曲目のを外したN-1曲の中から、３曲目はN-2曲の中から…M曲目はN-(M-1)曲の中から好きに選べて、M+1曲目以降はN-M曲の中から
• で行けそう
• あれ？これってM=0の場合も成り立つじゃん
• の計算どうするんだっけ。+ - 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

• あ、はパスカルの三角形だから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を返すべきケースも簡単！