mayoko’s diary

プロコンとかいろいろ。

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

SRM 486 div1 med: QuickSort

問題 TopCoder Statistics - Problem Statement 解法 配列の最小値と最大値を決めると, 配列内の数字の並びは一定になります。 よって, dp[mini][maxi] = (配列内の最小値が mini で, 最大値が maxi であるような配列で, swap する回数の期待値) とすれば, …

SRM 486 div2 hard: CrazyLine

ぶっちゃけ Crazy ではない。 問題 TopCoder Statistics - Problem Statement 解法 明らかにデコボコに人を並べるのが良いです。 大まかな方針としては, 背の高さを低い方から半分, もう半分に分けて, 奇数番目に背の低い人, 偶数番目に背の高い人を並べるよ…

SRM 486 div1 easy: OneRegister

問題 TopCoder Statistics - Problem Statement 解法 s から t を考えるといろいろ可能性があって面倒ですが, t から s を考えれば, ・t が平方数 -> s は t の平方根 ・t が偶数 -> s は t の半分 とほとんど場合分けがなくなり, また, t の遷移回数は 2^30…

SRM 487 div1 hard: BunnySequence

問題 TopCoder Statistics - Problem Statement 解法 この問題は typical DP contest の準急に非常に似ています(というかこれが元ネタかな?)。ある数 x について, g(x) がどうなるか, と考えるのではなく, 逆に考えます。1 から逆順に作れる数を辿って行っ…

SRM 487 div1 med: BunnyExam

問題 TopCoder Statistics - Problem Statement 解法 答えが -1 でないとすると, 答えは m/k となります。答えが -1 でない時, RandomAnser は 1 〜 k の答えを等確率で出力します(x 番目の答えとして選ばれる数字は 1 〜 k すべて等確率であり得る。対称性…