■ [CodeChef]January Challenge 2017 
https://www.codechef.com/JAN17
Cats and Dogs(CATSDOGS)
やる
https://www.codechef.com/viewsolution/12432868
Reservior(RESERVOI)
やるだけだけど問題文で網羅されていない仕様があって1WAした
https://www.codechef.com/viewsolution/12534258
Capital Movement(CAPIMOVE)
首都の隣かどうかで場合分け
https://www.codechef.com/viewsolution/12452430
Tourists in Mancunia(TOURISTS)
DFSして閉路を作る→グラフの残っている部分について閉路を作って最初の閉路に挿入する を繰り返す
https://www.codechef.com/viewsolution/12456303
Digits Cannot Separate(DIGITSEP)
普通に桁DPするだけ、にしては正解者数少ない
https://www.codechef.com/viewsolution/12457791
Chef and Circle(CHEFCIRC)
N点中3点を通る円を全列挙したい。
まず2点A,Bを決める。残り1点Cを決めたときに外接円の中心がABの垂直二等分線上のどこに来るかが分かる。
この垂直二等分線上で外接円の中心となる点の位置をソートしてスイープすると、A,Bを通って点がK個以上含まれるような円の中心となる範囲が分かる
これがO(N^3 logN)だけど、遅くてダメだった。
制限時間が来たらその時点での最善の解を出力するようにしたら通ってしまった
https://www.codechef.com/viewsolution/12562803
想定解は、半径Rについての二分探索。
円が通る点Aをまず1つ決めて、Aを中心とする半径Rの円周上を円の中心の候補として、ほかの各点について円に含まれるような円の中心の存在範囲を求めて偏角ソートしてスイープ
Fantastic Four(FOURSQ)
前半パートの積を求めるところはごく普通のsegtree（ただしオーバーフローに気をつける必要あり）。
後半パートの、4つの平方数に分解するところがわからず、定数倍高速化を頑張って通してしまった
https://www.codechef.com/viewsolution/12491784
想定解は、積を求めてしまってから平方数に分解するのではなくて、各要素を平方数に分解してから掛けていく方法だった
https://discuss.codechef.com/questions/90269/foursq-editorial
参照 : オイラーの四平方恒等式
Sereja and BOX(SEABOX)
最小化は木DP、最大化はGreedy
スコアは必ず 7*N+1 の形になるので、これを利用して状態を1/7に圧縮すると考えやすい。
一見変な問題かと思いきや普通だった。の割に正解者数少ない
https://www.codechef.com/viewsolution/12535146
Coprime 6-tuples(TUPLES)
包除原理やって部分点だけ
https://www.codechef.com/viewsolution/12563810
想定解はFFTを巧妙に使う方法 https://discuss.codechef.com/questions/90271/tuples-editorial
Sereja and Circles(SEACIR:タイブレーク)
候補の半径をある程度保守的に選んで、互いの距離が遠くなるように焼きなましで候補円の位置を調整
入力の円それぞれについて、半径が自分以上の候補円のうち最も半径が小さいものを選んでそこに置く
https://www.codechef.com/viewsolution/12587441
75.063点
type=2の結果が不安定すぎて まだ改善の余地はあった
結果
- 922.063pts/1000pts
- 17位/6866人
