hos' Xmas Contest 2010

maxの時は反対側にいることにして、minの時は同じ方角にいることにする。
- おっと、位置が異なるということはc==dのとき例外処理が要るのか。
  - トラップ回避ktkr
あとは算数で頑張るだけ。
- 苦手だけどどうにかなった。
せっかくトラップ回避したんだから一発で通したいな。submit.
Accepted. よかった。

Aより先に通してる人がごろごろいるんだけど、どういうことだろう。
- しかも構文解析って。
  - と見せかけて偶奇だけなので簡単。
    - にもかかわらずintで処理しようとして1回WAった。
Accepted.

問題を読むのに少し時間が掛かった。
ええとこれは...シュタイナー木？
- 「えぬぴぃこんなん」でしたよね。
...え？ N < 100 ? 無理ゲーじゃね？
... (5分後)
あ、よく見たら sum(s[i]) <= 10 って書いてあるじゃなイカ。はいはい Dreyfus-Wagner...
- いや、使わなければならないノードではなく、使わなくてもいいノードが10個イカなのか。
...Dreyfus-Wagnerより簡単じゃね？
- 使わなくてもいいノードのうち、どれをホントに使わないかを決め打ちしたらただのMST。
がりがりがりがり。できた。submit.
- No - 90% Accepted.
ケースごとの結果を見てみたら、見るからに定数倍でTLEしてる臭いが。
- vectorを全部static配列にして Accepted.

解いてる人が多いのでそろそろ手を付けてみよう。
- ひたすらスーパー実装タイム。
  - Bとか今度こそ構文解析しないといけないのかなとgkbrしたけど、全然そんなこと無くて#を見るだけで終わった。
submit. No - 50% Accepted.
- ちまちまバグを潰すけど点数は変わらない。何でだろう。
  - この問題の肝はAとGにありそうで、それ以外は適当に書いてもどうにかなる気がするのだけど...。
分からないのでちょっと他の問題を眺めたりする。
- Fは各入力10ケース、か...。
  - ...!
    - 入力ケースの数はチェックしてなかったぞ！
Accepted.

普通に難しそう。DPかな？
でもまずは単純な解法を疑ってみたい。
- 2つ以上の店で買っても最適にならない？
  - 証明も撃墜も出来なかったのでとりあえず書いてみたらサンプルで撃墜された。
普通にDPしよう。
- dp[n][p] := 店 n にいて、プレゼントを既に p 個持っている状態での (掛かった金額) + (溜まった疲れ) の最小値、でいいかな？
  - プレゼントはたかだか M (とりあえず1000ぐらい) 個だけ買えばいいことにしておこう。
愚直に実装すると O(NM^2) だけどもうちょっと減らせそう。これだと30%で、O(NM)にすると50%ぐらいくれるのだろうか。
- もう一つ落とすのなら...
  - a[n][p] := 店 n にいて、プレゼントを既に p 個持っていて、まだ店 n では買い物してないときの最小値
  - b[n][p] := 店 n にいて、プレゼントを既に p 個持っていて、店 n で既に1個以上買い物したときの最小値
- かな。
がりがりがりがり。submit. 20%。バグを取っても30%。Mを調整しても30%。
- あれれ...？

N <= 2 の部分点ぐらい狙えそう。
楕円はキモいので1,000角形ぐらいで近似して、包除原理でエンヤトットする。
- 凸多角形2つの共通部分は O(n) ぐらいででできるらしいけど、よく知らないので愚直にやってみた。
うーむ、全然精度が足りてない感じだ。
実は N = 1 のケースが10%ぐらいあるんじゃね？とか期待して適当に投げたけど、現実は (というかhos先生は) そんなに甘くありませんでした。