Hatena::ブログ(Diary)

菊やんの雑記帳

2012-04-15 GCJ2012予選

[] GCJ予選 19:54  GCJ予選を含むブックマーク

証明できそうな問題がないかなと探したところA問題だけだった。BとCもできるかもしれないけどめんどくさいからいいや

A問題 19:54  A問題を含むブックマーク

https://gist.github.com/2391779

ヒントの制約からなんとか関数を自動で生成したかった。

eexists (fun ch =>
  match ch with
    | "a" => _  | "b" => _  | "c" => _  | "d" => _
    | "e" => _  | "f" => _  | "g" => _  | "h" => _
    | "i" => _  | "j" => _  | "k" => _  | "l" => _
    | "m" => _  | "n" => _  | "o" => _  | "p" => _
    | "q" => _  | "r" => _  | "s" => _  | "t" => _
    | "u" => _  | "v" => _  | "w" => _  | "x" => _
    | "y" => _  | "z" => _
    | _ => ch
  end).

このへんまではまあ手で書いてやっても許されるだろう。で、ヒントをこの関数に食わせて reflexitivity で決定していく。

あれ、一個文字が確定しないぞ、しかたがないからほかの条件から埋めていくか。

しかし、ほかの条件はすごく重い。計算させようとしてすぐにemacsが凍りつく状態にないやがったので諦めて手で指定する。

ほかのプロパティーも重いのでかなり妥協して、Permutationだけにしたんだけど、やっぱり計算では証明できなくて非常に悲しい証明を書いてしまった。

OCamlを抽出して実行してもよかったんだけどめんどくさいから、trを抽出する。

tail -n +2 | tr ynficwlbkuomxsevzpdrjgthaq a-z | awk '{printf "Case #%d: %s\n", NR, $0}'

最終的にone liner

B問題 19:54  B問題を含むブックマーク

やるきがなくなってきたので、後の問題は適当にやった。B問題はやるだけ。

https://gist.github.com/2391806

C問題 19:54  C問題を含むブックマーク

非常にやるきがないので適当

https://gist.github.com/2391811

D問題 19:54  D問題を含むブックマーク

めんどくせー。格子点の方向にだけ光線を飛ばせばいいのはすぐにわかった。でも四角との交点の座標が有理数になる。めんどくせえー。

最初はboost有理数ライブラリを使って、直線と直線の交点を求めたりくそ複雑なコードを書いてみたんだけど、遅すぎるうえに計算が間違ってる。

しかたがないので、めんどくさくない方法を考えて、光線の方向が決まったら有理数が発生しないように空間をスケールしておけばいいじゃん。

ついでに、縦横のスケール比を変えれば8方向だけの移動しかなくなるじゃん。やったー。これで方程式解かなくても一歩ずつぶつかるまで歩いていけばいいじゃん。

https://gist.github.com/2391863

やったー実装できた。しかもかなり速くなったー。