読者です 読者をやめる 読者になる 読者になる

RCO presents 日本橋ハーフマラソン 参加記

ハーフマラソン(走らない)

予選

A19位,B9位で総合8位でした。


やったことが解説の想定とほぼ同じだった。
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点)

市松模様に並べて動かしていくという方針もあるが、これはめちゃくちゃ難しそう。

この問題の設定、見覚えがあると思って調べた所、Asymmetric Simple Exclusion Processと呼ばれているらしい。

反省や感想

今回は最初に間違った方針で、しかも重い実装に取り掛かってしまったので取り返しのつかないことになった。
まず最初に貪欲を考えるという方針が良いような気がする。
しかし、CODE RUNNERの2回目の予選A(交わらないように直線を引くやつ)のように、貪欲よりも頭の良い解法が圧倒的に良い場合もあるのでそのあたりは難しいなあと思った。
短時間マラソンでは、自信のない重い実装はやめたほうがよさそう。

その他:
・東京駅から徒歩2分、乗り継ぎもなかったのでめちゃくちゃ楽だった
・企業紹介と文章要約アルゴリズムについてのスライド?はどちらも面白かった。(途中で置いていかれた)
・懇親会は主にピザ🍕とフライドチキン🍗

2-SATを探索で解く方法とyukicoder No.470 Inverse S+T Problem

2-SATを想定解とする問題をyukicoderで出題しました。
No.470 Inverse S+T Problem - yukicoder

想定解通りの2-SAT解法とは別に、計算量のよく分からない探索を結構通されてしまいました。
探索解の中に正当なものがあるのか、調べていたところ2-SATを暗黙的に解いている提出が見つかりました。
たとえばヘクトさんの提出です。

その解き方というのが、Wikipediaの2-SATの解法の一つとして載っているLimited backtrakingです。
2-satisfiability - Wikipedia
http://epubs.siam.org/doi/abs/10.1137/0205048

例を用いて大雑把に説明します。
 (\lnot x_1 \lor x_2) \land (\lnot x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_5) \land (x_1 \lor x_3) \land (\lnot x_3 \lor x_4) \land (x_5 \lor x_6)
が充足可能か調べましょう。

真であると分かったリテラルの集合を Tで表します。
まず適当な変数を選び( x_1とします)真だと仮定します。( T = \{ x_1 \})
 \lnot x_1は偽になるので、このリテラルを含む節では、もう片方が真になる必要があります。
1つめの節から T x_2を加えます。
2つめの節から T \lnot x_2を加えます。
ここで T = \{ x_1, x_2, \lnot x_2 \}となり、矛盾が見つかりました。

今度は x_1が偽だと仮定します。( T = \{ \lnot x_1 \})
 x_1を含む節に注目します。
4つめの節から T x_3を加えます。
 x_1を含む節は1つだけです。新たに Tに加わった x_3に対して、 \lnot x_3を含み、真であることが確定していない節に注目します。
5つめの節から T x_4を加えます。
これで( T = \{ \lnot x_1, x_3, x_4\})になりました。これ以上 Tに追加することもできませんし、矛盾もみつかりませんでした。

 Tに含まれているリテラルを含むような節は、残りの変数の値によらず真になります。
そうでない節は、 Tに出てくる変数を含みません。この例では、 (x_5 \lor x_6)が余っています。

残った小さな問題についてこの手続を繰り返していきます。最終的に節が無くなれば残りの変数は適当に決めてよいです。
もし部分的な式が充足不能ならば全体も充足不能ですし、部分的な式が充足可能ならばいままでに確定した真偽の割り当てと合わせて全体が充足可能です。


ある程度無駄を省けば計算量は O(nc)になると思います(nが変数の数,cが節の数)。
このアプローチでも工夫すると線形時間で解けるらしいです。

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

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

解法

小さい 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;
	}
}

計算量

メモ化再帰の遷移に注目すると、三つ又に分かれているように見えます。
n2で割っていっているのでいつかは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は定数)の形の時は安心してよさそうです。

CODE VS for STUDENT 参加記

初戦で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で入賞したいからまた開催してください~~~~~

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

続きを読む

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

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 xwx内積)

このとき、浅い探索の評価値を深い探索をしたときの評価値に近づけるということを考える。
Xからベースの評価関数の値を用いてi手読んだ結果の最良の盤面をX_iと表す。
 s,ds < 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ヶ月くらいの間どういうことを試していたかの記事はまた別に書きます。

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.

全体の感想

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

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

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

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

結果は3位で、20000バーツの賞金をもらいました。
Scoreboard | 2016 ACM-ICPC Asia Bangkok Regional Contest
残念ながら、ファイナル進出はダメそうです。

大会の写真などはfacebookにたくさんあります。
ACM ICPC Thailand | Facebook
ACM ICPC at Chula Engineering | Facebook


以下もう雑に参加記

コンテスト色々

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

コンテスト本番

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

解法 実装
yosupo 61
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
(食べかけでゴメン)
ちなみに表彰式のホテルの飯の次くらいにおいしかった。

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

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