utsubo’s blog

競技プログラミングとか.

ICPC国内予選 2017 G 迷宮を一周

問題

迷路がN*Mのグリッドで与えられる.('.'が通路,'#'は通行不可)
グリッド上の(0,0)地点をスタートとする.
スタート以外の3隅の宝物を回収してスタート地点に戻ってきたい.
しかし,一度通った通路は通れないとする.
https://storage.googleapis.com/icpcsec/icpc2017-domestic/contest/all_ja.html#section_G

考察

まず,宝物は右回りまたは左回りで回収する必要がある.
右下隅の宝物を最初に取ると,右上隅から左下隅への経路が消えるため.

できるだけ,端に沿ってに移動するのが最適そう(証明は知らないっ!)
下図のように塗って,移動経路があればOKみたいなことをした

各端について(上,右,下,左端の通路)
・端の'.'は通行可能
・”端”の'#'と8近傍で連結している'#'を列挙
・列挙した'#'の8近傍で'.'の通路は通行可能


f:id:utsubo_21:20170722102935p:plain

感想

本番では思いついていたのに,組みきれなかった.
悲しい(´・_・`)

#include <bits/stdc++.h>
using namespace std;

int N,M;
bool dijkstra(vector<string>& maze,char number,int sx,int sy,int gx,int gy){

  priority_queue<pair<int,pair<int,int>>> pq;
  vector<vector<int>> dists(N,vector<int>(M,1e9));
  dists[sy][sx] = 0;
  pq.push(make_pair( 0, make_pair(sx,sy)));  
  vector<int> dx = {0,-1,0,1};
  vector<int> dy = {-1,0,1,0};
  maze[gy][gx] = number;

  while(!pq.empty()){
    pair<int,int> p;
    int cost;
    tie(cost,p) = pq.top();pq.pop();
    int x,y;
    tie(x,y) = p;
    if(x == gx && y == gy)return true;
    for(int i=0;i<4;i++){
      int nx = x + dx[i],ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= M || ny >= N)continue;
      if(maze[ny][nx] != number)continue;
      int newcost = -cost + 1;
      if(newcost >= dists[ny][nx])continue;
      dists[ny][nx] = newcost;
      pq.push(make_pair( -newcost, make_pair(nx,ny)));
    }
  }
  return false;
}

void fillgrid(vector<string>& maze,char number,int sx,int sy){
  queue<pair<int,int>> q;
  if(number == '1'){
    for(int i=0;i<M;i++){
      if(maze[0][i] == '#')
        q.push(make_pair(i,0));
      else if(maze[0][i] == '.')
        maze[0][i] = number;
    }
  }else if(number == '2'){
    for(int i=0;i<N;i++){
      if(maze[i][M-1] == '#')
        q.push(make_pair(M-1,i));
      else if(maze[i][M-1] == '.')
        maze[i][M-1] = number;
    }
  }else if(number == '3'){
    for(int i=0;i<M;i++){
      if(maze[N-1][i] == '#')
        q.push(make_pair(i,N-1));
      else if(maze[N-1][i] == '.')
        maze[N-1][i] = number;
    }
  }else{
    for(int i=0;i<N;i++){
      if(maze[i][0] == '#')
        q.push(make_pair(0,i));
      else if(maze[i][0] == '.')
        maze[i][0] = number;
    }
  }
  vector<vector<int>> used(N,vector<int>(M,0));
  int dx[] = {0,1,-1,-1,1,0,1,-1};
  int dy[] = {-1,-1,-1,0,0,1,1,1};
  while(!q.empty()){
    int x,y;
    tie(x,y) = q.front();q.pop();
    used[y][x] = 1;
    for(int i=0;i<8;i++){
      int nx = x + dx[i],ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= M || ny >= N)continue;
      if(used[ny][nx])continue;
      if(maze[ny][nx] == '.'){
        maze[ny][nx] = number;
      }else if(maze[ny][nx] == '#'){
        used[ny][nx] = 1;
        q.push(make_pair(nx,ny));
      }
    }
  }
}

bool solve(){
  cin >> N >> M;
  if(N+M == 0)return false;
  vector<string> maze(N);
  for(int i=0;i<N;i++){
    cin >> maze[i];
  }
  int vsx[] = {0,M-1,M-1,0,0};
  int vsy[] = {0,0,N-1,N-1,0};
  for(int i=0;i<4;i++){
    int sx = vsx[i],sy = vsy[i];
    int gx = vsx[i+1],gy = vsy[i+1];
    fillgrid(maze,'1'+i,sx,sy);
    // for(int i=0;i<N;i++)cerr << maze[i] << endl;

    if(!dijkstra(maze,'1'+i,sx,sy,gx,gy)){
      cout << "NO" << endl;
      return true;
    }
  }
  cout << "YES" << endl;
  return true;
}

int main(void) {
  while(solve()){}
  return 0;
}

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

https://ideone.com/j1M8ea

*1:去年も同じようなことを言っていましたが今年は本当に

モナコインのマイニングソフトをDockerで動かす

モナコイン

モナコインは,ブロックチェーン利用した仮想通貨で,同種で有名なものにはビットコインがあります.
詳しい説明は省きます.
モナーコインプロジェクト

概要

単独で採掘するほどのリソースがないので,皆で掘って報酬を分割するマイニングプールを利用します.
今回は取り敢えず,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 ⇒ ワーカーのパスワード


f:id:utsubo_21:20170614181036p:plain
良い感じのログが確認できたら成功です.
少しすると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. まだ塗られていないマスを隣接マスで一番多い色で塗る.
  4. 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()

提出

f:id:utsubo_21:20170421161221p:plain
訓練データを全て使わなくても88%とそこそこな値が出て満足しています.

感想

色々なサイトを見た結果公式ドキュメントが一番わかりやすくまとまっているのかなと思いました.
サンプルを見ないでやると割りとハマりポイントがあってちゃんと動いた時に達成感があったので,こんな感じで勉強を進めて行きたいです.

実装に参照した本とリンク

2016年振り返りと2017年目標

2017年に入りもう一月経ってしまった。

競技プログラミング

レート変動

topcoderでようやくDiv1に入れて嬉しい!
週に1問ぐらい解く習慣を付けていきたい。

英語

目標は達成できなかったが、TOEICの点数は上がった。
洋画を観ていたので、その効果が出たのかも(謎)

今年こそは730点以上取ります。

その他

何か作る目標を立てていたが、大きいものは作れなかった。

  • マイクロマウス、頑張って今年の大会に出る(かも)
  • 機械学習、ある程度勉強してKaggleとかに出る
  • コミケに何か書いて出す

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個しか消せない

制約

配列の長さ <= 300
1 <= 要素の値 <= 1000

Daruma Otoshi | Aizu Online Judge

方針

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

半年放置したらなんとか解けた.