Codeforces Beta84

lukcy number回。いつもと比べて問題文が読みやすい。
ところで7はともかくなんで4もluckyなんだろうか。

A問題

• これって答えめちゃくちゃでかくならない？
  • 4の数、7の数だけ考えればいいから別にいいのか。
  • ある一定の数を超えると常に作れそう。どう作る？
  • うーむ、めんどくさそう。と思ったけど尺取メソッドで上と下から攻めればいいか。
  • 書いた。pretestAC。

B問題

• lucky numberをk個含む確率を求める問題。
  • lucky numberはそんなに多くないから全ての場合を列挙すれば良さそう。
  • あとk=1の場合はやばそう。
  • てきとうに実装。pretestAC。

C問題

• 重み意味ねえー。
  • 最初のサンプルの答えは4になるんじゃないの？
  • ああ、同じ辺を使ってもいいのね。
  • DPで解くんかなあ。とりあえずluckyじゃない辺は縮約したほうが良さそう。
  • 縮約したら全てluckyな辺になるから…。あれluckyな辺を削除して、連結成分に含まれる頂点を数えればいいだけ？
  • 実装した。pretestAC。

D問題

• 特定の条件下でソートする問題。
  • むずそうだなあ。…って最小回数を求めるんじゃなくて、2n回以下で作るだけ？
  • それじゃあlucky numberを一つ使って先頭から順番に作ればいいだけじゃん。
  • 書いた。assertでチェックもしてみる。
  • サンプルで落ちた？ちょっと実装がまずかったみたいだ。
  • setを使って一から書き直す。時間がかかったけど書けた。pretestAC。
  • ってHackされた。残り4分しかないんですが。
  • どうせコーナーケースだろうと思って、試してみる。
  • 3という列で-1を返してる。これって答え0だよね。
  • という訳でlukcy numberが無くソート済みの列で死んでたっぽい。
  • 修正してsubmit。contest is over。

E問題

• 時間かければ解けそうな気はする。

結果

oooox 3600 47位 2057→2141。
Dの実装に時間がかかりすぎた気がするけど、こんなもんか。