スポンサーサイト

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

Facebook Hacker Cup 2011 Round 1A & reprise

1/16 0:00 ~ 3:00 に行われたが無効試合になった Facebook Hacker Cup Round 1A と、
1/23 3:00 ~ 6:00 に行われたその再試合 Facebook Hacker Cup Round 1A (reprise) の記録。

Tag : プログラミング FBHC

Round 1A

問題は最初 3 問だったけど、うち 1 問に不備があって途中で 2 問になった。
問題はここから参照できる。今はまた 3 問とも公開されている。

問題
1. After the Dance Battle
R×C のグリッド上で、S と描かれたマスから E と描かれたマスまで移動するための最小移動回数を求めよ。
○ 移動のルール
・ 1 回の移動では、隣接する 4 方向のマスのいずれかに移動できる。
・ ただし、1 以上の数字が描かれたマスにいる場合は、(離れたところにある)同じ数字が描かれたマスにも移動できる。
・ W と描かれたマスには移動できない。

2. Power Overwhelming
与えられた G, W, M に対して、
G×NG + W×NW ≦ M のもと NG×NM を最大化せよ。
ただし、G, W, M, NG, NW はすべて自然数。M ≦ 1012.

3. First or Last
T 個の確率の組 (pi, qi) (0<pi<1, 0<qi<1, i=1,2,...,T) が与えられる。
T 個のうち R 個の pi と T-R 個の qi を選ぶとき、
Π[i=1→T] (pi と qi のどちらか(選んだほう))
を最大化せよ。
結果は既約分数で答えること。


解法
  1. 典型的な BFS。解いた。

  2. C++ でやるなら多倍長演算のライブラリを用意しないといけない。
    二分探索で解ける気がするけど、解いてない。

  3. R 個の pi は、選ぶと値が大きくなるものから、すなわち pi/qi が大きい順に Greedy に選べばいい。
    long long で書いてみたもののオーバーフローしたので提出できなかった。これも多倍長ライブラリがいる。


Round 1A (reprise)

TopCoder SRM 494 と若干かぶったので、開始 30 分後くらいから参加。
3 問目だけ解いて、朝になったので打ち切った。
正解していれば 500 位くらいなので Round 2 には進めるはず。
問題はここから。

問題
1. Wine Tasting
問題文の意味がわからない。
なにかの場合の数を数える問題のよう。

2. Diversity Number
N 個の整数からなる数列 {an} で、
ある K があって
a1≦a2≦...≦aK
aK+1≧aK+2≧...≧aN
となっているものを ほぼ単調な数列と定義する。

また、
N 個の整数からなる数列 {an} に対して、
0≦bi<ai (i=1,2,...,N) かつ bi≠bj (i≠j)
となる、N 個の整数からなる数列 {bn} の個数を {an} の Diversity Number と定義する。
ただし、空な数列の Diversity Number は 1 とする。

与えられた {an} に対して、
{an} の部分列のうち、ほぼ単調であるものの Diversity Number の総和を mod 1000000007 で求めよ。

3. Turn on the Lights
R×C のグリッド上に電球が配置されている。各電球は点いているか消えているかのいずれか。
ある電球の状態を反転させようとすれば、その 4 近傍にある電球の状態も同時に反転してしまう。
すべての電球を点灯させるためには、最小で何回反転させればよいか?
R≦18, C≦18


解法
  1. 問題文がわからないのでわからない。解いてる人は 3 問中で一番多いので、多分簡単。

  2. よく考えてないけど、多分難しい。

  3. bitDP。以前に AOJ で類題を解いた気がする。
    一番上の行を反転させるパターン(≦218通り)を決めれば、2 行目以降のパターンは 1 通りに決まるので、順次反転させていって、最後の行がすべて点灯していれば成功。
    成功したものの中で反転させた数が最小のものが答え。
    bit列の反転は XOR を使えばきれいに実装できる。

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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