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

naoya_t@hatenablog

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

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

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

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を返すべきケースも簡単!