読者です 読者をやめる 読者になる 読者になる

2017年に解いた問題まとめ

まとめ

続きを読む

食のルーチン化

1日に3回も何食べるか考えないといけないのは大変なのでルーチン化するようにした
減量中なのでカロリーは低め


続きを読む

VagrantのBoxを作成する

実践Vagrantを読んだので,実際にLinux Mint18.1(MATE)のvagrant boxを作ってみる

続きを読む

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

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

続きを読む

AtCoder Beginner Contest埋め

ABC埋めてく

続きを読む

競技プログラミング用IntelliJ IDEAのプラグイン作った

とりあえず,AOJ, AtCoder, POJに投稿できます.
ちゃんと確認してませんが,IntelliJ IDEAやPyCharmなどJetBrainsのIDEでなら動くはず

github.com

続きを読む

巡回セールスマン問題

巡回セールスマン問題を,動的計画法,山登り法,焼きなまし法で解く

続きを読む

KinesisのWindows7相性問題

KinesisキーボードはUSB3.0のportがついているWindows7機だと相性問題がでるらしく,案の定ハマってしまったのでメモ.
公式によると以下のいずれか対処方法で動くかもしれないとのこと

  1. BIOSでEnable USB 3.0 Controllerのチェックを外す
  2. BIOSでenable USB Debugにチェックを入れる
  3. BIOSIntel xHCI Modeを無効にする

自分の場合はUSB debugを有効にしたら認識してくれるようになった もしダメな場合はKinesisからでるケーブルをPS/2に交換するように依頼することができるが5000円くらいかかるっぽい(保証期間内なら無償?)
ちなみにUSBとPS/2の変換器(こういうやつ )をつけてみたけどダメだった

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