スポンサーサイト

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

CodeChef July Long Contest 2011

CodeChef July Long Contest 2011 の参加記
2011/07/01 18:30 ~ 07/11 18:30 (JST)

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. AC [1 pts]
B. -
C. AC [0.991 pts]
D. AC [1 pts]
E. -
F. -
Standing : 45/460
Rank (Long) : 138 → 121
Rating (Long) : 71.739 → 83


問題

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

A. A-E Hash Function
文字列 S を引数にとり、整数値を返す関数 hash を次で定義する。
function hash(S):
result = number of characters 'A' in S
if |S| > 1:
(S1, S2) = split(S)
result = result + max(hash(S1), hash(S2))
end if
return result
end function

ここで、split(S) は S を前半 S1 と後半 S2 に分割する関数。
S の長さが奇数のときは S2 のほうが 1 文字多くなるようにする。

nA 個の 'A' と nE 個の 'E' からなる文字列 S で、hash(S) = V となるものが何通りあるかを mod 1000000007 で求めよ。

0 ≦ nA, nE ≦ 50
0 ≦ V ≦ 1000

B. Billboards
一直線にのびた高速道路に N 枚の看板が設置されている。
これらの看板から何枚かを選んで、広告を貼る。

このとき、
どの連続する M 枚の看板の中にも、少なくとも K 枚の広告が貼ってあるようにしたい。
さらに、この条件を満たした上で、広告の枚数を最小にしたい。

そのような看板の選び方の総数を mod 1000000007 で求めよ。

1 ≦ K ≦ M ≦ 50
M ≦ N ≦ 109

C. Large Kitchen
M × N のグリッド上に、次の条件を満たすように # を配置せよ。
# の個数が多いほど良い解とする。

・ 任意の 2 つの # に対して、それらをつなぐ # の列がとれる。 (4 近傍で考える)
・ 長さ 3 以上の # からなる閉路は存在しない。

10 ≦ M, N ≦ 100

D. Most Popular Friend
n 人の人がいて、誰と誰が友達であるという情報が複数与えられる。
i と j の距離を、 「 i から d 人の友人を経由すれば j にたどりつける」 ような d の最小値として定義する。

「自分以外のすべての人からの距離の平均値が最小になる人」 は誰かを求めよ。

1 ≦ n ≦ 100

E. Wireless Network
2 次元平面上に S 個のアクセスポイントがある。
各アクセスポイントには、接続できるコンピュータの数の上限が定められている。

C 台のコンピュータを 1 台ずつ平面に置いていく。
各コンピュータは 1 つのアクセスポイントと接続しければいけない。

コンピュータを置く各ステップにおいて、
コンピュータと、接続しているアクセスポイントとの距離の最小値を求めよ。

1 ≦ S ≦ 30
1 ≦ アクセスポイントの接続上限 ≦ 30
1 ≦ C ≦ アクセスポイントの接続上限の総和

F.

解答

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

A.
const ll M=1000000007;

ll dp[51][51][153];

// A=a, E=e のとき、hash(S)<=v となる S の総数
ll solve(int a,int e,int v){
if(v<0) return 0;

if(~dp[a][e][v]) return dp[a][e][v];

if(a+e<=1) return dp[a][e][v]=(a<=v);

ll res=0;
int m=(a+e)/2;
rep(i,m+1) if(i<=a && m-i<=e) {
res+=solve(i,m-i,v-a)*solve(a-i,e-(m-i),v-a);
res%=M;
}
return dp[a][e][v]=res;
}

int main(){
memset(dp,-1,sizeof dp);

int T; scanf("%d",&T);
while(T--){
int a,e,v; scanf("%d%d%d",&a,&e,&v);
if(v>152) puts("0");
else{
ll ans=(solve(a,e,v)-solve(a,e,v-1))%M;
if(ans<0) ans+=M;
printf("%lld\n",ans);
}
}
return 0;
}

hash の動作をじっくり見てみると、hash(S) の値はそれほど大きくならないことが分かる。
最大ケース nA = nE = 50 のときでも hash(S) ≦ 152 となる。
( どのような文字列で 152 になるかは忘れてしまった。 )

これに気付けば、
dp[nA][nE][V] := ( nA 個の A, nE 個の E からなる文字列 S で、hash(S)=V となるものの総数 )
として、DP (メモ化再帰) ができる。

DP の各段階では、S1 に A を何個割り当てるかでループすることで、小さいサイズの問題に帰着している。
今年の ICPC 国内予選 E に似ている気がした。

※ V ≦ 1000 で DP すると TLE するかもしれない。試してないけど。

B.


C.
const char *pttn[]={
"###.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.#####.###",
"#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#",
"##.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.##",
"#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#",
"##.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.##",
( 中略 )
"#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#",
"##.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.##",
"#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#.###.#"
};

int main(){
int T; scanf("%d",&T);
while(T--){
int m,n; scanf("%d%d",&m,&n);
static char grid[100][101];

rep(i,m){
strncpy(grid[i],pttn[i],n);
grid[i][n]='\0';
}

if(n%3==0){
if(n%6==0){
rep(i,m) grid[i][n-1]=(i%4==3?'.':'#');
grid[0][n-1]='.';
if(m%4==1){
grid[m-3][n-1]='.';
grid[m-2][n-1]='#';
grid[m-1][n-1]='#';
}
}
else{
rep(i,m) grid[i][n-1]=(i%4==2?'.':'#');
if(m%4==0){
grid[m-3][n-1]='.';
grid[m-2][n-1]='#';
grid[m-1][n-1]='#';
}
}
}

rep(i,m) puts(grid[i]); putchar('\n');
}

return 0;
}

それなりによさそうなパターンを見つけて埋め込んだだけ。
右端で # が分断されないされないように少し工夫した程度。

D.
int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
int adj[100][100];
rep(u,n) rep(v,n) adj[u][v]=(u==v?0:INF);
rep(u,n){
do{
int v; scanf("%d",&v);
v--;
adj[u][v]=1;
}while(getchar()!='\n');
}

rep(k,n) rep(i,n) rep(j,n) if(adj[i][k]+adj[k][j]<adj[i][j]) adj[i][j]=adj[i][k]+adj[k][j];

int ans,ans_sum=INF;
rep(u,n){
int sum=0;
rep(v,n) sum+=adj[u][v];
if(sum<ans_sum){
ans=u;
ans_sum=sum;
}
}
printf("%d %.6f\n",ans+1,(double)ans_sum/n);
}

return 0;
}

人を頂点、友達であるという関係を辺としたグラフで Warshall-Floyd やるだけ。
CodeChef らしくない問題。

E.

コンピュータを置く各段階ごとに、「二分探索 + 最大流」 で最適解を計算してみたが、最後まで TLE が取れなかった。
何ヶ月か前にあったダンスホールの問題のように、直前の結果をうまく再利用することも考えたけど、結局うまい方法が見つからなかった。

F.

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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