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人プレイ
- クリアに自身のスキルが必要
- ゲームオーバー→最初から
こういうゲームが好きな一派や、PCゲーを欲してる人々のために面白かった修行ゲーを紹介したい。
真面目に紹介を考えるのがあまりにも難しいので、ポイントだけ箇条書きするから詳しくはリンク先で（投げやり）
Crypt of the Necrodancer
Super Hexagon
- 60秒間迫りくる壁を避け続けたらクリア。全6ステージ。
- 300円と安い。ちなみにサウンドトラックは2ユーロ。
- 実はステージ1で粘りまくるとある種の通しプレイができる。
Getting Over It
- 下半身が大釜のハゲのおっさんがハンマー１本で山の頂上を目指すゲーム。
- 本日Steamで販売開始！
- 日本語訳がイマイチだから有志が作った日本語字幕付きトレーラーを見て
- "a certain kind of person"だと思う人は今すぐやって
- 苦しむ姿をストリーミングしろ
以下ちょっとオススメ度が下がるけど紹介したいやつ
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完で終わった。
Splatoon2 に向けてボイスチャット環境を変えた
Splatoonをやる時はイヤホンとヘッドセットを同時に装着していたので耳が痛くなっていた。
ヘッドセットが壊れたのと、Splatoon2が発売されることを考えてボイスチャット環境を見直した。
ゲーム音とPCの音をミキサーで混ぜてヘッドセットにつなぐことで、ヘッドホンとイヤホンの同時装着から解放され、各音量をツマミで調整できるようになった。
買ったもの
ミキサー： YAMAHA AG03
YAMAHA ウェブキャスティングミキサー 3チャンネル AG03
- 出版社/メーカー: ヤマハ(YAMAHA)
- 発売日: 2015/05/31
- メディア: エレクトロニクス
- この商品を含むブログを見る
ヘッドセット： Logicool G430
Logicool ロジクール G430 サラウンドゲーミングヘッドセット Dolby 7.1 Windows対応
- 出版社/メーカー: ロジクール
- 発売日: 2013/08/23
- メディア: Personal Computers
- この商品を含むブログを見る
ケーブル： 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。使うケーブルが違う。この場合ツマミでゲーム音を調整できないのでちょっとダサい。
ACM-ICPC 2017 World Final 参加記
バンコク大会で3位(サブリージョンで2位)で、World Final参加権を得ました。(バンコク行ってた時はFinal行けると思ってなかった)
東工大・チームpo(僕,yosupo,dnk,コーチhadrori)は5完で34位でした。
ちなみにペナルティ込みだと51位です。
応援・協力して頂いたみなさんありがとうございました。
本番のチームとしてのパフォーマンスはイマイチ目だったので悔しいです。
写真とかはここに多分あります。
icpcnews.com
トップの流れる画像4枚の一つにプラクティス中のチームの様子が映っててビックリ。
コンテスト
(覚えてる限り)
バンコクの時と同じくとりあえず3分割して並列に読むところからスタート。
僕はAから読み始めて、Aは幾何なのでパス、Bは超面倒系か？正確に読めなかったのでパス、Cは概要が簡単でまだ解けそう
Cの概要をよすぽに伝えて、解法を考えてもらった。
が、ここで箱を取るだけで移動できないと思いこんで伝えてしまう大失敗をした。
Cは最小流量制約付き最小費用流で解けるとよすぽに聞いたが、僕が組めないので実装をdnkにパス。
よすぽにスライド最小値覚えてますかって聞かれる→覚えてないのでパス
I問題の概要をよすぽに伝えて、僕は変換規則は単語だと思っていたんだけど、文字と言われてそうだねやるだけだねとなった。
Iを実装してAC。
順位表からFが簡単らしいので読んで概要をよすぽに伝えて、DP解法を貰った。
このときCかDのデバッグでパソコン空いてなかったので紙で実装を詰めるのと空いた時に書くのを往復して通した。
このあとはいろんな問題を読んで、B考えてこれはSATソルバーが無いと無理でしょｗとなって、Gの考察を始めた。
Gの考察中にCの誤読が判明した(絶望)
Cを読み直して正しい概要をよすぽに投げる。
Gはよすぽと相談しながら解いていった。ノートを塗って色々実験した。
サンプルが通ったあと、提出してRE。アサーションに引っかかってそうなのでランダムケースを食わせてみて実験。
気づいていないコーナーケース(これ→###)があって、修正。
それでも通らなくてよすぽにデバッグしてもらって修正、AC。
最後は詰まってるAのライブラリ写経ミスがないか調べたり祈ったりしてた。
反省
個人の部分では、要精進(毎回言ってる)を除くと、
C:思い込みで違う問題を伝えてしまったので最悪
I:ちゃんと読めてたら別に相談しなくてもよかった
F:これくらいの問題は相談しなくても解けるようにしたいかも？
G:これが通せたのは良かった
ラピッドシティと色々
サマータイム込みで日本との時差が-15時間。
日本→デンバーだと東回りで時間が巻き戻る。
日本と比べると緯度と標高が高くて、寒くて乾燥してた。
大統領の顔の彫刻があるラシュモア山で有名。
チームの顔をスキャンしてラシュモア山の彫刻っぽく3Dプリントしてくれたやつをもらえた。
正直どれが誰かを判別するのは結構難しい。
Finalの前の日の夜にダウンタウンに出て肉を食べた。
量が少なすぎるように見えるが、肉が超分厚くてこれでも7oz(200gくらい)。
これはラピッドシティからデンバーに帰る途中の機内から撮影したアメリカン農業
英語
気を使ってくれないと厳しい。
ギリギリできたのがフロントに電話して歯ブラシと歯磨き粉をもらうレベル。
ラピッドシティからデンバーに飛ぶ前、搭乗ゲートで止められて早口で喋られて分からんって言ったら席を替えられた。
(非常口付近の席は非常時にコミュニケーションを取れる人が座る必要があるため)
今後
今年のICPCに参加するかは未定です
RCO presents 日本橋ハーフマラソン 参加記
ハーフマラソン（走らない）
予選
A19位,B9位で総合8位でした。
A:一箇所選んでそこからサイズ8にするのを繰り返す。選ぶ場所は大きい数を優先。サイズを大きくするのは隣接する最も大きい数を選んでいく。
— カードの更新 (@p_shiki37) 2017年3月4日
B:最も近い、到着時スコアが正になるエサを食べるのを繰り返す。ただしスコアが負になるエサは壁っぽく扱う。
— カードの更新 (@p_shiki37) 2017年3月4日
やったことが解説の想定とほぼ同じだった。
www.rco.recruit.co.jp
本戦
RCO presents 日本橋ハーフマラソン 本戦 - RCO presents 日本橋ハーフマラソン 本戦 | AtCoder
A45位,B39位で総合46位でした😇
めちゃくちゃ冷えてます
学生10位まで賞金出るって聞いたとき狙えると思ったんですが本戦全然ダメでしたね・・・
さすがに悔しかったので時間をかけて復習していましたが、本戦1位のmamekinさんのスコアが抜けません
A問題
本戦中
クエリあたりの効率が大事な気がしたので、来た客に対して何手で渡せるか求めようとした。
ここで幅優先探索でなぜかいい感じなると思って実装してしまった。
実際の所、いい客には沢山のタンクを使う必要があるので3手程度しか読めない探索では何も出来ない。これは本番後に気づいた。
ここに2時間半費やして、最終的に下から2番目の点数だったので大事故となった。
練習
まず、来た客にたいしてfillとsellだけで売れたら売る、売れないならskipという貪欲を書いた。
これだけで本戦のスコアの1.5倍が出た。(3.4M点)
その後、
・Dの低い客を無視して小さいタンクにchangeを繰り返す(5.0M点)
・客が来る前に大きいタンクにfillしておく(6.2M点)
でスコアが上がった。
今の手持ちで、Dが一定以上の客が来た場合の稼げる期待値のようなものをスコアにして、fillとchangeを使った1手先のスコアの期待値を最大化するようにしたら、点数が7.3M程度に激増した。
1手読みのような凝ったことをしている人はあまり居なくて、changeやfillのルールとしきい値をうまく調整すると同程度の得点が取れる模様。
B問題
本戦中
実際の道路を参考に一方通行とか交差点を駆使すればいけるんじゃないかと思い、一部のマスでは移動できる方向を制限するようなことを考えた。
Aで時間を食っていたこともあって、結局まともな実装ができずほとんど点が取れなかった。
練習
目的地に向かう動きとランダムに動く動きをうまく混ぜるといい感じになるらしい。
・できるだけ目的地に向かっていくが、停止するのを禁止する。
・同じ距離になる場合はランダムに向きを選ぶ
・行動順はランダムに決める
でかなりいい感じに動くことが分かった。
終盤になったら停止を許可してできるだけ近づくといい感じになる。(6.7K点)
ここで引っかかって抜けられなくなってるやつがまだ残ってるので、5ターン中2ターンランダムに動かすと点数が伸びた。(388K点)
それでもまだ引っかかってるやつが残るので、これをスコアを下げずにいい感じにしたかったが面倒そうなので諦めた。
他の方針として、片側に詰めて並べていって最後にバッと戻す方針というのもあって、それも実装してみた。(497K点)
市松模様に並べて動かしていくという方針もあるが、これはめちゃくちゃ難しそう。
最後の方ビームサーチとか取り入れるともうちょっと落とせそう？ 42663点 / 172手 pic.twitter.com/K7yhZYzECz
— koyumeishi (@koyumeishi_) 2017年3月21日
この問題の設定、見覚えがあると思って調べた所、Asymmetric Simple Exclusion Processと呼ばれているらしい。
反省や感想
今回は最初に間違った方針で、しかも重い実装に取り掛かってしまったので取り返しのつかないことになった。
まず最初に貪欲を考えるという方針が良いような気がする。
しかし、CODE RUNNERの2回目の予選A(交わらないように直線を引くやつ)のように、貪欲よりも頭の良い解法が圧倒的に良い場合もあるのでそのあたりは難しいなあと思った。
短時間マラソンでは、自信のない重い実装はやめたほうがよさそう。
その他：
・東京駅から徒歩2分、乗り継ぎもなかったのでめちゃくちゃ楽だった
・企業紹介と文章要約アルゴリズムについてのスライド？はどちらも面白かった。（途中で置いていかれた）
・懇親会は主にピザ🍕とフライドチキン🍗
