yukicoder273でwriterを務めました

今回初めてyukicoderでコンテストを開催できました。testerの皆さん、参加者の皆さん、ありがとうございました。
難易度としては、ABCの点数で 300 - 300 - 400 - 400 - 500 - 600 くらいを想定していました。
全探索、データ構造、DPなど、色々な分野から出題することを意識していました。
丁寧に考察すると典型問題に帰着する、というタイプが多かったかなと思います。
全問題でA君とB君がバトルしていたり、問題名でしりとりしてみたりなど、少し遊び要素も入れてみました。
また機会があれば、次はもっと考察パートが多い問題の作成に挑戦してみたいなと思っています。

A. Array Battle

最近あまり見ない気がする順列全探索です。
最初は得点の最大値を求める問題でしたが、それだと実はソートだけで終わってしまうので、testerさんの提案でこの形になりました。
最大値を取るパターンが何通りか、ということなので、得点を全て配列に入れて最後にソートすればわかりやすいでしょうか。

B. Beyond C

おなじみの二分探索 or しゃくとり法の問題です。ただし桁数が大きいので誤差には注意してください。
例えば C++ では lower_bound という便利な関数が用意されていますが、小数を扱うと WA になることがあると思います。
可能であれば全て整数で処理する方が良いです。今回も問題文の通り、積が C を超えないという形で二分探索すれば大丈夫です。

C. Cigarette Distribution

数学的な考察が必要になるパズルのような問題です。B君がどう行動するかがわかれば解法が見えてくると思います。
和が一定の時に積を最大にするにはなるべく均等に割り振るのが良い、というのはたまに出てくるような気がします。
(ちなみに最初はアメの予定だったんですが、AtCoder に既に Candy Distribution という問題があったのでタバコに変更することに)

D. Display Elements

座標圧縮 + Fenwick tree の典型問題です。
注意点として、A君とB君の持っている数字全ての大小関係が必要なので、両方の数列をまとめて座標圧縮する必要があります。
A君が出すべき順番は直感通りかとは思いますが、証明も考えてみてください。(解説に書きました)

E. Extra Fee

最短距離以外にも情報を持つ、いわゆる拡張ダイクストラ法を用いる問題です。
ダイクストラ法はDPの一種だと考えれば、一般のDPと同じように情報を増やすことで実装できます。
とはいえ慣れていないと実装には結構手こずるかもしれません。
問題が完成した後にtesterさんが発見してくれたのですが、実は過去にかなり似ている問題があったようです。(yukicoder No.807)

F. Flip Game

巡回セールスマン問題 (TSP) の応用問題です。
TSPでは、各頂点について既に訪れたか否かの情報を二進数で管理する、いわゆる bitDP による実装が有名です。
今回は各マスについて三通りの状態があるので、三進数で管理すればよいことになります。
(余談ですが、つい最近Twitterで 3^N のDPの話をちらほら見かけて、偶然とはいえちょっとびっくりしてしまいました)