Codeforces Round #19
なんだか久々な気がするCodeforces.
Result
penalty 214 00:22 / 01:08(1WA) / 01:44 / - / -
58位 1509->1664 黄色になった。
A. World Football Cup
問題
nチームがワールドカップの予選を行う。
nチームそれぞれの名前および、n*(n-1)/2試合の総当りの試合結果が与えられる。
次のように予選通過チームを決定するとき、予選通過チームをアルファベット順に出力せよ。
- 試合に勝ったチームは勝ち点3,引き分けたチームは1点が入る
- 勝ち点が多いチームが順位が高い
- 勝ち点が同じとき、すべての試合の(取った点数)-(取られた点数)の和が大きいチームが順位が高い
- 上二つが同じとき、取った点数の合計が大きいチームが順位が高い
また、この3つの条件で順位は一意に定まることが保証されている。
試行錯誤
実装…すればいいのだけど変数名を衝突させる、stringのreplaceの使い方でハマるなどして時間を食われる。成長しねえorz
苦心してコンパイル通して送信→AC.
今回問題難しいのかなあ。それともこれだけ重いんだろうか。
B. Checkout Assistant
問題
泥棒がn個の商品を買い物する。
レジにおいて商品を読み取る時間がti秒、商品の価格がciで与えられる。
店員がレジを打っている間に買い物カゴの中の商品を万引きすることができて、万引きには一つの商品につきちょうど1秒の時間がかかる。
もっとも安くn個の商品を手に入れるような盗み方における、支払う金額を求めよ。
n,ti,ciはすべて整数で、n≦2000,ti≦2000,ci≦10^9を満たす。
試行錯誤
問題文が酷すぎる。
そして方針が立たない……B問題なのに難しくないか？
価格かレジ打ちにかかる時間でソートして貪欲に行けたりしないんだろうか。
どうも行けないような……？行けるのか？というかサンプルが簡単すぎて法則がつかめない。
ケースを作る、ああムリだ。
n個目の商品を時間tだけかけて買う場合の最小コストみたいな表をもってDPできないかな。2000x2000ってちょっと時間怪しい？
どうするのだろう。合計金額で二分法するとか。いやいや意味わからん。
上のDPでなんとか行けないかやってみよう。
うまくいかない。
あ、残り万引き可能個数を添え字でもっとけばいいんだ。
あれーでもこれダメな気がする。最初の一個は必ず買わなきゃいけないんだよな。
価格順にソートしてみる？いやーなんか色々反例が作れてしまう。。。
あ、残り万引き可能個数をマイナスまでもっておけばいいんじゃん！！
int型じゃオーバーフローするのでlong long使って書く。書いた。送信。
WA.(case 3)
あれ？あー価格が10^9ありえるからinfが2^28じゃ小さすぎるんだ。
infを適当に1LL<<60とかして送信。
AC.ハマりすぎorz
C. Deletion of Repeats
問題
n項の数列が与えられる。以下のルールにしたがって"繰り返し"を削除するとき、残った数列を出力せよ。
ただし繰り返しとはxの長さの連続する項が2回出現することをいう。
- 残っている数列でもっとも短い繰り返し文字列を見つける。
- それが複数ある場合、もっとも左にあるものを選ぶ。
- 繰り返しの半分の部分、およびそれより左にある項すべてを削除する。
n≦10^5, 数列の項は10^9以下の整数であり、同じ項は最大で10個しか出現しない。
D. Points
問題
以下のような平面の点を追加、削除、検索の操作ができるデータ構造を作れ。
- add x,y
- (x,y)をデータに加える
- remove x,y
- (x,y)をデータから削除する（(x,y)がすでに加えられていることは保証されている）
- find x,y
- x<x'かつy<y'を満たす(x',y')を検索し、出力する。そのような点が存在しない場合-1を出力する。複数存在する場合、x座標がもっとも小さいものを出力する。
操作の回数は2・10^5回以下である。
試行錯誤
読み終えた時点残り10分くらい。
えーと、なんだろう。set使えばいいんじゃないのか？
それともsetだと時間厳しくて探索木を自分で書けとかいう感じなのだろうか。
あ、いやfindでx<x'かつy<y'の条件があるからset使えない。。。
どうしたらいいんだろ。考えてみたが方針立たない。
時間終了。
