僕の競プロ環境(2018/4現在)

競プロ初めて1年が経ちました.

まだ全然実力が付いてないのですが,RUPC以降精進しまくってるので伸びると信じてます.

f:id:wheson:20180421114205p:plain

ちょうどMacBookAirを買って1年にもなり,競プロ環境が整ってきた気もするので,現在の競プロの環境を紹介します.

環境

現在競プロをする時に使っているのは以下のものです.

  • iTerm2
  • Neovim

iTerm2

これはターミナルです.⌘Dで左右に画面を分割できるので良いですね.

f:id:wheson:20180421114233p:plain

shellはfishです.

これは最初からコマンド補完機能やら付いていて,文字入力をサボることが出来るのでいいです.

fishのプラグインで入れているものは以下のものです.

  • z (雑にディレクトリ移動ができる)
  • agnoster (おしゃれなテーマ ※要powerline font)

Neovim

エディタとしてNeovimというものを利用してます. iTerm2上で起動します.

neovim.io

理由は特にないです.

色々と便利にしていったのでこれ以外で競プロ出来ないくらいになってしまいました.

プラグインとして色々入れてますが,ここでは競プロ時に利用しているものだけを紹介します

  • deoplete
  • neosnippet
  • ale

deoplete

github.com

補完してくれるやつです.次に紹介するneosnippetと連携してます.

neosnippet

github.com

スニペット機能を利用できます.

独自にスニペットを登録することができ,僕はテンプレートとライブラリを登録して,使う時にさっと展開してます.

例えばこう書いて f:id:wheson:20180421115037p:plain <C-k> f:id:wheson:20180421115044p:plain

~/.config/nvim/snippets/cpp.snipスニペットを書くことで登録できます.

ただそうすると,cpp.snipがかなり膨大になるのでオススメしません.

そこでsnipファイルを分ける方法があります.

cpp.snipinclude cpp/*.snipと書くと,cpp.snipと同じディレクトリにあるcppディレクトリ以下の*.snipファイルをincludeしてくれます.

これをすると競プロライブラリをいい感じに管理できるようになります.

僕は以下のリポジトリcppディレクトリ以下に置いています.

github.com

現在は競プロライブラリを随時増やしていってる途中です.

ale

aleは非同期コードチェックをしてくれるプラグインです.

github.com

コーディング中に色々と指摘してくれるので,コンパイルをせずにエラーを潰すことが出来ます.

最後に

競プロはいいぞ

RUPC2018参加記

立命館大学で行われる3日間の競プロ合宿(RUPC)に参加した.

1日目

コンテスト

ウクニキア様(@ukuku09)とtsutajさん(@_TTJR_)とチームを組むことになった. チーム名はdevison_homura

二人共とても格上なのでどんな感じで問題解いてるのかを見れたら良いなとコンテスト前に思った.

結果としてはチームでは全完で参加チーム中4位だったけど,僕はAしか通してないのでうーんって感じ.

うくさんに凄く丁寧に説明していただいて,B問題を理解しようとしたけど,頭の処理が追いつかず1時間かかってようやく理解した.その時はとても申し訳ありませんでした. (Bは実質日本語力問題)

けど上位勢の人がどういう感じで問題を見てるかを把握できた気がした1日目だった.

懇親会

立命館大学の食堂でご飯が用意されててそれを各自取っていくスタイルだった.

企業の懇親会っぽかった.

大体みんな流動性がなく固定メンバーで話してたので僕も移動せずにじっと同じ席で近くの人と話してた.

新入生にどういう感じで競プロを教えていったら良いですかねと質問を投げたらABCのA問題B問題をいっぱい解かせる感じかなーと聞けたので,いっぱい解かせる予定.

覚悟しておいて新入生.

2日目

コンテスト

jimmyさん(@jimmyo0705)とnadareさん(@Py2K4)とチームを組むことになった. チーム名はjimson_dare

1日目と同じく僕がAをサクッと通してそれ以降考察するというスタンスでいた.

A問題に重大な罠(ai1333*)があり1WAを出してしまったのだけど,あれはちゃんと問題文を読みましょうということで.

1日目以上に難しい問題が多かったので基本的にチームメイトの話を聞くという感じでいた.椅子が凄く暖かくなった.

懇親会

焼肉屋に行った.

3日目

c7c7さん(@C7C7LL)とprdさん(@prd_xxx)とチームを組むことになった. チーム名はprd_wheson_c7

いつも通りAをやることになったのだけど,Aが長くて少しだけバグらせた.やるだけだったのでとりあえずAC.(時間かかったけど)

その後D問題を見て,永遠に解法生やそうとしてDPっぽいと思ったけど,実装してたらDP書いてなくておかしいね.

そのあとc7さんにDPを書いてもらって途中で時間終了. c7さんをvim環境で困らせてしまったのが申し訳なくなった.

3日目が一番頭をフルで動かしてて,楽しかった.

終わったあとにc7さんとprdさんとで,もっと精進しないといけないねという話をした.

まとめ

Aしか解いてない.

上位勢の人たちと組んで,上位の人もかなりの問題を解いて今に至ることが分かった.

もっと問題を解いて,せめて典型をぱっと生やせるようになりたい.

そしてICPC2018国内予選は突破したい…

精進します.

fishシェルで閉じ括弧などの補完をするプラグインを導入した話

はじめに

neovimの方では閉じ括弧などの補完を自動で行ってくれるプラグインを入れてましたが,fishの方では入れてませんでした.理由としてはエディタほど""等を使う機会がなかったので.

しかし,commitメッセージを入れるときなどで使う機会が多いことに気付いて不便だと思い始めたので探してみました.

探すのに使ったのはfisherman公式サイト

Fisherman公式サイト

見つけたプラグイン

github.com

fishermanを導入している場合は下記コマンドで入る

$ fisher install laughedelic/brew-completions 

その他は上記リンクからインストール方法を見てください.

動作

こんな感じで動作します↓ (見にくくてごめんなさい)

f:id:wheson:20180104201751g:plain

まとめ

これで夜も眠れる補完生活が遅れそうです.

調べてると色んなプラグインがあったので,面白そうなものもあれば入れてみようかなと思います.

おすすめとかあれば教えてもらえるとうれしいです.

ではまた

RubyでBitBoardオセロを作成した話

概要

最近Rubyの勉強を進めてまして,その一環としてRubyでオセロを作成することにしました.

ただ,2次元配列を使って盤の状態を管理するのが主流だとは思うのですが,先輩がBitBoardというものを用いてC++でオセロを実装していたのを思い出したので,僕もBitBoardを用いて実装することにしました.

BitBoardとは

まずは普通の2次元配列を用いたオセロ盤の実装方法ですが,

board[10][10]

みたいな感じで,壁を含めた2次元配列を用いるのが主流だと思います. 初期値は以下のようになっていることが多いです(多分).

BLACK_STONE =  1
WHITE_STONE = -1
EMPTY       =  0
WALL        =  2
board = [
          [ 2,  2,  2,  2,  2,  2,  2,  2,  2,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0, -1,  1,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  1, -1,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  0,  0,  0,  0,  0,  0,  0,  0,  2],
          [ 2,  2,  2,  2,  2,  2,  2,  2,  2,  2]
        ]

しかし,今回使ったBitBoardは以下のようにして実装しています.

white = 0x1008000000
black = 0x810000000

なにこれって感じになるかと思います.上記のwhiteとblackはオセロの盤の初期状態を表しています.

このように2つの変数を用いて盤を管理するのがBitBoardで実装したオセロになります.

whiteとblack変数はそれぞれ白石の場所,黒石の場所を表しています.

どのように表しているかというと,以下の図を見ていただくと理解しやすいかと思います.

A B C D E F G H
1 1 2 3 4 5 6 7 8
2 9 10 11 12 13 14 15 16
3 17 18 19 20 21 22 23 24
4 25 26 27 28 29 30 31 32
5 33 34 35 36 37 38 39 40
6 41 42 43 44 45 46 47 48
7 49 50 51 52 53 54 55 56
8 57 58 59 60 61 62 63 64

表の1行目と1列目は座標を表す文字数字となってます. 内部の数字はその座標に割り当てられたbitの桁で,例えばA1であればbitの1桁目で表すことになります.

ちなみにこの2つの変数にはルールがありましてどちらも1となるbit位置が存在してはいけないというものです.同じ場所に2つの色を石が存在する状態はありえないので禁止状態になります.

BitBoardで反転処理

BitBoardを用いると高速に反転処理が行えるようになります.

def create_reverse_bit(player, enemy, pos)
  rev = 0
    
  # 既に石がある場合は0を返し,終了する
  if ((player | enemy) & pos) != 0
    return rev
  end
    
  # 右
  tmp = 0
  mask = (pos << 1) & 0xfefefefefefefefe
  while mask != 0 && (mask & enemy) != 0
    tmp |= mask
    mask = (mask << 1) & 0xfefefefefefefefe
  end
  if mask & player != 0
    rev |= tmp
  end
  ... 以下省略
end

このメソッドでは現在プレイヤーのbitboard変数とそうでないプレイヤーのbitboard変数,そして置かれた場所のbitを表すposを受け取ります.

このメソッドは最終的にrevというひっくり返る場所のbitを表すrevを返します.

既に石が置かれているときはひっくり返せないので0を返します.

# 既に石がある場合は0を返し,終了する
if ((player | enemy) & pos) != 0
  return rev
end

次に8方向に対してひっくり返る場所を探索します. ここでは右方向だけを紹介しますが,他も同じような方法で行います.

まず

tmp = 0

を用意します.ここにその方向でひっくり返る場所のbitを表す数値を格納します.

その後,mask変数というものがあるのが確認できると思います.

mask = (pos << 1) & 0xfefefefefefefefe

これはBitBoard特有の問題を解決するために使用されます. BitBoardでは以下の表のように管理されると紹介しましたが,連続した値が盤上では繋がっていないというのがわかるかと思います.

A B C D E F G H
1 1 2 3 4 5 6 7 8
2 9 10 11 12 13 14 15 16
3 17 18 19 20 21 22 23 24
4 25 26 27 28 29 30 31 32
5 33 34 35 36 37 38 39 40
6 41 42 43 44 45 46 47 48
7 49 50 51 52 53 54 55 56
8 57 58 59 60 61 62 63 64

これをmaskなしでbitをずらしていくと,繋がっていないはずの場所が,繋がっているように処理されてしまうのです.

0xfefefefefefefefeはA列だけに0にしたbit列です.これを使うことにより,探索ポイントを右にズラし続けたあとA列に入ってしまったときに強制的に0とすることで探索を打ち切らせることができるのです.

while mask != 0 && (mask & enemy) != 0
  tmp |= mask
  mask = (mask << 1) & 0xfefefefefefefefe
end

最終的に得られたtmpをrevに|=演算子で結合します.

if mask & player != 0
  rev |= tmp
end

上記の方法を全方向で繰り返すと反転するbitを作成することができます.

(説明が雑すぎる気がするので時間があれば編集します)

BitBoardで著手可能位置の生成

BitBoardで著手可能位置の生成を行うのは容易です. これも同じく右方向だけを紹介します.

def create_movable_pos(player, enemy)
  blank = ~(player | enemy)
  mobility = 0

  # 右
  masked_enemy = enemy & 0x7e7e7e7e7e7e7e7e
  t = masked_enemy & (player << 1)
  ## 5回繰り返す
  5.times{t |= masked_enemy & (t << 1)}
  mobility |= blank & (t << 1)
  ... 以下省略
end

(詳しい説明はまた追記します…)

汚すぎる僕のコード

github.com

リファクタリングしないといけないことは分かってます…

参考にさせていただいたサイト

オセロにおけるビットボード - Wikipedia

オセロの着手可能位置生成 【ビット演算テクニック Advent Calendar 2016 23日目】 - prime's diary

ビットボードの凄さをざっくりと解説してみる - Qiita

GitHub - odanado/crosswalk: オセロAI

2017年を振り返る

1月

  • 今年は英語に力入れるぞーって授業でのプレゼンで宣言した
  • ついでにムキムキになるぞーって言ってジムに通いだす

2月

  • 英語学習計画を2ヶ月分作成した f:id:wheson:20180101005256j:plain f:id:wheson:20180101005328j:plain

  • 1000番台の発表を待たずにGTX970のグラボを購入してしまう

    3月

  • 英語学習をほぼ完ぺきに完遂したので心が入れ替わったような気分になる. f:id:wheson:20180101005431j:plain

  • 何でもできるような気がしてきてゲームをほぼやらなくなったのがこの時期

  • ジムをやめる

    4月

  • 新学年になってゼミ配属先を決める
  • ゼミ室の前に貼ってあった競技プログラミングチームメンバー募集のポスターを見てたら教授に「入れば」と言われて,その後すぐにその教授にチームの代表に連絡された.
  • その後競技プログラミングチームに参加することになる(この時全く競技プログラミングをやったことがない)

5月

  • 例の関西地区(+α)の大学が集まって合同PBLをするやつに参加することになった

6月

  • 今通ってる大学とは別の大学院の見学に行く
  • 同時期に夏のインターンに応募する
  • ICPC国内予選に2軍チームで参加することになる(予選落ち)
  • 来年は絶対に国内予選突破するぞーってチームの雰囲気が良くなった気がする(気がする)

7月

  • 夏のインターンのESが通って舞い上がる
  • その後,次のステップの面接で落ちる

8月

  • デスク環境をがらりと変えてデュアルディスプレイにした
  • Web系の知識皆無だったなぁと思って,Progateやらなにやら色々触った.
  • ゼミ室のPCにvSphereを入れて仮想サーバー環境を整えた

9月

  • 例の関西地区(以下略)の夏合宿的な奴があった
  • 会議のプロになれた気もしたしなんかここで一気にチームメンバーとの距離が縮まった気がする(そう思っているのは俺だけかもしれない)

10月

  • 何をしていたのか忘れた

11月

  • 就活に向けて本格的に動き出す
  • とりあえず逆求人フェスティバルとか行ってみた ここでたくさんの企業の方と話をして,今後自分がどうなっていきたいかなどの自己分析が急激に進んだ気がする

12月

  • 就活が本格的に始まる
  • 逆求人フェスティバルで面談していただいた企業の見学に行ったり,でっかい企業のインターンをしたり,ギークフェスタに行ったりした. 東京に3日間いてとても疲れたし,濃い3日間を過ごした.

まとめ

  • 2017年は英語学習計画を完遂したあたりから人格が入れ替わったかのように勉強してた気がする.
  • 競技プログラミングを始めて多くの優秀な人に出会えたし,就活の場でも少しだけでも企業の人に注目されたりしたので,競技プログラミングはいいぞ. 実際数学的問題やパズルを解くことは昔から好きだったのでなぜもっと早くからやらなかったのかって感じなんですが.

2018年はもっとストロングな人物になりたい!

海外の人のカプセルホテルレビュー動画にハマってる話

この記事は、 OIT Advent Calendar 2017の12日目の記事です.

どうも

whesonです.

最近東京に行く機会が何度かありまして,ついに車中泊でなくしっかりと泊ることになりました

んで,泊るところを探すのですが,カプセルホテルってめちゃくちゃ安いじゃないですか.

けど不安だなーとか思ってて,とりあえずカプセルホテルのレビューでも見ようとするのですが,

Google検索 [カプセルホテル レビュー]

って調べてもカプセルホテルについてどんな感じで過ごすか分からない.大体綺麗だったとか当たり障りのないことを書いてて,そうじゃないんだよ!!と思ってました.

そこで天下のYoutube

まあ動くものって分かりやすくていいですよねってことで.

ただまあ日本人が普通に泊ってる動画なんて見ても何も面白くなくて.

カプセルホテルって日本独特の文化らしく,海外の人がカプセルホテルレビュー動画を結構あげてらっしゃるのですよね.

それがまあ面白い.

とりあえず1本見てください.(私の初カプセルホテルレビュー動画)

youtu.be

どうですか!?

これは日本語字幕が付いてるものですが,なんだか日本人の動画より面白くないですか?

何が面白いって反応です.

海外の人って凄く感情豊かなんですよね.(1人日本人だけど)

見てるこっちが幸せになりそうな感じしませんか?

ここからおすすめ動画

わさびキットカットカルピス兄貴

youtu.be

カプセルホテルの内容は少ないですが,なんかおもしろい

youtu.be

めっちゃいいカメラ持ってて,めっちゃ表情良い兄貴

youtu.be

めっちゃ未来なカプセルホテルに興奮してるの面白い

youtu.be

最後に

海外の人の日本旅行動画は,生の英語の勉強にもなるし,分からなければ字幕ありの動画でも楽しめると思います.

何しろ日本の旅行なのである程度予備知識はあるはず!

なので理解しやすく楽しめるはず!

という訳でここまで読んでくれた方は興味がありふれていると思うのでぜひいっぱい観てくださいね.

では,良い外国人カプセルホテルレビュー動画生活を!

Google App Engineを利用して自作ゲームのスコアを保存・取得するシステムを開発した話(PHP)

きっかけ

友人と二人でブラウザ上で動くゲームを作っていて,スコアをどこかに保存しようということになった.

Google App Engineにしようと思ったのは,所属する研究室とは別の先生にオススメされたので使った.

多分MySQLとかのデータベースを使うともっと簡単にできたかもしれないけど,key-value型のNoSQLを使う勉強,GAEを利用する勉強にはなったと思う.

実際の方法

Google Cloud Platform の利用登録

これに関してはかなり前に登録していたので忘れてしまった.

blog.apar.jp

上記のサイトが参考になると思うので載せておく.

Google Cloud SDKの取得

実はこれに数時間かけてしまった.おそらく普通に指示通り行なっていればつまずくことはなかったと思う.

これに関しても

ゼロから始める Google App Engine の使い方(2017年) | あぱーブログ

が参考になるのでここでは割愛させていただく.

本題のスコアを保存・取得するところ

準備

今回利用したのは,PHPである.開発環境にphpとcomposerが入っていなければまず取得する.

好きなディレクトリを作成し,そこでapp.yamlファイルを作成し,以下のように記述する.

application: ***** #任意のアプリケーション名
version: 1
module: default
runtime: php55
api_version: 1

threadsafe: true

handlers:
- url: /export  # スコアを保存するためのurl
  script: export.php

- url: /import  # スコアを取得するためのurl
  script: import.php

次にcomposer.jsonファイルを作成し,以下のように記述し,

{
    "require": {
        "google/cloud-datastore": "^1.0",
        "symfony/console": "^3.0",
        "google/apiclient": "^2.0"
    },
    "require-dev": {
        "phpunit/phpunit": "~4.8",
        "google/cloud-tools": "^0.6"
    },
    "autoload": {
        "psr-4": { "Google\\Cloud\\Samples\\Datastore\\Tasks\\": "src" },
        "files": ["src/functions.php"]
    }
}

composer updateと打つ. すると色々ディレクトリとファイルが増える.(深くcomposerについて理解してないので細かいことは割愛)

次にGoogle Cloud Platformのコンソールを開く.

APIとサービス→認証情報→認証情報を作成→サービスアカウントキーの作成でこの画面に遷移する

f:id:wheson:20171104135540p:plain

これで作成を押すとjsonファイルがDLできるので,そのjsonファイルを現在開発してるディレクトリに突っ込む.

スコアを保存するためのphp

app.yamlでexport.phpと指定したので,それに従ってexport.phpというファイルを作成して以下のように記述する.

<?php
# Includes the autoloader for libraries installed with composer
require __DIR__ . '/vendor/autoload.php';

# Imports the Google Cloud client library
use Google\Cloud\Datastore\DatastoreClient;

# 認証
putenv('GOOGLE_APPLICATION_CREDENTIALS=' . __DIR__ . '{jsonファイルの指定}');

# Your Google Cloud Platform project ID
$projectId = '{プロジェクトID}';

# Instantiates a client
$datastore = new DatastoreClient([
    'projectId' => $projectId
]);

# The kind for the new entity 
# Scoreという名前の種類にしているが,別にそのデータが何なのか分かればなんでもいい
$kind = 'Score'; 

# The Cloud Datastore key for the new entity
$taskKey = $datastore->key($kind);

# POST されたデータを変数に格納
# このシステムではscoreとusernameをデータストアに保存する
$postScore = $_POST["score"];
$postUsername = $_POST["username"];

# Prepares the new entity
$task = $datastore->entity($taskKey, ['score' => $postScore, 'username' => $postUsername]);

# Saves the entity
$datastore->upsert($task);

echo 'Saved ' . $task->key() . ': ' . $task['score'] . ', ' . $task['username'] . PHP_EOL;

試しに投入するプロパティを書き換え

$task = $datastore->entity($taskKey, ['score' => 1000, 'username' => 'hoge']);
dev_appserver.py .

とコマンドを打つことでローカルでサーバを起動しhttp://localhost:8080/exportにアクセスする.

それでGoogle Cloud Platformのデータストアのエンティティを見ると,名前が自動生成されたIDでscore 1000,username hogeのエンティティが作成されていることが確認できる.

これでデータストアにデータを格納することができた.書き換えた文は元に戻しておこう.

データを取得するためのphp

データを格納するだけではただのゴミ箱である.本システムではimport.phpで取得するためのphpを作った.

import.phpというファイルを作成し以下のように記述する.

<?php
# Includes the autoloader for libraries installed with composer
require __DIR__ . '/vendor/autoload.php';

# Imports the Google Cloud client library
use Google\Cloud\Datastore\DatastoreClient;

# 認証
putenv('GOOGLE_APPLICATION_CREDENTIALS=' . __DIR__ . '{jsonファイルの指定}');

# Your Google Cloud Platform project ID
$projectId = '{プロジェクトID}';

# Instantiates a client
$datastore = new DatastoreClient([
    'projectId' => $projectId
]);

$query = $datastore->gqlQuery('SELECT * FROM Score ORDER BY score DESC');

$result = $datastore->runQuery($query);

foreach ($result as $entity){
    $data[] = array('score' => $entity['score'], 'username' => $entity['username']);
}

echo json_encode($data);

GQLというSQLとほぼ同じ文でデータを取得することができるものを利用した.

SELECT * FROM Score ORDER BY score DESC

でScoreという種類のエンティティをscoreの降順で取得せよという意味である.

他の命令は以下のリファレンスを参考にするといい.

https://cloud.google.com/datastore/docs/reference/gql_reference

本システムではranQueryで取得した結果($result)をforeach文で$data[]に連想配列で格納している. その後,json_encodeしてechoしている.

これでデータを降順で取得できるので,後はそれを利用してランキング機能を作るなりする.

ちなみに取得する限度を決めることもできるのだが,LIMIT 10と指定してもエラーが出てどうしようもなくなったので,指定しないことにした. 何も指定しなくても最大限度が決まっているので(1000件)大変なことになることは無いだろうということで諦めた.

以上がシステムの詳細である.

感想

PHP GAE datastore」などで検索をかけても情報が出てくるが,それが思い通りに動かないということが多かった.ただデータを格納して,取得するだけなのになぜこんなにも難しいのかと嘆いていたが,とりあえずうまく動いたので良かった.

データを削除するのを作っていないのは必要がないのと,悪用されると危険かもしれないと思ったからである.

GAEを勧めてくれた先生はJava サーブレットで作っていたため,コードは見せてもらったが参考にはならなかった(ごめんなさい).

実はまだこのシステムは本番利用していないので,友人とゲームの方にも組み込むように手を加えないといけない.ゲームの方も完成すれば公開しようと考えている.

参考にさせていただいたWebサイト

PHP で Google Cloud Datastore のデータを読み書きする - koni blog

Getting started with the Google Cloud Datastore API  |  Cloud Datastore Documentation  |  Google Cloud Platform

データストアのクエリ  |  Cloud Datastore のドキュメント  |  Google Cloud Platform

Google Cloud Datastore API スタートガイド  |  Cloud Datastore のドキュメント  |  Google Cloud Platform

PHPでJSONのデータを処理する方法