動的計画法を用いる機会が無くてナップザック問題すら解いたことが無いのでナップザック問題を解きました。入力 n w w1 v1 ... wn vnn 種類の荷物から自由に選択し、重さ w 以下で価値が最大となる組み合わせを選択する。 i 番目の荷物の重さは wi で価値は …

動的計画法を学習してから数年、全然使っていないと思って DNA 配列の LCS を求めるプログラムを書きました。 長さ n の文字列 s と長さ m の文字列 t が与えられたとして、部分文字列がより長く一致する空白（ギャップ）の与え方を求めます。 s の i 番目ま…

Python3 で Wikipedia のデータを解析するために、 class Entry: def __init__(self, title, redirect_from=[], document=None, link_from=[], link_to=None): self.title = title self.redirect_from = redirect_from self.document = document self.link_f…

enchant.js を使ったゲームのソースコードを GitHub のリポジトリに追加する際、間違って enchant.js までアップしてしまったので、 git rm --cached js/enchant.jsで削除しました。これで、手元にファイルを残したままリポジトリから削除出来ました。

.gitignore に .DS_Store などを登録しておいたが、 git add . とコマンドを入力するとなぜか .DS_Store まで含まれてしまいました。 とりあえず git config --global core.excludesfile ~/.gitignoreを実行したんですが、 .gitconfig にただ内容を追加して…

今まで SSH はパスワードを使ってログインしていたのですが、先日、初めてさくら VPS に鍵認証の設定をしたので、それをメモしておきます。(OS:Ubuntu)なぜ鍵認証をしたかというと、ポート番号の変更がなぜか出来なかったからです。（他の PC では普通に出来…

ARC018 の C 問題「席替え」を（解説を見ながら）解きました。 i 行 j 列 (i,j) の人の成績 G(i, j) とするとき、 (a,b) まず、 x_i = (x_(i-1) + a) % p で、 a%p!=0, m*n 成績がすべて異なる値をとるとき、行は floor(G[i][j]/m) で確定し、列は交差しない…

N 個の数値のうち、好きなだけ選んで合計を X にできるパターンの個数を求めるという問題で、 N が小さい値ならばそのまま全探索(O(2^N))すれば良いんですが、 N が 32 だと時間切れになります。解説を読むと、N 個の数値を半分に分割し、片方の合計を p, も…

bit DP どころか DP すら碌に書いたことが無いレベルだが、 ARC016 の C 問題で bit DP を使うことになるようなので練習しました。学んだことを記しておきます。 bit DP とは 例えば TSP （巡回セールスマン問題）で、拠点 ABCD を回ることを考える場合、既…