Codeforces Beta round 97 (DIv.2)

結果

ooxo- 2576pts, 447th(Div2)

レートは
1583->1547(-36)

内容

A,Bはまぁやるだけ

C

数列{a_n}のいずれか1つを任意の数に変更して(変更しなければならない)
ソートしたときのk番目の値としてとりうる値の最小値を全てのkについて求めよ。

基本的には初めにソートしてk-1番目の値を取ればよい。(先頭は1)
しかし、変えなければいけないので1,1,1という場合は3番目のとり得る最小の値は2になる…
のは実装前に解っていたのに実装ミスった。
k-1番目の値を取ってから全てが1であるチェックをしてしまったので
{1,2}で落ちてた。(この場合は){1,1}が可能。

D

8個の点が与えられる。これを2つの4個の点の組に分けて片方は長方形、もう片方は正方形となる組み合わせがあるか判定する。(正方形⊂長方形、辺はx,y軸に平行でなくてもよい。)
計算量的には8C4=105に対して条件を満たしているかチェックする、が4点の順番が解らないのが厄介。

結局x座標でソートして、辺が軸に平行でない場合は
p[0]p[1]⊥p[0]p[2] && p[1]p[3]⊥p[2]p[3]　⇔ 長方形
であり、これかつ4辺の長さが等しければ正方形、とした。
p[0]p[3] == p[1]p[2]　対角線の長さが等しい　でも良いと思う。

でaccepted。通ったのは嬉しいけど実装が遅い。

まとめ

C通してればレートあがったのになぁ。D通せたのはよい。