Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2012-01-09

Codeforces Round #101 Div. 2

11:49

o failed o opened opened : 2134 pts. 147th. 前回と同じでした。B落ちたのよりDE提出ができないほうが酷い感じです。

  • A 486 pts
  • C 1648 pts

A

print (if sorted (a + b) == sorted c then "YES" else "NO")

追記の通り焦ったけど7分で終了。

B

やるだけ。

でしたが一箇所 else return -1; を忘れて "2 -1 3" で爆死。

if-elseが多くなりすぎていたので危ないことには気づいていました。が、しかしどうすればよいでしょう。最後30分で入力作ってcoverage testする、のがかろうじて可能でしょうか。

C

やるだけ。と書くとちょっと忘れそうです。

  • 人数の少ない順にソート
  • "N番目の人は前N人の中で背の順何番目?"を全部計算。この段階でN番目なのにN人前に人がいるとか言ったら-1
  • 最後尾から背の順を決めると全部確定する。

O(N^2)で余裕です。O(N log N)でいけるはず?

44分。Bがあったので。

D

端からDPで余裕。と思ったらスキー逆行だと!?

よくわからないので結局飛ばしました。ダイクストラで十分という話を聞きました。

たしか、O(頂点数^2)の辺を張られると死ぬのでひよった記憶があります。そんなケースは存在しないのでしょうか。

E

眠い頭で、

片方の枝だけでMST実践→もう片方の枝で完成させる→足りない方の枝を足して、出来たループから多い方の枝をカット

みたいなことをやるとできそうなことを導きました、が、眠い。

その他

前回から準備したMakefile+テストがうまくいってなくてハマりました。間違いは次の通り。

python try_cf.py --command $< --input $(<:.exe=.in) 2>&1 | tee $@
正       python2.7 ../try_cf.py --command ./$< --input $(<:.exe=.in) 2>&1 | tee $@

.exeまでをMakefileで作って手動でテストすることで回避しました。

それから、うっかりvirtualbox内の共有フォルダじゃない方で組み始めてしまい、Aを提出するときに焦りました。

 |