スポンサーサイト

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

Codeforces Round #104

2012/01/22 16:00~18:00 (JST)
Codeforces Round #104 (Div.1) の参加記録

lucky number 回

Tags : プログラミング Codeforces 未解決

結果

A. AC (00:03)
B. AC (01:03)
C. -
D. -
E. -
Standing : 145/454
Rating : 20432009


問題

問題セットの原文はここを参照。

A. Lucky Conversion

すべての桁が 4 または 7 である自然数を lucky number と呼ぶ。

n ≦ 10^5 桁以下の lucky number が 2 つ与えられる。
2 つの数の桁数は等しい。

操作
・ ある桁を 4 なら 7 に、7 なら 4 に入れ替える
・ ある桁とある桁を交換する
を繰り返して、一方をもう一方に一致させたい。

最小で何回の操作が必要か?

B. Lucky Number 2

・ "4" が a1 個
・ "7" が a2 個
・ "47" が a3 個
・ "74" が a4 個
含まれる最小の lucky number を求めよ。

1 ≦ a1, a2, a3, a4 ≦ 10^6

C. Lucky Subsequence

長さ n の数列 a[1..n] が与えられる。
長さ k の部分列で、同じ lucky number は高々 1 つしか含まないようなものはいくつあるか?
mod 10^9+7 で求めよ。

1 ≦ k ≦ n ≦ 10^5
1 ≦ a[i] ≦ 10^9

解答

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

A.
int main(){
char s[100001],t[100001]; gets(s); gets(t);
int n=strlen(s);
int a=0,b=0;
rep(i,n) if(s[i]!=t[i]) {
if(s[i]=='4') a++;
else b++;
}
printf("%d\n",max(a,b));
return 0;
}

1 つめの操作は 1 箇所をそろえるということ。
2 つめの操作は同時に 2 箇所をそろえるということ。
なので、できるだけ 2 つめの操作をしたほうがいい。

2 つの文字列を s, t とする。
a := ( s[i]==4 かつ t[i]==7 となる i の個数 )
b := ( s[i]==7 かつ t[i]==4 となる i の個数 )
とすると、
2 つめの操作は min(a,b) 回できる。
1 つめの操作は残った max(a,b) - min(a,b) 回行うことになる。

なので、答えは min(a,b) + (max(a,b) - min(a,b)) = max(a,b) 回。

きれいな問題。けっこう好きです。

B.
int main(){
int a1,a2,a3,a4; scanf("%d%d%d%d",&a1,&a2,&a3,&a4);

if(a3==a4+1){ // 4...7
if(a1>a4 && a2>a4){
rep(i,a1-a4) printf("4");
rep(i,a4) printf("74");
rep(i,a2-a4) printf("7");
puts("");
return 0;
}
}
else if(a3+1==a4){ // 7...4
if(a1>a3 && a2>a3){
printf("7");
rep(i,a1-a3) printf("4");
rep(i,a3-1) printf("74");
rep(i,a2-a3) printf("7");
printf("4\n");
return 0;
}
}
else if(a3==a4){ // 4...4 or 7...7
if(a1>=a3 && a2>=a3 && (a1>a3 || a2>a3)){
if(a1>a3){ // 4...4
rep(i,a1-a3) printf("4");
rep(i,a3-1) printf("74");
rep(i,a2-a3+1) printf("7");
printf("4\n");
}
else{ // 7...7
rep(i,a1) printf("74");
rep(i,a2-a1) printf("7");
puts("");
}
return 0;
}
}

puts("-1");

return 0;
}

単純な規則性があると思ったので、まずは答えを全探索するコードを書いて、それを何度も実行しながら規則を探した。

a3 と a4 が 2 以上違うとき、あきらかに解なし。
なぜなら、47 が 2 つあれば、その間に 74 が 1 つあるから。

大雑把には、答えは
4444474747477777
みたいな形になる。
細かいところはていねいに場合わけする。

小さいケースを列挙して全探索コードと比較したのでシステムテストも怖くなかった。

C. ( あとで解いた )
const ll M=1000000007;

vector<ll> lucky;

void dfs(ll a){
if(a>(ll)(1e10)) return;
if(a>0) lucky.push_back(a);
dfs(10*a+4);
dfs(10*a+7);
}

ll xgcd(ll a,ll b,ll &x,ll &y){
if(b==0){ x=1; y=0; return a; }
ll g=xgcd(b,a%b,y,x); y-=a/b*x;
return g;
}

ll modinv(ll a,ll m){
ll x,y;
if(xgcd(a,m,x,y)==1) return (x+m)%m;
return -1;
}

ll fact[100001],ifact[100001];
ll nCr(int n,int r){ return fact[n]*ifact[r]%M*ifact[n-r]%M; }

int solve(int n,int k,int one,const vector<int> &a){
int m=a.size();

// dp[i][i] := i 個目まで見て、うち j 個選んだときの場合の数 (容量節約のために i は使いまわす)
static ll dp[2][1023];
dp[1][0]=1;
rep(i,m){
rep(j,i+1){
dp[0][j]=dp[1][j];
dp[1][j]=0;
}
rep(j,i+1){
dp[1][j+1]=(dp[1][j+1]+dp[0][j]*a[i])%M; // i 個目を選んだ
dp[1][ j ]=(dp[1][ j ]+dp[0][j])%M; // 選ばなかった
}
}

ll ans=0;
rep(i,one+1) if(0<=k-i && k-i<=m) ans=(ans+nCr(one,i)*dp[1][k-i])%M;
return ans;
}

int main(){
dfs(0);
sort(lucky.begin(),lucky.end());

fact[0]=ifact[0]=1;
rep(i,100000){
fact[i+1]=(i+1)*fact[i]%M;
ifact[i+1]=modinv(fact[i+1],M);
}

int n,k; scanf("%d%d",&n,&k);
int a[100000];
rep(i,n) scanf("%d",a+i);

int one=0;
vector<int> A;
map<ll,int> f;
map<ll,int>::iterator it;
rep(i,n){
int j=lower_bound(lucky.begin(),lucky.end(),a[i])-lucky.begin();
if(j<lucky.size() && lucky[j]==a[i]) f[lucky[j]]++; else one++;
}
for(it=f.begin();it!=f.end();++it) A.push_back(it->second);

printf("%d\n",solve(n,k,one,A));

return 0;
}

コンテスト中は O(n^2) の DP しか思い浮かばなかった。
twitter でポイントを教えてもらった。

10^9 以下の lucky number は 1022 個しかないので、1022*n 回ループが間に合うということが重要。

a[1..n] の中の lucky number とそうでない数を別々に考える。
答えは
Σ[i=0..n] ( lucky number を重複なく i 個選ぶ場合の数 )×( lucky number でない数を n-i 個選ぶ場合の数 )
と書ける。もちろん mod で。

lucky number を重複なく i 個選ぶ場合の数は、1022 × n の DP で求める。

lucky number でない数を n-i 個選ぶ場合の数は、n'Cn-i 通り。
ここで、n' は a[1..n] の中にある lucky number でない数の個数。
nCr の計算は、階乗と階乗の mod での逆元を O(n log MOD) くらいで前計算しておけば O(1) でできる。

lucky number が少ないというキーポイントを聞いたらすぐに解けた。
この問題が解けなかったのはだめだめなので、同じミスをしないように深く心に刻み込む。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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