RUPC2018参加記
立命館大学で行われる3日間の競プロ合宿(RUPC)に参加した．
ウェイ pic.twitter.com/8BiSO0jePi
— wheson (@wheson) 2018年3月26日
1日目
コンテスト
ウクニキア様(@ukuku09)とtsutajさん(@_TTJR_)とチームを組むことになった． チーム名はdevison_homura
大悪魔様(@ukuku09)とtsutajさん( @_TTJR_ )とチーム#rupc2018
— wheson (@wheson) 2018年3月26日
二人共とても格上なのでどんな感じで問題解いてるのかを見れたら良いなとコンテスト前に思った．
結果としてはチームでは全完で参加チーム中4位だったけど，僕はAしか通してないのでうーんって感じ．
うくさんに凄く丁寧に説明していただいて，B問題を理解しようとしたけど，頭の処理が追いつかず1時間かかってようやく理解した．その時はとても申し訳ありませんでした． (Bは実質日本語力問題)
Bの問題文理解するのに思考時間O(2^n)かかった
— wheson (@wheson) 2018年3月26日
けど上位勢の人がどういう感じで問題を見てるかを把握できた気がした1日目だった．
懇親会
立命館大学の食堂でご飯が用意されててそれを各自取っていくスタイルだった．
企業の懇親会っぽかった．
大体みんな流動性がなく固定メンバーで話してたので僕も移動せずにじっと同じ席で近くの人と話してた．
新入生にどういう感じで競プロを教えていったら良いですかねと質問を投げたらABCのA問題B問題をいっぱい解かせる感じかなーと聞けたので，いっぱい解かせる予定．
覚悟しておいて新入生．
2日目
コンテスト
jimmyさん(@jimmyo0705)とnadareさん(@Py2K4)とチームを組むことになった． チーム名はjimson_dare
day2はnadareさん(@Py2K4)と jimmyさん(@jimmyo0705)とチームrupc_jimson_dareです．
— wheson (@wheson) 2018年3月27日
1日目と同じく僕がAをサクッと通してそれ以降考察するというスタンスでいた．
A問題に重大な罠(ai1333*)があり1WAを出してしまったのだけど，あれはちゃんと問題文を読みましょうということで．
Aでei1333*で提出しましてWA生やした．とてもよろしくない
— wheson (@wheson) 2018年3月27日
1日目以上に難しい問題が多かったので基本的にチームメイトの話を聞くという感じでいた．椅子が凄く暖かくなった．
懇親会
焼肉屋に行った．
3日目
c7c7さん(@C7C7LL)とprdさん(@prd_xxx)とチームを組むことになった． チーム名はprd_wheson_c7
c7さん(@C7C7LL)とprdさん (@prd_xxx)とチームrupc_prd_wheson_c7で出ます！#rupc2018
— wheson (@wheson) 2018年3月28日
いつも通りAをやることになったのだけど，Aが長くて少しだけバグらせた．やるだけだったのでとりあえずAC．(時間かかったけど)
その後D問題を見て，永遠に解法生やそうとしてDPっぽいと思ったけど，実装してたらDP書いてなくておかしいね．
そのあとc7さんにDPを書いてもらって途中で時間終了． c7さんをvim環境で困らせてしまったのが申し訳なくなった．
3日目が一番頭をフルで動かしてて，楽しかった．
終わったあとにc7さんとprdさんとで，もっと精進しないといけないねという話をした．
まとめ
Aしか解いてない．
上位勢の人たちと組んで，上位の人もかなりの問題を解いて今に至ることが分かった．
もっと問題を解いて，せめて典型をぱっと生やせるようになりたい．
そしてICPC2018国内予選は突破したい…
精進します．
fishシェルで閉じ括弧などの補完をするプラグインを導入した話
はじめに
neovimの方では閉じ括弧などの補完を自動で行ってくれるプラグインを入れてましたが，fishの方では入れてませんでした．理由としてはエディタほど""等を使う機会がなかったので．
しかし，commitメッセージを入れるときなどで使う機会が多いことに気付いて不便だと思い始めたので探してみました．
探すのに使ったのはfisherman公式サイト
見つけたプラグイン
fishermanを導入している場合は下記コマンドで入る
$ fisher install laughedelic/brew-completions
その他は上記リンクからインストール方法を見てください．
動作
こんな感じで動作します↓ (見にくくてごめんなさい)
まとめ
これで夜も眠れる補完生活が遅れそうです．
調べてると色んなプラグインがあったので，面白そうなものもあれば入れてみようかなと思います．
おすすめとかあれば教えてもらえるとうれしいです．
ではまた
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
(詳しい説明はまた追記します…)
汚すぎる僕のコード
リファクタリングしないといけないことは分かってます…
参考にさせていただいたサイト
オセロの着手可能位置生成 【ビット演算テクニック Advent Calendar 2016 23日目】 - prime's diary
icpc2017国内予選に参加した話
※この記事は2017/07/22にて別の場所で書いていたものをこちらに移行したものです．
強い先輩(4年)と僕と一緒に始めた同期(3年)でチームsiguma.makkusuとして参加しました．
大会当日の様子
大会前
僕のMacでやるということになったので環境設定をしてた．大会会場は僕の所属するゼミ室で． プリンターの設定をしようと，Macのプリンターの設定に戸惑いながらも別のチームの強い先輩にアドバイスを貰ってなんとかセットアップ完了した．
そこでまさかの不具合発生．なぜかゼミ室のwi-fiに繋ぐとインターネットに繋がらないということが起きた． ゼミ室のwi-fiに繋がないとプリントアウトが出来ないので困ったのだけど，結局プリントアウトする時だけゼミ室のwi-fiに繋ぎ，それ以外の時は大学全体のwi-fiに繋ぐということで何とか行うことになった．
大会開始
まず，同期の子がA問題をPCで解き，僕はB問題を先輩はC問題を紙で解くことになった．
00:20 経過 A問題 AC
同期がA問題を通してくれたので，PCを僕が操作しB問題を実装することに． 全然B問題を理解できてなくて実装に苦労した．詰まってた頃にC問題を解いていた先輩ができたっぽいということで，PCをチェンジ．紙でもう一度考え直すことに．
しかし先輩もC問題がサンプルが通らなかったみたいでもう一度PCをチェンジ．これを3回くらい繰り返したと思う．
01:40 経過 B問題 AC
かなり時間がかかってようやくB問題をACする．この時点でかなり出遅れてしまったと後悔．文字列定数をしっかり理解してなかった模様．
01:54 経過 C問題 AC
先輩がC問題をACした．この時点で80位くらいで4完しないと予選通過できそうにないなぁと話してた． D問題を全員で考察．先輩が普通のDPだと無理だろうねと言ってた．僕は知識がなさすぎてどう処理していったらいいか分からず．
03:00 大会終了
結局D問題が解けずに終了．104位でした．
大会の感想
今年の4月から競技プログラミングを始めて，短い期間だったけどある程度の問題は解けるレベルになったと思う．今回はD問題を解けなかったけど来年は必ず解きたい．同じ大学の別のチームの人もすごく悔しがってたので，来年に向けて切磋琢磨しながら力を蓄えようと思う．
まずはAtcoderの過去問を解きまくるぞーって意気込んでる．AOJ-ICPCっていうサイトの問題も上から順に埋めるつもり．
来年は絶対国内予選通過するぞー!!
Progate Lv.100になりました．
現状
Lv.100はどれくらい？
現在はおすすめの学習手順(リンク)に従って進めてます．
進捗状況なのですが，Railsコースの6番目が終わったところです．
とはいえ，道場コースのHTML/CSS，Railsもやってますので，おすすめコースのここでLv.100という訳ではないです．
まあ何が言いたいかというと，まだまだLv.100になっても初心者だなぁって感じることですね．
実際1周しかしてないので，HTML/CSSコースの内容が抜けつつありますし，定着させるには何度も周回しないといけないなって思います．
それと，進めてる途中でJavascriptコースが改装されたみたいで，これもまた進めないといけないです．
とりあえずおすすめ1周目を終わらせて，HTML/CSSコースを最後まで終わらせたらクラウドソーシングでお仕事を見つけようかなって思ってます．
Progate凄く楽しいのでおすすめです．
クリップボードに端末上でコピーする方法
はじめに
競技プログラミングの時にいつも端末でコンパイル・テストケースの確認をして、テキストエディタから範囲選択をしてクリップボードに保存していました。(Ctrl-a から Ctrl-cのような感じ)
今回、neovimにエディタを変更したことで、ふと思ったことが、実行確認を端末で行なった後、そのままコマンドでクリップボードにテキストを保存できないのだろうかと。
見つかった方法
Mac OS Xの場合は
cat hoge.cpp | pbcopy Linuxの場合は
cat hoge.cpp | xsel --clipboard --input Windowsの場合は
cat hoge.cpp | /dev/clipboardと端末で実行することによって、クリップボードに保存されるとのこと。私の環境ではMac OS Xでのみ確認済み。
これからはこの方法で競プロをやってみようと思います。
追記）Mac OS Xの場合は
pbcopy < hoge.cpp で出来たみたいです… ほかの環境ももっと短いコードありそうだなぁ…
こちらの記事を参考にしました
標準出力をクリップボードにコピーする pbcopy , macosx,ubuntu,cygwin でそれぞれ使う - my-notebook
