はじめに
kureha といいます。AtCoder 黄色ですが、半年ほど Rated 参加できてないのでそろそろしたい気持ちになっています。OUPC2023 Day1 大阪大学セットにて問題作成陣として参加してきました。原案を出した問題について色々書いています。
楽しんでいただければ何よりです。
D - Han Burger
ハンバーガー的な文字列を作りたいと色々試行錯誤していたところ、括弧列から定義を引っ張ってきて問題と相成りました。
サンプルが弱いのは意図的なのですが、ペナルティがたくさん出たのは特に想定していませんでした。最初の 15 分くらい AC が出なくて冷や冷やしていました。
E - Han Burger 2
原案と言っていいのかわかりませんが、出来た経緯をば。
Han Burger を区間クエリにして文字列の長さを聞く形にしようとしたところ、その性質から vwxyz さんがこの問題を生やしました。強い人はすごい...。
G - Impassable Game
問題文が長く、N - Bench と並んでそもそもあまり読まれなかった枠になるのでしょうか。やってみると案外解けるのではと思っています。
テストケース作成は KowerKoint さん、vwxyz さん、maspy さんにお任せすることになってしまいました。（ありがとうございます）
想定解法は O(NM/w + N^2) なのですが、python に合わせて 6sec にしたところ O(N^3/w) とかが通ったらしいです。
P - Score for Cutting Graph
Day1 唯一の構築問題でした。
着想は相加相乗平均の式から得ており、もともとは数列の並び替えでしたが、いろいろあって木を切る問題になりました。（vwxyz さんに証明していただきました。ありがとうございます）
部分点の実装を行う → 色々実験してみる → エスパー → 満点を取るという段取りが必要な想定となっています。
感想
楽しんでいただければ幸いです。ありがとうございました。
来年も作問側で参加したいと思っているので、そのときはよろしくお願いいたします。
卒論期間です。1文字も書けてません。
