Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Facebook Hacker Cup 2011 Round 1A [無効試合] (参加記録) (この記事を編集する[管理者用])

2011年01月16日00時から3時間(の予定だった),3問.
1回戦は3ラウンドのうち,それぞれ上位1000人が通過.
[Problems] [Score board]

はじめに・・・

サブミットしようとしてもサーバーが応答せずサブミットできない現象が起きたのと,
2問目のサンプルが間違えている,3問目のサンプルが入力の制約を満たしていない,などという問題があり,何故か早めに終了.
現在結果も明らかにならず,2問目は削除されている様子.
Round 1は1週間以上は延期するとのこと.

1問目 - After the Dance Battle

100*100以下のグリッドが与えられる.
スタート地点,ゴール地点が1箇所ずつ与えられるので,スタートからゴールまでのステップ数の最小値を求める問題.
グリッドは壁(入れない)か空白(0)か色がぬられている(1--9).
1ステップでできる行動は上下左右に移動するか,同じ色の他のセルにワープすることができる.

問題文が読みにくい.
入力から読む.入力と出力だけ読めば意味がわかるじゃん….
単にBFSするだけだ.
最悪ケースは,全部のマスが同じ色の場合だけど,10000^2程度なのでなんとかなるだろう.
書く.
書いた.サンプル通ったのでサブミット.

2問目 - Power Overwhelming

整数A, B (1以上100以下) とC (A+B以上10^12以下) が与えられる.
正整数x, yをxA + yBがC以下という制約のもとでxyを最大化するものとする.
ただし,答えが複数あるならxを最大化する.
xを求める問題.

三分探索やるだけでいいよね.
…違う!
x,yは整数なんだから,関数はギザギザしてるはず….
まぁ,適当にやればよさそうだが….
てか,待てよ!
Cが10^12ってことは…,xyの最大値が64bitで収まらないんだけど….
…,先に3問目に行こう.
3問目提出して戻ってきた.
twitterなどでは提出できないという噂がチラホラ見える.普通にできたけどなぁ.
多倍長+三分探索して,後はその周辺を調べたらいいんじゃないの?
ってことで書く.
合わない.
問題文ではyの最大値なんだけど,xの最大値を出力してみたらサンプルっぽいのがでてきた.
でも,結構違う….
てか,このサンプル間違ってないか?
なんか,自分の答えのほうがxyでかいんだが….
もういいや,サンプル無視してサブミットしてみよう.
インプットダウンロードして実行.
サブミット…できない.サブミットボタン押しても反応なし.
chrome, firefox, IEで試したけど駄目だった.
そうこうしてる間に6分間過ぎた.
しばらくしたら,6分過ぎてもサブミットしたら受け付けてあげるよ,とのアナウンスが.
ってことで,サブミット…,してもしてもできない.
10分ぐらい粘ったらサブミットできた.
残り1時間残して全部提出したので寝る.

3問目 - First or Last

R人でレースを行う.最初自分は最下位.
T箇所だけ,コーナーがあって,各場所について
 今の順位を維持するなら 1/p[k] の確率でクラッシュする
 1人だけ抜くなら 1/q[k] の確率でクラッシュする
という確率が与えられる.
クラッシュせずにR-1人抜く確率の最大値を有理数で厳密に求める問題.
Tは50以下,p[k],q[k]は500以下.

…多倍長から逃げてきたら,多倍長有理数ときたよ….
問題自体はDPするだけ.(実はgreedyで良いのに気づかない)
多倍長有理数のライブラリを貼りつけて書くか.
書いた.
インプットダウンロードして実行.
….時間かかるなぁ.
1分ぐらいかかった.怖い.
サブミット.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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