Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-04-22

SRM468 Medium: RoadOrFlightHard

| 23:50 | SRM468 Medium: RoadOrFlightHard - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM468 Medium: RoadOrFlightHard - naoya_t@topcoder SRM468 Medium: RoadOrFlightHard - naoya_t@topcoder のブックマークコメント

DPでコード書いてみたら250より簡単で泣けた。DPって分かっただけで終了なゲームなのになぜ…

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100422

2010-04-20

Member SRM 468

22:17 | Member SRM 468 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM 468 - naoya_t@topcoder Member SRM 468 - naoya_t@topcoder のブックマークコメント

青い人と黄色い人しかいない部屋。

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 T9 提出 - passed - 132.32
1 500 RoadOrFlightHard 間に合わず - - - -
1 1000 - - -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100420

2010-04-16

SRM467

12:08 | SRM467 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM467 - naoya_t@topcoder SRM467 - naoya_t@topcoder のブックマークコメント

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 LateProfessor 提出 - 撃沈 - 0.0
1 500 SuperSum 間に合わず - - - -
1 1000 - - -

剰余とりながら計算するやつ

13:32 | 剰余とりながら計算するやつ - naoya_t@topcoder を含むブックマーク はてなブックマーク - 剰余とりながら計算するやつ - naoya_t@topcoder 剰余とりながら計算するやつ - naoya_t@topcoder のブックマークコメント

cafelier先生のコードからの抜粋 cf. http://topcoder.g.hatena.ne.jp/cafelier/20100416/1271391378
typedef long long LL;

LL M = 1000000007LL; // その時々で。素数でない場合は以下のDIV()が使えないことがある

LL ADD(LL x, LL y) { return (x+y) % M; }
LL SUB(LL x, LL y) { return (x-y+M) % M; }
LL MUL(LL x, LL y) { return x*y % M; }
LL POW(LL x, LL e) { LL v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
LL DIV(LL x, LL y) { return MUL(x, POW(y, M-2)); }

LL C(LL n, LL k) { LL v=1; for(LL i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

cafeliercafelier2010/04/16 13:28素数でないと成り立たないです。

m(x)=x%MODVALとして、m(x)とm(y)からm(x/y)を求めたいわけなので
x/y=z ⇔ x=zy ⇒ m(x)=m(z)m(y) ⇒ m(x)m(y)^{MODVAL-2}=m(z)m(y)^{MODVAL-1} ⇒(フェルマーの小定理より)⇒ m(x)m(y)^{MODVAL-2}=m(z)
こんな感じ

cafeliercafelier2010/04/16 13:37素でない場合はそもそも先にmodを取ってしまうと情報が落ちて割り算が不可能になってしまうので、パスカルの三角形か何かで、割り算を回避して式を立てる必要があります。

n4_tn4_t2010/04/16 13:51腑に落ちました。どうもありがとうございます!

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100416

2010-04-04

SRM466

03:20 | SRM466 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM466 - naoya_t@topcoder SRM466 - naoya_t@topcoder のブックマークコメント

前回休んだのでちょっと久しぶり。1amまで寝てた。

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 LotteryCheating 提出 - 撃沈 - 0.0
1 550 LotteryPyaterochka 間に合わず - - - -
1 1000 - - -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100404