ビットコインパチンコ
取引所開くとまたやってしまいそうなのでもう開かないことにする。
これでいいモニターでも買おう。
2021年の目標
目標
- 年末まで今年の目標を覚えておく。
- 肝臓の数値をA判定にする。
- ダイエットする。70kg以下にする。
- 確定申告を忘れない。
- 自宅を最高の仕事環境にする。投資を惜しまない。
- ブログ書く。最低月2投稿。
高専プロコン2015競技部門練習場を作りました
つくりました
4日ぐらいがりがり作りました。
さくらインターネットのレンタルサーバ(ライトプラン)でpythonのcgiが動かせると聞いて、何か作ってみたいなと思ってたんですが、そういえば今年の高専プロコンの練習場ないなと思い、よし作ってやろうと思い立ってから１週間ほどで完成しました。
認証トークンがソースにベタ書きされているところがあったり、使っているライブラリのライセンスを整理したりしたらソース公開するかもしれません。
大変だったところとか
ライトプランで作ったんですが、sshできないのが致命的。ローカルで開発していざ乗っけてみると500ばっかり。
twitter連携しよう！と思い立ったがoauth系のライブラリをインストールすることすらできず。virtualenvもsshできないから作りにくいしで、結局自前で書いたんですがめんどくさかった。１日かかった。勉強にはなりました。
pythonのbottleというwebフレームワークはすごく軽量で、cgiで動かすことも想定されているのでわりとさっくり動きました。
ただprintデバッグしていたところがcgiで動かすとレスポンスヘッダに混入してしまって、Apacheに怒られて500になってはまるとか。
さくらのレンタルサーバのapacheではmod_deflateが使えないらしく自分でgzipしてあげないといけない(対応してくれー)。
作って乗っけてみるまでわからなかったんですが、cgi遅いですね(毎回全部実行されるので当然か)。静的ページを生成しておいてそれを返すだけにしてあげればよかった。
解答のシミュレーションにはC++で書いたコードがあったのでそれを使いまわしたんですが、C++のソースコードをftpでサーバに配置し、これをcgiからコンパイルしてバイナリを作るということをしました。
サーバに乗っているgccが4.2とか化石みたいなコンパイラで、-std=c++11というオプションすら無くて絶望しかけた。
clangが入っていた(これも古い)のでこちらを使いました。gccに比べたらrange-based-forも使えたし。std::moveがなかったりで一部修正したらちゃんとコンパイルできました。
解答のビジュアライザとしてcolunさんの汎用ビジュアライザを使わせてもらいました。すごく便利です。僕の中でマラソンマッチ必携のツールですね。 java版ばかり使っていましたが、js版のほうが圧倒的に早いしリロードもブラウザでリロードするだけで済むのでこりゃ便利だ。
AOJ0091
問題:Blur
解法:DFS
適当にやると計算量とメモリが爆発しそうなので、無駄に枝をはやさないように気をつける。
左上から右下に向かう落としかたに限定して、行単位で全部消えない場合はそこで探索をうちやめる。
盤面のコピーはとらず１つの盤面を使い回す（再帰だとこれが簡単にできて良い）。
答えは順不同かつ１つ見つければ良いため、解が見つかった時点で答えを出力しながら戻れば良い。
再帰苦手だったが、時間かければこれくらいは自力で書けるようになった。
#include<iostream> #include<vector> #include<map> using namespace std; #define rep(i,n) for(int i=0; i<n; ++i) const int N = 10; int c,n; vector<vector<int> > F; int SS[] = {3, 3, 5}; int SC[] = {5, 9, 13}; int S[3][5][5] = { { {0, 1, 0, 0, 0}, {1, 1, 1, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {1, 1, 1, 0, 0}, {1, 1, 1, 0, 0}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} }, { {0, 0, 1, 0, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 1, 1, 1, 0}, {0, 0, 1, 0, 0} } }; bool is_inside(int x, int y){ return x >= 0 && y>= 0 && x<N && y<N; } bool fall(int x, int y, int size){ if(!(is_inside(x,y) and is_inside(x+SS[size]-1, y+SS[size]-1)))return false; rep(i,SS[size])rep(j,SS[size])if(!(F[y+i][x+j] >= S[size][i][j]))return false; rep(i,SS[size])rep(j,SS[size])F[y+i][x+j] -= S[size][i][j]; c -= SC[size]; return true; } void undo(int x, int y, int size){ rep(i,SS[size])rep(j,SS[size])F[y+i][x+j] += S[size][i][j]; c += SC[size]; } bool hasline(int y){ rep(x,N)if(F[y][x] >= 1)return true; return false; } bool is_clear(){ return c==0; } bool dfs(int x, int y, int depth){ if(is_clear()) return depth == 0; if(depth <=0)return false; if(!is_inside(0, y))return false; if(!hasline(y))return dfs(0, y+1, depth); for(int i=x; i<N; ++i)rep(s,3){ if(fall(i, y, s)){ if(dfs(i, y, depth-1)){ cout << i+SS[s]/2 << " " << y+SS[s]/2 << " " << s+1 << endl; return true; } undo(i, y, s); } } return false; } int main(){ cin >> n; F = vector<vector<int> >(N, vector<int>(N)); rep(i,N)rep(j,N){ cin >> F[i][j]; c += F[i][j]; } dfs(0,0,n); return 0; }
CODEVS2.1予選に参加しました。
CODEVS2.1に参加しました。予選で何をやったかについて書いて行きたいと思います。
[予選開始]
ルールを、消えたブロックの周囲の邪魔ブロックが消えることと、点数計算式の計算方法の部分だけ読みました。参加登録も行いました。
CODEVS2.0が非常におもしろかったし、今回は社会人も決勝に出れるという事もあり、やりたいなという意識だけはあったのですが、実際に行動に移すことができませんでした。
平日は仕事で11時以降に帰宅することが多かったので、そこからコーディングする気力というか、まだ自分の中に火がついていない感じでした。
[予選終了3週間前]
ざっくりと方針を考え始めました。この時点ではtekさんが1位を独占していた頃だと思います。
コーディングする時間は無くとも、点数計算式だけを頼りに間違っていない方向の方針を立てることはできます。
具体的な点数計算式は公式ルールを見て頂くとして、大量のブロックの同時消し爆弾が大前提にあって、そこから線形に連鎖数とFc(それ以前の中起爆回数)が掛かる感じでした。
方針としては、
1.Fcを出来るだけ溜める
2.爆弾(大量の同時消しができる形)を作る
3.連鎖を作る
4.起爆する
という方針が高得点を狙えそう。2と3は作りやすい順番でいこう。
と考えました。
2.0予選で不定形連鎖よりも定形連鎖（システム連鎖）の方がつよかったこともあり、今回もシステム爆弾が強いに決まっているだろうと予想していました。
とりあえずSmallに向けてコーディングを開始
2.0のコードを少し修正して邪魔ブロックの消しに対応、点数計算式を修正、ランダムに落とすAIをつくってスコアが完全一致することを確認しました。
幅優先探索を使ってFcを溜めるAI(以後チャージAI)を作ったけれどFcが１増える前にノードが爆発してしまいうまく行きませんでした。
幅優先探索で、深さが増えるたびにノード数が一定以下になるまで減らす（ビームサーチ?)を初めて実装してみて、汚いコードになったけどそれっぽく動いてくれました。
システム爆弾をつくるための前準備として、とりあえず決め打ちした形に落とすAIを作りました。smallで100を超える同時消しが出来てテンション上がりました。
gitでソースコードを管理しようとして、
git init
git add codevs21/* (あ、不要なファイル追加しちゃった)
git reset --hard
とやって、ソースコードが全消滅しました。皆さん気をつけましょう。
VisualStudioで開いていたファイルや、2.0のコードの再利用で大体が復元出来ましたが、システム爆弾の部分は全て消えてしまいました。
[予選終了2週間前]
tekさんの点数を逆算して、方針を盗んでやろうと考えましたが、どう考えても数十倍足りませんでした。勝てる気がしない。
なんかどこかで見覚えのあるHNの人が1位をとっている。なんなんだこのおじいさんは。twitterみたら「ちょっとやってみた」とか言っている。頭おかしい。勝てる気がしない。
システム爆弾を作り直すの結構だるかったので、チャージAIをコピペして評価関数だけ書き換えて爆弾を作るAIを作りました。
数十ターンでシステム爆弾を上回る同時消しが生成されてテンションが上がりました。(システム爆弾とは何だったのか)
チャージAIをまたコピペして評価関数を変えて連鎖AIを作りました。
結局以下の3つのAIが出来ました。
・Fcの値をできるだけ溜める(チャージAI)
・連鎖尾爆弾を作る(ボムAI)
・連鎖を作る(チェインAI)
同時消しの小さい連鎖の連鎖尾として大きい同時消し爆弾を爆発させたいのですが、どうやったらうまく作れるのか分からず試行錯誤をしました。
結局、発火点を中央-1の列に固定して、フィールドの右半分で爆弾を作った後、発火点を一番左の列に固定して、左半分でとにかくスコアが大きくなるように探索する方針がうまく行きました。
ある程度大きな爆弾を作ってしまい、あとは連鎖でしかスコアが伸びにくい状況を作った上で探索すれば自然と連鎖が出来てくれます。
探索幅の制限を広くして、1回1時間程度のAIを走らせてみたところ、Smallで7e12点位(Small 当時6位)が出て、近いところまで来たという感じがしました。
ビームサーチの書き方がとても汚かったので、2.0のShoheiさんのコード(Githubに上がってる奴)を参考にさせて頂いて3つのAIを書き直しました。再帰で書くとか目から鱗でした（もしかしてとても基本的な書き方)。
AIの中のあらゆるパラメータを抜き出して定数化し、設定ファイルとして読み込めるようにしました。
余っていたノートPCがあったので、会社で覚えたJenkinsCIをインストールし、のJobでパラメータ付きビルドとしてAIのパラメータを選択できるようにして、仕事中や飲み会の途中にパラメータとスコアの関係を調べていました。
こんな感じでiPhoneからポチポチできます。
少しだけパラメータ変えて基本的に同じプログラムをMedium、Largeで走らせて6位に入りました。
[予選終了1週間前]
GOLDランクに入ってしまったからか新しい方針を考える思考がなくなってしまい、ずっとパラメータ変えて時間を浪費していました。
探索幅を広げて時間かければしっかりスコアが伸びていくのが確認できたので、シミュレータを高速化しました。
windowsで使いやすいプロファイラを知らなかったので、会社のMacBookAirでビルド出来る環境を作ってTimeProfilerを走らせました。すごくわかりやすいですこれ半端ないです。
想像通り連鎖の消去判定が実行時間の7割を占めていたので、ここを中心に高速化を行いました。
大体やったことは
・2.0のkusanoさんのコード(Githubに上がってる奴)のシミュレータを参考にして、STLを排除してテンプレートでシミュレータ全体を書き直し
・再帰で実装していた消去処理もしゃくとり法の定数回ループに置き換え
・落下したブロックのバウンディングボックスの範囲だけ対してだけ消去判定を行うように書き換え
ぐらいです。かなり早くなりました。
[予選終了直前]
パラメータ調整や軽い評価で枝刈りの範囲を広げたりしつつ何度も実行していました。
高速化の甲斐もあってか、4位に入っていてさすがに安全圏。欲がでてきて、
「僕は...あの人(3位のおじいさん)に...勝ちたい!!」
とか考えながらMedium抜いた瞬間おじいさんもスコア上げてきて全然勝てませんでした。
[予選終了当日]
4位で終了。と思ったら
給料日を迎えた課金勢のkusanoさんが突如現れ、気づいたら5位になっていました。
[工夫した点]
これをやっていなかったらGOLDランクに入れなかったなという点
・点数の概算
パラメータ調整の際、実際に何時間も走らせずに点数を概算することによって時間を節約し、反復回数を増やしました。
例えば、Fcの値は大体100-120位まで溜めるとしてあるので、ゲーム開始直後に(Fc=0の時に)爆弾->起爆のAIを走らせて、それを100-120倍すれば、大体Fcを溜める時間を省略して点数を概算する事ができます。
このように短い時間で強くなっているか測る判断基準を作ることが非常に大事です。
あと、点数計算式から、上位陣が何やってるのかを予想する事は非常に大事です。明らかに足りない場合は何か見落としている点があります。
・Git
バージョン管理システムGitです。
高速化用にブランチ切って、詰まったら一旦止めて元のブランチに戻ってAIの考察とか、
Large用にブランチ切って、ハードコードでひたすら調整し実行。そのまま何点取ったかをタグ打ち
のような使い方が出来てホント便利です。学生時代の僕に教えてあげたいです。
[おまけ]
予選動画 Small
SRM579Div2
Easy:PrimalUnlicensedCreatures
クリーチャーが何体か居て、それぞれのレベルがvector
自分の初期レベルが与えられる。
自分より低いレベルのクリーチャーを倒すことができ、倒したクリーチャーのレベル/2(切り捨て)だけ自分のレベルがUPする。
最大何体のクリーチャーを倒すことができるか。
解法:
弱い奴から順番に倒す。
class PrimalUnlicensedCreatures { public: int maxWins(int lv, vector <int> v) { int res = 0; sort(v.begin(),v.end()); rep(i,v.size()){ if( lv > v[i] ){ lv += v[i]/2; res++; } } return res; } };
Medium:UndoHistory
変なテキストエディタを使って与えられた文字列を入力する時の、最小プレス数を求める。
・入力した文字はバッファに格納される。(1文字あたり1プレス)
・Enterキーを押すとバッファに入っている文字列がアウトプットされる。この時別にバッファはクリアされない。(1回1プレス)
・バッファの履歴が残っており、UNDOで以前の状態のバッファに復元出来る。(1UNDOにつき2プレス)
解法:
UNDOは新しい行の行頭でしか使っても意味がないから、改行する度に、バッファの続きから打つ場合・UNDOを使う場合 の2通りに点数をつける。
点数 = 節約出来る文字数 - プレス数
点数が高い方でGreedyに処理していく。
バッファの履歴は全パターン取っておかなくても、そこまでに入力した行を覚えておけば良いらしい。
class UndoHistory { public: int minPresses(vector <string> lines) { int res=0; set<string> undo; string buffer; rep(i,lines.size()){ string line = lines[i]; int score_buffer = -1*(1<<29); int score_undo = -2; int start_pos = 0; if(buffer == "" || line.find(buffer) == 0){ score_buffer = buffer.size(); } rep(j,line.size()){ string s = line.substr(0,j+1); if(undo.find(s) != undo.end()){ if(score_undo < -2+j+1){ score_undo = -2+j+1; start_pos = j+1; } } } string restline; if(score_buffer > score_undo){ restline = line.substr(buffer.size()); }else{ res += 2; restline = line.substr(start_pos); buffer = line.substr(0, start_pos); } res += restline.size(); rep(j, restline.size()){ undo.insert(buffer + restline.substr(0,j+1)); } res++; buffer = line; } return res; } };
Hard:MarblePositioning
マーブルが何個か与えられ、それらを横一列に並べた時の距離の最小値を求める問題。
解法:
最大8個なので全通り試しても40320パターンくらいしかないので全通り試す。
class MarblePositioning { public: double dist(double r1, double r2){ double a = r1+r2; double b = r1-r2; return sqrt(a*a - b*b); } double totalWidth(vector <int> R){ double res=1e20; sort(R.begin(),R.end()); do{ vector<double> P(R.size()); rep(i,R.size()){ rep(j,i){ P[i] = max(P[i], P[j] + dist(R[j], R[i])); } } res = min(res, P.back()); }while(next_permutation(R.begin(),R.end())); return res; } };
TCO13 Round1B
Easy:
２人組みを作る。１組の能力は２人の能力の合計。
一人ひとりの能力の配列が与えられるので、一番能力が高いペアと低いペアとの能力差の最小値を求めよ。
一番能力が高い奴は一番能力が低い奴とペアを組むべき。
ソートしてそれぞれに求めて最大値-最小値が答え。
#include <vector> #include <algorithm> #include <iostream> #include <string> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) class EllysPairs { public: int getDifference(vector <int> in) { sort(in.begin(),in.end()); int n=in.size(); int _min = 1<<30; int _max = 0; rep(i,n/2){ int k = in[n-1-i] + in[i]; _min = min(_min,k); _max = max(_max,k); } return( _max - _min ); } };
Mid:
vector
'X'を全て取り除きたい。
1手につき、連続したR行又はC列に含まれている'X'を取り除く事ができる。
最小何手で'X'を全て取り除けるかを求めよ。
ある'X'は最終的に消されなければならないので、今の盤面の中の'X'1つに注目し、それを取り除くようなすべての行および列の選び方を子ノードにするようにBFS。
#include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) class EllysFigurines { public: int getMoves(vector <string> board, int R, int C) { int w = board[0].size(); int h = board.size(); queue<pair<int,vector<string> > > Q; Q.push(make_pair(0, board)); while(true){ int step = Q.front().first; vector<string> F = Q.front().second; Q.pop(); bool ok = true; int r,c; rep(i,h){ rep(j,w){ if(F[i][j] == 'X'){ r = i; c = j; ok = false; } } } if(ok) return step; rep(dx,C){ vector<string> f = F; for(int j=c-dx; j<c-dx+C; ++j){ if(j<0 || j>=w)continue; rep(i,h) f[i][j] = '.'; } Q.push(make_pair(step+1, f)); } rep(dy,R){ vector<string> f = F; for(int i=r-dy; i<r-dy+R; ++i){ if(i<0 || i>=h)continue; rep(j,w) f[i][j] = '.'; } Q.push(make_pair(step+1, f)); } } } };
