読者です 読者をやめる 読者になる 読者になる

utsubo’s blog

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

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

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

ICPC国内予選 参加記

ICPC国内予選に参加しました。
順位は、95位でした。

今年はあんまり参加する気はなかったのですが、ICPCが近づくとやっぱり出たくなりました。
チームメンバー集めは、4月ぐらいから始めて、5月頃メンバーが決まって、それから週1ぐらいで過去問を解いて練習。

僕以外は初参加だったのですが、A,B,Cまでは一人一問比較的スムーズに解くことができたので、
一応、最低限の目標は達成できたかなと思います。

その後は、D問題に絞ってウンウン唸っているだけでした。
区間DPだろうなとは思ったのですが、そこから何も思いつきませんでした。
完全に過去の問題の復習不足で、後悔しかないですね。
SRMで出てた括弧の問題とかちゃんと解いとけばなぁとかずっと考えていました。

僕は来年が最後なので、来年はもっと早くメンバーを集めて、ちゃんと復習して、国内予選を突破したいです。

応用情報技術者試験 合格しました

合格しました

応用情報技術者試験についてはリンク参照.
IPA 独立行政法人 情報処理推進機構:制度の概要:応用情報技術者試験
得点は,午前・午後共に8割程度で,割りと余裕がありました.

午前

自分は,情報系の学生であるものの,授業でやった基本的な部分ですら,覚えてたり,覚えてなかったりしました.
ということで,基礎を固めるため,適当な対策テキストを借りて,半分ぐらい読みました.

その後,面倒臭くなり試験3日前ぐらいまで放置.
本を読む気力がなかったので,そこからはずっと過去問道場で過去問を解いてました.
応用情報技術者過去問道場|応用情報技術者試験.com

午前試験は,過去問から結構出てる感じがあり,最悪それだけやってれば受かりそうだと思いました.

午後

対策せず.
全体を読んで,簡単な問題を探して解きました.
これ国語の問題でしょみたいなのもあったので,そんなにガッツリ対策はしなくて平気そうです.
あと,時間的にはかなり余裕があり,そこで焦る必要はないと感じました.

感想

数年振りに資格試験的なものを受けたので,だいぶ緊張しました.
twitterで受験費をつぶやき,固定ツイートにしておくと,モチベが上がるのでオススメです.
次はネスペを目指します.

ビームサーチの練習用にパズドラAIを組んだ

大学の先輩がパズドラのコンボのAIの話をしていて,そういえば組んだことがないなぁと思い立ち.

目的

パズドラのパズルにおいて,コンボ数をできるだけ大きくするようなパズルのスライドのさせ方を出力する.
今回は,ダメージ等については考慮しません.

方針

ビームサーチを使います.”ビームサーチ”で検索すれば良い記事が沢山出てくると思うので,詳細は割愛.

ビームサーチは下のをそのまま実装しました.

状態は,{”パズルの盤面の状態”,”今動かしている部分の座標”,”何手動かしたか”}とし,パズルを1手動かした状態を遷移状態としています(上下左右で4つの状態に遷移).
コンボ数をそのまま状態の評価値として扱います.

初期状態は,パズルをスライドさせるスタートの位置を変えたもの,計30個に設定.
また,ビーム幅は40000,最大ターンは12として実行します.

ZobristHashで盤面のハッシュ値を生成し,同じ盤面を2回探索しないようにしています(出来てるかは謎).


deleteしてないからヤバそうなC++コード
https://ideone.com/MbxQOR

まとめ

サクサクっと作った割には5,6コンボ出るので,凄いと思いました.
適当に作ったので(言い訳),全てにおいて杜撰なコードになっています.

記事の書き始めた時はもっとしっかり書こうと思っていたんだけど,途中で面倒くさくなってしまった.