非想定解法で殴る yukicoder Advent Calendar Contest 2016

競技プログラミングのいわゆるアルゴリズム部門のコンテストは数時間の間に数問を解く形式のものが多いです。 例えば topcoder SRM は1時間15分で3問、 codeforces は2時間で5問出題されます。
しかし最近は数日から数週間に及ぶ長期間コンテストが増えてきています。 例えば hackerrank の week of code は7日間で5問、 codechef の challenge は10日間で10問、 hackerearth の circuits は 8日間で8問です。
これら長期間のコンテストでは1問にかけられる時間が長いため、短時間コンテストではできない（実装しきれない / やろうと思わない）ような頭の悪い非想定の筋肉解法みたいなのでゴリ押せたりします。

yukicoder で開催された Advent Calendar Contest 2016 は、25日間に渡って毎日1問ずつ追加出題されていく長期間コンテストです。 この記事ではこのコンテストでやってしまったゴリ押し解法を自戒を込めて振り返りたいと思います。

(注) 基本的に想定解よりも悪い方針（計算量、実装量、精度等）なので、想定解で解けるのならそれが一番いいです。

お品書き

No.453 製薬会社

想定解法

線型計画問題だけど変数が少ないので手で式を少し整理したり、凸になることを利用して三分探索したりする

ゴリ押し解法

線型計画法をがんばる https://yukicoder.me/submissions/134867
判定がWAになってるけど運営者のお墨付きをもらってるので実質FA

本当に線型計画法でやろうと思ったらsimplex法やら内点法やらを使う

No.454 逆2乗和

想定解法

式変形して誤差の出にくい計算をする

ゴリ押し解法

適当な所まで計算したらε足して誤差調整 https://yukicoder.me/submissions/135150
差分が 1e-17 まで収まったところと正解との差を取ってεとしているのでケースによってそんなに差が付くことはないはず、という認識はあった

No.456 Millions of Submits!

想定解法

ランベルトのW関数

ゴリ押し解法

中途半端に式変形(何となく log を取ってみただけ)してニュートン法ゴリ押し https://yukicoder.me/submissions/136218
初期値次第で闇に吸い込まれるのでかなり怪しい

No.457 (^^*)

想定解法

制約小さいので \(O(N^2)\) でいい

オーバーキル \(O(N)\) 解法

制約を1桁間違えて認識してて 累積和 + 尺取 で \(O(N)\) https://yukicoder.me/submissions/136149
')' の左側直近の '*' の左側にある '^' を最大2つ deque に持ちながら計算すると、'(' の累積和と合わせて \(O(N)\) になる。 そこまで要求されてない

No.459 C-VS for yukicoder

想定解法

greedy

ゴリ押し解法

最小流量制約付きの最大流の復元 https://yukicoder.me/submissions/137248
適当に書いたgreedyが通らなかったので確認用に書いたら通ってしまった。 計算量的にはTLEなんだけど、Dinic爆速

No.460 裏表ちわーわ

想定解法

最上段を決めるとそれ以外も決まるらしい。 よくあるやつ。

ゴリ押し解法

https://yukicoder.me/submissions/137534
盤面を長さ \(NM\) の列ベクトル \(b\) と見なすと、ひっくり返す位置を列ベクトル \(x\) として \(Ax = b (\mod 2)\) と表現できる。 ガウスの消去法で解の一つを得られる。
しかし問題では最小を要求されているので、あり得る解を全探索する。 \(O(2^k * (NM)^2)\) だけど、制約の範囲を確認すると \(k \leq 15\) なので間に合う ( \(k\) は解の自由度。 \(2^k\) が解のパターン数になる)

自由度は小さい、というのは書いてからわかったことなのでダメ。 見切り発車良くない

No.465 PPPPPPPPPPPPPPPPAPPPPPPPP

想定解法

論文を読む

ゴリ押し嘘解法(TLE)

palindromic tree + bitset + 平方分割 + 枝刈り (結局TLE)　https://yukicoder.me/submissions/139112
palindromic tree の suffix link を辿っていけば PP 判定ができるが、 aaaaaaaa... などは \(O(N)\) 回辿らないといけないので \(O(N^2)\) になって TLE。 そこで 頂点v から根まで suffix link を辿ったときの集合(回文長をビット列として保持)を事前計算しておけば \(O(1)\) 判定可能(bitsetの計算量を\(O(1)\)と仮定）、なのだけど、 メモリの制限もあるので実際に集合を持つ頂点は \(O(sqrt(N))\) 頂点程度に間引いておく。 \(O(sqrt(N))\)回 suffix link を辿るだけで十分になる。 bitset 自体も平方分割して、 枝刈りも加えると更に高速になって \(10^5\) ぐらいまでなら通りそうになる。
しかし現実問題長さ \(N\) の bitset の計算量は \(O(1)\) ではなく \(O(N)\) の \(1/64\) 倍とかなので通らない。 無駄な努力だった

No.470 Inverse S+T Problem

想定解法

2-SAT なので 強連結成分分解 で解ける

ゴリ押し解法

SAT なので SAT-solver に投げる https://yukicoder.me/submissions/140005
SAT-solver に投げる CNF を書き下している時点で1項に2変数しかないの気付くべき
togatoga氏のTogasatを使わせていただきました

総評

考察放棄・見切り発車・嘘とわかっていながらチューニングして通そうとするのは自分の成長にもよくないですね。 悔い改めていきたいです。
ちなみにこのコンテストは25人 (今年は2問出題の日があって26人) が1問ずつ問題を持ち寄って行う一風変わったとても楽しいコンテストです。 出題者も出題日以外は普通のコンテスタントとして参加できます。 私も1問出題したので解いてみてください。 No.471 直列回転機
Advent Calendar Contest 2016 主催のyukicoder運営、出題者、テスターの方々は勿論、参加していただいた方々にも感謝申し上げます。 また来年もできるといいですね。