スポンサーサイト

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

Facebook Hacker Cup 2012 Round 1

2011/01/29 03:00 ~ 01/30 03:00 (JST)
Facebook Hacker Cup 2012 Round 1 の参加記録

500 位の人が解いた問題数以上を解けば通過

Tags : プログラミング FBHC

結果

A. AC
B. AC
C. AC


全部通った。よかった。

A, B はおもしろかった。
C はふつうすぎてつまらなかった。

問題

問題セットの原文はここを参照。 ( Facebook でのログイン必須 )

A. Checkpoint
自然数 S が与えられる。

2 次元のグリッド上に 2 点 (m, n), (x, y) ( 0 ≦ m ≦ x, 0 ≦ n ≦ y, (m, n) ≠ (0, 0), (m, n) ≠ (x, y) ) をとり、
(0, 0) から (m, n) を経由して (x, y) へ至る最短ルートの本数がちょうど S 通りあるようにする。
ここで、ルートはグリッド上のもののみを考え、斜め方向には移動できないものとする。

x + y の最小値を求めよ。

1 ≦ S ≦ 10^7

B. Recover the Sequence

次の擬似コード ( 原文から転載 ) にしたがってマージソートをする。
function merge_sort(arr):
n = arr.length()
if n <= 1:
return arr

// arr is indexed 0 through n-1, inclusive
mid = floor(n/2)

first_half = merge_sort(arr[0..mid-1])
second_half = merge_sort(arr[mid..n-1])
return merge(first_half, second_half)

function merge(arr1, arr2):
result = []
while arr1.length() > 0 and arr2.length() > 0:
if arr1[0] < arr2[0]:
print '1' // for debugging
result.append(arr1[0])
arr1.remove_first()
else:
print '2' // for debugging
result.append(arr2[0])
arr2.remove_first()

result.append(arr1)
result.append(arr2)
return result

配列のサイズ N とデバッグ出力の文字列が与えられるとき、ソート前の配列を復元せよ。
配列そのものではなく、次のチェックサムを計算し出力すること。
function checksum(arr):
result = 1
for i=0 to arr.length()-1:
result = (31 * result + arr[i]) mod 1000003
return result

2 ≦ N ≦ 10000

C. Squished Status

'0', '1', ..., '9' からなる長さ 1000 以下の文字列が与えられる。
これを適当に分割して、分割したすべてのパーツが 10 進数として 1 以上 M 以下の値に収まるようにしたい。
分割方法は何通りあるか?

2 ≦ M ≦ 255

解答

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

A.
const int INF=1<<29;

vector<int> divisor(int a){
vector<int> res;
for(int i=1;i*i<=a;i++) if(a%i==0) {
res.push_back(i);
if(i*i<a) res.push_back(a/i);
}
return res;
}

int main(){
// f(x) := min{ n | nCr = x }
static int f[10000001];
for(int n=1;n<=10000000;n++) f[n]=INF;
for(int n=1;n<=10000000;n++){
ll nCr=1;
rep(r,n+1){
if(nCr>=10000000) break;
f[nCr]=min(f[nCr],n);
nCr=(n-r)*nCr/(r+1);
}
}

int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n; scanf("%d",&n);
vector<int> d=divisor(n);

int ans=INF;
rep(i,d.size()) ans=min(ans,f[d[i]]+f[n/d[i]]);
printf("Case #%d: %d\n",T,ans);
}

return 0;
}

上記問題文の記号を使うと、
S = m+nCm × (x-m)+(y-n)Cx-m
となる m, n, x, y に対して x + y を最小化する問題と考えられる。 ( 高校数学の知識 )

x + y = (m+n) + (x-m)+(y-n) と変形しておく。

S の制約から、nCr > 10^7 となる n, r は考えなくていいことがポイント。
このことから、計算に登場しうる二項係数の値をすべて前計算しておくことができる。
具体的には、
f (x) := ( nCr = x をみたす最小の n )
を 1 ≦ x ≦ 10^7 について記録する。
そのような (n, r) の組が存在しない x については f (x) := INF とでもしておく。

S が 2 つの二項係数の積で書けているので、答えは
min{ f (d) + f (S/d) | d は S の約数 }
で求まる。

B.
int idx;
string s;

void merge(int *beg1,int *end1,int *beg2,int *end2){
int n_res=0;
static int res[10000];

int i1=0,i2=0;
while(beg1+i1!=end1 && beg2+i2!=end2){
if(s[idx]=='1') res[n_res++]=beg1[i1++];
else res[n_res++]=beg2[i2++];
idx++;
}
while(beg1+i1!=end1) res[n_res++]=beg1[i1++];
while(beg2+i2!=end2) res[n_res++]=beg2[i2++];

rep(i,n_res) beg1[i]=res[i];
}

void merge_sort(int *beg,int *end){
int n=end-beg;
if(n<=1) return;

int mid=n/2;

merge_sort(beg,beg+mid);
merge_sort(beg+mid,end);

merge(beg,beg+mid,beg+mid,end);
}

int checksum(int n,const int *a){
int res=1;
rep(i,n) res=(31*res+a[i]+1)%1000003;
return res;
}

int main(){
int T0; cin>>T0;
for(int T=1;T<=T0;T++){
int n; cin>>n>>s;
int a[10000];
rep(i,n) a[i]=i;

idx=0;
merge_sort(a,a+n);

int inv[10000];
rep(i,n) inv[a[i]]=i;

printf("Case #%d: %d\n",T,checksum(n,inv));
}

return 0;
}

デバッグ情報から、どのようにマージされたのかがすべてわかる。
1, 2, ..., N という配列についてマージソートをシミュレートして、結果の配列の逆置換を求めれば答えになる。

vector を使わないとか、無用な高速化をがんばった。

C.
const ll M=4207849484LL;

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int m;
char s[1001]; scanf("%d%s",&m,s);
int len=strlen(s);

// dp[i+1] := 部分文字列 s[0..i] についての解
ll dp[1001]={1};
rep(i,len){
int d=s[i]-'0';
if(1<=d && d<=m) dp[i+1]=(dp[i+1]+dp[i])%M;

if(i-1<0) continue;
d+=10*(s[i-1]-'0');
if(1<=d && d<=m && s[i-1]!='0') dp[i+1]=(dp[i+1]+dp[i-1])%M;

if(i-2<0) continue;
d+=100*(s[i-2]-'0');
if(1<=d && d<=m && s[i-2]!='0') dp[i+1]=(dp[i+1]+dp[i-2])%M;
}

printf("Case #%d: %lld\n",T,dp[len]);
}

return 0;
}

ふつうの 1 次元 DP.
dp[i] := ( i 文字目までの部分文字列についての解 )
0 の扱いにだけ注意する。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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