天下一プログラマーコンテスト2014予選A

2014-08-10 | [Competitive programming]

A

「C++ 以外も使えるようにしましょう」という教育的目的が感じられる問題．Ruby で解いた

C

「(s1, …, sn) がすべてマッチする文字列が存在 ⇔ 任意の i, j に対して，si, sj がともにマッチする文字列が存在」 を用いる．

B

面倒な実装やるだけ (puke)

D

線分を角度の範囲にした後，区間たちの(円上の)最大安定集合を求める． 最大安定集合を求めればいいことに気づかずだいぶ悩んだ…

E

x を動かしたら y も動く，という感じのグラフを作り，強連結成分分解し，DAG に落とす． その後，「この連結成分を動かしたら列 i はここから下が動く」という値を求める．

結果

C, B で WA を出した (>_<) 「天下一全完」8 人出たが，なんとかペナルティで勝って 1 位