SRM453.5

TopCoder

何でこんな簡単な問題が解けないのかと・・・。

250

  • 全通り試すだけじゃね？
  • BFS書いた。バグった。
    • 変数名の s.i, s.j と si, sj を間違えてたバグを見つけるのに10分強かかった。
  • でもまだ合わない。なんでだろう。
  • なんかこのプログラム無駄が多い気がする。・・・！
  • わざわざ H*W 回もBFS掛ける必要ないじゃん！1回掛けて一番遠いところに置くだけだ！
  • 書き直したらいつの間にかバグも消えた。submit.

450

  • 非平面グラフ <=> 頂点数5の完全グラフか頂点数3, 3の完全二部グラフを部分グラフに含む、だったはず。
  • まずは頂点数v辺数eでK5を含むのとK3,3を含むのと両方含むグラフの数をDPで求めて・・・。
  • あれ？
  • 問題を読み直してみた。同じグラフ何度も買えるし、そもそも買えるのは非平面じゃなくて平面なグラフだ。落ち着け俺。
  • 頂点数vの平面グラフの最大辺数か。ググって出てくるわけがないよな・・・。がんばって式立てよう。
  • がんばったら立った。サンプルの例とも合ってるし大丈夫っぽいけど、残り一分切ってた。
  • さすがに数十秒でBFSは書けないです。

Challenge Phase

  • あんまり落とせそうになかったので450の続き書いてた。書けた。
  • みんなのソース見てみよう。
  • なんでみんな 3*v-6 とか言ってるの？教えてうぃきぺ先生。
  • 普通に載ってた。泣きたい。
  • 自分の立てた式と比較してみた。V^3+E^2 <= 100の場合だけ全部合ってた。何なのこの微妙な式。

Result

  • 250が通って 144.46。
  • 1390 -> 1320.
  • Red Coder目指してますとか口に出すのも恥ずかしいレベルだ。
  • 明日(今日)は月曜授業に変更になったので1限目からです。