Codeforces Round #24

Codeforces 参加記録

今日でテストも大体ケリがつくので本格的にブログ再開します。（きりっ

Result

124位 3AC 00:37 / 00:52 / 01:20 / - / -
penalty 169


1660->1717


Aでハマる癖を何とかしたいorz
B,Cも解くの遅いしなあ。。。


相方様の順位が遥か上でやばいｗ僕もがんばろ。
僕は積み残し癖が良くないよなー……

A. Ring road

問題

n個の都市が、双方向に通行可能なn本の道路によって、（直接または間接に）どの都市も行き来できていた。
n本の道路を全て一方通行にしたが、それによって行き来できない都市ができてしまった。n本の道路のうち何本かを双方向に通行可能にして全ての都市を行き来できるようにしたい。
そのために必要な最小コストを求めよ。

試行錯誤

なんかAから結構重いような気がするんだけど。。。


えーと、行けない都市を見てけばいいのかな？？union-find?
書いてみた。答えが全部0になる。
union-findじゃ向き考えないもん、そりゃそうだろ……


なんだろ、ワーシャルフロイド的なことをして、
そんでもってクラスカル法ぽく安いエッジを採用していくのかなあ。
書いた。


あれ？サンプルが一つだけ合わない。
あー！木じゃない(cylic)からクラスカル法みたくエッジを貪欲に取って行っても最適解にならないことがあるのか！
今回ありえないくらいサンプル親切だなあ。


どうしたものか。グラフ書いてみる。
ん？エッジがn本で都市の数と同じ……
わっかになるんじゃん……orz


右回りか左回りか決めて安いほう選ぶだけ。
書く。意外と実装がむずいぞ。再帰の変数が5個になってしまった。
バグ出しつつサンプル通った（←これがいつも時間かかる原因なんだよな）
提出。AC.

B. F1 Champions

問題

F1レースの順位付けは次のような方式である。
t回のレースのそれぞれで、1位から10位までに、20,18,15,12,10,8,6,4,2,1点のポイントを与え、その合計点が高いものが優勝。
ポイントがタイの場合1位を取った回数が多いものが、それでもタイの場合2位の回数、3位の回数……と比較する。


次のような順序付けを考える。
1位の回数が多いものが優勝。その回数がタイの場合、ポイントの合計が高いものが優勝。
それでもタイの場合、2位の回数、3位の回数……を比較する。


t回のレースの結果が与えられた時、それぞれの方式における優勝者を求めよ。

試行錯誤

選手の構造体作ってソートすればいいのかな。
構造体には選手の名前、順位の回数、得点を持っておいて、比較関数を二つ用意する。


あ、順位は名前で与えられるのか。そこだけちょっと面倒。


関数オブジェクトとかあんまり自信ないんでちょっとずつコンパイルしていく。
書いた。サンプル通った。
提出。AC.

C. Sequence of points

問題

平面上に点M0,A0,A1,...,An-1が与えられる。nは奇数である。
今次のようにしてMiを定める。
MiはA(i-1)%nについて、Mi-1に対して対称な点である。
jが与えられたとき、Mjの座標を求めよ。

試行錯誤

まずは問題の意味がよくわからない。
点を書いていってみる。
M1はM0をA0を中心に対称移動した点、
M2はA1を……あ、M0をA0から順にj回対称移動させろってことか！


j≦10^18……ということは繰り返し二乗法とか、規則性を見つける、とかだろうか。
座標の範囲は1000,あまり移動のパターンはないから1000個とか2000個メモ化とかかなあ。


あれーでも対称移動しまくったら無限にぶっとぶケースないか？
A0(0,0) A1(1,0)とかで、(2,0)あたりから出発したらぶっとぶよなあ。
nが奇数だとそういうことはないのだろうか。


よくわからん。
とりあえず同次座標使って行列のn乗すれば解けるがバグなく組める自信はないし、想定解ではなさそう。


実験してみる。
あれ、A0からAi-1を二周すると元の点にもどる！？
なんだこれ。適当にAの座標とか個数とかを変える。でも成り立つ。
へー。よくわからんけど通してる人多いしそうなんじゃね。


m%(2*n)回の移動をするように書くだけ。
書いた。通った。

E. Berland collider

こっちを通してる人のほうが微妙に多いのでこっちを読む。

問題

加速器があり、n個の粒子が数直線上を動く。
それぞれの粒子の初期座標と速度が与えられた時、
最初に「向きの異なる」二つの粒子が衝突する時間を求めよ。

試行錯誤

まずは問題が理解できないｗ
colliderは加速器か。ふむふむ。elapseは時間が経つこと。
加速器が動くのか？？なんだかよくわからないが衝突までの時間を求めれば良いようだ。


nは5*10^5……nlog nくらい
なんだろ。


それぞれのプラスの向きの粒子について、その先にあるマイナスの向きの粒子のうち最も近い粒子を見てやればいい……のか？？


書いてみた。サンプル合わない。
そっか、向きの違う粒子の衝突だけ考えるから、粒子が追い抜いて先に衝突する場合がある。
今回サンプルめちゃくちゃ親切だなあ！


じゃあどうすれば良いんだろう。
粒子を領域ごとに分割してみてくとかかなあ。
平方分割して、それぞれの領域ごとに最高速と位置あたり持っておけばO(n^(3/2))くらいで解けそうな気がしないでもない。
書いてみる。


書こうとしてるうちに方針があってないような気がしてきた。大体粒子の到着時間がタイの場合それ全部しらべたら結局O(n^2)になるじゃねーか。
わからない。時間切れ。