スポンサーサイト

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

Facebook Hacker Cup 2011 Qualification Round

01/08 09:00 ~ 01/11 09:00 に行われた Facebook Hacker Cup 2011 Qualification Round の参加記録

開始日時のアナウンスが間違っていたり途中でルール変更があったりと、何かとトラブルが多かった。

Tag : プログラミング FBHC

問題は 3 問。
コーディングに制限時間はないけど、入力データを一旦ダウンロードしたら 6 分以内に答えを提出しないといけないというルール。
理由は知らないけど、結局、この 6 分ルールはなかったことになった。


結果
3 問とも正解だった。
ルールを読んでいなくて時間切れになったりしたので、6 分ルールがなくならなければ 2. しか通ってなかったはず。


問題
1. Double Squares
与えられた X を 2 つの平方数の和で表す方法は何通りあるか?

2. Peg Game
複数の釘が打たれているパチンコのような台の上から球を落とす。
球は釘に当たると等確率で左右どちらかに転がる。
狙った場所に球が落ちる確率を最大にするとき、その確率と球を落とす位置を求めよ。

3. Studious Student
10 文字以下からなる文字列が M (≦9) コ与えられる。
すべての文字列を適当に連結して、辞書式で最小な文字列を作れ。

ちなみに、問題の原文はここから参照できる。


解法
1. Double Squares
X = A2 + B2 とおく。
平方数のリストを予め作っておくと、
A が決まれば、B は配列を参照するなり二分探索するなりして短時間で求められる。

2. Peg Game
台と同じ大きさの配列を、上から順に DP で埋めていく。

3. Studious Student
全探索 + 枝刈り
枝刈りは、今までに見つけた最適解より大きくなったかどうかを調べただけ。
枝刈りせずに next_permutation で全部回すと遅すぎた。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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