utsubo’s blog

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

2017年振り返りと2018年の目標

はじめに

最近,何も書いていないなと思ったらもう年末だったので,振り返りでもしようと思います.

2017年の目標と達成度

年始にふんわり立てていた目標と達成度.

  • 競プロ:週に1問 → 問題を解くどころかコンテストにもほぼ出ていない.
  • 英語:TOEIC730点 → TOEICを受けていない
  • その他:機械学習コミケに出す → 機械学習◯、コミケ

2017年の感想

  • 割りと講義とかバイトとか遊び等で忙しくて,思うように動けなかった.
    • 気づいたら年末,年々年を取るのが早くなる
  • インターンにいくつか参加するとともに,比較的暇な学部3,4年生の内にもっと行くべきだったと思った.
    • 修士だと就活を視野に入れてインターンを選ばないといけないし,落ちた時に2回目のチャレンジができないため.
  • 学部生にやってきたことを使って,アウトプットをしていたなぁという感じ.
  • やりたいことを口にしていると協力してくれる人が結構いる.

2018年の目標

1~4月:研究と機械学習の勉強をメインに.

  • 機械学習は何かしらの成果物をブログに上げる.
  • 研究は海外学会発表に行く

5~8月:英語ガチ勢になりたい(夏に海外インターンとか行ってみたいので)

9~12月:研究のまとめとやりたい勉強.

Googleカレンダーを見ながら振り返り

1月

適当な学会に出す論文を書いていた.
あと,卒論も書いてたが,ほとんど前に書いたものを再利用したので,あんまやった気がしない.
卒論の発表にほとんど練習しないで望んだら,ぐだぐだ過ぎて怒られるかと思ったが,大丈夫だった.

そういえば,1~3月ぐらいまで36.8~37.5ぐらいの微熱が続いて辛かった.(医者に数回行ったが原因不明,恐らく副鼻腔炎
それとは別に顎のあたりにしこりがあって,微熱も続くし,死ぬんじゃないかと思った.(実際は,微熱とは関係なくガマ腫というらしい)

2月

毎週遊びの予定が入っているので,遊び呆けていた模様.(微熱が治らなかった原因の1つ)

大阪にも行った.夜行バス+微熱で死にそうだった.

3月

1月に出した論文に一応査読が付いていたので,直し.

先生のコネでF研究所で3週間のインターンシップ
内容は,詳しくはNDAで言えないが,仮想ネットワークの可視化してた.
知識0で行ったら,初日の説明会で知らない単語が無限に出てきてめちゃ焦ったが,割りとなんとかなった.まあまあ楽しかった.

3月末に卒業旅行で初の広島旅行に行った.
外国の方に「お前,日本人なのに広島も行ってないのかよ」みたいなこと言われたくなかったので,僕の希望で広島へ.
夜行バス+微熱で死にそうだった.

4月

何かをしてた形跡がない.3月まで疲れを癒やす1ヶ月.

5月

1月に投稿した奴のポスター発表のために北九州に行った(初めて本州以外の県に行った)
Yandex Algorithmの参加賞でTシャツ貰ってHappy:)

6~7月

インターンに数社落ちて悲しみにくれていた.
面接で落ちるの最高に精神に来る.

8月

コミケに初サークル参加.
友達4人と技術系記事の載った薄い本を書いた.僕はビットコインの仕組みについて書いてた(我ながら先見の明があると思う).
印刷所とか設営とか初めてなことだらけで大変だったけど,刷った30部が完売した時は感動だった.
冬コミも申し込んだけど,抽選漏れでした,残念!

9月

某社でインターン.やってきたことを評価してくれるし,かなり楽しかった.
初めて劇を見に行ったが,面白かった.

10~11月

アルバイトを新しく始めたら忙しくなってしまった.

DISCO presents Discovery Code Contestの本戦に出れた.
Ponanza開発者とプロ棋士の対談を聞きながら,もっと頑張らないといけないなと思っていた.

12月

学内でハッカソンを運営してた.小成功ぐらい.今後,大きくしていきたい.

Q-Learningで迷路を解く

はじめに

強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~

↑これを読みながら強化学習の基礎と雰囲気を学んでいるのですが,
読んでるだけで飽きてきたので,実際に実装してみました.
chainerRLとか使えば簡単にできるのだろうなと思いつつ,初めてなのでC++で適当に書きました.

Q-Learningとは?

詳しくは本を読むか,色々な人が解説記事を上げているのでそちらに.
ゼロからDeepまで学ぶ強化学習 - Qiita
強化学習で迷路を探索する - Qiita

方針

報酬 R(s_t,a_t)をゴールしたとき1,壁に移動したとき-1,その他0で設定.
探索する時の行動選択にε-greedyを用いていたのですが,上手く行かなかったため,
UCB1アルゴリズム*1を使って探索しました.

UCB1については下記リンク参照.
モンテカルロで二人ゲーム - ustimawのブログ

実装

実行環境
概要

競プロ形式で迷路を標準入力から読み込み.
高さH,幅Wの次の行から,各セルの情報が空白区切りで与えられる.(0:通路,1:壁,2:スタート,3:ゴール)

エピソード数(num_episodes=10000)の学習の後,1回テストが実行されます.

実行結果

テスト実行時の動画です.'x'が現在地を表しています.

Q-Learningの更新式についてメモ

説明できるほど理解できてないのですが一応.(中途半端かつ正確ではないです.)
状態 s_tの時行動 a_tを取った場合の価値関数 Q(s_t,a_t)がある.
 Q(s_t, a_t)を展開すると,期待報酬関数 Rと次ステップの価値関数 Q(s_{t+1},a_{t+1})の漸化式っぽくかける.

Q(s_t,a_t) = \sum γ^tR(s_t,a_t) = R(s_t,a_t) + γQ(s_{t+1},a_{t+1})


これを,Rイコールの式にすると,

R(s_t,a_t) = Q(s_t,a_t) - γQ(s_{t+1},a_{t+1})
となる.


報酬関数 R(s_t, a_t)を近似する関数 \hat{R}(s_t,a_t)と実際の報酬 r_tは,大体一致して欲しい.
そこで,誤差 \Delta R(s_t, a_t) \equiv \frac{1}{2} (r_t - \hat{R}(s_t,a_t))^2と定義し,これを最小化する.


最小化するように Q(s,a)を更新するために,TD法が提案されていて,これは大体勾配法.
TD法では, d = \frac{\partial \Delta R}{\partial \hat{Q}}として, \hat{Q}(s_t,a_t) = \hat{Q}(s_t,a_t) - \alpha dで更新.
 \alphaは学習率.


で, dは下式のように求まるので,
 d = \frac{\partial \Delta R}{\partial \hat{Q}} \propto -r + R(s,a)
近似価値関数は次の式で更新するといい感じになりそう.
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \hat{Q}(s_{t+1},a_{t+1}))

(正確にはここまでのQには肩に政策関数 \pi が乗ります.)


Q-Leaningでは
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \max_{a'}{\hat{Q}(s_{t+1},a'))}
で更新.

*1:雰囲気実装なので合ってない

IPアドレスを自動でGoogleスプレッドシートに書き込む(Windows10)

背景

学内や社内等のPCに接続したい時,IPアドレスが分からず困ることがしばしばあったので,*1
自動でIPアドレスGoogleスプレッドシートに書き込まれるようにしました.

構成

Windows 10 → Google Apps Script → Googleスプレッドシート
Google Apps Scriptが,Windows10からのGETに含まれるIPアドレスを受け取り,さらにGoogleスプレッドシートに書き込む

手順

サーバ側

まずは,GoogleスプレッドシートをGドライブから作成します.
この時,スプレッドシートのURLの{ここの文字列}部分がスプレッドシートのIDになっています.

https://docs.google.com/spreadsheets/d/{ここの文字列}/edit

次に,Google Apps Scriptを書いていきます.
Gドライブの右上の"新規"→"その他"→"Google Apps Script"で新規作成.

function doGet(e) {
  var id = '{スプレッドシートのID}';
  var sheet = SpreadsheetApp.openById(id).getSheetByName("シート1");
  var ipaddr = e.parameter.ip;
  sheet.getRange("A1").setValue(ipaddr);
}

上記コードでは,GETを受け取った時,"ip"に設定されているパラメータがスプレッドシートのA1セルにIPアドレスが書き込まれます.
そうしたら,"公開"→"ウェブアプリケーションとして導入"→"アプリケーションにアクセスできるユーザーを全員(匿名含む)に変更"→"更新"
として,WebAPIを公開します.

リモートPC側(Windows 10)

こっちがWindowsなので結構面倒くさかったです.
まず,IPアドレスをGETで送るbatファイルを作成しました.

set IPADDRPATH={batファイルがあるディレクトリ}\ipaddr.txt
ipconfig | find "IPv4" > %IPADDRPATH%
set /p myipaddr=<%IPADDRPATH%
curl {作成したWebアプリケーションのURL}?ip=%myipaddr:~38%

結構無駄ありそうですが,こんな感じで.
一度ipaddr.txtにipconfigからfindしたIPアドレスを入れ,そこから再度読み込んで"ip"のパラメータとしてAPIを叩いています.
最初に作成したスプレッドシートを確認すると,A1セルにIPアドレスが書き込まれていると思います.

後は,このbatファイルを定期的に実行するようにタスクスケジューラに登録します.
GUIからできるらしいのですが,上手くいかなかったのでコマンドプロンプトから設定.

schtasks /Create /tn "ipsender" /tr "{batファイルがあるディレクトリ}\ipsender.bat" /sc minute /mo 30

これで,30分に1回実行されます.ちなみに消す時はこう.

schtasks /Delete "ipsender" 

感想

作ったもののあんまり学内PCにアクセスする機会がないし,
そもそもIPアドレスが滅多に変わらなくて悲しい.(ネットワーク整備みたいなのしたっぽいし,固定IPになってる節)

そのうち,学内/社内のWindows PCにリモートデスクトップ接続する話を書きます.

*1:DHCPで変わったり等々

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で動かす

モナコイン

モナコインは,ブロックチェーン利用した仮想通貨で,同種で有名なものにはビットコインがあります.
詳しい説明は省きます.
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 ⇒ ワーカーのパスワード


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を作ったのはモチベの向上に割りと良かった.(素早く作れるように練習が必要そう)