[PHP][アルゴリズム] N人の人気投票順位予想でM人を的中させるパターン数

職場の人に考えてみてと言われたので解いてみました。

解法

動的計画法で出しました。
N人からM人一致させるパターンをdp[n][m]として考える。
1. n=mの時は全的中なので1パターン
2. m=0の時は全パターンからm>=1のパターンを引く
3. それ以外の時は(nからm人決める組み合わせ数) × (残りのn-m人から一人も選ばない組み合わせ数( = dp[n-m][0]))

計算量

O(N^2)。

コード

<?php
$combi = [];
$perm = [];
$dp = [];

solve(9);

/**
 * N人で人気投票順位を0~N人一致させるパターン数を計算して表示
*/
function solve(int $size) {
  makeCombination($size);
  makePermutation($size);

  for ($i=1; $i <= $size; $i++) {
    for ($j=0; $j <= $i; $j++) {
      printf("%d人から%d人一致するパターン数: %d\n", $i, $j, rec($i, $j));
    }
  }
}

/**
 * 動的計画法でN人で人気投票順位をM人一致させるパターン数を求める
*/
function rec(int $n, int $m): int {
  global $dp, $perm, $combi;
  assert($n >= $m);

  if (!isset($dp[$n][$m])) {
    if ($n == $m) {
      $dp[$n][$m] = 1;
    }
    else if ($m == 0) {
      // 直接求めるのは大変なので全パターンからm>=1のパターンを引く
      $result = $perm[$n];
      for ($i=1; $i <= $n; $i++) {
        $result -= rec($n, $i);
      }

      $dp[$n][$m] = $result;
    }
    else {
      // 当たっているm個を決める
      $result = $combi[$n][$m];
      // 残りはn-m個から0人一致
      $result *= rec($n - $m, 0);
      $dp[$n][$m] = $result;
    }
  }

  return $dp[$n][$m];
}

/**
 * 組み合わせを計算
 */
function makeCombination(int $size) {
  global $combi;

  for ($i = 0; $i <= $size; $i++) {
    $combi[$i][0] = 1;
  }

  for ($i = 1; $i <= $size; $i++) {
    $combi[0][$i] = 0;
  }

  for ($i = 1; $i <= $size; $i++) {
    for ($j = 1; $j <= $size; $j++) {
      $combi[$i][$j] = $combi[$i-1][$j-1] + $combi[$i-1][$j];
    }
  }

}

/**
 * 順列を計算
 */
function makePermutation(int $size) {
  global $perm;

  $perm[1] = 1;
  for ($i=2; $i <= $size; $i++) {
    $perm[$i] = $perm[$i-1] * $i;
  }
}

パッと浮かんだのがこれだったから書いたけど、もっとスマートな方法がある気もする...
(あとPHPグローバル変数初めて使ったので、globalっていうキーワードが必要なのを初めて知った)

[Contest][AOJ][C++] 高速ゼータ変換 / 高速メビウス変換

The Enemy of My Enemy is My Friend | Aizu Online Judgeを高速メビウス変換を使って解きました。その際に学んだことの備忘録としてこの記事を残します。

問題概要

N(N <= 40)個の国がある。国はそれぞれ軍事力B(B <= 1000)を持っている。
以下の条件を満たすように同盟を組むとき、1つめの国を含む同盟の軍事力の和の最大値を求めよ。

  • 自国の隣国とは同盟を結ぶことは出来ない。
  • 同盟をした国の隣国とは同盟を結ぶことは出来ない。

解法

半分全列挙 + 高速メビウス変換(厳密には違う?)

1. 国を20個ずつの2つの集合に分け、それぞれビットマスクmaskで表現する
(maskはnビット目が1→n番目の国を含む、0→n番目の国を含まないに対応)

2. 前半の集合(1つ目の国を含む集合)、後半の集合(1つ目の国を含まない集合)それぞれについて
dp[mask] = (maskに含まれる国で同盟を結ぶことができる→軍事力の和、できない→0)
を計算する

3. 高速メビウス変換で後半の集合について、
dp2[mask] = max_{(s \subset mask)}dp[s]
を計算する

4. 前半の集合の一つ一つにおいて、
dp[mask] + dp2[(maskに含まれる国に隣合わない後半の国の集合のビットマスク)]を計算する

4の最大値が答えになる。
(ただしこれは想定解ではなく、本来は単純に枝刈りで解けるらしい。。)

高速メビウス変換を使っているところ

全ての部分集合sに対して
dp[s] = max_{s \subset u} dp[u]
を高速に求めている(O(N/2 × 2^(N/2)))。

  // 高速メビウス変換でビットマスクsの部分集合から最大値を出す
  for(int i=0; i<size; i++) {
    for(int s=0; s<(1<<size); s++) {
      if ((s>>i&1)==1) {
        dp[dp_index][s]= max(dp[dp_index][s^(1<<i)], dp[dp_index][s]);
      }
    }
  }

計算量

O(N/2 × 2^(N/2))

ソースコード

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> ipair;
typedef tuple<int, int, int> ituple;

#define PI acosl(-1)
#define MAX_N (40 + 2)
#define SIZE_PER_ONCE 20

const ull ONE = 1;

// 国の集合の中の総和の最大
ull dp[2][1 << SIZE_PER_ONCE];

map<string, int> name2index;
vector<string> tmp_neighbor[MAX_N];
int power[MAX_N];
ull neighbor[MAX_N];

void set_dp(int dp_index, int start_index, int size) {
  // ビットマスクiに含まれる国の軍事力の和を求める
  for (int i = 1; i < (1 << size); i++){
    ull b = 0;
    ull score = 0;
    for (int j = 0; j < size; j++){
      if ((i & (1 << j)) == 0) {
        continue;
      }
      if ((b & neighbor[start_index + j]) != 0) {
        score = 0;
        break;
      }
      score += power[start_index + j];
      b |= ONE << (start_index + j);
    }
    dp[dp_index][i] = score;
  }

  if (start_index == 0) {
    return;
  }

  // 高速メビウス変換でビットマスクsの部分集合から最大値を出す
  for(int i=0; i<size; i++) {
    for(int s=0; s<(1<<size); s++) {
      if ((s>>i&1)==1) {
        dp[dp_index][s]= max(dp[dp_index][s^(1<<i)], dp[dp_index][s]);
      }
    }
  }

}

void init() {
  for (int i = 0; i < MAX_N; i++){
      tmp_neighbor[i].clear();
  }

  name2index.clear();
}

void exec(int n){
  string a;
  int b, c;
  string s;

  init();

  for (int i = 0; i < n; i++){
    cin >> a;
    scanf("%d%d", &b, &c);
    name2index[a] = i;
    power[i] = b;

    for (int j = 0; j < c; j++){
      cin >> s;
      tmp_neighbor[i].push_back(s);
    }
  }

  // 隣接する国のビット表現を作る
  for (int i = 0; i < n; i++){
    ull tmp = 0;
    tmp |= ONE << i;

    for (int j = 0; j < tmp_neighbor[i].size(); j++){
      tmp |= ONE << name2index[tmp_neighbor[i][j]];
    }

    neighbor[i] = tmp;
  }

  ull ans = 0;
  if (n <= SIZE_PER_ONCE) {
    // nが小さい場合は分割しない
    set_dp(0, 0, n);

    for (int i = 0; i < (ONE << n); i++){
      if ((i & 1) == 1) {
        ans = max(ans, dp[0][i]);
      }
    }
  }
  else {
    // 前半分を計算
    set_dp(0, 0, SIZE_PER_ONCE);
    // 後ろ半分を計算
    set_dp(1, SIZE_PER_ONCE, n - SIZE_PER_ONCE);

    for (int i = 0; i < (ONE << SIZE_PER_ONCE); i++){
      if ((i & 1) == 1) {
        ull tmp = dp[0][i];

        // 前半分の集合から、同盟を組める後ろ半分の集合を求める
        ull tmp_mask = 0, mask = 0;
        for (int j = 0; j < SIZE_PER_ONCE; j++){
          if (((i >> j) & 1) == 1) {
            tmp_mask |= neighbor[j];
          }
        }
        tmp_mask >>= SIZE_PER_ONCE;

        for (int j = 0; j < n - SIZE_PER_ONCE; j++){
          if (((tmp_mask >> j) & 1) == 0) {
            mask |= ONE << j;
          }
        }

        // 後ろ半分の集合の軍事力の最大値を加算
        tmp += dp[1][mask];

        ans = max(tmp, ans);
      }
    }
  }

  cout << ans << endl;
}

void solve(){
  int t = 1;
  while (scanf("%d", &t) != EOF) {
    if (t == 0) {
      break;
    }
    exec(t);
  }
}

int main(){
  solve();
  return 0;
}

sedで「git blame」に色づけ

CUIで「git blame」を打っても全く色がつかずに見づらいと思っていたところで、会社の先輩がsedでログの標準出力に色を付けていたことを思い出し、やってみました。

colorize_git_blame.sed

#!/bin/sed -rf
s/\([a-z0-9]\+\)/\x1b[31m\1\x1b[0m/
s/\((\)\([a-z0-9]\+\)/\x1b[35m\1\x1b[0m\x1b[32m\2\x1b[0m/
s/\([0-9]\+\)\()\)/\x1b[33m\1\x1b[0m\x1b[35m\2\x1b[0m/
s/\([0-9]\{4\}-[0-9]\{2\}-[0-9]\{2\} [0-9]\{2\}:[0-9]\{2\}:[0-9]\{2\}\)/\x1b[34m\1\x1b[0m/

Macに始めから入っているsedでは何故か着色出来なかったので、homebrewでgnu-sedをインストール。

brew install gnu-sed

最後に下のようなエイリアスを作成。

function gbl(){
  git blame $@ | gsed -f "(sedファイルの場所)/colorize_git_blame.sed" | less
}

gbl FILE_NAME」でFILE_NAMEファイルの色付きblame が出来ます。


(上がデフォルトblame、下が色付きblame)

なお、git blameの出力を加工している場合はこれでは駄目かもしれないです。

pecoを使って動的にgrepする

動的にgrepを行って絞り込みが出来るpecoというツールを教わったので使ってみました。候補の文字列を動的に絞り込めるのでとても便利なツールです。pecoはなんとGo言語で動きます(pecoの元になったpercolpython製)。

インストールはMacならHomebrewで一発(環境はMac OS X 10.9.4)。

brew tap peco/peco
brew install peco


いくつかpecoを使ったコマンドを定義してみました。

pecoをコマンドラインのどの文脈でも使う

alias -g P='| peco'
alias -g Px='| peco | xargs '

PやPxとうつとコマンドラインの途中でも使えます。あるコマンドc1の結果をpecoで絞り込み、その結果をコマンドc2で使いたいときは「c1 Px c2」で出来ます。例えば、「ls Px file」でディレクトリ下のファイルを絞り込み、その選択結果の詳細を表示します。

pecoの結果をクリップボードにコピー

function p(){
  $@ | peco | pbcopy
}

コマンドの結果を絞り込んで選択するとその結果をクリップボードにコピーします。
例えば、「p ls」と打つと、現在のディレクトリのファイル一覧を表示し、選択した結果をクリップボードにコピーします。

ファイルを探す

alias pls='ls -a | peco'
alias pfind='find -L . -name "*" | peco'

plsは現在のディレクトリ、pfindは再帰的にディレクトリを検索し、ファイル一覧を作成して絞り込み検索します。

ファイルの内部を探す

function pcat(){
  cat -n $@ | peco
}

「pcat f1 f2 ..」でファイルf1, f2, ...の各行を絞り込み検索します。

コマンドライン履歴検索

function peco-select-history() {
    local cmd=`history | tail -r | peco | cut -d ' ' -f 1`
    if [ "${cmd}" != "" ]; then
      r ${cmd}
      return 0;
    fi
    return -1;
}

zle -N peco-select-history
alias phist='peco-select-history'

phistと打つとコマンドライン履歴の一覧が表示され、絞り込んで選択するとそのコマンドを実行します。

絞り込みcd

過去のディレクトリ移動履歴から候補を選択し、そのディレクトリに移動します。

typeset -U chpwd_functions
CD_HISTORY_FILE=${HOME}/.cd_history_file # cd 履歴の記録先ファイル
function chpwd_record_history() {
    echo $PWD >> ${CD_HISTORY_FILE}
}
chpwd_functions=($chpwd_functions chpwd_record_history)

function peco_get_destination_from_history() {
    sort ${CD_HISTORY_FILE} | uniq -c | sort -r | \
    sed -e 's/^[ ]*[0-9]*[ ]*//' | \
    sed -e s"/^${HOME//\//\\/}/~/" | \
    peco | xargs echo
}


function peco_cd_history() {
  local destination=$(peco_get_destination_from_history)
  if [ "${destination}" != "" ]; then
    echo "${destination}"
    cd ${destination/#\~/${HOME}}
    zle -N reset-prompt
    return 0;
fi
  return -1;
}
zle -N peco_cd_history
alias pcd='peco_cd_history'

function peco_insert_history() {
local destination=$(peco_get_destination_from_history)
if [ $? -eq 0 ]; then
  local new_left="${LBUFFER} ${destination} "
  BUFFER=${new_left}${RBUFFER}
  CURSOR=${#new_left}
fi
zle -N reset-prompt
}
zle -N peco_insert_history
alias pins='peco_insert_history'

参考:http://stillpedant.hatenablog.com/entry/percol-cd-history

pcdと打つと過去のcd履歴が出るので、絞り込んで選択するとそのディレクトリに移動します。

Gitのブランチを扱う

function br_fmt(){
  git branch -a | peco | xargs echo | sed -e 's/\*//' | sed -e 's/remotes\/origin\///'
}

ブランチをpecoで選択し、その結果を整形して返します(整形は余分な空白と*を取り除き、「remotes/origin/」を取り除きます)。

僕は下記のようにpushやpull, checkoutの時にブランチを絞り込んで使ってます。

alias pgco='br_fmt | xargs git checkout'
alias pgcob='br_fmt | xargs git checkout -b'
alias pgpl='br_fmt | xargs git pull origin'
alias pgps='br_fmt | xargs git push origin'
alias pgb='git branch -a | peco'


とても便利なツールですので、是非使ってみてください!

 Vimのテキストオブジェクトの使い方と関連プラグイン

今日チームのVimmerの人が小さい勉強会を開いてくれました。そこで学んだ内容をメモに残しておこうと思います。

テキストオブジェクト

Vimではある程度のテキストのまとまりをかたまりとして扱う機能が標準でついています。
これを「テキストオブジェクト」というそうです。
指定の方法は「i + (文字)」か「a + (文字)」です。例えば、「i"」だとカーソル位置から見て「"」で囲まれた部分を指定でき(「"」を含まない)、「a"」だと「"」も含んだ部分の指定が出来ます。iはinside、aはaroundだとか。
これはvimでよく使うv(範囲選択)やd(削除)と組み合わせることができます。
例えば、「"I use MacVim."」というテキストがあるとき、テキスト上で「vi"」とうつと「I use MacVim.」が選択でき、「va"」とうつと「"I use MacVim."」が選択出来ます。
あまり詳しくは調べていませんが、「]」や「)」で括弧も扱うことができ、「s」や「p」で或る程度のかたまりを扱うことも出来るようです(sentenceとparagraph?)

これだけでも便利ですが、テキストオブジェクトを扱うプラグインをいくつか紹介します。

テキストオブジェクトを増やすプラグイン

https://github.com/kana/vim-textobj-user
https://github.com/kana/vim-textobj-entire
https://github.com/kana/vim-textobj-line

userでテキストオブジェクトの独自定義、entireでバッファ全体、lineで行を扱うことが出来ます。
他にもいくつかあるようです。

surround.vim

https://github.com/tpope/vim-surround

テキストオブジェクトを用いて括弧などの変更や削除が簡単にできるようになります。
例えば「ds"」で"abc"をabcにしたり、「cs])」で[param]を(param)にしたり。

expand-region

https://github.com/terryma/vim-expand-region

Emacsのexpand-regionみたいなやつないかなーと思ってたら見事にありました。
しかもさらに細かい設定が可能。
このプラグインを使うとルールに従って動的に選択範囲を広げたり縮めたりすることができます。

僕は括弧に囲まれた文章がある時に
括弧内を選択 → 括弧も含めて選択
という風にしたかったので、以下のような設定にしました。

" テキストオブジェクト
" 値に1が設定されていればマップを展開する

let g:expand_region_text_objects = {
\   'i"' : 1,
\   'a"' : 1,
\   'i)' : 1,
\   'a)' : 1,
\   'i}' : 1,
\   'a}' : 1,
\   'i]'  :1,
\   'a]'  :1,
\   'i''' :1,
\   'a''' :1,
\   'ip' : 1,
\   'is' : 1,
\   'iw'  :0,
\   'il'  :1,
\   'ie'  :1
\}

今までなんでテキストオブジェクトもこれも知らなかったのだろう・・・。
作業効率が段違いになりました。
Emacsよりも範囲選択が楽になったかもしれない。もしかしたらEmacsからVimに移行するかも・・・

おまけ

Vimでペーストする時に周りの文脈に合わせてペーストする

「]p」でいいそうです。これをpにマップ。

nnoremap p ]p
nnoremap ]p p
Vim + Chrome

VimキーバインドChromeを扱えるChrome拡張機能「Vimium」がいい感じ。
他に「Vrome」や「Vichrome」もあるけど、今のところVimiumが一番いいかな?
Vimiumは「/」で日本語が使えないのが残念だけど、機能豊富。
Vromeは機能満点だけど「/」の検索が遅いのと、ブックマークや検索などのChrome標準機能が使えなくなっちゃうのが難点。
Vichromeはややあとの2つに機能が劣る感じ?

emacs-navでファイルをウィンドウ分割して開けるようにしてみた

近頃Node.jsを書くことが多かったのでエディタはAtomを使っていましたが、どうも重く感じることがあるので最近はEmacsを使っています。

Emacsのファイラはemacs-navを使っています。ファイル構成をツリー状に表示してくれるだけでなく、Emacs上からファイルのコピーやデリート、grepまで出来るすごいやつです。
でも一つ不満があり、ファイルを開く際にvimみたいに画面を分割して新たにファイルを開く機能がないのが不満でした。そのため、「ファイルを開く」→「画面を分割する」のが手間でした。
(どうも昔のnavはあったみたいです。なんでなくなったんだろう?)

探してもなかなか見つからなかったので、自分でnav.elを改造してみました。

1. ここから最新のnavを落とす(現時点で最新はmay 2012になってます)

2. コードを書き足す

(defun nav-open-file-under-cursor-vertically ()
 (interactive)
  (nav-open-file-under-cursor-split 2)
 )

(defun nav-open-file-under-cursor-horizontally ()
 (interactive)
  (nav-open-file-under-cursor-split 1)
 )

(defun nav-open-file-under-cursor-split (k)
  "Finds the file under the cursor."
  (interactive)
  (let ((filename (nav-get-cur-line-str)))
    (nav-open-file-split filename k)))

(defun nav-open-file-split (filename k)
  "Opens a file or directory from Nav."
  (interactive "FFilename:")
  (if (file-directory-p filename)
    (nav-push-dir filename)
    (let ((navdir (or (buffer-file-name) default-directory)))
      (other-window 1)
      (if (equal k 1)
        (split-window-vertically)
        (split-window-horizontally)
        )
      (message navdir)
      (find-file (concat navdir filename))
      )
    ))

3. キーバインドを定義
続いてキーバインドをnav-make-mode-mapに定義します。sで水平分割、vで垂直分割したかったので、

(define-key keymap "s" 'nav-open-file-under-cursor-horizontally)

(define-key keymap "v" 'nav-open-file-under-cursor-vertically)

と定義。

(4. byte-compileとか・・・)



これで簡単に横に並べてファイルを開くことが出来るようになりました。あんまり真面目に作ってないけど、特に不自由なく動きます。格段に便利になった。


追記:2014/6/20
違うディレクトリに動いた時にバグがあったので修正。

コード品質管理ツール「CppDepend」を使ってみた

最近Node.jsを書くことが多く、コードの品質管理ツールとしてJSHintを使っています。VimEmacsSublimeAtomなどの有名どころのエディタと連携して動的にコードスタイルのチェックが出来るため、コーディングを重ねることで自然によいコードを書けるように矯正を行うことができます。
例えば、次のようなコードは怒られます。

var SOME_VARIABLE = LEFT_OPERAND 
                    + RIGHT_OPERAND;

正しくは以下のようにします。

var SOME_VARIABLE = LEFT_OPERAND + 
                    RIGHT_OPERAND;

JavaScriptセミコロンの省略が可能なため、なるべく解釈に間違いのないようなコーディングが求められます。よって、行が次の行に続いているのかが分かり難い上のコードよりも下のコードの方が好ましいわけです。僕は上のコードの方が好きだったのですが、JSHintによって間違ったコーディングをしていたことに気がつきました。


他の言語でもJSHintのようにスタイルチェックをしてくれるものがあればいいなーと思っていたある日、「C++のコード品質管理ツール『CppDepend』を使ってみないか?」と薦められたため、使ってみました。

CppDepend

http://www.cppdepend.com/

主な特徴

  • デフォルトでコードに対する項目や規則が120個用意されている
  • 2つのビルド間で、単なるテキスト比較以上の変更を検知
  • クラス数、名前空間数、メソッド数などの82個のコードメトリクス

skypeやhp社も使っているとか。対応しているOSはWindowsLinux。有料ソフトですが、14日間の試用ができます。
僕が普段使っているMacに対応していないのが残念ですが、今回はWindows7でやってみることに。
Visual Studioなどのプロジェクトファイルにも対応しているようなのですが、持っていないので今回は僕が競技プログラミングで使っているC++のライブラリに対して使ってみました。

はじめは何らかのプロジェクトファイルがないと使えないのかと思いましたが、Project Makerを使ったら普通のC++ファイルに対してもいけました。



実行してみるとこんな感じのHTMLが表示されます。行数が少ないのもあるんだろうけど解析が結構早い。
コードの総数が539行と意外と少なかったのと、コメントが23%もあるというのにびっくり。



こちらがデフォルトの設定で違反していた規則の一覧。
大まかにあげてみると

  • 型名は大文字で始まるべき
  • 同じ名前の関数使いすぎ
  • メソッドで局所変数多すぎ
  • 1つのメソッドが大きすぎ
  • メソッドのコメントが少ないかも
  • フィールドはprivateにすべき

すっごい怒られてますけど、競技プログラミングはコードが汚くても誰にも迷惑をかけないのでいいんです(言い訳)。


以上がCppDependを軽く使ってみた結果です。
コード管理の項目がきめ細やかなので、C/C++Visual Studioなどを使って大型開発をしていて、コードの品質管理に困ったら選択肢に入れてみるのもいいんじゃないかと思います。