TopCoder SRM 480 (Div 1)

僕ほど練習の成果がでない人も珍しいんじゃないか?

Result

233.88 / System Test Failed / Unopened
0チャレンジ

199位
1971->1937

Easy InternetSecurity

250 450 1100のセット。
お、ってことはMediumいけそう!チャンス!

問題

Webサイトのアドレスと、そのサイトのキーワードが与えられる。
"危険なキーワード"が与えられ、サイトのキーワードのうちthreshold個以上が危険なキーワードであるサイトは危険なサイトとされ、そのサイトのキーワードも全て危険なキーワードになる。
このプロセスは再帰的に適用される。


このとき、危険なサイトの名前を出力せよ。

試行錯誤

えーと、更新がなくなるまでループを回せばいいのかな?
危険なキーワードはsetに入れて……


Webサイトのキーワードがスペース区切りで与えられるのが微妙に鬱陶しい。
書いた。よく見直す。Increasing orderで出力せよとか書いてある。
あ、これはWebサイトのIDの昇順だから、最初に与えられた順でいいのね。
おk.送信。

Medium NetworkSecurity

自分にしてはめずらしくそこそこ速いEasyのSubmit.

問題

いくつかのコンピュータといくつかのサーバがDAG(有向で閉路のないグラフ)を作っている。
グラフの辺は、コンピュータ同士、またはコンピュータ→サーバを結ぶもののみである。


このネットワークの、コンピュータ→サーバ間の辺に以下の条件を満たすようゲートを設置したい。

  • コンピュータcから到達可能な全てのサーバsについて、ゲートを通りsに辿りつくようなパスが一つ以上ある

このとき、必要なゲートの最小の個数を求めよ。

試行錯誤

えーとえーと。悩む。
図を描いて考えると、要するに一番下流にゲートを設置すればいいってことだ。
コンピュータのノードのうち、葉のノードからグラフを逆に辿って行って、そこにサーバから初めて回線が来た場合ゲートを設置する、という感じでいいんじゃないだろうか。


いいんだよな?いいと思う……
えーこれ450なの?全然簡単じゃないじゃん。


書いてみる。サンプル合った。よーーーく見直しして送信。
残り時間は全てE,M見直し。

Hard

Unopened.

Challenge

Easyでループ一回しか回してない人とか、出力順おかしい人とか居るかなあ、とか思ったけど居るわけなかった。
そもそも出力順おかしかったらサンプル通らないしな。


Medはどう考えてもおかしい解答があったがサンプル作れなかった。

System Test

450おちたあああああああああああどうしてええええええええええええ
まじクズだなぼく