2012-01-31
SRM531 Div1 Medium: MonsterFarm
過去問 | | 
なんか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参戦
| 
（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位だったけれどなぜか真ん中より上）
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