スポンサーサイト

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

CodeChef September Cook-Off

2011/09/19 01:00 ~ 03:30 (JST)
CodeChef September Cook-Off の参加記録

なかなか書く時間が取れなかったので 2 ヶ月遅れの更新。

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

結果

A. 4WA, AC (00:40:36)
B. AC (00:16:17)
C. AC (01:20:22)
D. -
E. -
Standing : 53/557
Rank (Short) : 33 → 39
Rating (Short) : 1436.611 → 1490.446


問題

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

A. Digit Rotation

8 桁以下の自然数 A が与えられる。
A を 10 進数で書いたものに
操作
・ 左に 1 文字だけ rotate
・ 右に 1 文字だけ rotate
を好きなだけ行い、値を最大化せよ。
leading zero が現れた瞬間、その 0 はなかったものになる。

B. Hotel Bytelandia

N 人の客のホテルへの到着時間と出発時間が与えられる。
最大で何人の客が同時にホテルにいることになるか?

N ≦ 100

C. Last Digit Sum
非負整数 N に対して
S(N) := ( N の奇数桁の数字の和 ) + 2 × ( N の偶数桁の数字の和 )
D(N) := S(N) の最下位桁の数字
と定める。
D(A) + D(A+1) + ... + D(B) を求めよ。

0 ≦ A ≦ B ≦ 400,000,000

解答

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

A.
string trim0(string s){
int len=s.length(),i;
for(i=0;i<len;i++) if(s[i]!='0') break;
if(i==len) i--;
return s.substr(i);
}

int rotL(int n,int k){
char _s[10]; sprintf(_s,"%d",n);
string s(_s);
rep(i,k){
s=s.substr(1)+s[0];
s=trim0(s);
}
int res; sscanf(s.c_str(),"%d",&res);
return res;
}

int rotR(int n,int k){
char _s[10]; sprintf(_s,"%d",n);
string s(_s);
rep(i,k){
int len=s.length();
s=s[len-1]+s.substr(0,len-1);
s=trim0(s);
}
int res; sscanf(s.c_str(),"%d",&res);
return res;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,ans=0; scanf("%d",&n);
ans=max(ans,rotL(rotR(n,1),1));
ans=max(ans,rotR(rotL(n,1),1));
rep(i,9){
ans=max(ans,rotL(n,i+1));
ans=max(ans,rotR(n,i+1));
}
printf("%d\n",ans);
}
return 0;
}

実際に rotate してみればいい。
うっかり探しもらしやすい状態があるので、気をつけて実装する。
たくさん WA った。

B.
int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
pii a[200];
rep(i,n) scanf("%d",&a[ i ].first), a[ i ].second=1;
rep(i,n) scanf("%d",&a[i+n].first), a[i+n].second=0;

sort(a,a+2*n);

int ans=0,cnt=0;
rep(i,2*n){
if(a[i].second==1) cnt++; else cnt--;
ans=max(ans,cnt);
}
printf("%d\n",ans);
}

return 0;
}

ソートして、時刻の早い順に hoge する。

C.
int len;
char dgt[16];

vector dp[16];

vector dfs(int i,bool b){
if(b && !dp[len-i].empty()) return dp[len-i];

vector res(10);
if(i==len){
res[0]=1;
return res;
}

vector tmp(10);
// 上の桁で余裕を作った
if(b){
rep(d,10){
tmp=dfs(i+1,true);
rep(j,10) res[(j+(d%2?1:2)*d)%10]+=tmp[j];
}
dp[len-i]=res;
}
// 余裕がない
else{
int ub=dgt[i]-'0';
rep(d,ub+1){
tmp=dfs(i+1,d rep(j,10) res[(j+(d%2?1:2)*d)%10]+=tmp[j];
}
}
return res;
}

ll f(ll a){
if(a<0) return 0;

sprintf(dgt,"%lld",a);
len=strlen(dgt);

vector res=dfs(0,false);
ll res2=0;
rep(i,10) res2+=i*res[i];
return res2;
}

int main(){
int T; scanf("%d",&T);
while(T--){
ll a,b; scanf("%lld%lld",&a,&b);
printf("%lld\n",f(b)-f(a-1));
}
return 0;
}

界隈では桁DPといわれているアレ。
いまだに書き慣れない。
D(N) を計算するには S(N) の値そのものは必要なくて、S(N) mod 10 がわかれば十分だというのがポイント。

意外にもたくさんの人が AC していた。
数学的にも解けるらしい。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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