2016-12-19

ARC066/ABC050 D: Xor Sum - OEISからの解法

問題解説

コンテスト中に解けませんでした。

問題

D: Xor Sum - AtCoder Regular Contest 066 | AtCoder

解法

小さい $N$ に対して実験してOEISで検索します。
2,4,5,8,10,13,14,18,21,26,28,33,36,40,41 - OEIS

A007729が答えになりそうですが、残念ながらいい感じに求める式は見つかりません。
しかし、この数列はA002487の部分和で表されることが分かります。

A002487の一般項は次にように表せます。
$\begin{eqnarray} s(n) = \begin{cases} n & (0 \leq n \leq 1) \\ s(n/2) & (n \geq 2, nが偶数) \\ s((n-1)/2) + s((n+1)/2) & (n \geq 2, nが奇数) \\ \end{cases} \end{eqnarray}$

これの部分和 $f(n)=\sum_{i=0}^n s(i)$ を頑張って式変形します。

$n \geq 3$ のとき、
$s(0)=0$ であることを用いて、
$\begin{eqnarray} f(n) & = & \sum_{i=0}^n s(i) \\ & = & s(0) + s(1) + \sum_{i=1}^{\lfloor n/2 \rfloor} s(2i) + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} s(2i+1) \\ & = & s(0) + s(1) + \sum_{i=1}^{\lfloor n/2 \rfloor} s(i) + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} \{s(i) + s(i+1)\} \\ & = & \sum_{i=0}^{\lfloor n/2 \rfloor} s(i) + \sum_{i=0}^{\lfloor (n-1)/2 \rfloor} s(i) + \sum_{i=0}^{\lfloor (n-1)/2 \rfloor +1} s(i) \\ & = & f(\lfloor n / 2 \rfloor) + f(\lfloor (n-1) / 2 \rfloor) + f(\lfloor (n+1) / 2 \rfloor) \end{eqnarray}$

これであとはメモ化再帰で $f(N+1)$ を出力すると解けます。

ソースコード

import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		System.out.println(f(n+1));
	}
	static HashMap<Long, Long> hm = new HashMap<>();
	public static long f(long n) {
		Long memo = hm.get(n);
		if (memo != null) return memo;
		if (n <= 2) {
			return n;
		}
		long res = f(n/2) + f((n-1)/2) + f((n+1)/2);
		res %= MOD;
		hm.put(n, res);
		return res;
	}
}

計算量

メモ化再帰の遷移に注目すると、三つ又に分かれているように見えます。
$n$ を $2$ で割っていっているのでいつかは $n$ が小さい値になることは分かりますが、途中で状態数が爆発しないのでしょうか？
実はこの遷移では大丈夫です。

ある呼び出しの深さにおいて、引数 $n$ の取りうる値が $x$ 以上 $x+a$ 未満だったとします。
次の深さにおいて、引数 $n$ の取りうる値は $\lfloor (x-1)/2 \rfloor$ 以上 $\lfloor (x+a+1)/2 \rfloor$ 未満になります。
この幅はfloorを無視して $(a+2)/2$ 程度になるので、引数の取り得る値の幅は結局定数になります。

したがって計算量は再帰の深さと同じ $O(\log N)$ です。
再帰の形が $f((n+a)/b)$ (ただし $b(>1),a$ は定数)の形の時は安心してよさそうです。

2016-12-10

CODE VS for STUDENT 参加記

プロコン参加記マラソン CODE VS

初戦でkimiyukiさんに負けてベスト8です😇

AIの概要はこっちに書いてあります。
piroz.hatenablog.com

もう決勝からだいぶたっていてタイムシフトも消えてしまったのでかなり記憶が薄いです。
権利上の関係とかで動画にはならないのかな～～～

決勝当日

チームラボ本社は水道橋にある。
行くのは二度目だが出口を間違えて知らないところに出た。
その日東京ドームでライブがあるせいかわからなかったが人が多かった。

12:00に本社に突入したらまだリハーサルをしていてダメだった。(受付開始12:30と書いてあったので自分が悪い)
(どうでもいいけどエレベーター降りるとすぐオフィス内でビビる)

昼を食べてなかったので駅の方まで戻ってすき家で食べて、12:30に再突入した。
カメラやら配信機材やらが色々あってすごい。

Normal

人が足りてない・・・😇
上位の方はちゃんと探索して連鎖してた。見てて面白かった。

Hard

第一回戦第二試合が僕 vs kimiyukiさん。
予選では割と勝ち越してる相手だったのですがダメでしたね・・・
予選から決勝までの間に全然強化できなかったのが悔しいです。
コメントでも言ったけどトーナメントなので初戦負けるとバイバイで悲しい。

僕のAIは200以上そんなに出ないんだけど他の人たちは250～500くらいをポンポン出し、1000まで叩き出していたのでもうこれは勝てそうにないという感じだった。

当日色々

参加者全員にスポンサーから色々配られていたが、スクエニからはスライムが描かれたペットボトルカバーが貰えた。
懇親会は酒＆ピザだった。

決勝AIの反省

前回の記事の通り機械学習がバグっていてパラメータがおかしい可能性があった。
また、ハイパースレッディングが有効だったので、2スレッド実行すれば若干速くなるのではと2スレッドにしたら競合していた(最悪)。

他の参加者と話していて結局敗因は何かということを考えた。
今回のゲームの場合、評価関数を凝るよりはいかに探索を頑張るかという所のほうが重要なんだと思った。
連鎖のチェックをする場所を限定して盤面の評価を速くしたり、発火ターンを限定して読む幅を増やすのが効果的なのだと思う。
これらは試してみて今のAIと戦わせてみたい。

結局機械学習でAI強くできたの

冷静に100先をさせたところ、ベースの評価関数よりは明らかに強くなっていた。

	ベース	決勝提出	バグ修正
ベース	-	72-100	61-100
決勝提出	100-72	-	88-100
バグ修正	100-61	100-88	-

(これらAIはパラメータのみが異なる。ただし、ベースはパラメータすべて0と考える。)

最後に

CODE VSで入賞したいからまた開催してください～～～～～

ここからは予選～決勝のログ(を整理したもの)です。

2016-12-07

CODE VS for STUDENT で作ったAI、「MazAI」の紹介

プロコン参加記マラソン CODE VS

CODE VS for STUDENTの決勝用AI提出が完了しました！

残念ながら、予選通過したバージョンからいい感じの改良ができず、実質的にはわずかなバグ修正だけで終わってしまいました。
予選通過したときの記事にも貼ったAIの動画がこれです↓
youtu.be

提出したAIの内容を紹介したいと思います。
名前は「MazAI」です。
決勝AIは名前が「MazAI-Z」になっています。マザイゼットです。

提出したAIの概要

敵の盤面は見ずに、一人ゲームとして処理した。

評価関数

すべての列に1～9のブロックを落とし、最大スコアの連鎖を記録。
スコア = 連鎖数 * 1000 + log_10(連鎖スコア) * 1000
また、一定数以上の連鎖をしたノードには送ったオジャマ数*1000点を加算する。

このスコアに以下の値に係数をかけたものを足す。

予告オジャマ数
フィールドのオジャマ数合計
フィールドの色ブロック数合計
和が10になる特定の配置の数(5種類)

f:id:piroz95:20161206230025p:plain

各列の高さ(10列)
各列の高さの差の絶対値(9列)
最大連鎖
最大連鎖の消費ブロック数 / 連鎖数
最大連鎖の発火点の高さ

合計30次元

係数は機械学習を使って決めた。
詳しくは後述する。

探索

送れるオジャマの数が200を越えたら即発火する。
ビームスタックサーチ(chokudaiサーチ)を用いた。
ハッシュ(zobrist hash)による重複消去を実装した。
最初の発火までは深さ13・時間2500ms。
発火後は、深さ10・時間1500ms。
発火したノード(お邪魔を一定以上送ったノード)はそれ以上展開せず、ビームとは別に保存する。
発火ノードが存在しない時はビームサーチの結果を普通に使う。
発火ノードが存在するとき、そのいずれかに向かう。
発火ノードのうち、スコアと発火ターンで見て下位互換になっているものは候補から消しておく。
また、送るオジャマの数が200を超える発火ノードは最も早いものだけ残す。
向かうノードはノードのスコア/1.11^ターン数が最も高いものを採用した。

評価関数の係数の自動調整

「将棋機械学習」でググったら出てきた
近年のコンピュータ将棋の急速な伸びの理由は？ | やねうら王公式サイト
に影響を受けてやってみました。
（けどよく分からなかったので助けてほしいです。）

$X$ を盤面とする。
$X$ の特徴値ベクトルを小文字で $x$ と表すことにする。
特徴値を計算する関数を $\phi$ とすれば $x=\phi(X)$ とも書ける。

ベースの評価関数の評価値を $f(X)$ ,パラメータベクトルを $w$ とする。
機械学習付き評価関数の評価値 $f'(X)$ を次のようにする。
$f'(X) = f(X) + w^T x$
( $w^T x$ は $w$ と $x$ の内積)

このとき、浅い探索の評価値を深い探索をしたときの評価値に近づけるということを考える。
$X$ からベースの評価関数の値を用いて $i$ 手読んだ結果の最良の盤面を $X_i$ と表す。
$s,d$ を $s < d$ を満たす定数として、 $w$ を調整して次の式を最小化したい。
$\{f(X_d) - f'(X_s)\}^2$
つまり次式の最小化になる。
$\{f(X_d) - f(X_s) - w^T x_s\}^2$

ここまで1つの盤面 $X$ について考えたが、実際は複数の教師データについていい感じになるようにする。
盤面 $X$ に対して教師データを $(x_s,f(X_d) - f(X_s))$ とする。
$N$ 個の教師データを $\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots,(x^{(N)},y^{(N)})\}$ と表すと、
$w$ に対する目的関数 $L(w)$ は
$L(w) = \frac{1}{N} \sum_i^{N} (y^{(i)} - w^T x^{(i)})^2$
で表されて、これを最小化する。

これは微分可能な連続最適化の問題になり、勾配降下法を使うことができるが、勾配の計算が重いので代わりに確率的勾配降下法(SGD)を用いる。
SGDの学習率の更新にはAdaGradを使った。

あとは、特徴量に正規化をかけたりL2正則化を入れた。

$s,d$ は、最終的には $s=0,d=5$ とした。
教師データは実際の対戦における自陣の盤面を使用した。

機械学習失敗話

正直、よく分からずに使っている部分があってパラメータおみくじみたいになった。
正規化を入れないとヤバかった気がする。(追記：正規化がバグってた)
改良したAIの対戦から教師データを取ったらなぜか弱くなったことがあった。
教師データの数を増やしたら弱くなったことがあった。
特徴量は2000次元くらいのものも試したが最終的に30次元の方が強かった。
- 30次元の特徴量は色々な特徴量をぶちこんだ所から係数が大きいものを人力チョイスした。
ここを書いていて不安になって機械学習なしバージョンと戦わせ始めたら連敗した
- 追記：2-3くらいの割合で負けた

追記：
takaptさんにtwitterでリプを頂いてやり取りしていたら、正規化する時に分散の計算をバグらせていたことが分かりました。
takaptさんありがとうございました。
$\sigma^2 = E(X^2) - E(X)^2$ を計算するところを1箇所 $N$ で割り忘れていて[\sigma^2 = N E(X^2) - E(X)^2]を計算していました。
このバグった正規化の結果から何を学習していたのかは謎です。
次元数を減らして強くなったというのは、特徴量の計算時間が減って探索ノード数が増えたという可能性があります。
悲しい・・・

週末に決勝

チームラボ本社で決勝😇
live.nicovideo.jp

2ヶ月くらいの間どういうことを試していたかの記事はまた別に書きます。

2016-11-27

CODE FESTIVAL 2016 参加記

プロコン参加記

予選

Aで通った．さすがに予選は余裕．

3日前～1日前

研究会での発表で神戸に行って，ついでに姫路城を観光してきた．
その後だったので忙しいと思った．

1日目

新橋からベルサール汐留まで歩いて10分位．

今年もコミュ障不動の構えをやっていたのでコンテストまで暇だった．

海外勢も来ていて英語のアナウンスがあったりして，グローバル感があった．

コンテスト

ABはやった．
Cはちょっと難しい．出力を間違えてWA．ペナルティはないのでどうでもいい．
Dはなぜか半分くらい通らなくて激ヤバ．飛ばしてEへ行く．
Eは部分点が調和級数でNlogNになるタイプのDPだったので取った．
満点は難しそうだったのでFへ．
Fは数え上げだったがかなりスムーズに解けた．コンテスト中一番のファインプレー？だったと思う．
Gは苦手そうだし部分点がないからパス．
Hは部分点だけ取るつもりが誤読で時間がかかった．RMQをStarrySky木にして部分点．
Dを通してないのがさすがにおかしくて，いや合ってるだろうと思ったところを丁寧に書き直したらACしては～～～～～～～～～となった．
おしまい．
35位，日本枠17位．
これはかなり良くて，全体順位で言っても1年目(44)，2年目(53)より良い成績だった．
Dでハマらなければ1時間弱増えたかもしれないが他に解ける問題があったかは微妙だ．
I,Jは読んですらいない．

コンテンツ

tourist公演．たまに簡単な文や単語が聞き取れるくらいだったので通訳があって助かった．
飛行機で飛び回ってるという話でめっちゃ忙しそうだと思った．

今年はバッジ集めとかスタンプラリーがないのでのんびりした．

今年の夕飯は良かった．早めに行ったので寿司が食べられた．

Ponanzaの山本さんの公演を聞いた．
これは是非CODE VSに活かしたい．

続いて秋葉さんの公演，ペアプロを見た．
あのつくば大会の問題は面白かった．その時の記事に比が奇数:偶数なら勝ちと書いた気がするけど，2で割り続けて奇数:偶数なら勝ちだったようなので間違っていたかもしれない．

エキシビションはチーム戦なのに0完が2組出て見ててつらそうだった．

今年はホテルまで自力で歩くようでちょっとビックリした．Google Mapに助けられた．
銀座国際ホテルだった．

ホテルは鍵の開け方が分からなくて，他の参加者と開かねえなってやったあとまた別の人に助けられた．
ユニットバスがちょっと広い所が良かった他は普通？

コンビニで牛丼とSpriteを買ってダラダラtwitter見て優勝した．

2日目

十分な睡眠時間が確保できた．
ホテルから会場までは10分くらい．送迎のバスがない分むしろ去年より余裕があったかもしれない．

トーナメント

ラウンド1．Aは苦手そうでパス．
B問題の普通のDPを多倍長👊したら600点が帰ってきて通過出来た．
O(N^3)だと思ったので600点まで取れるとは思っていなかった．
Aは残りの時間で書いたけど最小の部分点さえ取れなかった．

ラウンド2.Aはすれ違う場合がどうなるのか不明で，自明な200点を取った．
Bも読んだけど難しそうで，もしかしたら400点対決になると思って400点を取りに行った．
B200点を提出している間により大きいケースを解く方法を考えていたが嘘しか思いつかなかった．
Bの部分点が落ちていてビックリした．逆転ができそうになく終了．
Aは終わった後よく考えると，ランダムに移動する方は止まる動きをしないので最初に調整して右に動くだけだった．それなら簡単だった．

ラウンド3.オープンコンテストになったので勝ちに行く方より満点を目指した．
AはNKlogNのDPが思いついて書いた．どうも間に合わなくてlogを削る必要があったが分からなかった．
Bは時間も無かったし部分点を取って終了．
Aはスライド最小値を使えばlogを削れると知ったのでスライド最小値をライブラリ化した．まだ原理は分かってない．

コンテンツ

まい泉の豚ロースカツ弁当？がおいしかった．

あとはトーク系を聞いていた．

リレー

B(Um_nik)チームでやった．
最初は日本人ペアで5問潰すという作戦でやった．
僕のペアはEを担当した．gcdを取ってゴニョる問題だと分かったが，2人ともgcdを空で書けないのでhogloidさんに教えてもらった．
Iを読むが全然わからない．奇素数は解けるなあとか考察してたけどそもそも奇数で解けるらしくこの問題僕は向いて無いなと思った．
Kは問題の意味が分からなかった．
Jが手を付けられそうな雰囲気があった．黒に変えられる白は全体の1/3くらいということと，hogloidさんのヒントから，一つ黒を置く毎に黒の連結成分を3つ減らせばよさそうということが分かった．
すると3列ごとにタテに真っ黒にして，ヨコに適当に真っ黒にするとよさそうなことが分かり，自分が実装する流れになった．
実装を詰めずに書き始めたらかなりバグらせた．(黒い所を塗る，同じところを2回塗るetc...)
助けてアピールをしながらsubmitデバッグをしてた．
一番右の列を埋めたほうがいいよというアドバイスを貰って，実装してN=1000を試したら足りたので投げてAC.

全体の感想

良問がガンガン消費されてヤバイと思った（特にトーナメント）

2016-11-17

ACM-ICPC 2016 アジアバンコク大会参加記 (タイ旅行記)

ICPC プロコン参加記

f:id:piroz95:20161117120607j:plain
つくば大会で悔しい思いをしたのもあり、なんやかんやタイに行くことになって、行きました。

チームpoは僕piroz,yosupo,dnkとコーチのhadroriで行きました。
バンコク大会に参加するにあたって特にコーチのhadroriさんや東工大の関係者には色々助けていただきました。
本当にありがとうございました。

結果は3位で、20000バーツの賞金をもらいました。
https://www.acm-icpc.eng.chula.ac.th/2016/asia/bangkok/scoreboard
残念ながら、ファイナル進出はダメそうです。

大会の写真などはfacebookにたくさんあります。
セキュリティチェックが必要です
 セキュリティチェックが必要です

以下もう雑に参加記

コンテスト色々

ICPCはチュラロンコン大学で行われた。日本で例えるなら東大である。
海外からの参加者は参加費が6000バーツの参加費が必要になっていたが、その分(?)待遇はとても良かった。
日本のチームにはチュラロンコン大学で日本語を専攻している学生たちがガイドとしてついていて心強かった。
他の海外オンサイトの経験がないからなんとも言えないけど割と快適だと思う。

コンテスト本番

全体ではこんな感じになっていた。

	解法	実装
yosupo	6	1
dnk	3	6
piroz	0	2

(修正しました)
チームメイトがめちゃくちゃ強くて僕は😇。
yosupoの解法生成の速さとdnkの実装力がとにかくすごい。

最初に12問を3分割して一人が4問読むようにした。
タイの特徴として最後の問題ともう1問が簡単になっているというのがあって、実装の速いdnkが最後の4問を読んでいたと思う。
僕はA-Dを読んだ。Aが難しそうでBがDPっぽくてまあマシ、Cが「は？」でDが幾何の構成っぽくて嫌だなあという感じだった。
Bを考察して解けそうな気分になったけど計算量がダメで、yosupoが考えた方が速そうなので投げた。
G(多分)の解法をもらって、フィボナッチ数の ${0, K, 2K, \dots, NK}$ 項目の和を求める問題だったんだけど、このタイプの式の計算方法を覚えていなかったのと、2次元配列で愚直な実装をするとJavaだと計算時間が結構ヤバいという事情があって、dnkに解いてもらった。ちょっと申し訳ない。
Bの解法をもらって、実装したら結構バグらせた(4WA)。つらい。
まず複数テストケースをある値についてまとめるという処理をミスって計算時間がおかしくなったり、DPから解を復元する部分をちゃんと理解していなくてヤバかった。
yosupoにめっちゃ助けてもらった。
まだ読まれていない問題を読んで(Hだっけ)「は？」となった。タイは問題文が読みにくいのが多い（今年はマシらしいが）。
その間にDの解法をyosupoから貰って、実装した。つくばのthin polygon(うろ覚え)と本質は同じで、2点が与えられるのであと1点を足して面積が0.5の三角形を作る問題。 ${|ax-by|=1}$ となるような点を探す。
最初Stern-Brocot木を実装して実は計算時間がやばくて1WA。extgcdにしたらなんとか解けた。extgcdのライブラリを持ってくるのを忘れたのでyosupoのを見た。
この後は問題を読んで分からん～～とずっとなるフェーズだった。
Cが解が大きくなる問題と聞いてJava得か?となったがint128で足りるじゃんと言ってしまいyosupoが実装した。
最後はyosupoのKが通るように祈ってた。

4問解法聞いて2問しか実装してないの、要精進と反省。

バンコク

飛行機に6時間くらい乗ると移動できる。
北半球で冬のはずなのに夏のように暑い。湿度は日本の夏より高い。

プミポン国王が亡くなって服喪期間中に訪れることになった。
タイの人々は全身の半分以上は黒を着ていたと思う。派手な色の服を着ている人は外国人っぽかった。
コンテストも風船が全部白、FAは黒で、ひもの色だけが異なるという仕様だった(わからない)

メシ。
f:id:piroz95:20161117123107j:plain
これは焼きそばに近い？油と塩の均一な味がした。50バーツ。1バーツ3円なので150円くらい。
飯屋の机には大体ナンプラーと砂糖と唐辛子が置いてある。これはナンプラーをかけるとおいしかった。
ホテルの朝食とか表彰式のホテルのご飯とかは特にハズレなくおいしいと思った。
辛いものが多めなので苦手な人は注意する必要がありそう。

Bangkok Centre Hotelに泊まった。
高くも激安でもないくらいのホテルで、水回りが結構ボロくてギリギリ感がある。
ホテルからの眺めはこんな感じ。
f:id:piroz95:20161117123435j:plain

ホテルの隣のマッサージ店は400バーツで1時間マッサージが受けられて普通に良かった。

アユタヤ

f:id:piroz95:20161117124138j:plain
エクスカーションで行った。全然調べてなくて、ガイドの説明もよく聞き取れなかったのであまりよく分かってなかった😇
昔の都でミャンマーの軍に破壊された(ザックリ)
廃墟感がいかにも遺跡という感じでいいと思う。

鶏。
f:id:piroz95:20161117124704j:plain

騙された話

アユタヤから帰って来た日の夜、賞金ももらったことだし有名店にでも行くか～という流れになった。
で、バンコクセンターホテル前のトゥクトゥクに乗った。(これが悪名高いことは帰国後に知った)
到着後すぐには僕は気づかなかったが、言った場所と違う店名がわからない謎のレストランに来た。(ヤバい)
Market Price(激ヤバ)の蟹カレーを4人で1つ頼んだ。店員の説明だと1200バーツだったがこれが2000バーツに化けた。
f:id:piroz95:20161117125848j:plain
(食べかけでゴメン)
ちなみに表彰式のホテルの飯の次くらいにおいしかった。

騙された外国人たちが次々とタクシーやトゥクトゥクで運び込まれてくるのがいい話感が高かった。

タクシーの行き先には気をつけよう！

2016-11-17

CODE VS for STUDENT 予選7位!

プロコン参加記 CODE VS マラソン

総合7位,学生5位で予選通過しました！

f:id:piroz95:20161117104100p:plain

予選を通過できて本当によかった・・・
CODE VS 5.0の時から勉強した成果が発揮できたと思います。

CODE VS for STUDENT(公式サイト)は落ちものパズルのAIを作るコンテストです。
実際の試合はこんな感じです。
youtu.be
タテ・ヨコ・ナナメに連続するブロックの数字の和が10になると消えるというルールです。
お邪魔の個数は ${ 1.3^{連鎖数}}$ に比例するので、長い連鎖を素早く組むのが最初のポイントです。

決勝は、12月10日(土)にチームラボ本社で行われます。
今年も配信予定でchokudaiさんやきゃんちさんが来るそうですよ！

12月5日に決勝AI提出なのでそれまでまた頑張ります👊

2016-10-17

ACM-ICPC 2016 アジアつくば大会参加記

プロコン参加記 ICPC

f:id:piroz95:20161017013453p:plain
6完12位でした．　順位表

国内予選のときのブログはこれ↓
ACM-ICPC 2016 国内予選参加記 - ぴろずメモ

0日目

姿勢を変えた時やくしゃみをしたときに胸が痛いから超不安になって病院に行ったら気胸じゃなくてただの胸筋の筋肉痛だった．心配性．

ライブラリの印刷が深夜になって準備不足を悔いた．

1日目

秋葉原からつくばエクスプレスでつくばへ移動．
poは移動のスケジュールのマージンが少ない傾向がある．
つくばは町並みが整ってるけど人の密度は高くなくて不思議な感じがした．

プラクティス．
英字キーボードが練習のために買ったのと違う方で残念だった．
B問題で2次方程式の解の公式を思い出すのに時間がかかった．

筑波大学に移動して歓迎会．
スピーチジャンケンに負けてポ😇．嘘を言った．

ホテルが綺麗で良かった．(マークワンつくば)

いいじゃん pic.twitter.com/sKk0s21HCs
— ぴろず (@p_shiki37) October 15, 2016

ARCに参加して300-300-900-1300の900で無理を感じ寝ようとした．
前日までの生活が破滅していたので2時まで寝られずつらかった．

2日目

朝が早くてつらい．
推奨電車時刻をぶっちしてタクシーで移動した．歩かなくていいのでこれは良かった．

コンテスト

まずB問題を読む．
書けそうなのでPCが空いているか聞いたらすでにA問題がdnkさんによって解かれていた．(FA)
Bを普通にAC．
yosupoがCの解法をくれたので実装してAC．
この後幾つか問題を読んで，解ける問題ないなあという感じだった．
ABCDGの5完までは圧倒的速度で，5完時は1位だった．
ここですでに僕は置物になっていた．
大炎上したのがF．
Fの解法をyosupoから聞いたが，自信がなかったので実装をパス．あと，最初に推移閉包を取るのは嘘ということに気づけなかった．
ここで実装を引き受けていたら違う展開になっただろうなあと思う．結果論だけれども．
僕以外が実装しているときは構成ゲーのIを考えたりしていたが全く成果がなし．
Fは最終的に全員で解法を検討してデバッグもしたけど結局ミスに気づけなかった．

反省

前半は本当によかった．
実装に対する自信や幾何やその他難しい問題を解けるパワーがあれば後半置物にならずに済んだかなあと反省．
精進しよう．

チーム戦としては，さすがに国内予選の時よりは大分よくなった．

懇親会

スポンサーの企業ブースが沢山並んでいてお祭り感がある．
問題とそれを解いた人限定の景品を出すスポンサーがたくさんあり大変．
面白い問題が色々配られていて全完はまず不可能という感じだった．

頂いたもの:

HP 50g Graphing Calculator | HP® Official Store

すごい関数電卓．
Fixstarsに頂きましたが実はなぜもらえたのかよく分かっていない．

テレビちゃんぬいぐるみ
Tシャツ(超会議で販売されたもの?)
Unix考古学 Truth of the Legend
dwangoステッカー

dwangoブースはWA回数に応じて輪投げができるWA投げをやっていて，poにとって有利だったのでやってきた．
うまくいって全部の景品をもらってきた．

Indeed Tokyo リングノート

Indeedのスタッフに2人ゲーム(先手か後手を選べる)で勝つともらえる．
16x16の格子が与えられ，先手は直線で2分割し，後手は片方を選んで消滅させる．これを先手後手を入れ替えて続けていき，分割ができなくなったほうが負け．
全然分からなくて法則性が見えるまでDPしたりして，結局勝つまで4回かかった．
後手を選び，分割後のそれぞれの長方形のタテヨコ比が奇数：奇数のになるように分割し続ければ勝てる．

感想いろいろ

コンテストの環境は快適だった．
PENDINGがどれくらい待つか分からなくてドキドキするくらい．

DOMJudgeのJavaはpackage宣言がついていてもOKらしい．
スタックもデフォルトで64MB設定になっていたのでやさしい．
贅沢を言うとJava8が良かった．

去年のルールとは異なり英字キーボードしか提供されないのがわかっていたので，急いでLenovoの英字キーボードを買って使うようにした．
for文を高速で打ち込んだりは問題ないレベルにはなったが，使用頻度の低い記号が若干怪しいままだった．
逆に今は日本語キーボードに戻すのも大変なので，これからは英字配列を使う．

ライブラリは色々持っていったが結局高速入出力のみ使った．

これはしょうがないけどイベント中食事が圧倒的に偏る．ホテルの朝食にありがたみを感じた．

今後のICPC

もしかしたら今年まだ開催される海外の予選に参加するかもしれない．
来年は機会があればまた出たい．