ICPC国内予選参加記 2017
参加まで
忙しいし出なくて良いかーと思っていたのですが*1，先輩の後押しで参加することに．
今年で3回目の参加だったので，登録まではバタバタせずにすみました．（監督・コーチありがとうございました！）
メンバーは去年と同じ同期のメンバーが1人と研究室の後輩1人引き連れて参加しました．
締切ギリギリで参加を決めたので，一度だけ通し練習をして本番へ．
当日
プリンタの不調で問題が10分ぐらい印刷できず，テンパる（ちゃんと印刷確認しましょう）
落ち着いた後は，後輩にA,同期にBを任せて，自分はCを取り組む．
Cは去年，一昨年と面倒くさい実装だったのですが，今年は簡単で余裕があったので，Aのバグ取りを一緒してました．
CよりBの問題の方がパッと見て面倒臭そうだったので，先にPCを使うことに．
バグらせながらゆるゆるとAC．
Bを任せるのが結構不安だったので，問題を読みながらペアプロ．
想定よりだいぶ早く解けて（自分が解いてたら焦ってやばかったかも），この時点ではかなり良い順位に．
Dをフローとかじゃん？しばらくやった後，Gも外壁の近くを良い感じに辿るだけでいけそうと思って実装していました．
Gの実装をバグらせてる間にタイムアップ．
69位でした．国内予選落ちです．
感想
3年もやってて4問解けないの情けなさすぎて泣いてました．
Dの場合分けに気づけないの本当に悔しかったです．
Gの実装も上手く行けばワンチャンあったかもしれないのに，それも間に合わなかったので，完全に練習不足でした．
僕は今年で引退ですが，後輩が引き続き参加して，うちの大学も常連校ぐらいまで成長してほしいと思っています．
とりあえず，宣伝・指導をしないと来年から消えそうなので頑張ります．
反省
D問題解きました．Gもそのうち解きます．
#include <bits/stdc++.h> using namespace std; // n(<=23)が小さいとき，全探索 int nsmall(int n,int m,const vector<bitset<501>>& bits){ int ret = 0; for(int i=0;i<(1<<n);i++) { bitset<501> used; int cnt = 0; for(int j=0;j<n;j++){ if((i>>j) & 1) { used = used ^ bits[j]; cnt++; } } if(used.none()){ ret = max(ret,cnt); } } return ret; } // mが小さいとき，レシピの状態でDP vector<vector<int>> dp; int msmall(int n,const int N,int used,const vector<int>& b){ if(n == N){ if(used == 0)return 0; else return -1e9; } if(dp[n][used] != -1) return dp[n][used]; return dp[n][used] = max(msmall(n+1, N, used ^ b[n], b) + 1, msmall(n+1, N, used, b)); } bool solve(){ int n,m; cin >> n >> m; if(n == 0 && m == 0) return false; vector<string> vs(n); for(int i=0;i<n;i++){ cin >> vs[i]; } vector<bitset<501>> bits(n); vector<int> b(n); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(vs[i][j] == '1'){ bits[i].set(j); b[i] |= (1<<j); } } } if(n <= 23){ cerr << "n:" << n << endl; cout << nsmall(n,m,bits) << endl; }else{ cerr << "m:" << m << endl; dp = vector<vector<int>>(n,vector<int>((1<<m),-1)); cout << msmall(0,n,0,b) << endl; } return true; } int main(void) { while(solve()){} return 0; }
*1:去年も同じようなことを言っていましたが今年は本当に
モナコインのマイニングソフトをDockerで動かす
モナコイン
モナコインは，ブロックチェーン利用した仮想通貨で，同種で有名なものにはビットコインがあります．
詳しい説明は省きます．
https://monacoin.org/ja/
概要
単独で採掘するほどのリソースがないので，皆で掘って報酬を分割するマイニングプールを利用します．
今回は取り敢えず，VIP Poolに登録しました．（※現在，新規登録ができません．）
https://vippool.net/index.php
また，マイニングソフトとして，cpuminer-multiを使います．
環境構築
VIP Poolの設定は下リンクを参照．
マイニングプールの設定 ~ Start-MonaCoin スタートモナコイン
マイニングソフトは，cpuminer-multiを入れたいのですが，
ホスト環境をあまり汚したくないので，Docker上にcpuminer-multiのコンテナを立てました．
githubページ内から，Dockerfileを探し，ダウンロードします．
GitHub - tpruvot/cpuminer-multi: crypto cpuminer (linux + windows)
Dockerfileと同じディレクトリで以下のコマンドを実行します．
# イメージの作成 docker build . # イメージからコンテナを作成，起動 docker run Imageid -a lyra2rev2 -o stratum+tcp://vippool.net:8888 -u Weblogin.WorkerName -p WorkerPassword
Weblogin ⇒ ユーザー名
Worker ⇒ ワーカー名
Workerpassword ⇒ ワーカーのパスワード
良い感じのログが確認できたら成功です．
少しするとVIP poolサイト上のワーカーやトランザクションのページも更新されます．
バックグラウンドで実行したい場合は，一回コンテナから出てから起動しなおすか
runの-dオプションで新たにコンテナを作成するかしてください．
# コンテナをバックグラウンドで起動 docker start Containerid # イメージからコンテナを作成，バックグラウンド起動 docker run -d Imageid -a lyra2rev2 -o stratum+tcp://vippool.net:8888 -u Weblogin.WorkerName -p WorkerPassword
自分は，実際には，ログが一杯になるの嫌だなと思ったので，
docker run -d --log-opt max-size=100m ...
として，100Mまでしか保存させなくしています．（もっと小さくてもいいかも）
Dockerだとどの環境でも簡単に動かせて良いですね．
ちなみにMonappyのアドレスはこれです．
MTYHb3QmNtNmrUUaQZj9JzUT7uN3qkXE72
ありがとうございました．
Yandex Algorithm 2017 Marathon 感想
Yandex Algorithm 2017 Marathonの反省です．
Marathon Roundは2017/5/6, 6:00~2017/5/8, 6:00の2日間で行われました．
https://contest.yandex.com/algorithm2017/contest/4524/problems/
問題
N×Mのグリッド上に生命の泉と魔法の泉がK個ある．
このグリッドをK色に塗り分ける．
この時，同色のマスは連結であり，生命の泉と魔法の泉をちょうど1つずつ含む必要がある．
スコアは，面積 / 別の色との隣接数^2 を各色について算出したものの平均とする．
方針
- 生命の泉と魔法の泉のペアを作る．（ペア間の線分の交差数と距離の和が小さくなるようにビームサーチ）
- 各ペア間のパスを塗る
- まだ塗られていないマスを隣接マスで一番多い色で塗る．
- 1つペアを変えて2,3を試す．（スコアでビームサーチ）
ソース
綺麗にしてから上げます．
反省
- ペア生成に関して
- 方針の1は最小費用流を使ったマッチングでこれより良いペアが見つかりそう．
- 塗り分けに関して
- まず，ペアの作成より色を塗る部分の方が得点に関わってくることを見抜けなかった
- 同面積であれば正方形に近い方が得点が高いので，その辺を考慮すべきだった．
- 全般
- 制約を確認していない．
- スコアの伸ばし方をしっかり考えずに取り組み始めた．
- ビームサーチ等の実装に時間を取られすぎるのでパッと試せるようにテンプレ化しておきたい
- 雑なvisualizerを作ったのはモチベの向上に割りと良かった．（素早く作れるように練習が必要そう）
kaggleのDigit Recognizerへ初提出（Chainer）
はじめに
kaggle -Digit Recognizer
Digit Recognizer | Kaggle
kaggle初提出までしたことをとりあえずまとめます．
初提出まで
まずは軽くお勉強
ニューラルネットワークと深層学習
http://nnadl-ja.github.io/nnadl_site_ja/index.html
さすがに何もわかっていない状態でサンプルを動かすだけだと無意味そうだったので少しお勉強．
式は完全には追わずに何故この関数なのかみたいな部分だけ拾い読みしました．今後ちゃんと式も理解したい．
実装
まずは，訓練データ等をkaggleからダウンロードしてくる．
NNのモデルは各層ニューロンの数を以下のように適当に決めて実装．
また，コスト関数はクロスエントロピーコスト関数を導入．
| input | hidden1 | hidden2 | output |
|---|---|---|---|
| 784 | 1000 | 1000 | 10 |
modelはこんな感じ．
class MyChain(Chain): def __init__(self): super(MyChain,self).__init__( l1 = L.Linear(784,1000), l2 = L.Linear(1000, 1000), l3 = L.Linear(1000,10) ) def __call__(self, x): h1 = F.sigmoid(self.l1(x)) h2 = F.sigmoid(self.l2(h1)) h3 = self.l3(h2) return h3 class Classifier(Chain): def __init__(self,predictor): super(Classifier,self).__init__(predictor=predictor) def __call__(self,x,t): y = self.predictor(x) loss = F.softmax_cross_entropy(y,t) return loss,F.accuracy(y,t)
訓練データを読み込んで，実際にモデルを学習させます．
まず，MacBookAirでやるには訓練データのサイズが大きすぎるので，先頭1000行ぐらいを切り分けする．
head -n 1000 train.csv > small_train.csv
訓練データをpandasを使ってpythonに入力．
traindata = pd.read_csv(train_filename).values x_data = np.array([row[1:] for row in traindata]).astype(np.float32) y_data = np.array([row[0] for row in traindata]).astype(np.int32)
モデルの定義．
model = Classifier(MyChain()) optimizer = optimizers.SGD() optimizer.use_cleargrads() optimizer.setup(model)
学習，バッチサイズは5として，20回回す．（ここはTrainerを使った方が良いのかな）
batchsize = 5 datasize = len(x_data) for epoch in range(20): print "epoch %d" % (epoch) indexes = np.random.permutation(datasize) for i in range(0,datasize,batchsize): x = Variable(x_data[i:i+batchsize]) t = Variable(y_data[i:i+batchsize]) optimizer.update(model, x, t)
学習したモデルで提出用ファイルを出力．
def submit(model): f = open('submit.csv','w') f.write("ImageId,Label\n") testdata = pd.read_csv("./csv/test.csv").values x_data = np.array(testdata).astype(np.float32) datasize = len(x_data) for i in range(datasize): x = Variable(x_data[i:i+1], volatile='on') y = np.argmax(model.predictor(x).data[:]) f.write("%d,%d\n" % (i+1,y)) f.close()
提出
訓練データを全て使わなくても88%とそこそこな値が出て満足しています．
感想
色々なサイトを見た結果公式ドキュメントが一番わかりやすくまとまっているのかなと思いました．
サンプルを見ないでやると割りとハマりポイントがあってちゃんと動いた時に達成感があったので，こんな感じで勉強を進めて行きたいです．
実装に参照した本とリンク
- Chainerによる実践深層学習 Amazon CAPTCHA
- Introduction to Chainer（公式）Introduction to Chainer — Chainer 1.23.0 documentation
2016年振り返りと2017年目標
2017年に入りもう一月経ってしまった。
競技プログラミング
レート変動
- SRM 1165 -> 1373
- CodeForces 1702 -> 1702(不参加）
- AtCoder ? -> 1574
topcoderでようやくDiv1に入れて嬉しい！
週に1問ぐらい解く習慣を付けていきたい。
ACM-ICPC 2016 国内予選 D : ダルマ落とし
問題
配列の隣り合った2つ要素の差が1以下であれば，その2つ要素を消すことができる．
この操作を繰り返す時，最適に消していくと，最大何個要素を消せるか．
例：{1,3,2,1}が与えられたとき
{1,3,2,1} -> {1,1} -> {} ⇐4個消せる
{1,3,2,1} -> {1,3} ⇐先に右端の要素の2,1を消すと，2個しか消せない
方針
dp[ l ][ r ] := [ l , r ]の区間で最大いくつ取り出せるか
とすると，
ある幅dに対して，
① {1,2,3,4} -> {x,x,o,o}
dp[ l ][ l + d ]より小さい区間のdpが求まっているとすると，
dp[ l ][ l + d ] = max{ dp[ l ][ k ] + dp[ k + 1 ][ l + d ] }
となりそう．
② {1,3,3,1} -> {1,x,x,1} -> {o,x,x,o}
dp[ l ][ l + d ] = d + 1 （oの間のxの要素が全部消えてる）
かつ
abs( x[ l - 1] - x[ l + d + 1] ) <= 1 （端にあるoの要素の差が1以下）
であれば，
dp[ l - 1 ][ l + d + 1 ] = d + 1 + 2 （間の要素数+2）
となりそう．
良い感じにループを回す．
コード
#include <bits/stdc++.h> using namespace std; bool solve(){ int n; cin >> n; if(n == 0)return false; vector<int> x(n); for(int i=0;i<n;i++) cin >> x[i]; vector<vector<int>> dp(n+1,vector<int>(n+1)); for(int i=0;i<n-1;i++){ if( abs( x[i] - x[i+1] ) <= 1 ) dp[i][i+1] = 2; } for(int d=1;d<n;d++){ for(int l=0;l<n;l++){ if( l + d >= n )continue; for(int r=l;r<l+d;r++){ dp[l][l+d] = max(dp[l][l+d], dp[l][r] + dp[r+1][l+d]); } if( l - 1 >= 0 && l + d + 1 < n){ if( dp[l][l+d] == d + 1 && abs( x[l-1] - x[l+d+1] ) <= 1 ){ dp[l-1][l+d+1] = max(dp[l-1][l+d+1] ,dp[l][l+d] + 2); } } } } cout << dp[0][n-1] << endl; return true; } int main(void){ while(solve()){} return 0; }
半年放置したらなんとか解けた．
ICPC国内予選 参加記 2016
ICPC国内予選に参加しました。
順位は、95位でした。
今年はあんまり参加する気はなかったのですが、ICPCが近づくとやっぱり出たくなりました。
チームメンバー集めは、4月ぐらいから始めて、5月頃メンバーが決まって、それから週1ぐらいで過去問を解いて練習。
僕以外は初参加だったのですが、A,B,Cまでは一人一問比較的スムーズに解くことができたので、
一応、最低限の目標は達成できたかなと思います。
その後は、D問題に絞ってウンウン唸っているだけでした。
区間DPだろうなとは思ったのですが、そこから何も思いつきませんでした。
完全に過去の問題の復習不足で、後悔しかないですね。
SRMで出てた括弧の問題とかちゃんと解いとけばなぁとかずっと考えていました。
僕は来年が最後なので、来年はもっと早くメンバーを集めて、ちゃんと復習して、国内予選を突破したいです。
