2019-01-16
■ TopCoder SRM 746
新年初コンテスト、何故かtouristとPetrと同部屋に入れられて死を覚悟する
Easy
問題文が本当に分かりにくい、頑張って読むと全点間の距離が元のグラフと全て異なるグラフを構成すれば良いらしい
-> 1 / 2以上 は直接繋がるかどうかで分かれるんだから補グラフを出せばOKね -> 出す
Medium
構築だけどこれはDPから復元するタイプに見えるのでそこまで苦手ではないはず -> 何度か嘘をやる -> 最終的に、(ab)*n bb (ab)*m bb (ab)*kみたいにすると、n*n + m*m+m + k*k+k になることを使ってDPしたら全部構成できた、テストを真面目にやりすぎて凄く遅い
Hard
やることは平行なら平方完成するだけ、平行じゃないなら法線ベクトルを求めて平面と点の距離の公式に代入するだけ -> 出す
challenge
PetrにHard落とされる (そう....)
System Test
前2つは通る、35位
Rating
2605 -> 2562
感想と反省
"Changing this to long double and just hoping it will pass is a risky strategy" じゃないんだよね、とは思うもののICPCでは普通に出るレベルだし__int128かpythonか多倍長ライブラリ
Mediumが遅いのはテストに時間かけ過ぎたのと嘘をやったタイムロスだけど、こういうのは方針ガチャだししょうがないね
