C♯の勉強

C♯4.0 で TopCoder の過去問を解きます。

2013-09-28から1日間の記事一覧

TopCoder SRM592: LittleElephantAndArray

dp[i][j] = 「(A+i) の部分シーケンスで j 番目に小さい数(以下 A[i][j]) 」に到達するパターン数 とすると dp[0][*] = 1; dp[i+1][j] = sum dp[i][k] where A[i][k] で動的計画法を適用できる。ただし、毎回合計を取っていくと TLE になるので、工夫して合…

TopCoder SRM592: LittleElephantAndPermutationDiv2

N! のペアを全部試す必要はない。片方の並び順だけを固定したうえでもう片方の順列を全て試して、最後に N! を掛ければ良い。LINQ の Sum を使ったら TLE だった。こういう next_permutation するだけの問題は大抵 8! の上限だったのだけど、今回は何故か制…

TopCoder SRM592: LittleElephantAndBooks

pages をソートした配列を A とすると、 A[0],...,A[number-2],A[number] が2番目に最小な本の選び方になる。 public class LittleElephantAndBooks { public int getNumber(int[] pages, int number) { return pages .OrderBy(p => p) .Where((p, index) =…