TTPC 2015
TTPCに個人で参加してきました．
結果は35位と割と解けた印象．
以下，コンテストの詳細
六本木に向かうため，電車に乗ると中央線が人身事故で運転中止...
昼食を得るタイミングを失い，そのまま会場へ
0:00 Start!
A問題に取り組む．
スペルミスが怖いので，答えをコピペしてコードを書く．
0:03 A AC
B問題に取り掛かる．
DPかなと一瞬思ったけど，入力がソートされていたり，考えると貪欲なのでそのまま書く．
0:07 B AC
C問題に取り掛かる．
文字列の置換の問題だ!
問題文の手順をそのまま実装する．最後のサンプルケースだけ合わない...
部分文字列Tではなく，文字列Sに対して置換していたのが原因だった．
修正する．(もっと簡単に書けるし，C++しか書けない点で時間を取られた)
0:27 C AC
D問題に取り掛かる．
数字は高々5種類で，n<=10^9の素数判定だから全探索すれば行けるとすぐに分かったので書く．
0:35 D AC
50点セクションを全完したので，次を見る．
E,F,Gヤバそうと思い，Hに取り組む．
Hは答えの候補になる単純多角形は三角形と四角形になることに考察して気づく．
その後，何も考えずに幾何ライブラリを持ってきて，全探索するコードを書いて投げる．
当然TLEする．WAもあった．
1時間経過で焦りを感じたのでE問題に取り組む．
O(N^2)で累積和を前計算して，O(2^K)でK個のマスの中からi個を含む最小の長方形について赤のマスと青のマスの差の絶対値を求める．
外側に長さを+1したものを考慮して書いて提出
WA...
必死に反例を探す，その中でここ違うと気づいてbitの集合列挙のバグを修正する．この後も反例を探し続ける．
反例だと思ったケースが反例ではなかったと気づいた時に，コードを修正したことに気づく... 10分くらい無駄にした．提出する．
1:42 E AC
F問題に取り組む．
Digit DPじゃないかなと考える．
こういうDPをすると良いかなと書いていく．SRM665 div1 easyを思い出しながら
書き上がる．サンプル通る．提出する.
1:57 F AC
G問題に取り組む．
最初は,部分文字列を並び替えても良いと勘違いしながら実装する.
しかし，難易度的になにか違うと感じて，問題を読み直して勘違いに気づく．
最初は，bool dp[97][17][17][17][17][17][17][17];
とかいうdpを考える．どう考えても無理
そこで，Tが2回出てくるのがネックだと考えて，TITECHを半分に分けて考える．
そうすると，bool dp[97][17][17][17][17];とテーブルが削減できる．
書き上がる．サンプル通る．提出する.
2:31 G AC
I問題に取り組む．
JAG夏合宿 Day2 ツインリバースを思い出す．
どういう風にソートするのが良いのだろう...
考えてみると，どの数列でもソートできそうだなと思う．(解なしの場合に出力する文字列も気が抜けているし...)
大きい数字を右に追いやると楽そう．それが分からなくて詰む
3:00くらい経過
ここで，一通り見てみるかと考える．
P問題 そっ閉じ
J問題 L問題が解かれているなと考える．
J問題に取り組む．
サイクルに分解すれば解けそう．
4 2のケースについて考える．サイクルのパターン数を重複カウントすることに気づく．
各サイクル長について，DPすればいける．
計算量について考えてみると少しヤバそうと思うが,JAG夏合宿 Day3 Jを思い出す.
ハーモニックナンバーが出てくるのでlogが付くだけだから行けると思い,書く.
サンプル全部通る.提出する. WA
ここで,最大値Kというフレーズを思い出す.
最大サイクル長がK以下のパターン数から最大サイクル長がK-1以下のパターン数を引けば良いことに気づく.
書き直すと,サンプル全部通る.提出する.
3:45 J AC
K問題に取り組む．
とりあえず，aの和がNC4になっているかと不等式を考えてゴニョゴニョする．
WA
YES/NO 問題はやりにくいと思い，撤退．
L問題に取り組む．
残余ネットワークを基に，いろいろ試行錯誤するけど，方向性が見つからず．
Hに戻る．
ソースコードのバグに気づく．
三角形の辺上に原点がある場合にのみ四角形をさらに探索する方針で書き直す．
TLEする．WAもあった．
5:00 Finish!
終了後に，G問題の解法を聞くとフローだとか怖い発言が聞こえる．
想定解法は穏やかでした．
16問のうち8問ACすると,かなり解いた感がある.
H問題は思考停止して解けなかったのが辛い...
I,K,L,M,N問題は解けそうに見えるから復習.O,Pは無理そう...
あと,お菓子はおいしかったです.
