Yet another Bangladeshi Contest

UVa

こうも難しい問題セットだと気力が切れてしまうのです。

Problem A: Hello World!

  • 布団取り込んだり晩御飯食べたりしてる間に始まってました。
  • 2^iを突っ込んだ配列から lower_bound で n を検索して、見つかった場所の添え字を出したら答えになってました。
  • lower_boundは意外なところで役に立ってくれる良い子だと思います。

Problem D: Guard the Land

  • 包除原理・・・を持ち出すまでも無い計算問題。
  • ちょっとだけバグったけどすぐ終わりました。

Problem J: Bits

  • 一番解いてる人が多い(と言っても数人でしたが)のでやってみました。
    • こういう問題はあまり得意ではないのですが。
  • 2のべき乗のときの答えは比較的簡単に求まりそうな気がします。
    • 頑張ってDPしたらでてきました。
  • あとはこれを使って一般的な場合を・・・。
  • ・・・。
  • わからん。あきらめよう。

Problem C: Temperature Monitoring

  • ・・・問題が長い。良くわからない。
  • 気力が無くなったので小一時間ぼーっとしました。

Problem H: Knight Tour

  • あんまり解かれてない問題でしたが、id:iakasTが突っ込んでたので真似してみました。
  • ただのBFS + TSPっぽい。簡単そうですね。
    • その割にはid:iakasTが何度かrejectされてるのが気になります。
    • Statistic見たら、案の定TLEが大量発生してました。
    • BFSをK回かけると間に合わないのか・・・。どうしよう。
      • BFSの代わりに計算で求まらないかと思ったけれど、ボードの端では移動が制限されることを考えると難しい。
  • ・・・。
  • ある駒から、周り 4x4 ぐらいのマスについてBFSで移動に必要な回数を求める。
  • それ以上離れたマスについては計算でどうにかしよう。
  • ・・・。
  • どうにか書けた。が、やっぱりTLE・・・。
  • とりあえず手元で最大ケースを作って100回走らせてみた。だいたい7秒ぐらいでした。
  • よく見たらTSPの方で時間を9割がた食ってる！
  • 素直にあきらめました。

Probrem J: Bits (retry)

  • 発想の転換。11の出現位置ごとに出現回数を数えてみよう。
  • 規則的なパターンが出てきた。こっちが正解だったのかー。
  • 頑張ってコーディングしましたが、最後のバグが取れたのが終了5分後でした。
    • ただの変数名の間違いでしたorz
      • まだsubmitしてないけど、こういうのは得てして一発ACだったりするので困る。
  • ぼーっとしてる場合じゃありませんでしたね。反省。