ICPC2018国内模擬予選参加記

今年もICPC国内予選の時期になりましたね.

昨年度は競プロを始めて間もなかったので,あまり大したことが出来なくて悔しかった思い出があります.

今年は1年間競プロをして力もある程度は付いた気がするので楽しめるかなと思ってます.

チームメンバー

チーム名は”Incoming Tomoya”です. 弊学の2軍チームでAtcoderではレートが全員緑色です.

wheson (@wheson)

僕です.B4で来年就職なので今回が最後のICPC出場になります. メンバーで唯一C++で競プロをやってます. そのためライブラリは必然的に僕のものを使う感じになりました.

たいちょー (@xztaityozx_001)

M1の先輩です.競プロを始めたのは僕と同じ時期で,ちょうどレベルも同じくらいなのかなぁと言う感じです.難読化シェル芸をしてるみたいで,怖い人ですが,怖くないです. 普段はC#で競プロをしてるらしいです.

xztaityozx.hatenablog.com

いらいざ (@eliza0x)

後輩です.コンパイラを作ったり,CPUを作ったり,最近は機械学習をしてたりと,幅広く何かやってます.構文解析を得意とするらしいので,構文解析の問題は彼に投げます. 普段はHaskellで競プロをしてるみたいです.

のばなしうさぎ

模擬予選の内容

開始前

ライブラリの印刷をして,適当にダラダラしてました. 会場はたいちょーの研究室を使うことになっていたので,準備は彼に全て任せてしまってました.

開始

A・B・Cと流し見して,AはやるだけだったのでPCを受け取り実装しました.

15min

AをACする. Bをたいちょー,Cをいらいざ君がやることになったみたいで,先にいらいざ君がPCを受け取る. とりあえず僕はDを読み始める.

60min

Cを実装していたいらいざ君からC++わからんと言われ,コードを見ると,Lambda式で闇のようなことをしていてこれは読めないと思ったので,悲しい顔をした.

Dをたいちょーと考察して桁ごとに個数を決められそうだなーと思って数式に起こすが,誤差が出てダメだった.

諦めてEを読み始める. たいちょーにEの概要を伝えると,二部グラフっぽいと言われて,確かに二部グラフですねと返した.二部グラフのライブラリは印刷しておいたので,とりあえず実装を固めるために紙コーディングを始める.

90min

結構長いこといらいざ君がPCを専有していたので,そろそろ交代しようということで,たいちょーに交代した.

120min

たいちょーもバグらせる. Eがやるだけなので実装したいと伝えると,交代してもらえたのでライブラリの写経を始める.

130min

Eのサンプルが合わない. 後ろでBとCの考察の確認をしていたみたいで,交代して先にCをいらいざ君が修正を始める.

150min

いらいざ君がCをACする.

とりあえずホッとした.

170min

たいちょーがBをACする.

ちょうどその時に,二部グラフの写経ミスに気付いたので,急いで修正を始める.

178min

僕が実装に焦って,横でたいちょーが過呼吸のマネ(田中ヒメのマネ)を始めて,いらいざ君が落ち着いて落ち着いてと言う地獄みたいな状態になってた.

Eのサンプルが通ったので,提出するとACする.

終了後

ABCEの4完55位(ゲスト除く)だった.

ランキングを見ると,学内1位だったのでテンションがとても跳ね上がった.

その後,国内予選突破圏内を意味するselectedになっているのを見てテンションがおかしくなりそうになった.

本番も同じ調子で行くぞー

neovimでLSP(LanguageServerProtocol)を使ってみる

今までずっとALEっていう非同期コードチェックプラグインを使ってましたが,少し挙動が遅いと思ってました.

先日この記事を見て,

kutimoti.hatenablog.com

LSPを使うと早くなるっぽい??って思って導入してみました.

結果として,コードチェックは爆速になりました.

LSPとは

この記事に詳細があります.

language server protocolについて (前編)

要約するとLSPを使うことで,

  • 自動補完
  • ヒント(ホバー)の表示
  • シンボルの定義の位置を取得
  • コードの整形
  • エラー分析,修正案の提示

等が利用できるようになります.

neovimでLSPを導入する

LanguageClient-neovimを使います.

上記プラグインを入れる前はvim-lspを入れたのですが,コードチェックの挙動がおかしかったのでやめました.

プラグイン構成

  • LanguageClient-neovim
  • deoplete
  • neosnippet

dein.toml

[[plugins]]
repo = 'autozimu/LanguageClient-neovim'
rev = 'next'
build = 'bash install.sh'
hook_add = '''
source ~/.config/nvim/plugins/LanguageClient-neovim.rc.vim
'''

dein_lazy.toml

[[plugins]]
repo = 'Shougo/context_filetype.vim'

[[plugins]]
repo = 'Shougo/neosnippet.vim'
on_event = 'InsertCharPre'
on_ft = 'snippet'
depends = 'context_filetype.vim'
hook_source = '''
source ~/.config/nvim/plugins/neosnippet.rc.vim
'''

[[plugins]]
repo = 'Shougo/deoplete.nvim'
depends = 'context_filetype.vim'
on_event = 'InsertEnter'
hook_source = '''
source ~/.config/nvim/plugins/deoplete.rc.vim
'''

~/.config/nvim/plugins/LanguageClient-neovim.rc.vim

set hidden

let g:LanguageClient_serverCommands = {}

" 言語ごとに設定する
if executable('clangd')
    let g:LanguageClient_serverCommands = {
        \ 'cpp': ['clangd']
        \ }
endif

augroup LanguageClient_config
    autocmd!
    autocmd User LanguageClientStarted setlocal signcolumn=yes
    autocmd User LanguageClientStopped setlocal signcolumn=auto
augroup END

let g:LanguageClient_autoStart = 1
nnoremap <Leader>lh :call LanguageClient_textDocument_hover()<CR>
nnoremap <Leader>ld :call LanguageClient_textDocument_definition()<CR>
nnoremap <Leader>lr :call LanguageClient_textDocument_rename()<CR>
nnoremap <Leader>lf :call LanguageClient_textDocument_formatting()<CR>

~/.config/nvim/plugins/neosnippet.rc.vim

let g:neosnippet#snippets_directory = '~/.config/nvim/snippets'
imap <C-k> <Plug>(neosnippet_expand_or_jump)
smap <C-k> <Plug>(neosnippet_expand_or_jump)
xmap <C-k> <Plug>(neosnippet_expand_target)
if has('conceal')
    set conceallevel=2 concealcursor=niv
endif

~/.config/nvim/plugins/deoplete.rc.vim

" deoplete options
let g:deoplete#enable_at_startup = 1
let g:deoplete#auto_complete_delay = 0
let g:deoplete#auto_complete_start_length = 1
let g:deoplete#enable_camel_case = 0
let g:deoplete#enable_ignore_case = 0
let g:deoplete#enable_refresh_always = 0
let g:deoplete#enable_smart_case = 1
let g:deoplete#file#enable_buffer_path = 1
let g:deoplete#max_list = 10000

言語ごとのLanguageServerを導入する

https://langserver.org

上記サイトから自身が使う言語のLanguageServerを導入してPATHを通してください.

一例としてclangdをmacで導入する流れを紹介します.

clangdを導入

  • Homebrewでllvmをインストールする

$ brew install llvm

  • PATHを通す

brew install llvmで出力された最後の方に現在のshellでの通し方が書いてあるのでそれを見てください.

  • $ clangd --versionでPATHが通ってることを確認する.

使用感

コードチェックが爆速すぎて気持ちがいい.

今まで:%s/hoge/huga/gで置換をしてたけど,それが変数であれ,コメントであれ全てのhogeが置き換わって不便だった.

LSPの機能のRenameを使うと変数のhogeだけを置き換えるということが出来るので凄くいい.

気になったこと

  • LanguageServerから取得される補完リストを出力するのが少し遅い
  • nvim newfile.*で新たにファイルを作成しつつneovimを起動すると,LanguageServer-neovimが起動しない.手動で:LanguageClientStartとすると起動する.

参考サイト

github.com

github.com

http://langserver.org

僕の競プロ環境(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年はもっとストロングな人物になりたい!