プログラミング上級者を目指して Twitter

2018-04-04

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

01:22


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

解法

動的計画法で出しました。
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っていうキーワードが必要なのを初めて知った)

2018-03-25

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

04:40


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;
}


参考

解法の参考

AOJ 2403 The Enemy of My Enemy is My Friend - okaduki's diary
AOJ 2403 The Enemy of My Enemy is My Friend - mayoko’s diary

高速ゼータ変換/高速メビウス変換について

高速ゼータ変換 - (iwi) { 反省します - TopCoder部
no title
高速ゼータ変換 - とどの日記
高速ゼータ変換、高速メビウス変換 - omochan's diary
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
AOJ 2446 Enumeration + 高速メビウス変換まとめ - simezi_tanの日記
競技プログラミングにおける畳み込み問題まとめ(FFT,アダマール変換,メビウス変換,ゼータ変換) - はまやんはまやんはまやん

想定解法

Staff/山口 - ACM-ICPC Japanese Alumni Group
AOJ2403 The Enemy of My Enemy is My Friend - nanikakaのAOJ航海日誌

2014-11-03

sedで「git blame」に色づけ

| 20:48


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では何故か着色出来なかったので、homebrewgnu-sedインストール

brew install gnu-sed

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

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

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

f:id:mkiken:20141103203913p:image
(上がデフォルトblame、下が色付きblame)

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

2014-08-30

pecoを使って動的にgrepする

| 14:05


動的に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'


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

2014-07-09

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

| 01:55


今日チームの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つに機能が劣る感じ?

Connection: close