スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Facebook Hacker Cup 2011 Round 2

2/6 6:00~9:00 に行われた Facebook Hacker Cup 2011 Round 2 の参加記録。
Round 1 に比べると、ずいぶん難しかった。

Tag : プログラミング FBHC

結果

1. -
2. -
3. AC (2h42m)

Rank 133/364

3 問とも全然方針が立たなくて苦しかったけど、90 min くらい経ったところで 3. の解法に何とか気付くことができた。
Final に行くには Rank 25 以内が必要。
ちなみに、今年 2 完以上の人は 28 人いた。
来年にはそれだけの力がついているといいな。

問題

問題は最初 3 問。
問題はここから参照できるけど、Facebook のアカウントをもっていないと見られないかもしれない。

1. Scott's New Trick
与えられた素数 P と定数 A1, A2, A3, A4, A5, B1, B2, B3, B4, B5 (すべて 0 以上 P 未満) に対して、
長さ N の数列 { ai } と長さ M の数列 { bj } を次のように定義する。

a1 = A1
a2 = A2
ai = (ai-2 * A3 + ai-1*A4 + A5) mod P, for i = 3, .., N


b1 = B1
b2 = B2
bj = (bj-2 * B3 + bj-1 * B4 + B5) mod P, for j = 3, .., M


与えられた L (0 以上 P 以下) に対して、
#{ (ai, bj) | ai * bj < L; i = 1, 2, .., N; j = 1, 2, .., M }
を求めよ。
( #S は集合 S の元の個数とする。)

2. Studious Student II
長さ L (≦60) の a と b だけからなる文字列 s が与えられる。
この文字列に対して、以下の命令を繰り返し適用することを考える。

命令:
0 ≦ i < j < L なる整数 i, j を任意に選ぶ。
s[i] ~ s[j] からなる s の部分文字列を t とする。
t に含まれる文字 c を任意に 1 つ選ぶ。
s[i] ~ s[j] を 1 つの c に置き換える。

適用できる命令列は何通りあるか? mod 1000000007 で答えよ。
( 空の命令列もカウントすること )

3. Bonus Assignments
N (≦106) 人の社員にボーナスをあげよう。
社員 i のボーナスを bi と書くことにする。( bi は整数 )
ボーナスをあげる際には
min { bi | i = 1, 2, .., N } ∈ [A, B]
max { bi | i = 1, 2, .., N } ∈ [C, D]

をみたさなければならない。
( 1 ≦ A ≦ B ≦ 106, 1 ≦ C ≦ D ≦ 106, すべて整数 )

すべての社員は、ボーナスをもらうとコーラを買えるだけ買う。
( コーラの単価より少ない残金は使わずに持っている。)
コーラの単価はわからないが、2 以上の整数であることだけはわかっている。

コーラの単価がいくらであっても、少なくとも 1 人の社員がお金を残すようなボーナスの与え方は何通りあるか?
mod 1000000007 で答えよ。

解答

言語は C++。テンプレはここを参照。

3.
const ll M=1000000007;

map<ll,ll> memo;

ll modpow(int a,int n){
ll pow2[21]; // pow2[i] := a^(2^i) mod M
pow2[0]=a;
for(int i=1;i<=20;i++) pow2[i]=(pow2[i-1]*pow2[i-1])%M;

ll r=1;
for(int i=0;n;i++,n>>=1){
if(n&1) r=(r*pow2[i])%M;
}
return r;
}

ll countCoprime(int n,int l,int u){
if(l>u) return 0;
if(l==u){
if(l==1) return 1;
else return 0;
}

ll code=u*(1LL<<30)+l;
if(memo.count(code)==1) return memo[code];

ll whole=modpow(u-l+1,n);

ll cnt=0;
for(int i=2;i<=u;i++){
cnt=(cnt+countCoprime(n,(l+i-1)/i,u/i))%M;
}
return memo[code]=(whole-cnt+M)%M;
}

int main(){
int T; scanf("%d",&T);
while(T--){
memo.clear();

int n,a,b,c,d; scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
ll ans=0;
ans=(ans+countCoprime(n,a,d))%M;
ans=(ans-countCoprime(n,b+1,d)+M)%M;
ans=(ans-countCoprime(n,a,c-1)+M)%M;
ans=(ans+countCoprime(n,b+1,c-1))%M;
printf("%lld\n",ans);
}

return 0;
}

競技中に考えたのはもっと粗いものだったけど、ちゃんと書こうとするとかなり長くなってしまった。


まず、少なくとも 1 人がお金を残すというのはどういうことかを考える。
実は、これは
gcd(b1, b2, .., bN) = 1
であることと同値。
その理由は否定を考えたほうがわかりやすいかもしれない。
否定命題は
「全員が残金ゼロ ⇔ gcd(b1, b2, .., bN) > 1」
( ⇒ )
コーラの値段を C とすると、
全員が残金ゼロということは、すべての i で bi は C の倍数ということ。
このとき、gcd() > C > 1 となるから、⇒ は正しい。
( <= )
すべての i で bi は gcd(b1, b2, .., bN) の倍数になっているので、C = gcd(b1, b2, .., bN) としたときには残金ゼロになる。
ゆえに正しい。

問題を改めて書くと、
3 つの条件
(a) min { bi } ∈ [A, B]
(b) max { bi } ∈ [C, D]
(c) gcd(b1, b2, .., bN) = 1

をみたす N 次元ベクトル b = (b1, b2, .., bN) ∈ [A, D]N はいくつあるか? が訊かれている。
( 区間の右上添え字は、直積集合の意味。また、区間の記号で書いているけど、整数点のみを考えている。)

次に、問題を考えやすいように 2 つに分解する。
ステップ 1 では、条件(a)(b)を簡単な形に書き換える。
これは、数学的な式変形だけでできる。

考えている全体集合を X = [A, D]N とおく。
{ min b ∈ [A, B] } := { b ∈ [A, D]N | min { bi } ∈ [A, B]; i = 1, 2, .., N } などと略記する。

この記号を使えば、条件 (a)(b) は、それぞれ

{ min b ∈ [A, B] } = X \ { min b ∈ (B, D] }
{ max b ∈ [C, D] } = X \ { max b ∈ [A, C) }

となるから、 (a) かつ (b) は次のようになる。

{ min b ∈ [A, B] and max b ∈ [C, D] }
= ( X \ { min b ∈ (B, D] } ) ∩ ( X \ { max b ∈ [A, C) } )
= X \ { min b ∈ (B, D] } \ { max b ∈ [A, C) }

包除原理により、この集合の元の個数は

#{ min b ∈ [A, B] and max b ∈ [C, D] }
= #X - #{ min b ∈ (B, D] } - #{ max b ∈ [A, C) } + #{ min b ∈ (B, D] and max b ∈ [A, C) }
= #X - #{ min b > B } - #{ max b < C } + #{ min b > B and max b < C }
= #[A, D]N - #[B+1, D]N - #[A, C-1]N + #[B+1, C-1]N

で計算できる。
実際に求めたいのは、(a) かつ (b) かつ (c) の集合の要素数なので、それは

#{ (a) and (b) and (c) }
= #{ b ∈ [A, D]N and (c) } - #{ b ∈ [B+1, D]N and (c) } - #{ b ∈ [A, C-1]N and (c) } + #{ b ∈ [B+1, C-1]N and (c) }

これで (a) かつ (b) かつ (c) という複雑な問題を "区間内にある (c)" という問題に分解できた。

ステップ 2 では、一般の自然数 P, Q (P≦Q) に対して、
#{ b ∈ [P, Q]N and (c) }
すなわち #{ b ∈ [P, Q]N and gcd(b) = 1 }
を計算する方法を考える。
これがわかれば、問題が解けたことになる。

b ∈ [P, Q]N である b に対しては、gcd(b) ≦ Q となることに注目する。
gcd の上限がわかったので、次の式変形が使える。

#{ b ∈ [P, Q]N and gcd(b) = 1 }
= #{ b ∈ [P, Q]N }
- #{ b ∈ [P, Q]N and gcd(b) = 2 }
- #{ b ∈ [P, Q]N and gcd(b) = 3 }
:
- #{ b ∈ [P, Q]N and gcd(b) = Q }

2 ≦ k ≦ Q なる k に対して、gcd(b) = k となる b はどのようなものかを考えると、
b の各成分は k の倍数なのだから、
ある b' ( gcd(b')=1 ) があって b = k b' となっているはず。
ここで、b' ∈ [ceil(P/k), floor(Q/k)] である。
つまり、

#{ b ∈ [P, Q]N and gcd(b) = k }
= #{ b ∈ [ceil(P/k), floor(Q/k)]N and gcd(b') = 1 }

だから、サイズ [P, Q] の問題がサイズ [ceil(P/k), floor(Q/k)] のより小さな問題に変換できたことになる。
また、もちろん
#{ b ∈ [1, 1]N and gcd(b) = 1 } = 1
#{ b ∈ [k, k]N and gcd(b) = 1 } = 0 (k≧2)
である。これが基底状態になる。

以上より、目的の値は再帰的に計算できることがわかった。

上のコードはメモ化再帰で実装してある。
愚直に再帰していると時間がかかりすぎたので、べき剰余の計算を高速化したり、P,Q をメモ化したりするとテストケース 1 つにつき約 1 秒で計算できるようになった。
計算量は O(D*logD*logN) くらいだと思う。


上位者のコードを見ていると、Moebius 関数を使った解法がいくつかあった。
これに関しては私は全く知らないので、今後の勉強課題。

あと、上記の解法と似た方針で、gcd の値を使って DP することもできるみたい。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。