オープニングセレモニーのUETのパフォーマンスはUETの学生さんたちがやっていたらしいです。活力を感じます。
色々と問題準備を手伝っていました。自分が原案だった問題の記録を書きます。
C問題 (Bit Count Sequence)
昔作ってボツにしていた問題を取り出してできた問題です。 規則によって生成される巨大な数列の中に、入力から与えられる数列が連続した部分列として何個出るか求めるような問題を作りたいと思っていました。 類題として FizzBuzz の出力を連結したときに特定の部分文字列が何個あるか求める問題がどこかにありましたが、そんなノリです。
規則性のある列としてはなんでもよかったのですが popcount なんかいいんじゃないかなぁと思ってそれっぽく作りました。元々は数え上げの問題のつもりだったのですが冷静に考えると想定解がおかしい事に気づいたのでやむをえず最小値を求める問題に変えました。 問題文を整理していると最初のアイデアの根本にあった「巨大な数列」というのは消滅して、単に自然数を求めるだけの問題になりました。
様々な解法がありえる問題で、解説に書いたもの以外にも2つ異なる解法があることをコンテスト前から知ってました。 想定以上に誤答が多く、かつ落ちているケースも選手によってだいぶバラバラという、あまり見かけない状態になりました。
E問題 (Duplicates)
大昔に作ってボツにしていたところから引っ張ってきました。何を思って作ったのかあまり記憶がありません。当初は構築要素なしで、最小値だけ求める問題のつもりでした。
今回 Championship で出題するに当たって、最小値だけだと無証明で突撃できちゃうからちょっと微妙だなと思って構築要素をつけました。 方針次第ですが想像以上に難しくなったので直前になってサンプルを拡充させたりしていました。
I問題 (Symmetric Boundary)
これも大昔に作ってボツにした問題を引っ張ってきてリメイクしたものです。 当初は「点対称」という条件付けはなく、単に与えられた点を境界に持つ凸集合としてありうる最小面積を求めるだけの問題でした。 なんかかっこいいつもりの想定解があるつもりだったのですが、この設定だとかなり微妙なことになることに真面目に考え出してから気づき、この設定のままだと出題できないなぁとなりました。(理由は自明ではないですが書くのも面倒なので考えてみてください)
でも設定が個人的に好みだったのでどうにか復活させられないかとかなり試行錯誤して「点対称」な領域に限定するとまぁまぁいい感じの解法が生えることに気づいて、それを問題案として完成させました。
アルゴリズム自体は割とシンプルですが凸包を取るところで普段あまりやらないようなことを求められる(同一直線上に乗っている点も残して凸包を取ったりしないといけない)ので実装は見た目よりだいぶ罠があるんじゃないかなぁと思っています。 提出までたどりついたチームがいなかったのは少し寂しかったですが、考察自体もそんなに自明ではないはずなのでやむを得なしとも思います。
G問題
改題の提案とテストケース作成をしました。強いテストケース作るのが地味に難しかったです。
D問題, L問題
解説を書きました。包除原理も線形代数も難しい。
全体
とにかく初開催ということで参加者のレベル感がまるで掴めないので難易度調整とかまるでわからんと思いながらやっていました。 少なくとも日本大会でいうとトップ15位くらいが集まっているのでだいぶレベルは高そうで、かつ他のリージョンとかチラ見してもレベルが低い感じは全然ないように思っていました。 どちらかというとちょっと難しすぎるんじゃないかと感じるくらいがちょうどいいんじゃないかと思って自分は進めていた気がします。
開催前にチーム HoMaMaOvO の皆様から有益なフィードバックをもらえて非常に助かりました。
今回は環太平洋のアジアの国々の人たちが集まるグローバルなチームで問題セットを作り上げました。 この手の経験は個人的に久しぶりだったので良い刺激になりました。英文校正は chatgpt にかなり頼りました。
競プロの問題をいつものように準備してるだけだとなんか物足りないなぁと思って途中から kotlin を使って想定解を書いたりしていました。 書いてて楽しい言語なのがわかってよかったです。
今回は偶然にも自分の有給消化期間とコンテストの準備期間が被っていたのでかなりコンテストの準備に時間を割けました。 来年以降は… 個人的にはヒューマンリソースが欲しいところではあります。。
