Hackerrank HourRank 12

1. Repeated String

やるだけ

2. Fair Cut

問題

n個の数値からなる集合Aを要素数kの集合Iと要素数n - kの集合Jに分割したい
集合Iと集合Jのunfairnessを以下のように定義する

{
\begin{equation}
F(I) = \sum_{i \in I} \sum_{j \in J} |a_i - a_j|
\end{equation}
}

unfairnessが最小になるように分割したときのunfairnessを求めよ

解法

 dp[\alpha][\beta][\theta] = \sum_{i \in I} \sum_{j \in J} |a_i - a_j| - \theta \cdot (\sum_{i \in I} a_i) とする.

よって,求めたいの答えはdp[n][k][0]となる

a[\alpha]を追加して, dp[\alpha][\beta][\theta]へ遷移するときするとき,以下のように計算できる

  1. 集合Jに追加
    {
\begin{equation}
dp[\alpha][\beta][\theta] = dp[\alpha - 1][\beta][\theta - 1] + \beta \cdot a[\alpha]
\end{equation}
}

  2. 集合Iに追加
    {
\begin{equation}
dp[\alpha][\beta][\theta] = dp[\alpha - 1][\beta - 1][\theta + 1] + (\alpha - \beta) \cdot x - \sum_{i \leq I} a[i] + \theta \cdot a[\alpha]
\end{equation}
}

計算が必要な\theta \alpha\betaを指定すれば一意に決まるので,\thetaのループはいらずo(n2)で求めることができる.

3. Jumping Rooks

code

オンライン広告関連の資料

オンライン広告関連の論文・資料まとめ

続きを読む

TopCoderのプラグインのGreedを使う

Greedを入れたときのメモ

続きを読む

2016年に読んだラノベまとめ

2016年に読んだラノベまとめ

続きを読む

PC-OP-RS1をpythonで操作する

BuffaloのPC-OP-RS1をpythonから操作する

続きを読む

pythonでランレングス圧縮

pythonだとランレングス圧縮が1行くらいでかける

続きを読む