mayoko’s diary

プロコンとかいろいろ。

2016-01-29から1日間の記事一覧

SRM 483 div1 hard: Sheep

問題 TopCoder Statistics - Problem Statement 解法 「こんなの二分探索するだけでしょwwww」って感じですが, それだけだと落ちます。単調性を持たないからです。ただ, ある数 C が最小の答えであるとすると, C+maxw でも羊を運ぶことが出来ます(maxw …

SRM 483 div1 med: Bribes

問題 TopCoder Statistics - Problem Statement 解法 influence の値はたかだか 500 なので, now 番目の人は, now+8 番目までの人にしか影響は及ぼしません。そこで, dp[now][state] = (now 番目の人で, now-8 番目から now+7 番目の人への賄賂を送ったか送…

SRM 483 div2 hard: BestApproximationDiv2

問題 TopCoder Statistics - Problem Statement 解法 mayokoex.hatenablog.comさっきとほとんど同じです。今度は maxDen の値が大きいので, B を決めた後の A の範囲をある程度絞り込みます。 A の値はだいたい B*number となっているのが良いので, B*number…

SRM 483 div1 easy: BestApproximationDiv1

問題 TopCoder Statistics - Problem Statement 解法 maxDen の値が小さいので, A, B のすべての候補を総当りします。B/A の小数点以下の数は, B/A をそのまま見ると整数部分, 10*B/A を見ると小数点第一位以上, 100*B/A を見ると小数点第二位以上が見れる, …

SRM 680 div1 med: BearSpans

問題 TopCoder Statistics - Problem Statement 解法 1 回の操作で必ず component の数が半分以下になります。 また, sample 1 のように, 「あと 1 回で操作をやめたい」と思ったら, component のひとつ目の要素と, 他の component を小さい辺で結べば終わり…

SRM 680 div1 easy: BearFair

問題 TopCoder Statistics - Problem Statement 解法 dp[b][even][odd] = (b 以下の数の set で, 偶数の数が even で奇数の数が odd であるようなものは存在するか) とします。普通に dp して dp[b][n/2][n/2] が true かどうか見るだけですね。 int dp[1010…

SRM 486 div1 hard: BatmanAndRobin

問題 TopCoder Statistics - Problem Statement 解法 2 つの交わらない凸多角形が存在するときは, それらの凸多角形の間にそれら2つを分断する直線が存在します。よって, あり得る直線の候補を列挙して, 分断された直線による凸多角形を求めて, 最小面積を…