ACM-ICPC 2018 アジア・ハノイ大会 参加記

1日目

飛行機の離陸後にめまいで倒れる。おそらく迷走神経反射というやつで、寝不足やストレスが原因だと思う。
チームメイトに空き席に移動してもらって3座席に横にならせてもらった。すまん・・・

空港からタクシーで移動。
タイでぼったくられたので警戒していたが、無事に相場価格でホテルに来れた。
ホテルに着いてからはサークルKに寄るくらいしかしてない。

隣でemacsでハノイの塔を遊んでる人の影響を受けて、ハノイの塔の解法を出力するよくあるプログラムを書いてた。
ハノイでハノイの塔書いた - ぴろずメモ

ホテルで食べた夕食。

フォーが有名と聞いていたので、フォーを頼んだらタイでも見たようなやつが出てきた。
フォーは米粉を使った麺のことらしい。
味は基本的に野菜炒めなのでおいしい。ソースの正体は分からなかった。

2日目

本来開会式とかがあるんだけど大事をとってホテルで休む。

夕飯でみんなと合流して食べた。’
食べかけの写真しかなかったので画像は上げられない・・・
色々出てきたが基本的においしい。近いジャンルを挙げると中華。パクチーなどの香草が効いてる料理もあって、おいしかった。

3日目

コンテスト

冷えた。結果は24位でした。
フローが見えて実装を拒否した(A)のと、オートマトンとDPだねみたいな問題を実装してバグらせる(I)のをやった。
つまり僕は0完で虚無です。
個人的な反省としては実装力つけたいねって思った。これは1年ちょっと前のWFと同じ反省をしている。
チームとしては慣れない環境で普段の流れやコミュニケーションがうまくいかなかった所がある。横浜ではチームとして良い動きができるようにしたい。

ツアー

陶器で有名なバッチャン村で陶器やその製造過程を見学した。
現地の人が普通にめっちゃ働いてる中で見学してたので、観光というよりは工場見学みたいなイメージになった。

色をぬる前の陶器。全て手作り。

4日目

早朝にタクシーで空港に行き、なんとか帰国する。

帰りはベトナムエアラインだった。

反省

ほぼずっと食欲が無かったのでとても消耗した。
原因がはっきりしないのがつらいが、一番有り得そうなのが異なる生活リズムや環境によるストレスじゃないかな？？
ともかく体調管理に気をつけたい。

ハノイの色々

気候とか

ハノイはあの辺りのイメージよりは寒い。11月だと朝晩やや涼しく、昼はあたたかい、過ごしやすい感じだった。
ただ、交通量がすごいので空気が悪い。ハノイの特にバイクに乗っている人はよくマスクをしている。

道路

交通量が多い。あとバイクが多い。
特に混雑している所では車線の概念が壊れる。
とにかく頻繁にクラクションを鳴らす。事故らないためにやってるんだと思う。

町並み

バスから撮った写真1

バスから撮った写真2

印象的なのを撮ったからこういうのが全てではないんだけど、とにかくLEDやらなにやらで光っているお店が多い。
小さい店舗が並んでいる通りが目立ち、通りごとにファッション・家具・家電などがジャンル別に固まってたりするのが良かった。

タクシーではAndroid端末のYoutubeの再生リストでベトナムの音楽を流していてエモかった。
流行りなのか、ノリノリのダンスミュージック的なやつが多かった。
これがベトナムか～～～～～ってなった（？）

ハノイでハノイの塔書いた

ICPCアジア地区ハノイ大会のためにハノイに来ています

空港についたときの写真（見えないがNOI BAIターミナルの看板がある）

ハノイの塔

ハノイに現物はないらしい。

public class Hanoi {

	public static void main(String[] args) {
		hanoi(3, 0, 2, 1);
	}

	public static void hanoi(int n, int from, int to, int other) {
		if (n == 1) {
			move(from, to);
			return;
		}
		hanoi(n-1, from, other, to);
		move(from, to);
		hanoi(n-1, other, to, from);
	}

	public static void move(int from, int to) {
		System.out.println(from + "->" + to);
	}

}

0->2
0->1
2->1
0->2
1->0
1->2
0->2

体調を崩した

やばい

先々週くらいのCODE FESTIVALの話

まともな参加記を書けず。
今年で（少なくとも選手としては）最後の参加になるんですが、無事5年間連続出場＆5着のパーカーゲットを果たせたのは嬉しかった。
今回も入賞できなかったので賞金は一度ももらえることなく終わった。残念。

ICPC国内予選2018

2年ぶりのICPC参加でした。
nariさん、rianさんのチームに入ってnarianZとして参戦しました。個人的には「なりあんズ」と読んでほしいです。

A問題

ファイル入出力の準備をしている間に、問題が印刷され、自明と言われた。
問題を読んだら自明だったので出した。

Java + Eclipseでやっているとき国内予選フォーマットはどうやるのが早いんでしょうね・・・？
標準入力からファイル名を読んで".txt"をつけたファイルに書き出すようなテンプレを用意していました。

D問題

nが9以下という不穏な制約があり、枝刈り全探索をしようねという問題だと分かる。
サンプルの最後に最大ケースがあった。（優しい）
実装では少々バグらせるが以降の問題の解法ができる前だったので軽症。

その他

他の問題はチームメンバーがやってくれたので僕は解法の説明にうなずいたり、実装画面を後ろから眺めていました。
（Eのデバッグにちょっとだけ口を出した）

感想

自明と軽考察しか解いてないので最低限の働きでしたが、誤読とか大失敗はなかったので良かったです。
2位は完全にチームメイトが強すぎる～～～

就活は落ち着いたので
・講義（なんとまだ単位が足りない）
・研究
・ICPC
3本立てで学生生活最後を頑張りたいですね

サマーセールだ！ 2018上半期最も遊んだSteamゲーTop5

上半期くらいで遊んだゲームをまとめようと思っていたら丁度サマーセールがやってきたので書きました！

1.『Slay the Spire』　（アーリーアクセス）

37%オフ 995円 111時間プレイ

デッキを組みながら塔を登っていくカードゲーム＆ローグライクゲー。1プレイはラスボスまで行っても1時間くらいだが、毎回展開が大きく変わるので無限に遊べる。アーリーアクセスだがすでにコンテンツが充実していて、週1のアップデートもあるのでセールの間に買おう。英語でも短い文が読めれば遊べるが、有志の翻訳もあるので日本語でも遊べる。

2.『Opus Magnum』

25%オフ 1,537円 39時間プレイ

あの熱狂的なファンも多いZactronicsの最新作。アームなどの機械を使って分子を目的の形に変換するゲーム。単にクリアするだけでなく、省スペース・低コスト・短時間といった目標で最適化する、あるいは美しさを求めて設計する楽しみがある。このゲームで最高なのはGIFエクスポート機能が内蔵されていることで、完成した機械をGIFで眺め続けたり、あるいは人に自慢することができる。日本語訳もちゃんとしていて遊びやすい。

3.『Celeste』

20%オフ 1,584円 31時間プレイ
ドット絵やプラットフォーマーが好きなら買い。難易度高めなアクションゲームを求めている人にはうってつけ。特に各ステージで集められるカセットを拾うことで解禁される「B面」や隠されたハートを集めることで進めるようになる8面などは非常にやりごたえがある。英語でやってたらストーリーの理解が怪しくなったが、それでも6面以降の盛り上がりは良かった。日本語も対応。アクションゲームが苦手な人に補足すると、1面はよゐこもクリアしていたし、アシストモードもあるので多分なんとかなる。
Switchでも発売中。あとサウンドトラックもおすすめです。

4.『Heroes of Hammerwatch』

20%オフ 976円 30時間プレイ

ダンジョンに潜る→死ぬ→町を強化する→新しいスキルを習得→ダンジョンに潜る・・・
オンラインマルチプレイに対応。他のクラスの仲間と組んでダンジョンを攻略するのはかなり楽しい。人数が多ければ簡単になるわけでもなく、蘇生回数は「ソウルリンク」システムで実質的に制限されているし、ザコ敵やボスの体力も増える。その辺りよく考えられていて面白いと思う。時々バグがあるが、まだ頻繁にアップデートを続けていてどんどん良くなっている。

5.『Info the Breach』

20%オフ 1,216円 27時間プレイ
あのFTLを作ったSubset Gamesの新作。シミュレーションゲームとローグライクを合わせたようなゲームで、不思議とめちゃくちゃバランスが取れている。毎ターン先に敵が移動して攻撃対象を選ぶのだが、そのターンでうまく敵の位置をずらすと攻撃を外させたり、敵を同士討ちさせることができる。「このターンノーダメージで越せるかな？」とか考えるのはシミュレーションよりもパズルに近いところもある。頭を捻って窮地を切り抜けていく面白さが体験できる。オススメ。
ちなみに前作の宇宙船ローグライクFTLはなんと245円！

おまけ：500円以下のゲーム

Terraria

store.steampowered.com
サマーセールと言えばワンコインTerrariaみたいなところがある。500円の割には遊べすぎる。1人MMOをやっている気持ちになれるゲーム。
ていうかマルチやりたい。

Crypt of the NecroDancer

Save 80% on Crypt of the NecroDancer on Steam
Steamゲーで一つだけしか紹介できないとしたらこれを選ぶかもしれない。難しいゲームなんだけど理不尽ではないし、練習モードが存在したりとちゃんとステップアップできるようになっている。実績の解除を狙い始めるとめちゃくちゃ難度が高く、とにかくやりごたえがあるゲーム。セールのうちにサウンドトラックごと買ってしまうのがオススメ。そうしないと僕のようにゲーム本体よりサウンドトラックの方に何倍も払っているという事態になる。

I am Bread

store.steampowered.com
僕はヘンテコ物理アクションゲームのファンです。ヘンテコ操作に習熟して巧みに自らを焼きたくないですか？焼きましょう。192円でパン買うくらい安いです。
500円より高いですが壺おじさんやヘビになるのもまあまあオススメです。

PCでできるオススメの修行ゲー

修行ゲー

何度も繰り返し挑戦して、少しずつ上手くなっていって、最終的にクリアする。
この手の楽しみ・達成感をもたらすある種のゲームを個人的に「修行ゲー」と呼んでる。

修行ゲーを構成する要素には次のようなものがある：

1. 1人プレイ
2. クリアに自身のスキルが必要
3. ゲームオーバー→最初から

こういうゲームが好きな一派や、PCゲーを欲してる人々のために面白かった修行ゲーを紹介したい。
真面目に紹介を考えるのがあまりにも難しいので、ポイントだけ箇条書きするから詳しくはリンク先で（投げやり）

Crypt of the Necrodancer

store.steampowered.com

• リズムに合わせてダンジョンを進む、ローグライク・リズムゲーム。
• 普通にステージクリア制のゲームとして遊べるのでこの中では初心者向け？

Downwell

store.steampowered.com

• 攻撃と減速を兼ねるガンブーツで井戸を降りていく高速アクション。
• 普通に面白いアクションで300円と安いのでぜひ。

BLOCKSUM

BLOCKSUM official website

• せり上がるブロックをくっつけて消す足し算アクションパズル。
• 非Steam。フリーゲーム。
• 難易度の上がり方とか曲の盛り上がり方が好き。

Super Hexagon

store.steampowered.com

• 60秒間迫りくる壁を避け続けたらクリア。全6ステージ。
• 300円と安い。ちなみにサウンドトラックは2ユーロ。
• 実はステージ1で粘りまくるとある種の通しプレイができる。

Getting Over It

store.steampowered.com

• 下半身が大釜のハゲのおっさんがハンマー１本で山の頂上を目指すゲーム。
• 本日Steamで販売開始！
• 日本語訳がイマイチだから有志が作った日本語字幕付きトレーラーを見て

www.nicovideo.jp

• "a certain kind of person"だと思う人は今すぐやって
• 苦しむ姿をストリーミングしろ

以下ちょっとオススメ度が下がるけど紹介したいやつ

FTL

store.steampowered.com

• 宇宙船シミュレーションローグライクゲーム。
• １プレイが長いのと運要素強いので上に入れなかった。

海腹川背

store.steampowered.com

• フックアクションの名作。
• 攻略サイトフル活用してもクリアは大変だった。

東方天空璋

store.steampowered.com

• 弾幕STG。
• 東方シリーズ最新作。比較的簡単なのでシリーズ入門でも大丈夫だと思う。

Super Meat Boy

store.steampowered.com

• ステージクリア制ジャンプアクション。やたら難しいので修行度は高い。

I am Bread

store.steampowered.com

• 物理演算セルフトーストゲー。修行というよりはバカゲー。

CODE FESTIVAL 2017 感想と本戦Dの貪欲パート

今年はトーナメント勝ちました

ICPC以後競プロをあまりやっていなかったのですが、やはりオンサイトはワクワクします。

予選

予選A→頑張ったら構築ゲーに勝利して通過
予選B→寝てた
予選C→ボロボロだった

予選Aからちゃんと出ておいて正解だった

本戦

前日十分に寝れず、つらかった。

A問題

正規表現👊　一発AC。

B問題

ABC...のようなパターンしかない。一発AC。

C問題

最小値の最大化を最大値の最小化と思い込みタイムロス。
最小値をk以上にできるかという判定問題を考えれば、2-SATに帰着できることは分かったがどう考えても500点の難易度ではないので実装を考えた。
結局色々考えたあげく、2人の間の関係を(同じ符号のみOK/異なる符号のみOK/どちらでもOK)の3つに分け、dfsして解いた。2-SATに還元したほうがマシだったまである。

D問題

どう考えても順序が必要なので、H順,P順がダメな事を確かめてH+P順を考えたがうまく証明できない。
めちゃくちゃ色々考えて詰まる。
残り1時間くらいになったので仕方なく他を読む。

F問題

Eは回文というキーワードを見た瞬間無理と感じたので、構築ゲーのFを考える。できなさそう。残り30分くらいでDに戻る。

D問題

実験でどうもH+P順が正しそうなのでDPを実装中。バグって時間切れ。
終了後15分くらいで解けた。

4完を目標にしていたが3完でレートも40以上減ってとても悲しい。

Dの貪欲部分の証明

2以上の最適解が存在すると仮定する。
この時、座布団を置けない人は後ろに固めても最適である。以降座布団を置く人のみを考える。
連続する2人に注目する。この2人が座布団を置く前の座布団の枚数を,先に座布団を置く人を、後に置く人をとおく。
この時次が成り立つ。
かつ
ここで、と仮定し、この2人の順序を入れ替えても同じ人数で座布団をおけること、すなわちを示す。


ゆえに、座布団を積む人は昇順に並べ替えてもよい。

トーナメント

本戦が3完で冷えたため、もっとも下のグループ6に入った。

Round1

なぜかC,D問題の2問。
C問題を開く。カッコ列と言えばDP。
カッコ列１つでどうこうするのかと思い込み誤読する。
素直なDPのだとやばいが、カッコ列に対応するxy平面上を動く点を考えると、原点近くの5つくらいしか要らないことに気づいてなんとかなった。
遷移を書くのがややしんどかった。
D問題は最小の部分点（パスの場合）を目指したが、ギリギリ提出してWA。
勝ち上がった。

Round2

A問題を読む。概要を理解するのが少し難しい。
部分点をよく読むと200点はただ最小全域木を実装すれば取れることに気づき、提出。
Aでさらに点を取れる気がしなかったのでBへ。
B問題、k=1の操作が左シフトなことには気づくが、k=n-1は全く思いつかなかった。
最初の部分点を幅優先探索で取ろうとしたが時間切れ。
200点のみだが早めだったため勝ち上がり。

Round3

Round2までの順位表から、グループ6では早解きだけしてれば勝てそうというのが分かったので、とにかく小さい点から素早く取る作戦にした。
Eの200点(1): 愚直に距離（演算はmin）を計算するだけ。面倒なのでダイクストラを貼った。
Fの200点: bitDPで全列挙して条件に合うやつをカウントするだけ。
Eの200点(2): コストが2の辺のみで連結成分を考えて、うまく計算するだけ。UnionFindを貼った。
余った時間は祈ってた。
結果作戦大成功、2位でトーナメント勝利。
１位は本戦なぜか0点の赤コーダーなので実質優勝（？）
4年間CODE FESTIVALに出て壇上は実は初めてな気がする。本戦がダメだった分ちゃんとパフォーマンスを出せて良かった。

リレー

チーム内の本戦順位は下から2番めだったが、開始直後に雑に問題を取ったのでD問題を読んだ。
そこそこ考えたが、1と2を含む連結成分のうち大きい方に残りの頂点全部くっつけてクリークにすればよさそう。
と、考えた所でJ問題の公式が降ってきて実装を任された。
万が一公式が間違っていたら大変なことになるので不安だったが、断れないのでやった。
実装中にキーボード操作が一切効かなくなるトラブルが発生してパソコン再起動（つらい）
実装もintをintで割るなどして3WAくらい出し、パソコンスペースで時間を食いすぎてしまった。
後半戦で実装が詰まる状況になったのでこれは良くなかった。
JをACしてからは隣のrianさんとEの考察をしていた。式変形していたらそれっぽいのが出てきたので、rianさんと確認し、海外プロのお墨付きも貰って良さそうだとなった。
Eは通ったので一安心。
実験ゲーや構築ゲーが残っていなかったので残り時間は祈っていた。
チームとしては8完で終わった。

雑多な感想

• 秋葉原UDXを知らず、電気街口から大通りの方に歩きながらGoogle Mapを開いてびっくりした。
• 参加人数が前年から200人→100人になったり、一部コンテンツが縮小してしまったのは残念だが、海外参加者が世界中から集まったり、置いてあるお弁当が強そうだったりと良くなっている点もあった。（まい泉とかね）
• 席が映像や音響をやってる人と超近く、真後ろに高そうな機材が並んでいた。機械を眺めるのは面白いが、近くを通ったり飲み物を運ぶのは怖い。
• 今年もCODE FESTIVAL開いてくれたリクルートに感謝🙏
• じゃがりこチーズ味が戦利品バッグに入りっぱなしなことを今思い出した

Splatoon2 に向けてボイスチャット環境を変えた

Splatoonをやる時はイヤホンとヘッドセットを同時に装着していたので耳が痛くなっていた。
ヘッドセットが壊れたのと、Splatoon2が発売されることを考えてボイスチャット環境を見直した。

ゲーム音とPCの音をミキサーで混ぜてヘッドセットにつなぐことで、ヘッドホンとイヤホンの同時装着から解放され、各音量をツマミで調整できるようになった。

買ったもの

ミキサー： YAMAHA AG03

YAMAHA ウェブキャスティングミキサー 3チャンネル AG03

ヘッドセット： Logicool G430

Logicool ロジクール G430 サラウンドゲーミングヘッドセット Dolby 7.1 Windows対応

ケーブル： audio-technica ATL462A/1.5
http://www.yodobashi.com/product/100000001001251353/

ゲームの音(GamePad, Switch, AVT-C875から)とPCからの音をパソコンの外で混ぜたいのでミキサーを使用する。
ミキサーについては全然分からなかったので、先例があった(Splatoon での VC 環境について - モノトーンの伝説日記)AG03を買ってみた。
AG03のブロック図は下の記事のリンクにあるので、参考になるかもしれない。
http://www.dtmstation.com/archives/51931706.html

ヘッドセットはPCでFPSなどをやることを考えてサラウンド対応のものにした。
ステレオミニプラグで接続できることを確かめる。(USBのみのやつはダメ)

接続例

接続はこんな感じになる。

背面でUSBケーブルがPCと繋がっている。
ヘッドセットは中央につなぐ。
ゲームからの音声は、ステレオミニプラグ→モノラル標準プラグ×2の変換ケーブルを使って上部2/3につなぐ。

自分の声を聞かないようにするために右下のMONITOR MUTEボタンを押す。

TO PCのスイッチはDRY CH 1-2Gにする。その他にするとゲーム音などの余計な音もPCに送られる。
この場合一番左のスライダーはマイク音量に関係しない。マイク音量の調整は中央左のツマミを使う。
(あとエフェクトをかけられなくなる)

一番下のツマミの左がゲーム音、真ん中がPCからの音、右が全体の音に対応する。

ゲーム音はAUXを通して入れてもOK。使うケーブルが違う。この場合ツマミでゲーム音を調整できないのでちょっとダサい。