Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-01-10SRM483(DIV1)

SRM483 第一問(250pt) BestApproximationDiv1

|  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11023

1000(a) * 1000(b) で全探索余裕でした

何か引っ掛けがあるかと思いきや、特になし。

続きを読む

SRM483 第二問(500pt) Bribes

|  SRM483 第二問(500pt) Bribes - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM483 第二問(500pt) Bribes - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11037

ポイントは賄賂の影響が前後8人までしか伝わらないこと。

そこで、ある人を堕とすことができる、17人(前8人、後8人、本人で17名)の賄賂パターンを17bitで表してやるといいようです。

「0」を賄賂しない、「1」を賄賂するに対応させると、例えば本人と前後1人ずつに対して賄賂する場合は

← 並び順
00000001 1 10000000(2)

と表せます。

そして、ある人に対して上記パターンで賄賂に成功した場合は、

次の人に対する賄賂は1bitずつ右にずらして、次のように表せます。

← 並び順
?0000000 1 11000000(2)

? の部分には「0」と「1」を入れ、次の人に対する賄賂の探索候補とします。

続きを読む