yukicoder contest 209:writerをしました

　こんにちは。2019/3/22(金) 21:20~23:20のyukicoder contest 209(yukicoder contest 209 - yukicoder)
でwriterをさせていただきました。初めてのことで開始前は尋常じゃなく緊張しましたが，およそ160人の方に参加していただけました。ご参加ありがとうございました！
　以下では，準備の話とかコンテスト中のおきもちとかをてきとうに書いていきます。

A:野菜が苦手

　☆1が必要だなと思って作りました。野菜が苦手なのは本当で，特定の条件を満たさない限り野菜が食べられません(肉が十分量あるとかはその1つです)。最初は $O(A)$ を許していなかったのですが，☆1ということでやめました。コンテストでは150人程度の方がACしていました。

B:UMG

　バランス調整のために作りました。制約と計算量を意識しましょうという問題で，初心者向けとしては良かったのではと思っています。UMGというのは僕がいつも持ち歩いているウマゴン(UMAGON)のことです。他の問題文でも出てくるumgくんもそうです。こちらもおおよそ150人程度の方がACをしていました。

C:木を道に

　今回のセットの中で最初に生えたのはこの問題でした。なぜ生えたのか覚えていませんが，この位置として良い問題だったと思います。証明を考えると☆2.5でもよかったかもしれませんね。
　結局分岐の数を数えればよいということで，想定解は $\sum \max((次数)-2,0)$ でしたが， $(葉の数)-2$ で出している方も多かったです。よく考えると両者は一致するのでどちらでも良いです。
　僕やtesterさんは最初にこの問題を考えたとき，木の直径でなんとかするのかと思っていたのですが，提出でもこれをやってWAという方がそこそこ見受けられました。提出を見ながらわかるなあ思いつつとにやけていました。コンテスト中のACは120人程度でした。

D:umg tours

　ツーリストチケットと言いたかっただけなのですが，結果的に教育的な問題になったのでここに置きました。頂点に状態を持たせてDijkstra法を行うのはありがちな解法で，初めてという方にはいい練習になったのではないでしょうか。コンテスト中のACは70人程度でした。もう少し解かれると思っていましたが，頂点を増やしてから適切に辺を張る必要があったりなど，詰める段階や実装面では難しい部分があったと思います。
　ところで，この問題はC++でも実行時間がかかり，恐らくこの問題が原因でコンテスト中にジャッジが詰まってしまいました。ジャッジについては少し運営の方と相談すべきだったかもしれません。また，Python勢は制限時間が4秒でもちょっと厳しかったと思います。制約を小さくするのはなんかなあと思ったので許してください。

E:Kaiten Sushi?

　ボスとして用意しました。元々は「席が回る回転寿司屋で問題を作ろう！」というコンセプトで考え始めて(は？)，ボツ問を生やしつつこの問題に辿り着きました。実は解に気付いて証明をつけるのに数時間かかり，またtesterさんも同様で，証明までやるのはかなり大変な問題，という想定でした。想定解としては，ある位置での $(寿司の個数)-(お茶の個数)$ を見ると必要な最小の周回数がわかり，さらに最後に飲むことのできるお茶の位置も寿司とお茶の配置だけでわかるという，芸術点の高いものを用意していました。解けた方も解けなかった方も，是非とも解説を読んでほしいです。特にtesterさんは明示的に解を構成してくれました。
　ところがコンテストでは，寿司とお茶の取り方について貪欲が可能で，多くの人にsetなどを用いて貪欲をシミュレーションする解法で通されてしまいました。こちら側ではこの貪欲のちゃんとした証明が生やせていなかったのですが，普通に正しいようです。コンテスト中にtesterさんや既に全完していたtさんと証明を検討していました。提出をちゃんと見ると，想定解に近い方法で通している人も見受けられたので，それは嬉しかったです。
　結果的にコンテスト中のACは20人程度と，ボスとして十分機能したと考えています。解けた方も解けなかった方も，是非とも解説を読んでほしいです(大事なことなので2回書きました)。
　そういえば，「最近開店したというKaiten Sushi」というギャグには気付きましたか？

全体を通して

　難易度のバランスが不安だったのですが，結果的におおよそのAC者数が150-150-120-70-20だったのを見ると，良いバランスだったのではと思っています。DまではABCを意識，Eは暖色の人用という気持ちでしたが，狙い通りのセットになったと思います。コンテスト後は良セットだったという感想も多く見受けられ，嬉しい限りでした。

最後に

　またセットでやるとしたら夏休み頃なのかなあと思っています。競プロの実力としてはまだまだなので，力をつけて作問のレパートリーが増えればよいなあと思っています。
　時間があったので半分ノリで作問してしまいましたが，多くの人に解いてもらって，感想をいただけるのは本当に嬉しかったです。問題を見てくださったtesterの皆さん，参加者のみなさん，そしてジャッジシステムを提供してくださっているyukiさん，本当にありがとうございました！