Hatena::Grouptopcoder

Hiro180の日記

 | 

2019-01-16

TopCoder SRM 746 18:35

新年初コンテスト、何故か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が遅いのはテストに時間かけ過ぎたのと嘘をやったタイムロスだけど、こういうのは方針ガチャだししょうがないね

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Hiro180/20190116
 |