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を提出するときに焦りました。


SRM 527 practice

23:38

opened x opened: 0.00 pts. 自分の実力を認める展開。あるいはpracticeでよかったともいいます。

275

なぜか貪欲でいけると思い込みました。手元で貪欲法を作ってはその反例を作るを繰り返して時間を潰しました。

やっている最中にノートPCが電源トラブル?で電源が落ちました。再起動してから冷静になって次に。

25分くらいかけてました。本番ならもっと早く動いているはずです。心配だし。

Systest後、ブログにあるDPという記述を見てやっと解法に気づく。気づけば簡単でした。

木の端の頂点をひとつ除いたものを考えます。名前が有りそうですが忘れたのでブランチとでもいいましょう。1頂点だけ使ったブランチは、その唯一の頂点の次数は1です。2頂点のブランチは次数はそれぞれ1, 2です。

max_score[頂点数][ブランチ数]に、N頂点使ってブランチをb個作った時のスコアの最大値を保持します。これを下から順に埋めていきます。

これでDPになりました。

450

  • 辞書順なので頭から探索するに違いない。
  • 探索の途中でも条件を満たすかどうか調べたほうがいい。
  • 条件を満たすかどうかは、二部グラフがfull matchするかどうか確認すればよい。

手元に2部グラフのコードが見当たらないのでゴリゴリ書きました。Edmonds-Karpで。サンプル通ったので提出。

しかしなぜかTLE Systest Failed。調べたところ大きなグラフで0と?としかない入力でした。手元では600 ms程度で実行できているのですが。

1050

残り時間が殆ど無かったので眺めるだけでした。後で解きます。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/gusmachine/20120109
 |