Codeforces Round #367 (Div.2) 参加記

はい。 ox---(0/0) 1148(-1)
http://codeforces.com/contest/706
B問題は気づくべきだった。。。

A. Beru-taxi

ざっくりと大意

・今いる(a,b)に最も早く迎えに来てくれるタクシーを探す？？
・タクシーは(x,y)から速度vで迎えに来る？？

方針のようなもの

・全部計算する。

python

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\)である。
・各日の予算で購入可能はお店は何件あるか？？

方針のようなもの

・先頭から単純に全部調べるのは無理。

python

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

ざっくりと大意

・長さ10⁵を超えない英小文字の文字列sがn個と、それらの文字列を反転させるコストcが与えらえる。
・いずれかの文字列を反転させてn個の文字列を辞書順にするのに最小コストはいくつか？
・サンプル1では1つ目の文字列を反転させるのが最小、2では3つ目の文字列を反転させるのが最小。3,4は辞書順には出来ない。

方針のようなもの

・後で