スポンサーサイト

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

CodeChef September Long Contest 2011

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

そろそろ、正解者が少ない問題も 1 問くらいは解けるようになりたい。

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. AC [1 pts]
B. -
C. -
D. -
E. -
F. AC [1 pts]
Standing : 29/711 (※ 29 位が 200 人以上いる)
Rank (Long) : 113 → 111
Rating (Long) : 90.774 → 96.914


問題

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

A. Younger Brother
格子が書かれた C 個の盤を使って 2 人でゲームをする。
盤 i のサイズは Mi × Ni である。

ゲームはターン制で行われる。
ゲームの開始時には、すべての盤のマス (1, 1) に 1 つずつ駒が置かれる。
各プレイヤーは、(i, j) にある 1 つの駒を選んで、その駒を
(i+1, j), (i+2, j), (i, j+1), (i, j+2), (i+1, j+1), (i+2, j+2)
のいずれかのマスに移動させる。
盤の外には移動させられない。

動かすことのできる駒がなくなったプレイヤーの負け。

両プレイヤーが最善手をとると仮定するとき、先手必勝かどうかを判定せよ。

1 ≦ テストケース数 ≦ 10000
1 ≦ C ≦ 20
2 ≦ Mi, Ni ≦ 1000

B.

C.

D.

E.

F. BIT Magazine
N ページの本がある。
1 ページ目と 2 ページ目は同じ紙 (の表と裏) に印刷されている。
3 ページ目と 4 ページ目...についても同様。

全 N ページのうち、F 個のページにはページ番号が印刷されていない。
( 印刷されていないページ番号はすべてわかっている )

さらに、この本に使われている紙のうち T 枚が破れてしまった。

どの T 枚が破れる確率も等しいとするとき、残っているページ番号の和の期待値を求めよ。

N ≦ 2000

解答

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

A.
int main(){
int T; scanf("%d",&T);
while(T--){
int c,g=0; scanf("%d",&c);
while(c--){
int m,n; scanf("%d%d",&m,&n);
g^=(m+n+1)%3;
}
puts(g!=0?"MasterChef":"Football");
}
return 0;
}

1 つの盤に限定して、駒があるマスにあるときの Grundy 数を計算してみると、非常にシンプルな規則があることがわかる。
5 × 5 の盤だと、
21021
10210
02102
21021
10210

となる。( 左上が (1, 1) で右下が (5, 5) )

この規則性から、各盤の Grundy 数が O(1) で求められる。
あとは、それらの XOR をとって 0 かどうかを見ればいい。

Grundy 数の問題は Chef では頻出。

B.


C.

けっこう色々考えたのだけど、結局、TLE しない解法が思いつかなかった。
うまく状態をもって BFS か Dijkstra をする。
それでダメなら、A* などのさらなる工夫をするのかと思っていた。

あとで復習しよう。

D.


E.


F.
int main(){
int T; scanf("%d",&T);
while(T--){
int n,m; scanf("%d%d",&n,&m);
int sum=n*(n+1)/2;
rep(i,m){
int a; scanf("%d",&a);
sum-=a;
}

n=(n+1)/2;
int k; scanf("%d",&k);
printf("%.4f\n",(double)sum*(n-k)/n);
}

return 0;
}

本には M := ceiling(N/2) 枚の紙が使われている。

ページ i が破られない確率 P は、
P = i が破られない破り方 / 全ての破り方 = M-1CT / MCT = (M-T) / M
となる。
これは i によらない。( どのページが破られる確率も等しいのだから当然といえば当然 )

あとは、期待値の定義にしたがって計算すればいい。
P が i によらないのでループを回す必要すらない。

上記のソースコードと、この説明で使った文字は対応していないので注意。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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