JOIでコードゴルフ１
JOIの問題を解いていたらいくつかの問題でShortest Codeが取れた。
最近の実装に対する意識の変化によるものだと思う。
記念にまとめておく。
グラフ系
春09 Advertisement(難易度8)
強連結成分分解
(795Byte→)673Byte
SCCが最もシンプルな形。
春10 Highway(難易度10)
オイラーツアー、最小共通祖先、セグメントツリー
(2210Byte→)1596Byte
セグメント木は様々な面から非再帰を用いる。
幾何
春07 Lines(難易度10)
線分の交点の重複排除
(1111Byte→)541Byte
複素数平面を使うと回転が簡単にできる。片方の線分を(0,0)→(0,a)の形にしてから内分の比を取ると、単純な式になる。
春08 Nightman(難易度10)
線分交差など
(1879Byte→)1481Byte
複素数平面で式を単純化。入力が整数であることから、微小な値だけずらすようなことをすることで、正確性を保ちつつ場合分けを回避できる。
春08 Belt(難易度10)
偏角の扱いなど
時間制限が10秒なので怪しい解法が通っているが、それを除けばShortest。
(1008Byte→)877Byte
本質的には他のコードと変わらない。
変数名が短い。
その他
本選09 博覧会(難易度10)
実装方針は複数考えられる。
(843Byte→)815Byte
４回転することで場合分け回避、二分探索で判定問題に落とすことで最大最小の扱いによるバグを回避。
