スポンサーサイト

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

September Cook-Off 2012

一番難しいのが解けないので 10 位以内に入れない。

Tags プログラミング CodeChef

結果

5 問中 4 問解いて 17 位。最後はちまちま実験してたけどダメだった。

問題

CARVANS. Carvans
直線上を N 台の車が順番に走る。
車はできるだけ速く走る。
前の車を追い越せない。
最高速を出せる車は何台あるか?

1 ≦ N ≦ 10000

COALSCAM. Coal Scam
辺に重みがついた無向グラフがある。
辺にはタイプ 1 とタイプ 2 の二種類がある。
このグラフの全域木を作り、全域木に使われているタイプ 2 の辺の重みの和を最大化せよ。
答えが複数あるときは、その中で使われているタイプ 1 の辺の重みの和を最小化せよ。

2 ≦ |V| ≦ 5000
1 ≦ ( タイプ 1 の辺の数 ) ≦ 20000
1 ≦ ( タイプ 2 の辺の数 ) ≦ 20000

PPERM. Prime Permutations
{1, 2, .., N} の順列 p が prime permutation であるとは、すべての i = 1, 2, .., N について、p[i] が p[1..i] の中で X 番目に小さいことをいう。
ここで、X は 1 または素数。

N が与えられたとき、prime permutation の個数を mod 10^9+7 で求めよ。

1 ≦ テストケース数 ≦ 5・10^5
1 ≦ N ≦ 5・10^6

PTOSS. Pizza Tossing
今までコインを M 回投げた結果と、長さ N の lucky sequence が与えられる。
lucky sequence は表or裏からなる列。
このままコインを投げつづけると、lucky sequence が部分文字列としてはじめて現れるまでにコインを何回投げることになるか? 期待値を mod 10^9+7 で求めよ。( 答えは整数であることが知られている。)
コインの表と裏は等確率で出て、各試行は独立とする。

1 ≦ M, N ≦ 10^6

RRECIPE. Recipe Reconstruction
アルファベット小文字からなる穴あきの文字列が与えられる。
穴を埋めて回文を作る方法は何通りあるか? mod 10^7+9 で。

1 ≦ 文字列長 ≦ 10^6

解答

CARVANS
min を取りながら前からなめる。簡単。

http://www.codechef.com/viewsolution/1363352

COALSCAM
タイプ 2 の辺で最大全域森を作って、そのままタイプ 1 の辺で最小全域木を作る。Kruskal を二回。簡単。

http://www.codechef.com/viewsolution/1364146

PPERM
実験すると簡単な規則性がみえる。
dp[i] := ( 長さ i の prime permutation の個数 )
として DP してもいい。( Editorial 参照 )

http://www.codechef.com/viewsolution/1364926

PTOSS
かなり難しい。
Editorial とそのコメントと komiya さんの記事を参考にして解いた。

E[i] := ( lucky sequence の i 文字目までマッチしているときの、これからコインを投げる回数の期待値 )
として DP したくなる。
漸化式を立てると、
E[i] = (1/2)・E[i+1] + (1/2)・E[rematch[i]] + 1
となる。rematch[i] は lucky sequence の i 文字目でマッチに失敗したときに戻る位置。

rematch 配列の計算は、KMP の failure link を利用して文字列長の線形でできる。

あとはこの漸化式を解けばいいけど、E[0] がわからないので DP できない。( 連立方程式と思えば計算できるけど TLE する。)
そこで、
E[i] = P[i] + Q[i]・E[0]
と分解する。E の漸化式を使うと、P と Q についての漸化式ができる。
初期条件は P[0] = 0, Q[0] = 1 で、P と Q は i = 0 から順に計算していくことができる。
結局 E[0] がわかり、答えが求められる。

Editorial のコメント欄に書いてあるように、Q についての漸化式の形をみると、すべての i で Q[i]=1 であることに気付く。なので、実際は P だけを計算すればよい。

また、これとは別に E[0] を直接求める方法もコメント欄に書いてある。これはよくわかっていない。

http://www.codechef.com/viewsolution/1470154
( 日本語コメントが文字化けしてるけど、plaintext を押せば見えるようになる。 )

RRECIPE
文字列の左半分が決まれば右半分も決まるのでいい感じに数えられる。簡単。

http://www.codechef.com/viewsolution/1363183
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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