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
カッコの対応が取れているかを判定する問題と同じ．
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
はじめはカレーの濃度は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; }
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; }
