A Contest from Dinajpur, Bangladesh

UVa

なんとも頭が回らない。国内予選が不安になってきた。

Problem F: Horror Dash

  • 問題文が何を言いたいのかよく分からない。
  • 最小値を出せばいいだけに見えるけど。
  • Accepted.

Problem B: Mega Man's Missions

  • サーバが重くて問題読めないので、ちょっとまったりしたりしてみた。
  • えーと、ただのビットDPだよね。
    • オーバーフローしないかな？ 16! を計算してみる。
      • 大丈夫っぽい。
  • 書いた。submit.
  • ...?
  • submissionがなかったことになってる...。
    • まだまだサーバが重いみたいだ。とりあえず次書こう。

Problem D: Drutojan Express

  • 単純なシミュレーションっぽい。
  • 書いた。
  • どうやらジャッジサーバも復活してるっぽい。
  • Bと一緒にsubmit.
  • Accepted.

Problem B: Mega Man's Missions

  • Wrong Answer. あれ？
  • とりあえず最大ケースを突っ込む。
    • 16! が...出てこない？
      • 違う武器で倒した場合も違う倒し方ということになってた。
  • submit. WA. えー。
  • ...
  • 1体目を倒すときにしかロックバスター使ってなかった。
  • 今度こそ Accepted.

Problem C: Dog Distance

  • 問題文がよく分からない。
    • R, S, Tが与えられないとと一意に決まらない気がするんだけど...。
      • あ、時刻 T にちょうどPNにたどり着くような速度ってことね。把握しました。
  • 両者の相対速度が同じであるような区間に区切ってやればいいな。でも面倒だ。
    • どちらかが折れ曲がる瞬間だけ考えればよくね？
      • 書いた。合わない。
      • ...よくないよ！
  • 片方が常に原点にいるかのように考えて、もう片方の軌跡を求める。
    • でも合わない。
    • バグも見つからない...。
  • というかこの研究室、さっきより蒸し暑くなってないか？
    • いつのまにか冷房切れる時刻になってた。
      • 室温30度弱。
      • 窓はほとんど嵌め殺し。
      • 泣いていいですよね。
  • 区間をもっと細かく区切ってやったら何が出るだろうか。
    • 答えが出てきた。
      • 時刻から位置を求めるところは合ってそうだけど...。
  • ...
  • これ使って嘘解法できないかな。
    • 時間帯を N 分割して、N個の時刻だけを考えてみたりとか。
      • 精度緩いし、書いてみようか。
        • 1,000分割: WA
        • 4,000分割: TLE
        • 時刻から位置を求めるルーチンを高速化してみた。
        • 4,000分割: WA
        • 40,000分割: TLE
        • 30,000分割: WA
      • 入力よく読んだら、これではダメなケースが作れそうな気がしてきた。
      • もう頭使いたくないけど、仕方ないので真面目に考えよう。
  • もう一度冷静になって書き直す。
    • やっぱり合わない。
  • ...あれ？
  • 片方を原点固定にして、もう片方をの軌跡をなぞりながら、点と線分の距離で最近点と最遠点をもとめる。
    • だめじゃん！
    • 最遠点ってどう見ても点と点の距離だよ！
  • やっとsampleでてきた。なんという回り道...。
  • submit.
  • WA.
  • もうやだ。

Problem G: Determine the Shape

  • 凸包をとることで反時計回りに並べてやって、あとは定義どおりにひたすら実装。
  • sample一発で出てきた。よしよし。
  • Wrong Answer...
  • あれ、4点なんだから凸じゃないケースあるよね。凸包って危ない気がする。
    • 凸じゃないケースを入れてみたら確かに間違ってる。
    • そういうのは絶対普通の四角形ってことでいいよね。
  • Accepted.
  • 次は何にしようかな。
    • miracさんが E を解いてる。やってみよう。

Problem E: Colorful Board 2

  • DPの匂いしかしない...。
  • 全然頭が回らんなぁ。どうやるんだろう。
  • ...。
  • dp[l][a][b][c] := 最大 l 色使えて、(0, 0)から(a, b)までを塗り、(a, b)の色が c であるような塗り方の数
  • でどうだろう。
  • 書いた。バグった。直った。送った。
  • RE. 配列の長さいっこたりない。TLE.
    • O(K4N2) (K = 50, N = 20) になってた。厳しいな。
      • でもローカルだと 1.2 秒ぐらい。
        • MODとる箇所を減らしてみた。ローカルで 0.9 秒。
      • まだまだTLE.
      • 各状態ごとに2重ループも回す必要ないのでは？
        • 式変形したら1重に畳めた。ローカル 0.1 秒。
          • submitぉぉぉぉ！
  • Contest is Over.

Result

  • 4AC, 26th.
  • とりわけ C が残念でした。
  • この暑さどうにかならないものかなぁ...。