Codeforces Round #367 (Div.2) 参加記
はい。 ox---(0/0) 1148(-1)
http://codeforces.com/contest/706
B問題は気づくべきだった。。。
A. Beru-taxi
ざっくりと大意
・今いる(a,b)に最も早く迎えに来てくれるタクシーを探す??
・タクシーは(x,y)から速度vで迎えに来る??
方針のようなもの
・全部計算する。
IS=float('inf') def euclid_dis(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5 a,b=map(int,raw_input().split()) n=int(raw_input()) ans=IS for i in range(n): x,y,v=map(int,raw_input().split()) tmp=euclid_dis(a,b,x,y)/v ans=min(ans,tmp) print ans
2点の距離を求めるのはテンプレに入ってたのでそれを使った。計算の仕方としては三角関数?で各x,y座標の距離を2乗したものの和と、距離(斜辺に相当)の2乗が等しいので平方根を求めると距離。それを速度で割れば迎えに来る速さになる。
うちの部屋だけでもC++系で書いてる人が5人落ちてた。桁精度が指定しないとヤバイらしい。落ちてたということは撃墜できるチャンスでもあったはず。。。今回撃墜できたはずのケースは5.0/3.0の時の精度。覚えておけばいつかチャンスがあるはず。。
B. Interesting drink
ざっくりと大意
・nのお店のコーラの販売価格が\(x_i\)でq日のそれぞれの予算が\(m_i\)である。
・各日の予算で購入可能はお店は何件あるか??
方針のようなもの
・先頭から単純に全部調べるのは無理。
import bisect n=int(raw_input()) x=map(int,raw_input().split()) x.sort() q=int(raw_input()) for i in range(q): m=int(raw_input()) print bisect.bisect_right(x,m)
はい。これはコンテスト中は出来なかった。いや、bisect使って二分探索すればよかったんですが。。。もったいなかった。。
C. Hard problem
ざっくりと大意
・長さ105を超えない英小文字の文字列sがn個と、それらの文字列を反転させるコストcが与えらえる。
・いずれかの文字列を反転させてn個の文字列を辞書順にするのに最小コストはいくつか?
・サンプル1では1つ目の文字列を反転させるのが最小、2では3つ目の文字列を反転させるのが最小。3,4は辞書順には出来ない。
方針のようなもの
・後で