ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

WUPC2019のお話(有志コンテストの準備編)

ということで、今回はWUPC2019に向けて準備してきたことなどをつらつらと書いていこうと思います。数か所問題のネタバレになる部分がありますのでご注意ください。
問題の解法についてはこちらをご覧ください。

emtubasa.hateblo.jp

やったこと

自分は運営サイド初参加で、(一応)途中参加だったので、大事な部分は先輩方に任せ、全体でやるような部分のお手伝いが主な部分であったかと思います。
いくつか羅列していくと、

  • 問題の考案

  • 解法の"捻出"

  • writer解、嘘解法、TLE解等の作成

  • テストケースの作成

  • 問題文の清書

といったところでしょうか…日程決めや、AtCoderさんとのやりとり等は先輩方がやってくださったので、特にかかわることはなかったです。

問題の考案、解法作成

途中参加ということで、初めからいくつか問題の候補は存在していました。が、せっかく参加するので、問題をいくつか作ってみよう、と思いつくることにしました。
基本的には、自分はまず問題を作成してからその問題についての解法を考える、というスタイルをとっていました。
そのため、あるかもわからない(+自分が解けるかもわからない)問題について1日解法を考えていたりもしました…

今回作成した問題

自分は、Choose Your Charactersと、Artistの2問を作成しました。
どちらも、細かい(?)話はもう一つの記事に書いてあるので、興味があればそちらをご覧ください。
前者は、問題の枠組みを作成してから、自分でも解けるような解法になるように条件、制約を設定しました(結果的には高速化が可能だったので制約は引き上げられることになりましたが…)。後者については、最初から制約や条件を決めてから、解法を半日ぐらいかけて出しました(が、結局それが嘘だったのは秘密です)。
あと数問作成したりもしていましたが、つまらなかったり、解法がわからなかったり、時間が遅すぎたりしたのでお蔵入りとなりました。
先輩方に話を聞いたところ、問題の作成方法は問題ごとにバラバラみたいで、あるアルゴリズムを作りたいからそれに合わせた問題を作成する、というパターンもあるみたいです。それはそれで問題の作成難易度が高そうです…

writer解、嘘解法、TLE解等の作成

解法をいよいよコードに落とし込んでいきます。今回、できる問題については全員がwriter解を作成する、というのが目標だったため、そこそこのwriter解を書きました。
とはいっても、今回の問題は自分にとって難しいのが多かったため、ヒントだったり答えを教えてもらいながらが多かったです(むしろ、最終的に出題された問題の大半は自力で解けていない気がします)。ここで初めて実装したアルゴリズムもありました。
嘘解法や、変な貪欲解等も作成していきました。真面目に解いた問題が嘘解法でも役に立つのが、すこし悔しかったです。

テストケースの作成

テストケースは、ランダムなケースと、手で作成したケースの2つを用意します。
また、上で作成した解法や、このテストケースは、github上で管理します。
そして、今回はrimeというツールを利用して、randomケースの作成や解法の一致(と同時にTLE、WA...等)の確認を行っていきます。
こちらのツールの使い方については、beetさんの記事がわかりやすいので割愛します。
ここで驚いたのが、ランダムケースの作成の難しさ、です。
例えばChoose Your Charactersの場合、特に何も考えずにランダムにケースを生成すると、答えが"1 2"になるケースがほとんどになってしまいます。
同様に、Artistの場合は、答えが"0"になります。
そこで、ある程度故意に変数を偏らせたり、一部先に手で変数を決めてから残りをランダムに埋めていくことで、きっちりと答えがばらけるようにする必要があります。
最初は適当にランダムに配置すればいいや、と思っていたのですが、そんなことなかったです。
また、手でいくつかのテストケースの作成も行います。
一番変数が小さく(大きく)なるケースはもちろんのこと、ランダムケースでは対処しきれない、様々な嘘解法を落とすケースを作成しなければなりません。
ただ変数が大きいだけのケースよりも、解くのに時間がかかる最悪ケースを考えたり(これは解法によって最悪ケースが変わってきたりもするので、想定できる範囲の解法すべてに対応できるようにします)、貪欲や乱数を利用しつつ、細かい部分を想定解よりも時間がかかる解法で解く、といった嘘解法を落とすようなテストケースの作成も必要になります。
また、ハッシュを利用する問題では、ある程度弱いハッシュの作成方法だと落ちるように、ハッシュを衝突させたりもしました。
誰がどのような解法を提出してくるのかがわからない分、この部分はとても難しいと感じました。実際、嘘解法が通るといったコンテストもちらほらありますし、それだけ大変だということを改めて実感しました。

問題文の清書

そして、ある程度完成に近づいてきたら、いよいよ問題文の清書です。
問題文は、誰が読んでも理解できることを目指さなければならず、これまた難しい作業です。普段ブログを書いてるときのように、パパパッと適当に書くわけにはいきません。
例えば、Choose Your Charactersの問題の
f:id:emtubasa:20190309012948p:plain
この部分ですが、かなり悩みました。
最初は、数式だけ表示していれば確実ではあると思っていたのですが、それだと直感的な理解ができないと思い、文章だけで表現することを試みました。
ということで、一番最初は

  • 同じ数字のペアが2回以上現れることはない。

という一文だけでした。
自分の中では、同じ入力と、a,b反転させた入力の両方を表現しているつもりだったのですが、これだとわかりにくいかもしれないということだったので、

  • 問題文の条件と矛盾する入力は与えられない。

という文章に変更しました。しかし、これだと結局矛盾した入力がどういうものかわからない可能性があるため、最終的に上の画像のような文章になりました。
これにより、問題文をさらっと読める方が増えたかどうかはわかりませんが、自分の中では納得できる文章になったと思っています。
このように、どの問題文についても、誰が読んでも理解できる問題文、というのを目指して全員で確認していきました。
また、問題文はhtml形式で書いていくのですが、自分はこれを触るのが初めてでした。
そのため、最初はほかの方のを真似してそれっぽくやっていたのですが、文法をかなり間違えていたため、大変でした…

解説PDFの作成

自分はD問題の解説を作成しました。
問題文同様、できるだけ多くの人が理解できるように書かなければならないので、とても難しいです。理解できなかった方々、文章力が足りず申し訳ないです。
また、普段ブログに解法を書く際は、いきあたりばったりでささっと書くことが多く、大した見直しもしないのですが(そのためバグがたくさんありそうです、見てないのでわかりませんが、ごめんなさい)、今回はきちんとしたものを作成しなければならないため、余計に難易度が上がっていました。AtCoderさんの普段のコンテストの解説は、とてもシンプルかつわかりやすく、綺麗にまとまっているのですごいと思います。
おそらく、完成した解説PDFは数日後にアップされるかと思うのでいましばらくお待ちください。

完成

こうして、問題文、想定解、テストケースが揃ったので、AtCoderのサイトにアップをして完成です。
問題の得点は、人によって500点だったり700点だったり、得意分野等によっても難易度が変わってくるので、今回はざっくり100~300でまとめることになりました。
結果、あのような配点になりました。
問題の順番も結構悩んだ部分で、要求される知識や考察力、得意分野によってバラバラなので、これが最適、と決めるのはなかなか難しいです。実際、E問題とC問題は、数日前に順番が逆になりました。必要されるアルゴリズムの難易度が理由です。結局、問題を解く際には、得点よりもコンテストの順位表から判断するのが一番賢いかもしれませんね。

当日の動き

基本的には、Clarの対応と、順位表を眺めるだけです。
Clarの対応はほとんど先輩方がやってくださったので、自分は順位表を眺めていました。
嘘解法で通されていたりしないか、どんな別解があるかのチェック等をしたり、参加者がどんなケースで落ちているかを確認していました。
直前に加えたコーナーケース等がすごい機能していて、眺めている側としては面白かったです。
また、ちらほら自分達とは違うやり方で通している問題があり、これもまた面白かったです。
ただ、A問題で詰まっている人を見ていると少し胸が痛かったです。

感想

楽しかったです!主な作業が春休みに入ってからだったので、自分の時間をある程度ゆったりと使うことができました。グループワークをするのもなかなかない経験で、しかもいろんなツールを使ったりしながらだったので、新しいことだらけで面白かったです。
高難易度の問題を自力で全然解けなかったのが唯一悔しい点です。
また何か機会があれば、コンテストを開催したいなぁと思っています。