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; }
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; }
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)
実行するとこんな感じになる．
Pythonのコンテキストマネージャは１つで複数のコンテキストを管理できる
<|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で管理していそう．
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; }
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}
tmuxのタイトルにssh接続してるホスト名を表示させる
たくさんのサーバにsshする場合，tmuxのstatusが"ssh"で埋まってしまう．
以下のスニペットによって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 }
こうなる．
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
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を書けば全データをメモリに載せなくても学習可能
gensim.models.word2vec with generator
学習時にgeneratorを渡していた場合，__next__()が重いとworkersの値が2以上であっても
1スレッドしか学習が行われない現象が発生する．
gensimの並列化ではmasterが常にgeneratorからデータを取得し，各サブプロセス(workers個存在)のうち
空いているプロセスに投入する仕組みになっているために起きる現象の模様．
generatorの中でfor文を書いたりすると起きるので注意が必要．
2017/07/19 ~ 2017/07/20
税率変更
- 以下のように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
pair
pair
//#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; }
2017-07-05 ~ 2017-07-18
Dynetのインストール
gccはlinuxbrewで入れたものを使う
% which gcc gcc (Homebrew gcc 5.3.0) 5.3.0 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Eigen3をインストール
brew install eigen
glibcのバージョン
brew install glibc
> glibc: stable 2.19
> The GNU C Library
リポジトリをクローン
git clone https://github.com/clab/dynet.git
ビルドの準備
cd dynet mkdir build cd build cmake .. -DEIGEN3_INCLUDE_DIR=$HOME/.linuxbrew/include/eigen3/ -DPYTHON=`which python``
ビルド
make -j20 <|| 実行確認 >|sh| ./examples/train_xor # 動いた
c++までは動作を確認した．
-
- -
cd python
python setup.py install
実行
python >> import dynet # ImportError: /lib64/libc.so.6: version `GLIBC_2.14' not found (required by ./_dynet.so)
残念
あとで頑張る
考えられる原因
連続する整数の和
Sum of Consecutive Integers | Aizu Online Judge
整数Nがあたえられる．
２つ以上の連続する整数の組み合わせのうち，
和がN（1<=N<=1000）に等しくなるものの数を求める．
1. 連続する整数，つまり初項1，等差1の等差数列の部分列
2. 2点（左右）が定まれば良いので，全探索できる
//#define _GRIBCXX_DEBUG #include <bits/stdc++.h> # define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; int sum (int l, int r) { return (r*(r+1)-l*(l-1)) / 2; } int main() { int n; while (cin >> n, n) { int l, r; int ans = 0; for (int l=1; l<=n; l++) { for (int r=l+1; r<=n; r++) { int ret = sum(l, r); /* if (ret == n) cout << l << ", " << r << "= " << ret << endl; */ if (ret == n) ans++; } } cout << ans << endl; } return 0; }
Keitai Message
Keitai Message | Aizu Online Judge
つらいやるだけ問題．
1. ヘッドを用意して順次更新
2. 0が入力されたら出力にpushしてヘッドを初期化
//#define _GRIBCXX_DEBUG #include <bits/stdc++.h> # define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; class Keyboard { public: string input, output; vector<vector<char>> keyboard; string make_output(); Keyboard(string input) : input(input) { // IMPORTANT: vector<vector<char>> keyboard; // これをここでやってしまうとメンバ変数とは違う // 形で初期化が行われてしまい外部から参照できなくなる keyboard.resize(10); keyboard[0] = vector<char>({'A'}); keyboard[1] = vector<char>({'.', ',', '!', '?', ' '}); keyboard[2] = vector<char>({'a', 'b', 'c'}); keyboard[3] = vector<char>({'d', 'e', 'f'}); keyboard[4] = vector<char>({'g', 'h', 'i'}); keyboard[5] = vector<char>({'j', 'k', 'l'}); keyboard[6] = vector<char>({'m', 'n', 'o'}); keyboard[7] = vector<char>({'p', 'q', 'r', 's'}); keyboard[8] = vector<char>({'t', 'u', 'v'}); keyboard[9] = vector<char>({'w', 'x', 'y', 'z'}); } }; string Keyboard::make_output() { int curr; int prev = -1; int freq = 0; output = ""; rep (i, input.size()) { curr = (int)input[i] - 48; // ascii code // 一緒 or 初め if (curr == prev || prev == -1) freq++; // 入力確定 if (curr == 0) { if (prev != -1) { freq--; int qindex = keyboard[prev].size(); /* cout << "i, j: " << prev << "," << freq % qindex << endl; */ /* cout << keyboard[prev][freq%qindex] << endl; */ output += keyboard[prev][freq%qindex]; } // 初期化 prev = -1; freq = 0; } else prev = curr; } return output; } int main() { int n; string s; cin >> n; rep (i, n) { cin >> s; Keyboard k = Keyboard(s); cout << k.make_output() << endl; } return 0; }
お姫様のギャンブル
Princess's Gamble | Aizu Online Judge
実際にシミュレーションをする．
分母に0が来ることがあるので0除算の恐れがある．
場合分けを行えば良い．
//#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, f; while (cin >> n >> m >> f, n) { vector<int> x(n); rep (i, n) cin >> x[i]; float sum = 0; rep (i, n) sum += 100.0*x[i]; float ret = sum - ((float)f/100) * sum; int ans = ret / x[m-1]; cout << (ans > 0 ? ans : 0) << endl; } return 0; }
C++で文字列を数値にする
c_strでconst char*に変換するといける
普通はどうするものなのかよくわかっていない
（そもそも文字列->数値な変換が発生すること自体がダメ？）
//#define _GRIBCXX_DEBUG #include <bits/stdc++.h> # define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; int main() { string a = "53"; int i = atoi(a.c_str()); cout << i << endl; return 0; }
Long Short-Term Memory Over Tree Structures
- 論文: https://arxiv.org/abs/1503.04881
- 実装: https://github.com/pfnet/chainer/blob/master/chainer/functions/activation/slstm.py (in chainer)
概要
LSTMの木構造への一般化を考える．
背景
LSTMは線形な系列を入力に受け取る，非常に成果をあげているニューラルネットワークである．
しかし，いくつかのケースでは入力が線形ではなく，なんらかの構造を持っていた方が良さそうなケースというものもある．
代表的なものにstanford nlpの[sentiment treebank](https://nlp.stanford.edu/sentiment/)がある．
これは文を構文解析し，構文木が入力として与えて文の極性を予測するタスクである．
葉ノード（単語に相当する）と内部ノード（フレーズに相当する）に対して極性が人手（？）でアノテーションされている．
[Socher et al.](https://nlp.stanford.edu/~socherr/EMNLP2013_RNTN.pd://nlp.stanford.edu/~socherr/EMNLP2013_RNTN.pdf)はRecursive Neural Network(RvNN)・RNTNNを用いてこのタスクを解いた．
RvNNは内部に再帰構造を持っており，木を入力とすることができる一方で，木の深さが深くなると勾配消失が起きてうまく学習できない問題がある．
これは通常のRNNにも見られる問題であり，LSTMはメモリブロックという概念を導入することでこの問題に対処した．
この成果を活かし，RvNNにもLSTMのメモリブロック構造を導入し，より深い構文木が入力されても学習可能なS-LSTM(Structured-LSTM)を提案した．
手法
モデル全体は以下の図のようになっている．
また，各ノードに注目すると以下の図のようになっている．
LSTMと非常によく似た構造であり，差分としてはS-LSTMには忘却ゲートが2つ存在する．
ちなみに，忘却ゲートが2つと言っているが，これは入力される木が2分木であると仮定しているからそうなっているだけであり，n分木の場合は忘却ゲートがn個になる．
著者曰く
> Extension of teh model to handle more children is rather straightforward
である．
ちなみに，なぜ入力が2分木なのかというと，sentiment treebankのデータ構造が2分木であり，Socher et al.と同じ条件で実験しているからである．
入力・セル・重み・入力ゲート・忘却ゲート・出力ゲートについて詳しく見ていく．
忘却ゲートとセル，および重みが2つあることがわかる．
学習はSocher et al.と同じように行う．ロス関数は2通り考えられている．
実験
sentiment treebankを用いて評価実験を行なった．
比較対象はSocher et al.のRvNNとRNTN,，あとNaive BayesとSVM．
RvNNは通常のRecursive Neural NetworkでRNTNはRecursive Neural Tensor Network．
RNTNはテンソルを用いたRvNNの一般化(?)モデルであるらしい．Socher et al.を読んでください．
| MODEL | ROOTS | PHRASES |
|---|---|---|
| NB | 41.0 | 67.2 |
| SVM | 40.7 | 64.3 |
| RvNN | 43.2 | 79.0 |
| RNTN | 45.7 | 80.7 |
| S-LSTM | 48.0 | 81.9 |
S-LSTMが一番良い性能を発揮した．
S-LSTMはRNTNと比較すると学習にかかる時間が短い点もアピールされている（論文を読んでください）．
ここからが面白い点だが，著者らはsentiment treebankのアノテーションはあまり現実のデータに則していないことを指摘している．
というのも，sentiment treebankは木のすべてのノードに対してアノテーションを行なっているが，現実のデータにフレーズ単位のアノテーションが付与されているとは考えにくい．
そのため，フレーズ単位のアノテーションが得られていない以下の2つの設定で追加実験をを行なった．
おそらく以下のようなデータが与えられている（赤色がアノテーションされていることを示す）．
| MODEL | ROOTS |
|---|---|
| (a) RNTN | 29.1 |
| (a) S--LSTM | 29.1 |
| (b) RNTN | 34.9 |
| (b) S--LSTM | 44.1 |
同じ条件下ではRNTNよりも良い予測性能を発揮していることがわかる．
議論の腰を折りかねない疑問として「本当に入力に構造があった方が良いのか？」というものがある．
通常のLSTMも暗黙的に構造のようなものを学習していて，入力データには明示的な構造は必要ないのではないかという意見も起きうる．
そこで，データに対して特殊な制約を加えて，それらのデータを学習に使った場合と木構造を入力とした場合の予測性能も比較している．
LSTM--LRとLSTM--RRという2つの特殊なデータは，本来木構造を持っていた入力データの枝を張り替えて，構造を壊したものである．
LRは文中の1番左の単語の左側にルートノードを張り，RRは1番右の単語の右側にルートノードを張っていることを示している．
| MODEL | ROOTS |
|---|---|
| (a) S--LSTM--LR | 40.2 |
| (a) S--LSTM--RR | 40.3 |
| (a) S--LSTM | 43.5 |
| (b) S--LSTM--LR | 43.1 |
| (b) S--LSTM--RR | 44.2 |
| (b) S--LSTM | 44.1 |
LRとLLはほぼ同じ性能，もともとの木構造を入力としたものがそれより良い性能を発揮していることがわかる．
この結果から，著者は少なくともいくつかのタスクにおいては入力データの木構造は予測性能に影響を与えると結論付けた．
