JOI春合宿や各種コンテスト, JJMOでたまに出題されるファレイ数列についていろいろ書きます. 面白い性質がたくさんあります.・ファレイ数列とは？ 約分された分数を昇順に並べた一群の数列であり、正の整数 n に対して、n に対応する (または、属する、深さn…

問題文 : Milking Time解法 : dp[N] : 時間Nまでに得られるミルクの最大量, とすると,dp[N] = max(i = 1 ... M, e[i] ≦ N | dp[s[i]] + v[i] where s[i] = i番目の仕事が始まる時間, e[i] = i番目の仕事が終わる時間)となる. ここで, 区間の端以外の時間はい…

問題文 : Crazy Thairs解法 : dp[i][j] = j番目を終点とする長さi + 1のLISの総数, とするとすべてのjについてdp[0][j] = 1,dp[i + 1][j] = Σ[k = 1...j - 1 | a[k] となります. Σの部分の計算をBITを使うと, O(nlogn)時間でこの問題を解くことができます.あ…

問題文 : 台風(pdf注意, 2ページ目~3ページ目)解法 : 昔解いた気もするのですが, そのときはセグメント木を使っていました.基本的には昔と方針はいっしょなのですが, 今回はReactive型の問題として出題されたときに対応できるよう, オンライン風に書いてみま…