2017/08/13 ~ 2017/08/16

c++のヘッダを探索パスに追加

毎回調べては忘れているのでメモ.
g++などのコンパイラのオプションとして渡せないときは環境変数を使う.


たとえば,deepnlのビルドにはeigenが必要である.
linuxbrewを使ってeigenをインストールしていた場合,
ヘッダファイルは $(brew --prefix)/Cellar/eigen/version_name/include/eigen3 にある.
よって以下のようにヘッダを指定してやればよい.

CPLUS_INCLUDE_PATH=$(brew --prefix)/Cellar/eigen/3.3.4/include/eigen3 python setup.py build

github.com

Vimでヤンクなしで一行を削除する

"_dというコマンドがあることを知った.
以下のようなmappingをすることでdでヤンクなし削除が実現できた.

github.com


stackoverflow.com

Recurring Decimals

繰り返す10進数 | Aizu Online Judge

 a_{k-1} の各桁の数値を持つベクターを作り,
ソートはベクターに対して行う.
ソート後に a_k を計算すればよい.
コードやや汚い.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int make_number(vector<int> &a, int l) {
  int res = 0;
  for (int ll=l-1; ll>=0; --ll) {
    res += a[l-ll-1] * pow(10, ll);
  }
  return res;
}

int main() {
  int a0_raw, l, d;
  vector<int> a, a0;

  int i, j;
  int ak_raw;


  while (cin >> a0_raw >> l, a0_raw || l) {
    a0.resize(0); a.resize(0);
    bool reached = false;

    for (int ll=l-1; ll>=0; --ll) {
      d = a0_raw / pow(10, ll);
      a0_raw -= d * pow(10, ll);
      a0.push_back(d);
    }

    a.push_back(make_number(a0, l));

    while (1) {
      sort(a0.begin(), a0.end());
      int amin = make_number(a0, l);

      reverse(a0.begin(), a0.end());
      int amax = make_number(a0, l);

      a0_raw = amax - amin;
      a.push_back(a0_raw);

      i = a.size() - 1;
      rep (j_, i) {
        if (a[i] == a[j_]) {
          j = j_; reached = true;
          break;
        }
      }

      if (reached) break;

      a0.resize(0);
      for (int ll=l-1; ll>=0; --ll) {
        d = a0_raw / pow(10, ll);
        a0_raw -= d * pow(10, ll);
        a0.push_back(d);
      }
    }

    cout << j << " " << a0_raw << " " << i-j << endl;
  }

  return 0;
}
latexなどで利用可能なフォントの一覧を見る

XeLaTeX環境を作るとき,フォントの設定をどうすればよいかわからず色々調べた.
結果として,使用可能なフォントの一覧は fc-list というコマンドで確認できることがわかった.

Presentation with XeLaTeX

matplotlib.pyplot で日本語を使う

matplotlib.rcでフォントを指定できる.

from matplotlib import rc

font = {'family': 'YuGothic'}  # NOTE: use YuGothic for Japanese
rc('font', **font)

paper.hatenadiary.jp

2017/08/09 ~ 2017/08/11

shell script (bash) の配列

bashには配列というものが存在しないらしい.
stackoverflow.com

が,200から1000まで200ずつ増やした数字をループの中で作りたい状況に遭遇した.
seqコマンドでやりたいことができた.

HIDDEN_UNITS=$(seq 200 200 1000)

for hidden_unit in $HIDDEN_UNITS; do
  python train.py --hidden $hidden_unit
done

これでパラメータを変更しながら実験する作業を自動化できる.

A-un Breathing

阿吽の呼吸 | Aizu Online Judge


カッコの対応が取れているかを判定する問題と同じ.
bool wrongを初期値なしで初期化してWAを大量にもらってハマっていた.
bool wrongの初期値がtrueになる場合とfalseになる場合がある?

stackでもできるはずだけどREをいただいてしまう.なぜ?
http://jag2016-domestic.contest.atcoder.jp/submissions/1501888

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n;
  cin >> n;

  int cnt = 0;
  bool wrong = false; // 初期値はtrueなことがある

  string s;
  rep (i, n) {
    cin >> s;
    if (s == "A") {
      cnt++;
    }
    else if (s == "Un") {
      if (cnt > 0) {
        cnt--;
      }
      else {
        wrong = true;
      }
    }
  }

  if (wrong || cnt > 0) {
    cout << "NO" << endl;
  }
  else {
    cout << "YES" << endl;
  }

  return 0;
}
Curry Making

カレー作り | Aizu Online Judge


はじめはカレーの濃度はCよりも低い.
Cよりも濃度が高くなるようにルーを追加し,
そのあとで水を加えれば良い.
そのため,水はルウの個数と切り離して考えることができる.
また,ルウは必ず整数個であることが保証されている.
つまり,ルウの個数を1から適当に大きな数まですべて試せばよい.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int r_0, w_0, c, r;
  while(cin >> r_0 >> w_0 >> c >> r, r_0) {

    for (int x=0; x<1001001001; x++) {
      if (c <= (double)(r_0+x*r)/w_0){
        cout << x << endl;
        break;
      }
    }
  }
  return 0;
}

2017/08/04 ~ 2017/08/09

2582: Step Aerobics

両足で踏み台を登るか降りるかした回数をカウントする.
左足と右足が現在何段目にいるか,前回カウント時に両足は何段にいたかを変数として持つ.
実際にシミュレーションすれば解ける.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n;
  string input;

  while (cin >> n, n) {
    int prev_h = 0;
    int curr_l = 0, curr_r = 0;
    int ans = 0;

    rep (i, n) {
      cin >> input;

      // cout << input << endl;

      if (input == "lu") curr_l++;
      if (input == "ld") curr_l--;
      if (input == "ru") curr_r++;
      if (input == "rd") curr_r--;

      // cout << curr_l << "-" << curr_r << endl;

      if (curr_l == curr_r && curr_l != prev_h) {
        // cout << "count" << endl;
        ans++;
        prev_h = curr_l;
      }
    }

    cout << ans << endl;
  }
  return 0;
}


Step Aerobics | Aizu Online Judge

Entrance Examination

ギャップはi番目とi+1番目の学生の得点の差である,
合格者の数が条件を満たしているか確認したあとで
ギャップがこれまでのギャップの最大値以上か確認する.
ギャップがこれまでの最大値以上であった場合は合格者数を更新する.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, left, right;
  vector<int> p;

  while (cin >> n >> left >> right, n) {
    p.resize(n);
    rep (i, n) cin >> p[i];

    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());

    int n_passed = 0;
    int max_gap = 0;

    rep (i, n-1) {
      if (! (left <= i+1 && i+1 <= right) ) continue;
      if (max_gap <= p[i] - p[i+1]) {
        n_passed = i+1;
        max_gap = p[i] - p[i+1];
      }
    }
    cout << n_passed << endl;
  }
  return 0;
}

Entrance Examination | Aizu Online Judge

2017/07/31 ~ 2017/08/03

Python matplotlibとpandasで信頼区間つきのグラフを描画する

fill_betweenをつかうとよい.
これはpandas.DataFrameを使っているときにも利用できて便利.
pandasとmatplotlibの仲の良さはとてもありがたい.

以下にコード例を示す.

import math
import random
import pandas

x = [i for i in range(100)]
y = [math.sin(i) for i in range(100)]
stdy = [random.random() for i in range(100)]

data = zip(x, y, stdy)
df = pandas.DataFrame(list(data), columns=['x', 'y', 'ystd'])

plt = df.plot(x='x', y='y')
plt.fill_between(df.x, df.y-df.ystd, df.y+df.ystd, alpha=0.3)

実行するとこんな感じになる.
f:id:himkt:20170801094038p:plain

Pythonのコンテキストマネージャは1つで複数のコンテキストを管理できる

<|python|
with open('input1.txt') as input1_fp, open('input2.txt') as input2_fp:
for line1, line2 in zip(input1_fp, input2_fp):
print(line1, line2)
|

8. Compound statements — Python 3.6.2 documentation

pickleで大きなデータをシリアライズ

普通だとpickle.dumpに4GB以上のオブジェクトを渡すと

OverflowError: cannot serialize a bytes object larger than 4 GiB

と言われてしまう.これはpickle.dumpの中でint32が使われているせいらしい.
調べて見たらprotocol4というのがあって,このプロトコルではサイズをint64で管理していそう.

www.python.org

C++の非決定的な乱数生成

標準で使えるrand()は決定的な乱数を生成する.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  for (int i=0; i<10; i++) {
    cout << rand() << endl;
  }
  return 0;
}

これをコンパイルして何回実行しても結果は以下のようになった.

16807
282475249
1622650073
984943658
1144108930
470211272
101027544
1457850878
1458777923
2007237709

一方,ハードウェアの状態などを用いて非決定的な乱数を生成する生成器がC++11にはある.
以下のように使える.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  random_device rnd;
  for (int i=0; i<10; i++) {
    cout << rnd() << endl;
  }
  return 0;
}

C++11 乱数 std::random 入門

ディレクトリのツリー構造の可視化

treeコマンドでやっていたけどlsコマンドにも良い感じのオプションがあることを知った.

takuya-1st.hatenablog.jp

2017/07/27 ~ 2017/07/30

centos6にglibc2.14をビルド

何かと必要になるアイツ
centos6.5のglibcは2.12

configureのときにlinuxbrewで新しいgccをインストールしていた場合はコケることになる.
システムのgccを使うようにしてやればよい

wget http://ftp.gnu.org/gnu/glibc/glibc-2.14.tar.gz
tar xvf glib-2.14.tar.gz
mkdir build
cd build
CC=/usr/bin/gcc ../glibc-2.14/configure --prefix=$HOME/.local
Python3系ではkey in dict.keys()をすればよい

dictionary.keys()ってリストを返すと思っていた.
リストに対するin演算子は線形探索をするだろうからめちゃくちゃ遅そう.
KeyErrorを引っ掛ける実装をしたほうが良いのでは?と思ってずっとそのようにしていた.

key = 3334
dict = {i: 1 for i in range(100000)}
try:
    dict[key]
    print('found')
except KeyError:
    print('not found')

だが,調べてみたところPython3系ではdictionary.keys()はdict_keysというビューオブジェクト(イテレータ)を返す.
Pythonのドキュメントには以下のようにあった.

Calling d.keys() will return a dictionary view object. It supports operations like membership test and iteration, but its contents are not independent of the original dictionary – it is only a view.

5. Data Structures — Python 3.6.2 documentation

そしてこのオブジェクトに対するin演算子は定数時間で実行可能なようだ.

というわけで,Python3系を使っているなら安心して

key in dict.keys()

を使いましょう.

  • Python2系,dictionary.keys()がリストを返していることがわかる
In [3]: type(dic.keys())
Out[3]: list

In [4]: dic = {i: 1 for i in range(100000000)}

In [5]: %time 3333334 in dic.keys()
CPU times: user 1.34 s, sys: 160 ms, total: 1.5 s
Wall time: 1.5 s
Out[5]: True

In [6]: type(dic.keys())
Out[6]: list

In [7]:
  • Python3系
In [1]: dic = {i: 1 for i in range(100000000)}

In [2]: %time 3333334 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 11.9 µs
Out[2]: True

In [3]: %time 0 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 10.7 µs
Out[3]: True

In [4]: %time 11111120 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 11.7 µs
Out[4]: True

In [5]: %time 1111112343220 in dic.keys()
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 10.3 µs
Out[5]: False

In [6]: type(dic.keys())
Out[6]: dict_keys

In [7]:
pandas.read_csvのときに特定のラベルのデータの型を指定したい

read_csvの引数としてdtype=dictionaryを与えてやればよい.
たとえば以下のようなcsvファイルがあったとする.(test.csv

label, precision
+1,0.8
-1,0.7

このとき,ラベルのカラムのデータは数値というよりは文字列である.
pandasは+1も数値としてパースして1にしてしまうので,以下のようにしてやる.

pandas.read_csv('test.csv', dtype={'label': str}

pandas.read_csv — pandas 0.20.3 documentation

tmuxのタイトルにssh接続してるホスト名を表示させる

たくさんのサーバにsshする場合,tmuxのstatusが"ssh"で埋まってしまう.

f:id:himkt:20170730173747p:plain

以下のスニペットによってstatusにhost名を表示させることができる.

ssh() {
    if [ "$(ps -p $(ps -p $$ -o ppid=) -o comm=)" = "tmux" ]; then
        tmux rename-window "$(echo $* | cut -d . -f 1)"
        command ssh "$@"
        tmux set-window-option automatic-rename "on" 1>/dev/null
    else
        command ssh "$@"
    fi
}

こうなる.
f:id:himkt:20170730174126p:plain

Set tmux pane title on SSH connections – blog.no-panic.at

When Can We Meet?

When Can We Meet? | Aizu Online Judge

n人のミーティングに参加可能な日程が与えられ,もっとも参加人数の多い日を求める問題.
std::mapを使って簡単に解ける.最後に制約条件qを満たすかどうかを確認するのを忘れないように注意.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, q, m, d;
  map<int, int>::iterator it;

  while (cin >> n >> q, n) {
    map<int, int> freq;
    rep (i, n) {

      cin >> m;
      rep (k, m) {
        cin >> d;

        it = freq.find(d);
        if (it == freq.end()) {
          freq[d] = 1;
        }
        else {
          freq[d]++;
        }
      }
    }

    int max_d = -1;
    int max_v = 0;

    for (pair<int, int> p : freq) {
      if (max_v < p.second) {
        max_d = p.first;
        max_v = p.second;
      }
    }

    if (max_v >= q) {
      cout << max_d << endl;
    }
    else {
      cout << 0 << endl;
    }
  }
  return 0;
}

2017/07/21 ~ 2017/07/26

Kagisys


Kagisys | Aizu Online Judge


n本の認証キーとm回の認証試行がある
m回のループを回して各回で扉を開錠可能かどうか判定すればよい
扉の状態を保存するためにループの外側に変数openedがある

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n, m;
  cin >> n;
  vector<string> u(n);
  rep (i, n) cin >> u[i];

  cin >> m;
  vector<string> t(m);
  rep (i, m) cin >> t[i];

  vector<bool> ut(m);
  bool opened = false;

  rep (i, m) {
    bool solved = false;

    rep (j, n) {
      if (t[i] == u[j]) {
        if (opened) {
          cout << "Closed by " << t[i] << endl;
          opened = false;
          solved = true;
        }
        else {
          cout << "Opened by " << t[i] << endl;
          opened = true;
          solved = true;
        }
        break;
      }
    }

    if (!solved) cout << "Unknown " << t[i] << endl;
  }

  return 0;
}
便利なgensim.models.word2vec
  • loggingの設定を書けば学習の進捗状況をレポートしてくれる
  • 単語の表層形を返すgeneratorを書けば全データをメモリに載せなくても学習可能

rare-technologies.com

gensim.models.word2vec with generator

学習時にgeneratorを渡していた場合,__next__()が重いとworkersの値が2以上であっても
1スレッドしか学習が行われない現象が発生する.

gensimの並列化ではmasterが常にgeneratorからデータを取得し,各サブプロセス(workers個存在)のうち
空いているプロセスに投入する仕組みになっているために起きる現象の模様.

generatorの中でfor文を書いたりすると起きるので注意が必要.

github.com

2017/07/19 ~ 2017/07/20

税率変更

税率変更 | Aizu Online Judge

  • 以下のように1つのループで税込み価格を探索しようとしたが失敗した
for (int p1=1; p1<s; p1++) {
  int p2 = s-p1;
}
  • 税抜き価格で全探索する
//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int x, y, s;
  while (cin >> x >> y >> s, x && y && s) {
    int ans = 0;

    for (int o1=1; o1<s; o1++) {
      for (int o2=1; o2<s; o2++) {

        int p1 = o1 * (100+x) / 100.0;
        int p2 = o2 * (100+x) / 100.0;

        if (p1+p2 != s) continue;

        int n1 = o1 * (100+y) / 100;
        int n2 = o2 * (100+y) / 100;

        ans = max(ans, n1+n2);

      }
    }

    cout << ans << endl;
  }
  return 0;
}
Amida, the City of Miracle

Amida, the City of Miracle | Aizu Online Judge

あみだくじの枝を高さでソートする
始点を選び,辿っていく
[解説](http://www.deqnotes.net/acmicpc/p0102/)をみてmultisetを使った

イテレータにはドット演算子ではアクセスできない
アロー演算子を使う必要がある
C++よくわかっていないので原因はあとで調べる

pair v = it.second; // ダメ
pair v = it->second;
pair v = (*it).second;

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

typedef multimap< int, pair<int, int> > HL;

int main() {
  int n, m, ans;
  int h, p, q;

  while (cin >> n >> m >> ans, n && m && ans) {
    set<int> hs;
    multimap<int, pair<int, int>> hl;

    rep (i, m) {
      cin >> h >> p >> q;
      hs.insert(h);
      hl.insert(make_pair(h, make_pair(p, q)));
    }

    for (set<int>::reverse_iterator sit=hs.rbegin(); sit!=hs.rend(); sit++) {
      int hhead = *sit;

      for (multimap<int, pair<int, int>>::iterator it = hl.lower_bound(hhead); it != hl.upper_bound(hhead); it++) {
        pair<int, int> v = it->second;
        if (v.first == ans) {
          ans = v.second;
          break;
        }
        else if (v.second == ans ) {
          ans = v.first;
          break;
        }
      }
    }

    cout << ans << endl;
  }
  return 0;
}
幸運の操作者

Luck Manipulator | Aizu Online Judge

10000+1 (0回目+10000回の試行) の乱数生成結果を先に作る
あとは作った乱数とYを照合する
計算はもっとサボれる (毎回10000回乱数生成をする必要はない) が,
一番楽な実装でも十分間に合いそうだったのでこのまま

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int solve(int n, int a, int b, int c, int x, vector<int> &y, vector<int> &z) {
  int head = 0;
  rep (t, 10000+1) {
    if (y[head] == z[t]) head++;
    if (head == n) return t;
  }
  return -1;
}

int main() {
  int n, a, b, c, x;
  vector<int> y;
  vector<int> z(10000);

  while(cin >> n >> a >> b >> c >> x, n) {
    y.resize(n); z[0] = x;
    rep (i, n) cin >> y[i];

    for (int i=1; i<=10000; i++) z[i] = (a*z[i-1] + b) % c;
    cout << solve(n, a, b, c, x, y, z) << endl;
  }
  return 0;
}