|
これは、Competitive Programming Advent Calendar Div2013の15日目の記事です。
注）pepsin_amylaseさんはコンテスト翌日に解説を完成させていました。
競技プログラミングの幾何って強実装に偏り過ぎだよなーもっといろいろできるよなーと思ってたので開催しました。*1
また、難しい問題ばかりでつらぽよにならないように部分点をたくさんつけました。
乱択を出そうと思ってたら乱択じゃなくなってた問題です。
個人的には一番のお気に入りです。
DPかフローと絡めてなんかできないかなーと思ってたら思いついた問題です。
部分点解法がDP、満点解法がフローとやりたいことやれました。
計算幾何っぽいアルゴリズム問題出したいなぁと思って出しました。
あと、あんまりクエリ問題が出題されてないのでその辺で一問出したいと思っていました。
有名すぎるかなぁと思ってましたがあんまり激しいと誰も解けないのでこれくらいでいいかなとなりました。
やっぱり強実装は出さないと、ということで出題しました。
実はD(2)が夏合宿のボツ問なのですがボツにするにはもったいないので幾何コンで出してみました。
「幾何コンの最終防衛問題」となると円錐曲線程度では生ぬるいなと思ってやばい問題を出しました。
本当はもっと難しい制約になるはずだったんですが、解けなかったのでこの制約で落ち着きました。
全体的におもしろい問題を作れたと思っています。
特にABはいろんな人に褒められて嬉しかったです。
Cの制約が読み落としやすいのはすいませんでした。
ああいう制約は問題文中にも書かないと読んでもらえないことがわかったので皆さん気をつけましょう。
あんまり幾何じゃなかったという感想を聞きましたが、正確には「あんまりICPC幾何じゃなかった」だと思います。
CDは完全に幾何ですし、ABも幾何の感覚があると解きやすいと思います。*2
幾何ライブラリを使う問題が計算幾何ってわけじゃないでしょ、というコンテストなので思惑通りではあります。
難易度調整はかなり悩みましたがそこそこうまくいったと思っています。
「３時間幾何を解かせ続ける」という難しい課題をそれなりには達成できたかなと思っています。
部分点を大量につけましたが、小問ごとに別の問題にしたほうがTLE待ちしなくていいからいいんじゃないのという意見がありました。
事前にそれは考えていましたが問題文どうしようかなぁとか色々考えていると面倒になったのでやめました。
たぶん分けたほうが良かったと思います。
既出リスト
来年もやろうかなぁと思っているので変な問題の案がある人はぜひ作問側にまわってみませんか。
