SRM467 の成績・ソース (要ログイン) : WA/AC/- : このセットでレート挙げられないようだとお先真っ暗ですだ…
500開く
- 問題短い！素敵！
- 『SS(0,n)=n、SS(k,n)=Σ_{i=1～n} SS(k-1,i) な関数があります SS(k,n)を求めよ。mod 1000000007 で』
- テストケース作成
- 最小ケース (1,1)
- 最大ケース (50,1000000000)
n=
1 2 3 4
------------------
k=0 1 2 3 4 ..
k=1 1 3 6 10
...
● ● ● ●
○
n=
1 2 3 4
------------------
k=0 1 2 3 4 ..
k=1 1 3 6 10
...
◆ ◆ ◆
◇
n=
1 2 3 4
------------------
k=0 1 2 3 4 ..
k=1 1 3 6 10
...
◆ ◆ ◆ ●
◇ ○
- てことは、左端の1 1 1...と上端の1 2 3 4...が
- いろんな経路を通って足されてきて、上から来た分●と左から来た分◇をたしたら欲しい○の値になるわけだから、
- SS(k,1)から○までの経路の個数*k + SS(0,2)からの経路の個数*2 + SS(0,3)からの経路の個数*3 + ...
- が答え。
- 経路の個数は、これは典型パターンだ。chokudaiさんの記事の「数学的解法」にあるとおり、組み合わせの個数nCkを使って求まる。
n=
1 2 3 4
------------------
-1 1 1 1 1 ... ← new!!!
k=0 1 2 3 4 ..
k=1 1 3 6 10
...
●
◇ ○
- こう一列増やして考えると、全部1になるので、「一番左上SS(-1,1)から○までの経路の個数」を求めればそれが答えになる。
- 手元のmod演算ライブラリにnCkの求め方まで入ってるのでコピペ
- 実質一行で解けちゃうんだけどこんなんでいいのかな。
- サンプル答え合った。
- あれ、自分で入れた最大ケースで0返してるけどなんで？？
- あ、そうか、C(10億+k,k+1) が答えだから、MOD 10億7 だと0になる
- ちょっと小さめのデータを入れてみると…なんか普通の値出た。良さそう。
- submit!!
static const LL MODVAL = 1000000007;
LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
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;
}
- 足し算、引き算、掛け算はそのまんまとして
- ベキ乗、xのe乗は、これも頻出テクニックだと思いますけど、eの二進数表示を考えながら、x,x^2,x^4,x^8,x^16,...を順番に計算しつつ必要なものだけ掛け算するという方法が高速です。
LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); }
- 問題は割り算。
- (x/y) % MODVAL ではマズい
- 足し算や掛け算は (x*y)%MODVAL = (x%MODVAL)*(y%MODVAL)%MODVAL のような式が成り立つので、引数が既にMOD済みの値であってもそのまま掛け算して大丈夫ですが、割り算はこれが成り立たないので注意が必要。
- (10/5)%3 = 2 ですが (10%3)/(5%3)=1/2=割り切れない！ とか
- どうするかというと
- 「割り算する」ではなくて「逆数を掛け算する」と考える
- 逆数 = かけると1になる数
- MODを取る値が素数の場合（topcoderで良く出てくる1000000007は素数です）は、MODの世界で必ず「逆数＝かけると１になる数」が存在して、とても簡単な式で求まります。
- つまりyの逆数は POW(y, MODVAL-2) です。
- 証明は フェルマーの小定理 を使う。
- フェルマー先生曰く
- y^{MODVAL-1} % MODVAL = 1
- なので、yをMODVAL-1回掛け算すると1になります
- ということは、yに、(yをMODVAL-2回かけた物)をかけると1になるので
- y の逆数は POW(y, MODVAL-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;
}
250開く
- 部屋で誰も解いてない
- Division Summaryみたらrngさんでも220点台だ。面倒くさいのかなあ。
- 『授業の開始待ちです。先生は時刻wAからbAの間のどこかの時間にランダムにやってきます。教室に入るのが、先生が教室に来た瞬間からlt秒以上遅れると遅刻認定されます注意。暇つぶしに、wait秒先生を待つ→その間に来なかったらwalk秒の散歩にでる、を繰り返すことにすると、遅刻認定を食らう確率は何％？』
- 1≦lt,walk,wait,wA≦1000000
- 0≦bA≦wA
- テストケースは適当に最小と最大を…
- bA=0 wA=10000000, walk,waitは中間の1000くらいなど
- 範囲が1000万しかないから、「先生がこの時間に来たら遅刻認定になる区間」を全部列挙して足し算して、wA-bAで割ればいい
- ガリガリと実装
- for(int t=0; t<=wA; t+=wait+walk) ...
- で各(wait,walk)セット毎にまずい時間の幅を求める
- 求める
- これ、t<=wAで大丈夫かな？先生が来る時間と遅刻認定デッドラインに幅があるから、もう一周念のためカウントした方がいいかもしれない
- for(int t=0; t<=wA+wait+walk; t+=wait+walk) ...
- (※ とするつもりで
- for(int t=0; t+wait+walk<=wA; t+=wait+walk) ...
- としていた。これはひどい…。こんなの無しで通るし、そもそもやるならltを足したりすべきではないのか、俺）
- できた
- 和を取ったものをwA-bAで割れば…
- 割れば…？
- これ 0 除算になる可能性あるよね
- wA=bAありうる。うん、なる。
- その場合は…別に場合分けすればいいか
- t = (wA=bA)%(wait+walk) が
- wait圏内ならセーフ
- walk圏内でも、t+ltがwalk圏外ならセーフ
- t<=wait || wait+walk<=t+lt
- ちょっとまって不等号これでいいか？
- t+lt がちょうと wait+walk の時は…
- 問題文を読むと…これは遅刻だ。アウト。
- ということはその場合は遅刻にするように修正。
- この辺のケースすごい撃墜ポイントっぽいなー、めも。
1000開く
- 『|seed|桁の[a-z]*の文字列で、連続するn文字に現れる文字の種類がたかだかd個であるものを辞書順に並べたとき、seed以上のものでk番目の文字列を求めてね』
- |seed|≦50
- n,d≦10
- kはlong longに入る程度
- 簡単のために seed = "aaa...aaa" の場合を考えてみる
- 26進数と思って…
- aで始まるパターンもbで始まるパターンも残りの並べ方の個数は同じだから、
- その「残りパターン数」でkを割れば一文字目がわかる
- みたいに再帰的にやればどうにか
- ↑これができれば二分探索でseed(以上の最小の条件を満たす文字列)も求まるから、それがi番目だったら全体ではi+k-1を求めればいいわけなので、↑が解ければ全部とける。
- さて
- なにか直前n文字に使った文字列を覚えるメモ化的な感じで…
- うまく正規化すれば2^10くらいのメモでどうにか…
- うーむ
- わからない
撃墜タイム
- wA==bAを重点的に見ていって1ミス1成功
- 自分のが変な不等式のおかげで撃墜されてる…
感想
