Hatena::Grouptopcoder

not's memo

 | 

2013-12-15

幾何コンテストの解説と感想

23:32 | はてなブックマーク - 幾何コンテストの解説と感想 - not's memo

これは、Competitive Programming Advent Calendar Div2013の15日目の記事です。

なんで解説を公開するのがこんなに遅くなったんですか?

f:id:not522:20131215224339p:image

注)pepsin_amylaseさんはコンテスト翌日に解説を完成させていました。


解説

slideshare

開催趣旨

競技プログラミングの幾何って強実装に偏り過ぎだよなーもっといろいろできるよなーと思ってたので開催しました。*1

また、難しい問題ばかりでつらぽよにならないように部分点をたくさんつけました。

出題意図

A

乱択を出そうと思ってたら乱択じゃなくなってた問題です。

個人的には一番のお気に入りです。

B

DPかフローと絡めてなんかできないかなーと思ってたら思いついた問題です。

部分点解法がDP、満点解法がフローとやりたいことやれました。

C

計算幾何っぽいアルゴリズム問題出したいなぁと思って出しました。

あと、あんまりクエリ問題が出題されてないのでその辺で一問出したいと思っていました。

有名すぎるかなぁと思ってましたがあんまり激しいと誰も解けないのでこれくらいでいいかなとなりました。

D

やっぱり強実装は出さないと、ということで出題しました。

実はD(2)が夏合宿のボツ問なのですがボツにするにはもったいないので幾何コンで出してみました。

D(4)

「幾何コンの最終防衛問題」となると円錐曲線程度では生ぬるいなと思ってやばい問題を出しました。

本当はもっと難しい制約になるはずだったんですが、解けなかったのでこの制約で落ち着きました。

感想

全体的におもしろい問題を作れたと思っています。

特にABはいろんな人に褒められて嬉しかったです。


Cの制約が読み落としやすいのはすいませんでした。

ああいう制約は問題文中にも書かないと読んでもらえないことがわかったので皆さん気をつけましょう。


あんまり幾何じゃなかったという感想を聞きましたが、正確には「あんまりICPC幾何じゃなかった」だと思います。

CDは完全に幾何ですし、ABも幾何の感覚があると解きやすいと思います。*2

幾何ライブラリを使う問題が計算幾何ってわけじゃないでしょ、というコンテストなので思惑通りではあります。


難易度調整はかなり悩みましたがそこそこうまくいったと思っています。

「3時間幾何を解かせ続ける」という難しい課題をそれなりには達成できたかなと思っています。


部分点を大量につけましたが、小問ごとに別の問題にしたほうがTLE待ちしなくていいからいいんじゃないのという意見がありました。

事前にそれは考えていましたが問題文どうしようかなぁとか色々考えていると面倒になったのでやめました。

たぶん分けたほうが良かったと思います。

それ、既出ですよね?

既出リスト

  • C(4):動的凸包はCFに出たらしい
  • D(1):CFで同じ問題が出たらしい
  • D(1):furaさんのライブラリにこれ専用みたいなライブラリがあった
  • D(2):ICFPCで同じ問題が出たらしい

来年に向けて

来年もやろうかなぁと思っているので変な問題の案がある人はぜひ作問側にまわってみませんか。

*1:最近のICPC幾何は方針によって実装量が変わる問題が多くなって良いですね

*2:まぁ僕は幾何じゃないものが幾何に見えることが多いので感覚が違うかもしれませんが

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/not522/20131215
 |