OUPCについて・反省文
難易度見積りを完全に読み間違えてご迷惑をおかけしました。
問題はAizu Online Judgeの2350~2361に収録されているので解いてもらえると嬉しいです。
ジャッジデータはここでダウンロードできます。不備が見つかった場合は指摘していただけると助かります。
解説スライドは http://www.slideshare.net/oupc に上げてあります。
コンテストについて
企画段階の話
オープンにするかどうか
ジャッジシステムについて
- 1ファイルに複数ケース突っ込むか1ファイル1ケースにするかという問題が最初にありました。
- 1ファイル複数ケースというのは初期化処理とか計算量考える時とか色々余計なことを考えないといけないのであまり好きな形式ではありませんでした。
- しかし1ファイル1ケースというのはジャッジに時間がかかる場合キューが混雑する原因になりかねません。
- 一長一短ですが今回は1ファイル1ケースにしました。
- キューが詰まらないように大きめなテストケースを最初にジャッジするようにしました。
- また、よく知られているようにAOJは爆速で愚直な全探索が通ったりするので本番直前はジャッジの方にお願いしてAOJサーバでテストランさせて貰いました。とてもありがたかったです。
- しかし結果的には、提出自体が多くなくキューが詰まることはなかったようです。
コンテスト開催してみた感想とか
準備
ネガティブな面
- 難易度見積りに関しては完全に失敗で、申し訳なさでいっぱいです。本当にすいませんでした。
- 問題のhtml化とかは面倒だと感じることが多かったです。その辺の作業はほとんどhasi君に丸投げしてしまいました。彼には本当に色々と世話になりました。
- テストケース作るのは、面白いと感じることもありますがどちらかといえば面倒寄りな作業です。
- Divisorはテストケース生成でハミング数っぽいのを生成とかしていて面白かったんですが、今回面白かったのはそれくらいでした。
- RMQや四則演算は難しいケースを作るのが問題そのものより難しいと思います。
- バリデートが問題そのものより本質的に難しい、というのはよくあることです。今回は四則演算がわかりやすくそれでした。
- 数え上げが多いのもこれに起因していて、最適化系の問題は嘘解法落とすのが大変ですが、数え上げ系だと適当に大きいのを作ればコーナーケース以外は十分カバーできるから生成がとても楽になります。
ポジティブな面
- 問題考えるのすごい楽しかったです。
- 難しめの問題が必要になったときは、アルゴリズムの本とか読んで勉強しました。少しは実力向上につながったと思います。
- 有名なアルゴリズム教科書の練習問題がそのままコンテストに出てくる、という例はいくつかあります。
- 作問していると自分のジャンルの好き嫌いがはっきりとしてきました。
- ジャッジをしながら提出された解答を眺めて不安になったり喜んだり驚いたりしてました。
- 不安になるのは、合ってそうな解法が落ちたときとかです。
- 喜ぶ、という表現はあれですが想定どおりの解答や誤答が提出されると安心します。
- 見ても何をしているのか分からない解法が通ったり、すごい序盤で難しめの問題が通されたりすると驚きます。
- 長い期間(3~4ヶ月)同じ問題に向き合っていたので、問題にはどれも愛着が沸いてきました。
- 簡単な問題を入れるためどの問題を外すか選ぶときには愛着が沸きすぎていて選定に苦労しました。
- 自作の問題が「面白かった」と言ってもらえたときはやっぱりとても嬉しいです。
問題セットについて
難易度
- 難しくしすぎて本当にごめんなさい。
- 単に野良コンテストとして開くのではなく、立命合宿というイベントの一企画であることは強く意識していました。
- 合宿参加者の方々はわざわざ遠方からこのイベントを楽しみに来ているので、易しくしすぎて3時間とかで全完されるのも難しくしすぎて0完がでるのも等しく悪だと思っていました。
- 難易度についてhasi君と話をするときは、大体僕が簡単だと主張してhasi君が十分難しいと主張していました。
- 総評に書いていた難易度予想は実装量を無視して解法を思いつく難易度としてのものでした。
- それを踏まえても外しすぎでした。同じ問題に長く向き合っているとどうしても簡単、自明に見えてしまいます。これをどうやって回避すればいいのかは今でも分からなくて困っています。
傾向
- ICPCのアジア地区予選を想定した問題なので、ロシアゲーやクエリ処理系は出さないことにしていました。
- ロシアゲーはいつか出題したいと思っています。
- これに関してはICPCっぽくないのですが、問題文は簡潔明瞭にしてサンプルの説明は丁寧にすることが僕個人の意向により決まりました。
- TopCoderってサンプルに説明ついてて親切でよいですよね。
- ついでに問題自体も複雑な設定にしないことにしていました。
- 長い問題文にしてもあまり面白いネタを持ってる訳でもないし、重要事項がちゃんと記載してあるかのチェックが困難になるだけだというのがJAGの作業を通じて経験則として身についていたからです。
- 典型問題は出すまいと心に決めていました。
- もちろん典型手法を使うことには全く問題はなくて、出題の仕方から適用の仕方まで何から何まで典型というのが嫌なのでした。
- hasi君にも黙っていましたが、一時期は密かに蟻本補完コンテストにしたいと考えていました。αβが入っているのはその名残です。
余った問題
- 使わない問題が大量に余ってしまいました(僕が作ったのだと5~6問くらい？hasi君が作ったのも同程度余っている)。
- せっかくなのでこの問題も供養したいけど、どこで供養すればよいのやら。
- AOJに問題投稿できれば手っ取り早いんですけど。
- 簡単過ぎる、典型すぎる、無駄に複雑で綺麗じゃない、精度保証ができないという理由で切り捨てた問題なので再利用してコンテストやるのもいいかもしれません。
各問題について
作問方法とか解法とか。
A-B Problem
- very easy枠が必要であることに締切り数日前に気づいて、hasi君に適当に考えてもらったらできました。
- 問題はアルファベット順に並べることを早めに決めていて、この問題を追加する以前はClosest Segment Pairが先頭だったのでAかBで始まる問題名にすることを注文していました。(幾何が先頭とかドン引きされる)
- 最初に問題概要を聞いたときはgreedyやDPで解けそうだなあと思いましたが、very easy枠なので全探索で通るサイズにして出題することにしました。
- greedyでやってハマってしまったチームもいくつかあったようです。
- DPで解いてる人がとても多かったです。
- 競技プログラミングに慣れすぎると感覚が麻痺してしまいますが、慣れてない人にとって全探索というのは意外にコーディングが難しいという事実を忘れがちなので注意したいです。
Closest Segment Pair
- なんか面白そうなネタないかなー、といろんなアルゴリズムの本の練習問題をパラパラ見ていました。
- この問題はセジウィックのアルゴリズムCに練習問題として載っていて、これを幾何枠2に当てようと思っていました。
- でも締切りが近づいても全然分からなかったので、制約を緩めてネタ問題にしました。
- とはいえ線分の距離を求めるのはそれなりに大変だし、幾何計算が重くて枝刈りしなきゃいけないしでそれなりに面倒な問題であることは認識していました。
- 制約が怪しいことは思ったよりも気づきにくかったようです。
- 制約が怪しいことに気づいても、ソートして枝刈りというのがまた盲点になっていたようで、定数倍最適化をごりごりやって通している方が多かったです。
Divisor
- Hallの結婚定理とかちょっと調べていたら、Dilworthの定理というのが存在することを知りました。
- 知った瞬間、「何て競技プログラミング向けの定理なんだ！」と感動したのを覚えています。
- とりあえず「Dilworthの定理」で検索してみましたが全然ヒットしませんでした。もしかしてあまり知られていないのでしょうか。
- 知識ゲーになるのはちょっと気が引けましたが、あまりに競技プログラミングにぴったりな定理だったのでこれを使う問題を考えてみました。
- そしたらDivisorの原型ができました。初めは、最大サイズのみを答える問題でした。
- 手っ取り早く思いつく半順序って、集合の包含関係とか倍数の関係くらいしかなかったので…。
- でも最大サイズを求めるだけだと焼き鈍し解とか提出してこられる可能性があるのに気づきました。それをされるとキューが詰まって大事故につながるのでおまけで辞書順最小を付けました。
Four Arithmetic Operations
- 元は行列式を整数でどうやって計算するか、というのが問題でした。
- 割り算はmod pでやればうまくいくことに割と早い段階で気づくことができました。
- Advent Calendarの記事で浮動小数点数について書いたとき、これを練習問題として紹介するつもりでした。
- でももしかしたら難しいのかもしれないと思ってhasi君に出題してみました。意外と気づかれなかったので出題することになりました。
- 初めは答は0以上2^31未満、|Y|≦10^9とかで考えていました。
- 負の場合でもうまくいくことをfura_2君に教えてもらった(直接この問題について話した訳ではないですが)ので答の下限が-2^31になりました。
- 本当はオーバーフローとか面倒なだけだったので緩くしたかったのですが、-2^31以上2^31未満とした方がこの制約が本質でないように見せかけられるので仕方なくこのままにしました。
- また、|Y|の上限も緩くした方が素因数分解とかちらつかせることができそうだったので制約を緩めて|Y|≦10^6にしました。
- 本番当日、想定誤答であるBigIntegerのTLE解が最初に提出された時はテンションが上がりました。
- そしてコンテスト終了後、予想以上に参加者の時間を奪ったことに困惑しました。
- かなりの上位者でもBigInteger解を提出しているのを見るに、やはり多倍長整数の計算量というのはうっかりしやすい要素のようです(自分だけではなかった！)。
- 素数pを自分で好き勝手に選ぶ、というのが自分には面白く感じられました。
- 結構インパクトのある問題になったのではないかなあ、と自画自賛してみます。
Fractional Knapsack
- 最初はvery easy枠で容量も価値も正のものだけを考えていました。
- その後難易度がアジア地区予選想定ということでどうやって難化させるか考えていました。
- 容量と価値を負にしたらどうなるかな、という話をふとhasi君に話してみたら線形だからこれでもgreedyでいけそうなことが分かりました。
- そういえば、許容誤差は最初10^-5でしたが浮動小数点数の精度の問題上10^-3に変更になりました。相対誤差は色々面倒なので…。
- 意外に解かれませんでした。理由はいくつか考えられます。
- そもそもgreedyというのが実は気づきにくい。
- 0の場合のコーナーケースに引っかかりやすい。
- 正と負の両方を考えないといけないgreedyだから、実装が難しい。
- 三分探索でやっていた人も結構いたようです。
- 全て正の場合に帰着させる解法は僕等には思いつきませんでしたがすごく感心しました。
Game
- 作問者が二人ともゲーム木探索好きなのでゲーム木探索な問題を入れることは初期から決まっていました。
- 勝ち負けだけを判定する問題は解き方が知られ過ぎているので、教育的な意味を込めて最短手数で勝ちにいく問題にすることも決まっていました。
- 後は適当にルールを決めてゲーム木探索の問題にしました。
- よくあるビットDPはあまりに典型すぎて面白みがないのでαβ探索を要求することにしました。
- 普段からαβ好きだと公言していた自分ですが、さすがにコンテストが近くなると発言しないように注意しました。
Palindromic Anagram
- Aで始まるvery easyな問題が欲しかったのでAnagramという問題名で最初考えていました。
- 文字列といえばPalindromが定番なので組み合わせてみました。
- そうすると簡単な問題に落ち着いたのでそのまま出題することにしました。
- 最初はO(|S|)で解けるからサイズを大きくしてmodで計算させようとしていましたが、階乗で割り算するときとかにフェルマーの小定理という割と難しい知識を要求していることに気づいて全て64bitで計算できるサイズまで小さくしました。
Permutation
- トポロジカル順序の個数を数え上げる問題をいくつか考えていました。
- 最初は木が与えられてノードvが丁度k番目にくるトポロジカル順序の個数を数えよ、という問題でO(V)を要求するつもりで考えていました。
- タイトルもTopological Orderというのが初期案でした。
- 数日間O(V)を考えていましたが解けなかったのでO(V^2)で出題することにしました。ずっとO(V)を考えていたのでO(V^2)は自分としてはすぐに見えました。
- とはいえO(V^2)も決して自明というほど簡単ではないのでこれはこれで程よいDPだなあと思っていました。
- その後、木として陽に与えるよりも順列として出題したらうまく偽装できることに気づいて問題を変更しました。
- この偽装はお気に入りで、これによって難しさが上がっただろうと予測していました。
Plane Division
- hasi君に、「やるだけだけど狂気感ある問題作っといて、できれば幾何系で」とか無茶振りしていたらコレが出てきました。
- しかもhasi君のジャッジ解はロバストに誤差無しで解いていたので恐怖を感じました。
- その後自分の解答作るのが遅れてしまいましたが、doubleで解いたら割とあっさり書けました。
Range Minimum Query
- RMQは自分の一番好きな問題です。というかsparse tableが好きなだけですが。
- そのことはTopCoder関西飲み会のときに公言していて、誰かに「OUPCに出題されるに違いない」とか言い当てられてヒヤヒヤしていました。
- 最初は実際に復元を要求する問題で、値の更新は無しで考えていました。
- しばらく考えると解き方が分かって、また更新があっても同じ考えが使えるため点に対する更新を要求することにしました。
- 実際に復元するのはバリデートが大変なだけなのでYES/NO問題にしました。
- 締切り直前に、点更新だと蟻本丸写しでできてしまうのでよくないと思って区間更新に差し替えました。
- NOの難しいケースを作るのは大変でした。データはとても弱いです。
#2SAT
- とりあえず激ムズな問題を作るためにアルゴリズムデザインの木分解あたりのところを読んでいたら3SATに関する記述があったのでSATの数え上げを考えてみました。
- 木分解については結局よく分からなかったけど、SAT数え上げは出現回数の制約つけたら解けそうに思えました。でも3SATは難しかったので2SATで考えることにしました。
- 最初は2SATなら制約無しでも解けるんじゃないかとか思って考えましたが無理でした。変数の出現回数2回に制限してみたらうまく解くことができました。
- 簡単なDPの割に典型でない感じになって気に入ったので今回のセットにねじ込みました。
- 特に、環を適当な箇所で切断する、というのが自分には面白く感じられました。
- ただ、数え上げのグラフ系DPというのが順列と被っていたのがやや気になりました。でもグラフといっても線か環のなんちゃってグラフだし、難易度も大分差があるのでそのまま出題しました。
- N=1000はブラフです。
- あまり解かれなかったのはとっつきにくさが原因だったんでしょうか。
- 解法自体は見えやすいものの、簡潔な実装が意外と難しいというのも原因かもしれません。
おわりに
- 参加して下さった皆様、色々な意見を下さった皆様には本当に感謝しています。ありがとうございました。
- 立命合宿で問題提供の機会をくれた伊藤さま、Aizu Online Judgeを使わせてくれた田山さまには特にお世話になりました。ありがとうございました。
- さまざまな環境整備をして、難易度に関して暴走しがちだった自分を諫めてくれた橋本くんもありがとうございました。
- またいつかコンテストを開催する機会があるかもしれません。その時は今回の反省を生かして難易度調整をしっかり行った上で出題したいと思います。その時があればまたよろしくお願いします。
