#procon29 競技部門参加記

※この記事は ICT Advent Calendar 2018 3日目の記事です.

昨日はPCKモバイル部門でグランプリを獲得したびーまかです.

b-mk.hatenablog.com

結果

結果のソース

予選

P10リーグ

対戦相手 結果 勝敗
木更津 98-84
沼津 144-131
舞鶴 89-56

予選敗退 0勝3敗 リーグ4位

敗者復活戦

L7リーグ(リーグ内リーグ戦)

対戦相手 結果 勝敗
73-98
石川 69-83

リーグ内リーグ戦のため,2勝チーム同士で比較して総得点数が多いチームが通過

比較相手 結果 勝敗
高知 102-181

敗者復活 2勝0敗 リーグ1位

決勝トーナメント

対戦相手 結果 勝敗
北九州 128-124

1回戦敗退

チームメンバー

SolverのAlgorithm

この問題は,「二人零和有限確定不完全情報ゲーム」として分類できる(?) 不完全情報ゲームのAIを考えるのがめんどくさくなったので完全情報ゲームみたいな問題に置き換える.

不完全情報である理由

まず,完全情報ゲームは,「すべての意思決定ノードにおいて,今まで取られた行動などが得られる」ものである. この問題では,双方のチームの意思決定が同時であるため,上記を満たさないと考えられる.

この問題を,先手・後手に分かれ交互に手を打つ「完全情報ゲーム」とみなせば.囲碁等のAIで知られる モンテカルロ木探索(MCTS) が適用出来ると考えた. ちなみに,囲碁AIで世間を賑わしたAlphaGoはこのモンテカルロ木探索と機械学習を組み合わせているらしいが,囲碁のように各マスに同じ点数が割り振られているわけではないので,本問題に対しては機械学習は有効ではないと考えた.

モンテカルロ木探索において,次にプレイアウトするノードを決めるUCB1値という有名な計算式があるが,それだけでは弱いので,現在のマス8近傍を見て,マイナスのマスに行こうとする場合や相手マス削除の場合,重みをつけるようにした.

前日(10月26日)

実はGUIが完成していない状態だったので,飛行機やバスの移動中や旅館についてからもずっとGUI開発班の手伝いをしていた. 動くものが出来たのはAM2:00くらいだったと思う.ここで初めて指示出しの練習を始める.

一通りの確認をしたあと,エージェント役の二人には寝てもらった.当日,冷静な判断が出来なくなったら困るからだ.

司令塔である僕と,出場はしないMadofukiくんと一緒にパンフレットを眺めて対戦相手の分析をしたり,ソルバと人力で対戦してパラメータ調整を行ったりした.

AM4:30くらいに就寝.

1日目(10月27日)

AM6:00くらいに起床.全く眠気が取れていない状態で試合に臨むことになってしまった.

予行練習が始まる前に,GUIの重要な部分を実装するのを忘れていたことに気づく.自分たちが右側か左側によって見た目が変わるので反転が必要になることを忘れていた. 今後の試合で必要になってくるので実装を始めた.予行演習では反転する必要がなかったのでそこは問題ではなかった.が,GUIが落ちて何も出来なかった. 原因としては,Solverからの候補が送られて来ていない状態でGUIに候補を表示するボタンを押してしまうと死ぬことはわかった.バグを直す時間がなかったので,それを避けるように人間が頑張ることにした.

予行演習が終わったあと反転機能の実装を完了させることが出来た.

1試合目,1ターンごとにSolverが使える時間を長くしすぎたため,間に合わなくなる.人力に切り替えたものの負ける.

2試合目,1ターン目は他のターンよりも長い時間が使えるので,その分Solverも使える時間を増やした.と思っていたら,1ターン目が短くて,他のターンのほうを長くするようにしてしまい指示が間に合わなくなる.人力に切り替えたものの負ける.

3試合目,1ターンに書ける時間は問題なかった.が,盤面の入力ミスがかなり多くなってしまい,正しくSolverが探索が出来ない.GUI上では勝っていたが,当然実際の盤面と違うので負ける. どうも,冷静な判断が出来なくなってしまったのは司令塔である僕らしい.完全に寝不足だ.

旅館に戻ったあと,死ぬほど体調が悪いことに気づき,指導教員から薬をもらった. 奇しくも,この日は僕の19歳の誕生日だった.たぶん,今まで生きてきた中で一番最悪の誕生日だったように感じる.体調最悪だし,予選全敗だし.

予選の結果から,入力ミスが出ないようにGUIの改良が必須であるという意見が話し合いで出たため,3人に開発を丸投げして僕だけPM10:00くらいに寝た.

2日目,僕が冷静な判断を出来るようにするために.

2日目(10月28日)

AM6:00くらいに起床.ぼくはなんとか体調が回復していたので安心した.周りを見渡すと,敷布団も掛け布団も無しに寝ている3人が目に飛び込んできた. 正直,涙出そうになった.いつまで起きて開発していたか分からないが,彼らは相当頑張ってくれたと思う.

GUIの動作を確認するとかなり良くなっていた.1つのボタンで2人のエージェントを移動出来たり,元に戻したりするように出来ていたし,GUIの落ちるバグも修正されていた.

敗者復活戦が始まった.

1試合目.予選では座って指示を出していたが,自分は立ったほうが落ち着くことを思い出したので,椅子を外してもらって立ってやることにした. 入力ミスは少しだけあったので不安だったが,なんとか勝つことが出来た.

2試合目,またも若干のミスがあったので不安だった.結果は負けだった.待機席に戻りながら「あぁ,今年のプロコンは決勝にも上がれず終わりか」と落ち込んでいた. しかし,北九州のWA_TLEくんが,

「この盤面,ルール違反してる!!」

的なことを割と大きめな声で言っていた.驚いたぼくは,スクリーンと配られたデータを確認する.

f:id:kurokoji:20181204015300p:plain
高専プロコン競技部門2日目ストリーミングから引用

なるほど,初期位置の時点で平等じゃないやん. ということで,すぐさま運営に抗議した.この画像は抗議したときの僕の画像.

f:id:kurokoji:20181204020201j:plain
抗議しているときの僕

運営に対するヘイトが溜まっていくにつれ,他高専との絆が深まったのでそこに関しては運営に感謝したいと思う.

10分ほどしてから,運営から「再試合をします」との連絡があった.謎の拍手が起こる.何の拍手だよ.(以下のストリーミングの2:41:38ほどから)

兎にも角にも,再び決勝トーナメントに行くチャンスが与えられた.

2試合目(再試合),落ち着きを取り戻すことが出来たのか,なんと入力をノーミスでやることが出来た.試合が終わったあとに勝利を確信した.結果,勝っていた. 本当に良かった.「最後まで諦めるな」という言葉はこの現象にピッタリなのではないか.

敗者復活戦はリーグリーグという特殊なルールで,6,7チームのうち,勝率が高いチームが2つあった場合,総得点数で復活者を決めるという理不尽ルールが適用されている. なんとか突破できた.なるべく膠着した試合にならないように,人力で補正を掛けたのは良かったと思う.

決勝トーナメント,さっきルール違反に気づかせてくれたWA_TLEのいる北九州と当たった. あのIOI金メダリストと戦えると思うと怖さもあったが,ここで勝てば優勝すらいけるのではないかと内心ワクワクしていた.試合中はほとんどミスもなく,最後まで勝ち負けが分からない接戦だった.

結果,最後のターンで逆転されてしまい4点差で敗北を喫した.あとで彼らに聞くと,最後はWA_TLEくんが天才的な頭で指示を出したので勝てたらしい.流石だ.

反省

良かったこと

  • タスクをちゃんと振れた
    • 昨年は僕のワンマンチームで,ほとんどのプログラムを僕が書いてしまったのでストレスが半端なかった.この反省を生かして,ちゃんとチームメンバーにタスクを振って分散させることが出来た.
  • ちゃんとプログラムで勝てた
    • 最後まで人力でやるチームがある中で,諦めずにプログラムで戦えたのは良かったと思う.

悪かったこと

  • 練習が前日にしか出来なかった
    • 1日目のミスは明らかに練習してないことに起因する.開発を平行にやるよりも全員でGUIを先に完成させてしまったほうが良いような気がする.
  • デスマをしたこと
    • デスマをしない高専は負けると言われるが,体調を壊すと元も子もないのでやめましょう.

感想

運営に対する愚痴

ゲームの内容は良い.ただ謎の人力要素をやめてほしかった.人力要素にしてもあまりにも本質的じゃないヒューマンエラーを生んでしまうような競技はどうなんだろう.来年からは期待したい.

あと,ちゃんと問題をチェックしているのか.procon27でも再試合があったのでもう二度と繰り返してほしくない.この大会には高専生活を掛けて戦っている人もいる.そういう人たちのために真面目にやってほしい.

阿南高専生の補助学生に対する扱いがひどい.ただでさえボランティアなのにどうにかならないのか.

雑多な感想

我々沖縄高専競技部門のチームは「塗、無言、枡目にて。~私はずっとそうやって過ごしてきた~」というものだ. これは涼宮ハルヒの憂鬱長門有希のキャラクターソングである雪、無音、窓辺にて。を改変したものだが,全然言及されなくて悲しくなった.結構いい名前だと思うんだが.

今回は決勝トーナメントまで出場できた.優勝を目標にしていたが,上出来の結果だと思っている. 来年も参加したい気持ちは山々だが,僕は来年5年生で受験勉強や卒研があるので参加しない予定である.後輩にはぜひ優勝を目標に頑張ってほしい.(助け舟くらいは聞いてくれれば全然だすけども)

また,最後までついてきてくれたチームメンバーと,何かとお世話になった教授に感謝の意を表したいと思う.本当にありがとうございました.

最後に,沖縄高専競技部門の努力の結晶であるgithubリポジトリを貼って締めようと思う.みなさんお疲れ様でした.

github.com


明日はみずきち先輩の記事

shimamiz-m.hatenadiary.jp

Ubuntu18.04でneovim(or vim8)+LanguageClient-neovim+clangdでC++の補完をする

普段はMacで使ってますが,TwitterUbuntuで上手くいかなかった人がいるみたいなのでやってみました.

必須なやつ

インストール手順

dein.vimとneovimのインストール手順は省きます.(他に書いてる人がたくさんいるので)

clangd

clangも一緒にインストールしておきます

sudo apt install clang-6.0 clang-tools-6.0
sudo update-alternatives --install /usr/bin/clang++ clang++ /usr/bin/clang++-6.0 100
sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-6.0 100
sudo update-alternatives --install /usr/bin/clangd clangd /usr/bin/clangd-6.0 100

LanguageClient-neovim

tomに書いてください.tomlに書いてない場合,適宜読み替えてください.

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

# vim8用
[[plugins]]
repo = 'roxma/nvim-yarp'
if = "!has('nvim')"

# vim8用
[[plugins]]
repo = 'roxma/vim-hug-neovim-rpc'
if = "!has('nvim')"

[[plugins]]
repo = 'Shougo/deoplete.nvim'
hook_add = '''
let g:deoplete#enable_at_startup = 1
'''

[[plugins]]
repo = 'autozimu/LanguageClient-neovim'
rev = 'next'
depends = ['deoplete.nvim']
build = 'bash install.sh'
hook_add = '''
set hidden
let g:LanguageClient_serverCommands = {
      \ 'cpp': ['clangd'],
      \ }
let g:LanguageClient_loadSettings = 1

nnoremap K :call LanguageClient#textDocument_hover()<CR>
nnoremap F :call LanguageClient#textDocument_formatting()<CR>
'''
hook_source = '''
set completefunc=LanguageClient#complete
'''

結果

同様に,prabirshrestha/asyncomplete-lsp.vimを使ってもできます. これに関してはkutimoti氏が記事を書いてくれているのでどうぞ.

kutimoti.hatenablog.com

また,cquery-project/cqueryなどでも同様です.

kutimoti.hatenablog.com

HiDPI(Retina)環境にReaperを適応させて最高な気分になろう

いつの間にかReaperがHiDPIに対応していたので,記事にすることにしました.

どうもkurokojiです.

HiDPIとは

HiDPIとは「High Dot Per Inch」の略で「1インチあたりのドットがめっちゃある」みたいな解釈でたぶん合ってると思います.(たぶん)
これの何が嬉しいのかという話ですが,HiDPI表示をするとフォントやらUIやらが何かと綺麗に見えます.

例えば200×200の画像と1000×1000の画像を同じディスプレイで同じ大きさで表示するとき,1インチ中に含まれるドットが多い1000×1000のほうが綺麗に細かく表示されることを考えるとわかりやすいかもしれません.

HiDPI表示にする方法はググってもらうと直ぐに分かるので,ここでは書きません.

デフォルトの設定でPCがHiDPI表示になっている場合があって意識していない人もいるかもしれませんね.

動作を確認した環境

  • Laptop: MacBookPro(13-inch, 2016)
  • OS: macOS Sierra, Windows10
  • Reaper: v5.70/x64

HiDPIに対応させる

(注意: v5.34以降にしか対応してないので気をつけてください)

まず,ReaperのForumにあるHiDPI対応したThemeをダウンロードします.

ここの「...ReaperThemeZip」みたいに書かれてるリンクをクリックするとダウンロードが始まります. ダウンロードした「Default_5.0_hidpi.ReaperThemeZip」をダブルクリック,またはReaperにドラッグアンドドロップすると,インストールするぞ的なことを聞かれるので,従順になってやります.

メニューの「Options->Themes->Default_5.0_hidpi」を選択します.

Macユーザの皆さんはここで終了ですが,Winユーザの皆さんはまだやることがあります.

メニューの「Options->Preferences->General->Advanded UI/system tweaks...」をクリックして,「HiDPI mode(Windows 7+)」「Aware(experimental)」に変更します.

Reaperを再起動しましょう.

f:id:kurokoji:20180217010751p:plain:w270f:id:kurokoji:20180217010755p:plain:w300
←デフォルト HiDPI→

フォントの部分を見ると分かると思うんですが,デフォルト状態の時よりもHiDPI状態のほうが美しくなっています.最高!! HiDPI万歳!!!!

これでReaperをHiDPIに対応させて綺麗な画面になりました!! 嬉しい!!

ま,CubaseとかポピュラーなDAWは大抵HiDPIに対応してると思いますが.

もしかして今日って2017年12月26日ですか!? え… ちょっと待って… ということは…

おはよーーーー!! こんちはーーーー!! こんばんはーーーー!! おやすみーーーー!! おきてええええええ

こんちわっす! 輝夜月だよ! kurokojiです.

はじめに

最近バーチャルYouTuberが流行っていますね.バーチャルですよバーチャル.凄い時代になったもんです. お気づきの方もいると思いますが,冒頭のセリフは輝夜月ちゃんから取っています.

ぼくはミライアカリちゃんが好きです.僕は基本的にYouTubeのチャンネルを登録したりしないんですが,ミライアカリちゃんとバーチャルのじゃロリ狐娘YouTuberおじさんキズナアイシロイルカちゃんは登録しています.輝夜月ちゃんは登録していないです.

[追記2018/01/06]今は富士葵さんが好きです.

あとTokyo 7th シスターズを始めました.もう〜〜〜〜めっ〜〜〜〜〜ちゃ曲がエモいのでみんなやってほしい.



CD買いたい.え? アイドルマスターですか? 工藤忍SSRデレステで実装されましたね.

僕はまだ引けてません.工藤忍かわいいですよね.好き…

あとHappy Hacking Keyboard Professional2を買いました.

僕はプロなので,Professionalと書かれているものをChoiceしたわけですね.嘘です.

ICT Advent Calendar 2017の季節ですね.この記事は26日目の記事です.知ってましたか?

1年間の振り返り

大会出場した数で言えば去年に比べると少ないです.が,精神と肉体のつらさで言えば今年が一番ですかね.

出た大会

大会名 結果
第16回日本情報オリンピック(JOI 2016/2017) 本選進出
第28回全国高等専門学校プログラミングコンテスト(競技) 1回戦1位,準決勝15位敗退
パソコン甲子園2017プログラミング部門予選 予選落ち
パソコン甲子園2017プログラミング部門もう一つの本選 ダメ

JOIを今年に入れていいかと言われると微妙ですが,一応今年度ということで.

や〜 なんといっても高専プロコンはきつかったですね.某がチームから抜けたときはどうなることやらと思いましたが,まぁなんとか僕の鋼のメンタルで1回戦1位を勝ち取りました.決勝には出ることが出来ませんでしたが,自分の力でも勝てるんだという自信が付きました.(実際は僕だけでなく,orisano先輩の力もお借りしましたが)

あと高専プロコンのせいで生活リズムが崩れました.設定画面からちゃんと判定調整しようとしたんですが,UIがバグってて無理でした.

SuperCon2017には出ることが出来ませんでした.予選に応募しようかなぁとか思っているときに,インフルエンザを患ってしまい辛かったです.体調管理には気をつけよう!!

PCKに関してはつらいので話しません.後輩諸君は頑張ってください.

昨年欲しかったものたち

昨年欲しかったものを,昨年こう述べていました

このうち,

を手に入れました.

  • 多分Macなかったら高専プロコンは1回戦敗退してただろうなぁと思います.(モチベの問題)
  • サマカニめっちゃ元気でる
  • 藤忍いいよなあ〜〜〜〜(suki♡)

アイドルマスターシンデレラガールズから引用

昨日は委員長りしの記事でしたね.

10riridk0.hatenablog.jp

来年欲しいもの

  • 高専プロコン競技部門優勝という称号
  • お金

これ以外にはほしいものリストがあるので,買っていただいた方には何かしらの特典があります.

やりたいこと

D言語 進行形でやってます.

出来たら高専プロコンの競技部門はD言語で書きたいなぁとか思ってるけど,どうなんでしょ.

VST/AUプラグイン開発

VST/AUプラグインというのはDTMをしている人なら分かると思うんですが,まぁエフェクトとかを掛けるやつです.

種類としては色々あるんですが,まぁEQ(イコライザ)とかコンプレッサ,シンセとか C++で書けるらしいし書いてみたいですね.D言語で書いてる猛者もいそうですが流石にC++で書くことになりそう.

おわりに

最後はこのツイートで締めたいと思います.皆さん良いお年を.

あ,明日はmitoです.

ABC066

ABC066

テンプレは省略

A

sortして先頭2つを取っておわり.

ソース

#include <bits/stdc++.h>
using namespace std;

signed main() {
  int a[3];
  rep(i, 3) cin >> a[i];
  sort(all(a));
  print(a[0] + a[1]);
}

B

与えられた文字列が偶数の長さで,半分に割ったときに左右で一致していれば偶文字列と分かるのでsubstrで分割してあげる.

ソース

#include <bits/stdc++.h>
using namespace std;

signed main() {
  string s;
  cin >> s;
  int res = 0;
  
  while (true) {
    string a, b;
    s.erase(s.begin() + s.size() - 1);
    res++;

    if (s.size() % 2 != 0) continue;
    a = s.substr(0, s.size() / 2);
    b = s.substr(s.size() / 2, s.size());
    if (a == b) {
      break;
    }
  }
  print(s.size());
}

C

反転して末尾にpushしていくのは,先頭と末尾へ交互にpushしていくことと変わらないのはすぐに分かる. 先頭・末尾へのpush,アクセスが高速なデータ構造といえばdequeであるから,この子を丁寧に扱ってあげると答えに導いてくれる.

ソース

#include <bits/stdc++.h>
using namespace std;
 
signed main() {
  deque<int> q;
  int n = in();
  
  rep(i, n) {
    int a = in();
    if (i % 2 != 0) q.push_back(a);
    else q.push_front(a);
  }

  if (n % 2 != 0) {
    rep(i, n - 1) {
      cout << q[i] << " ";
    }
    print(q[q.size() - 1]);
  } else {
    rrep(i, q.size() - 1, 1) {
      cout << q[i] << " ";
    }
    print(q[0]);
  }
}

D

逆元を用いた {{}_n C_r \pmod{a} } の実装が分からず,時間内に解けなかった.

 {N}個の数が必ず一つ以上使われている長さ {N + 1}の数列から,長さ {k}の部分列の個数を出力する問題.

 { {}_n C_r} (組み合わせ)を使う.

そのままやってしまうと重複部分を数えてしまうので,重複分を引いてあげる.

 { {}_{N+1} C_k } (長さ {k}の部分列の個数)

 { {}_{N-d} C_{k-1} } が重複分( {d}は被った2つの数字の数列上での距離)

 {{}_{N+1} C_k - {}_{N-d} C_{k-1} }

逆元と親身に接することで答えがでる.

ソース

#include <bits/stdc++.h>
using namespace std;

lint fact[100010], ifact[100010];

lint pow(lint a, lint k) {
  if (k == 0) return 1;
  lint res = pow(a, k / 2);
  res = res * res % MOD;
  if (k & 1) res = res * a % MOD;
  return res;
}

lint inv(lint a) {
  return pow(a, MOD - 2);
}

lint C(lint n, lint r) {
  if (n < 0 || r < 0 || r > n) return 0;
  if (r > n / 2) r = n - r;
  return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

signed main() {
  lint n = in();
  int N = n + 1;

  fact[0] = ifact[0] = 1;
  rep(i, 1, 100010) {
    fact[i] = (fact[i - 1] * i) % MOD;
    ifact[i] = inv(fact[i]);
  }

  int d = -1;
  int used[100010];
  fill(all(used), -1);

  rep(i, N) {
    int a;
    cin >> a;
    if (used[a] != -1) {
      d = i - used[a];
    }
    used[a] = i;
  }

  rep(i, N) { print((C(N, i + 1) - C(N - d - 1, i) + MOD) % MOD); }
}

1125 -> 1173(+48, Highest!!)

はやいところ水色になりたいです

Bash on Ubuntu on WindowsとWindowsでクリップボード共有っぽいことする

初投稿です.既出だったら許してください. Qiitaに投稿したやつをここにも残しときます

qiita.com

Windows10は2017年4月11日にCreators Updateが配信されました. そこで新しく追加された機能の中に「Windowsアプリケーションとの相互運用」があります.
今回はこれを利用して,Bash on Ubuntu on Windows(以下BoW)とWindowsとのクリップボード共有まがいのことをしてみようと思います.

準備

Windows10側での準備

まずはWindows10でのCreators Updateを行ってください.
そのあとghuntley/pasteboardreleasesから「pasteboard-v1.1.0.zip」をダウンロードしてください.この中の pbpaste.exe を使います.

ダウンロードし,展開したフォルダpasteboard-v1.1.0pasteboard にリネームした後,任意の場所に移動,コピーして環境変数pasteboard-v1.1.0 までのパスを追加します.

ここでは C:\app\pasteboard環境変数に追加しました.

コマンドプロンプトpbpaste と打って動くか確認したら準備は終了です.

BoW側での準備

改行コードや文字コードの変換に必要なnkf をインストールします.
sudo apt-get install nkf でインストール出来ます.Linuxはコマンド一つでインストール出来てとても楽ですね.

nkf --help と打ってヘルプが表示されたら準備は終了です.

作業

さぁ,実際に使うための作業をしましょう.
BoWを起動し,vim ~/.bashrc などで.bashrc を開きます.
ここに以下のコードを追加してください.

alias wcopy='clip.exe'
alias wpaste='pbpaste.exe'

保存して,source ~/.bashrc するかBoWを再起動してください.

使ってみる

windowsで適当なテキストファイルを作りましょう.ここではデスクトップにhoge.txt を作ってみます.

ばっしゅおんうぶんつおんうぃんどうず

ぽよよ

BoWで/mnt/c/Users/{Windowsのユーザ名}/Desktop に移動します.

cat hoge.txt | wcopy と入力するとコピーが出来ます.

その後pbpaste と打つとターミナルにコピーした内容が表示されますが,文字化けしていると思います.そこで間にnkf をはさみ,文字コードを変換してからコピーするようにします.

nkf -w hoge.txt | wcopy
(ちなみに,ここで改行コードをLFに変換してもclip.exe の仕様のせいかCRLFになってしまうっぽいのでwpaste したあとに改行コードを変換する必要があります)

wpaste で確認すると文字化けが解消されているかと思います.

また wpaste > out.txt とすることで wpaste の内容をout.txt に保存することが出来ます.

使い方まとめ

  • cat ファイル名 | wcopy でコピー
  • wpaste でコピーした内容が見れる
    • wpaste > ファイル名 でファイルに出力できる

以上でクリップボード共有まがいを実現する計画は完了です.
もし何かあったら,コメントかTwitterでリプしてくださると助かります.