ULM Local Contest

UVa

最近鬱モードなので、気晴らしに参加してみました。


いろいろあって、25分遅れで参戦。

Problem A: Another lottery

  • 問題を読むのに手間取る。
  • 最後のくじに当たった人が勝つに決まってる。さっくり書いて通した。

Problem B: Ballot evaluation

  • 面倒くさいけど書くだけだ。
  • 書いた。通した。
  • id:iakasTはGを解いてる。やってみよっと。

Problem G: Generate random numbers

  • もしかして: 平方採中法
  • 画面端をよく見てみたら、「Sampleの最後のケースが最悪ケースだよ」と書いてあった。
    • わざわざそんなこと言わなくても、最悪ケースでも一瞬で終わることは鳩ノ巣原理から明らかなのに・・・。
    • これはどうでもいい文章を読ませて時間を奪うトラップに違いない。まんまとひっかかったぜ！
  • そんなことを考えているうちに通りました。
  • またまたStandingsを見てid:iakasTを追いかける。Dか。

Problem D: Dark roads

  • ・・・何のひねりも無いMST？
    • こういう問題出されると、なにかトラップがあるのでは / 問題読み間違えたのではと疑ってしまう。
  • 適当にクラスカルして、Sampleが合わなかったらそのとき考えよう。
  • 手元のマシンにライブラリを用意していなかったので、適当にDisjointSetを実装。
    • つまらないバグ埋め込んでしばらく嵌った。orz
  • Sample出たので送ったら通った。
  • ついにid:iakasTと問題数で並んだので、適当にEを解いてみることに。

Problem E: Elias gamma coding

  • 頭に追加できる 0 は1個だけと勘違いしてしばらく嵌る。
  • 左から順に、頭に0を追加するか決めていく方針で考えてみた。
    • DP ... 現実的な値まで計算量を落とせない。
    • Greedy ... 書いてみたけど答え合わない。
    • モンテカルロ ... Sampleの最後のケースがどうしてそうなるのか知りたくて書いてみた。もちろん送れない。
  • いつの間にかid:iakasTがHを解いてる。進路変更。

Problem H: Hotel booking

  • 楽な方法をいろいろ考えてみたけど、結局「ホテル+始点+終点の数だけDijkstra」に落ち着きました。
  • バグを入れたり取ったりしながら実装。
  • さぁSubmitだー！と思ったらサーバ落ちてた。
  • しばらくしたら送れたけど、ジャッジサーバも落ちてるみたいなので次に行くことにしました。
    • 結局コンテストが終わるまで結果は返ってきませんでしたが。

Problem E: Food portion size

  • 「最適な量は、きっと誰かの食べる量の 1/1, 1/2, 1/3 のどれかになるじゃろう・・・」と決め付けて実装開始。
  • 有理数型作るのが面倒臭かったので、値を全部6倍してみました。
    • 問題ありそうだったけど、考えるのが面倒だったので問題ないと信じることにしました。
  • 答えが出てきません。問題があったようです。
  • そして終了。

Problem H: Hotel booking

  • TLEでした。
    • 4秒あるからと言って適当に書いたのがマズかったみたいです。
  • そういえば、問題を解くのは国内予選以来初めてのような気がします。
  • 順調に脳みそが萎縮してます。
  • 後は任せた > id:iakasT