Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2011年01月22日03時から3時間,3問.
1回戦は3ラウンドのうち,それぞれ上位1000人が通過.
[Problems] [Score board]

1問目 - Wine Tasting

G次 (100以下) 対称群の元のうち,s(i) = iを満たさない個数がC個以下のものの数をmod 1051962371で求める問題.

うーん,なんか見覚えがある.
なんかいい方法なかったっけなぁ….なんか規則性とかあった気がする.
小さいケースで全探索してみる.
規則性わからない.
もういいやDP書こう….
dp[使った数][相方がいなくなった数字の数][まだ間違えて良い個数]とかでメモ化すればOK.
書き書き.
微妙に合わない….
あれぇ….
微修正であった.サブミット.

2問目 - Diversity Number

ある数列t[k]のdiversity numberとは,
 0 <= b[k] < t[k],かつ,b[k]は全て異なる
を満たす数列b[k]の個数.
長さ100以下,各要素100以下の数列a[k]が与えられるので,その部分列で,
最初は単調非減少,残りは単調非増加となるような数列のdiversity numberの和をmod 1000000007で求める問題.
部分列は,長さが違うか,同じ場所なのに違う値になるものが存在したら違うものとみなす.

どう見てもDPなんだが….
どうやれば良いのだろうか….
まず,diversity numberを計算するのは,どうするの?
a[k]をソートしてa[k]-kをかけていくだけか….
てか,それはTopCoderで見た気がするなぁ.
じゃあ,どうするの?
小さい方から処理していきたいから,両端から処理して行こう.
同じ値の処理が面倒….
しかも,重複して数えたらいけないのか!
えーっと,結構難しくないか….
とりあえず,書いた.
答え合わない.
うーむ.デバッグ.デバッグ.時間切れ.

3問目 - Turn on the Lights

R*C (18*18以下) のグリッドが与えられる.
各セルは.かXの文字が書かれている.
毎ターン1セル選んで,そのセルと,その上下左右のセル (あれば) の状態を反転させる.
すべてのセルをXにするのに必要な最小ターン数を求める問題.
不可能ならばそれを指摘する.

自分,これのライブラリ昔作ったぞ….
貼りつけ,サンプル通る.提出.
思いの外,実行に時間かかったけど問題ない.
ビット演算を駆使すれば早くなるが….
サイズが大きくなると,連立方程式に落として解くべきなのか….

結果

1問目と3問目は問題なく通った.
1問以上解けた人数が1000人もいなかったため問題なく通過.
無効試合になったRound 1Aと比べるととても難しくなった.
後,3問目のジャッジの答えが間違えてたのか,一部正しく判定されなくて,その後修正された.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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