Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1839-11fd6007
この記事にトラックバックする(FC2ブログユーザー)

Facebook Hacker Cup 2011 Round 2 (参加記録) (この記事を編集する[管理者用])

2011年02月06日06時から3時間,3問.
2回戦は上位25人が通過,オンサイト決勝に進出.上位300人にTシャツ.
[Problems] [Score board]

1問目 - Scott's New Trick

要素数N (10^7以下) の数列aと要素数M (10^7以下) の数列bが与えられる.
a[i] * b[i] mod P が K 以下となるよう(i,j)の組が何通りあるかを求める問題.
Pは250000以下,KはP未満.
(数列は実際には乱数生成のパラメータが与えられる)

それぞれの数列の要素がそれぞれmod Pで何個あるか覚えてやるだけ.
と思ったけど普通にやったらO(N+M+P^2)でP^2がでかくて駄目だ….
えーっと,どうするんだろう….
3問目やって,2問目にはまってたので,何もできず.

2問目 - Studious Student II

60文字以下のa,bのみからなる文字列が与えられる.
以下の操作を何回でも繰り返して良い.
 ある部分文字列を,その部分文字列に含まれている1文字で置き換える
操作の適用方法は何通りあるか,mod 1000000007で求める問題.

うーん,どうやるんだろう.
あんまり生成される文字列の種類って無いんじゃないのかな?
単純に現在の文字列をメモしてDPしてみる.
….
長さ20ぐらいですでに全然終わらない.
良く考えてみると,作れる文字列の種類数めちゃくちゃ多いなぁ….
うーんうーん.
DPだとは思うんだけど….
カッコをつけて,それを中にある1文字で置き換える.
実際には内側から処理していくけど,外側からやっていけばいいのでは!
でも,内側の適用結果によっては置き換えられる文字が変わってしまう….
内側に含まれる文字の種類も全部状態に含めればいいのでは!
状態数は…,左端,右端,内側に含まれる文字の種類で,60*60*4ぐらい.
いけそう.
違う!
えっと,カッコは内側から適用しないといけないけど,それ以外は順番が任意だからそれの分をかけないといけない….
でも,それって求まるか…?
….
ツリーつくって,
 ノード数!/Πそれぞれのノードを根とするサブツリーのノード数
あたりをかけたい….
使うカッコの個数も状態に含めればいけるか.
とりあえず,遅いかもしれないけど書いてみよう.
書いた.
状態数は左端,右端,括弧の数,全体をくくるカッコを許すかどうか,内側に含まれる文字の種類,で60*60*60*2*4.
で,更新するのは,次のカッコの左端と右端,括弧の数をどのように配分するかで60*60*60.
合計O(60^6*たくさん).
当然のごとく終わらない….
次のカッコの左端とか考えなくていいじゃん!左端を1つシフトするだけでいいじゃん!
合計O(60^5*たくさん).
….
まだ厳しい.
60文字1ケースに1分以上かかる.
しかし,残り時間わずか.
インプット落としてきて,4つに分割して,4つプログラム動かして手動並列!
落とした.長さ60のケースが17個もある…無理だ….
結局6分以内に実行終わらず12分ぐらいかかった….
O(60^5)で通している人もいるし,ボロいPCだった人は通せなかったりしたらしい.
しかし,自分のPCはそんなにボロくないので,プログラムがかなり定数倍遅かったと思う.

3問目 - Bonus Assignments

N個 (1000000以下) の自然数a1, a2, ..., aNのうち以下の条件をみたすものはいくつあるかをmod 1000000007で求める問題.
 a1~aNはすべてがKの倍数になっている,というような2以上のKが存在してはいけない
 a1~aNの最小値はA以上B以下
 a1~aNの最大値はC以上D以下
A,B,C,Dは1000000以下.

最初問題を読み間違えて意味がわからなかった.
ふむふむ.意味がわかった.
どうするんだろう….
包除原理で行けるんじゃない?
 すべて - 2の倍数 - 3の倍数 - 5の倍数 + 6の倍数 - …
いけそう.
そして,最小値がA以上B以下とかそれも包除原理で行ける.
書こう.
サンプル通った.
サブミット.

結果

難しかった.結局3問目しか解けず敗退.
そもそも1問以上解いた人が150人しかいなかったためTシャツはゲット.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1839-11fd6007
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。