今年もジャッジメンバーとして問題準備をやっていっていました。
コンテスト全体を通して、ほとんどの問題は自分が予想を超える正解数で、個人的にはめでたいなぁと思いました。
- 全チームが3完した: E 問題なんかまぁまぁ実装が面倒な気がするんですがちゃんと対応できていて素晴らしいなぁと
- I 問題: それなりに難しいデータ構造問題だと思ったのですがなんだかサクッと通されていて驚きました
- G 問題: 実装がかなり面倒でコンテスト中に手を出せる人はいるのか…？とやや懸念だったのですがそれを吹き飛ばすような提出と正解が来て良かったです。testing tool が活躍していたなら僕は喜びます
D 問題の思い出
E := 1 | ( E E )というシンタックスがあって木の生成過程を表している。 2つの式に対してどちらからも生成可能な木はいくつあるか。
この問題に限らないのですが問題を作ったときの記憶というのがいまいち残っていません。最初は割とごちゃごちゃしたことを考えていて、整理し終えれば綺麗になるのですがその過程はいろんなものを選んだり捨てたりしていて言語化するのが難しいというのがあるのかもしれません。なので以下は半分くらい作り話ではあるのですが、書いてみます。
まず現代だと寂れた主題を扱いつつ中身が COOL な問題作ってみたい気持ち*1がありました。構文解析は定義通りに再帰関数を実装するだけの味気ないテーマですが、これを考えることにしました。 あとは変なものを構成して遊んでみたい気持ちもありました。これらが混ざりあった結果、無向木を作る構文を考えてみることにしました。 この時点だと何が生まれるのかよくわからんのですが、とりあえず終端記号はなんか必要で、二項演算子みたいなのも欲しい気持ちになります。 二項演算子というのは木と木から新しい木を作るわけですが、1本枝を足すのが自然そうに見えます。自然なのですが任意性が色々あってどれか一つに決めるのは難しいのでとりあえずはランダムに選ぶものだとしてみます。 そうすると式は木を生成するランダムな過程だということになります。ランダムならやはり確率とか考えた方が面白いんじゃないか… という気持ちが芽生えます。 芽生えたところでなんの確率を主題にするのかとまた悩むのですが、手で少し試行錯誤していると違う式から同じ木が生成できることがあるのに気づきます。そこでいまの原案に近いものができました。2つの式から木を生成して偶然同じになる確率はいくら？と。 このように最初は確率の問題として考えていたのですが、確率の分母のところは面白くないから要らないと思って削り、分子のところだけを問う数え上げの問題として仕上げました。 想定解も最初はよくわかってなくて2乗くらいのものを想定していたのですが少し冷静になって線形時間になることに気づいたり。
コンテスト後に面白かったと言ってくれた方がいてとても嬉しかったです。
その他
表彰式のホールが例年使っている場所と変わり、豪華で良かったです。yes/no セッションはだいぶ見入っていました (ジャッジはあらかじめ結果を知っているはずなのですがこのセッションのときは記憶が揮発しています。不思議)
選手だった人がスタッフになってコンテストを回してるのを見ると嬉しい。
