info
writer(アルファベット順)
Badlylucky, Herring101, kotamanegi, KowerKoint, shinchan, vwxyz
tester(アルファベット順)
Daylight, E869120, hiiragi589, littlegirl112, WA_TLE, ygussany
講評
OUPC2022はいかがだったでしょうか？ 難しい問題が多かったこともあり、チーム制限を大幅に緩和しましたが、それでもまだ難しい問題セットになっていたと思います。本当にお疲れ様でした。
東京大学の学祭「駒場祭」や京都大学の学祭「11月祭」と被ってしまったことは、こちらの確認不足であり今後の改善点としたいところです。予定が重なっていてもなおこちらに出てくださかった方々に、この場を借りて多大なる感謝を申し上げます。
問題を募集したところ、想定以上に高難易度の問題が揃ってしまいました。そこで、OUPC2022では問題はそのまま出して、チーム編成の制約緩和などの面から難易度を緩和しようと試みました。問題の難易度はまばらですが、チーム全体のAC数としてはきれいに並んだため、一定の効果はあったと考えています。
問題数が多くなったこと、問題が難しくなったこと、実装難の問題が複数含まれていたことを受けて、今回競プロ史上初(?)となるレイドチームの創設に至りました。期待通りの人数が集まってくれるか、集まった人たちがチームワークを発揮して楽しんでくれるか心配だったところはありますが、10人以上が集まってD問題以降の問題の議論に取り組んでくださっているのを見て安心しました。
来年また開催できたらより多くの人を集めて、レイドチーム同士でも対戦できるくらいにしたいと思っています。
前述の通りOUPC2022はOUPC史上最難かつ問題数最多のコンテストとなりましたが、作る側の負担も最大となりました。解法をチェックする人も全体的に不足傾向にあり、testerを探すのも大変でした。tester探しに苦労する問題は今後も続くと予測されるので、協力してくれる方を募集しています(AtCoder橙以上)。
また同時に、問題文をチェックする人も不足していました。問題文については、10問を超えると1人でのチェックは困難になってくると思います。testerの問題にもつながりますが、担当する問題を分けるなどのマネジメントの分割が必要になってくるのではないでしょうか。しかしそれをする人員も足りていないのがつらいところ……TTPC2022はOUPC2022より2問多いセットでしたが、いったいどのように管理していたのか……。
以下、問題ごとの講評です。
A:
最初の問題でしたが、少し注意力が必要な問題でした。
B:
簡単枠として出題しました。
結果として、コンテストに参加された方のほとんどに「解けた！」を届けることができました。
難易度が控え目なので、導入文 など に小ネタを挟んでいます。見つけられるかな？
C:
針の長さの倍率に平方根がついてるなど少しだけひねっていますが、ここまでは競プロをある程度やってる人なら誰にでも楽しんでもらえる問題だったと思います。
行列派と複素数派に分かれていたのは面白いです。
D:
問題テーマを見て面食らった人が多かったのか、1時間ACが出なかった問題でした。
三次元の計算幾何は競プロではあまり見ないので苦手意識を持っていた人も多かったかもしれません。
こういう問題は同時コーディングありのコンテストでは分担作業ができるのでチームの強みが出るところじゃないかなと思っています。
E:
この問題はもともと所持金が減っていく問題設定になっていて、鉄道社長になってお金を稼ぐ某ゲームに影響されたものでした。
行列を構築する際に少しややこしいことを考えないといけないので時間がかかることを想定していましたが、28分でFAを取られてしまいました。おめでとうございます。
F:
ひねくれ枠として出題しました。実はtesterも全員ペナルティを出しながらACしており、サンプルを親切にするか悩んだ問題です。あえて修正を加えずにそのまま出題したところ、目論見通り(?)ペナルティが多いもののAC率も比較的高い問題になりました。
G:
ボス問でした。
DPをBitsetを用いて高速化する問題でしたが、経路復元のためにすべての配列を持ったままにするとMLEが発生するという凶悪な設定でした。
実はこの問題のメモリ制限のためにAOJさんの仕様を変更していただきました。
本当にありがとうございました。
H:
これもかなり難しい問題でした。
木DPを行う中で $\mathrm{mod}\ 1000000007$ でのK乗根を求める必要があり、そこでもテクニックを要求されます。
さらに $K=500000003$ のときは特殊な場合分けが必要で、相当数のペナルティが発生して見ていてヒヤヒヤしました。
問題文の誤りが原因で発生したペナルティもあったかと思います。それに関しては深くお詫び申し上げます。
I:
D問題以降の中では比較的簡単めな枠でした。
二項係数のまま立式したところから少し約分をしないと計算量が減らせないというひねりがあり、面白い感じになっていました。
J:
テスター陣でもいろいろな解法が出た問題でした。
裏ではテストケースを作るのに少し苦労しました。
K:
これも比較的簡単目な枠の問題でした。
素因数分解した形を考えて平方数の条件を見抜くと解ける問題で、制約からも半分全列挙っぽいことが読み取れる問題だったと思います。
L:
実は仮完成時にはこの問題はなくて、テスターのWA_TLEさんにより計算量を減らせることを提案していただき、問題として採用されました。
中にははじめからこの制約で考察を進めていた人たちもいて、強さを感じました。
M:
去年の「Jigsaw Puzzle and Detective」のパワーアップ版復刻でしたが、想像以上に取り組まれなかったので少し残念でした。
一意に定まる条件を証明するのは困難ですが、勇気を出して取り組んで見れば意外と解ける人も多いのではないかなと思います。
各問題の解説
A「Grouping」
B「CD Collector」
C「Clock」
D「Icosahedron」
E「WA_TLE's Bless」
F「Cueing」
G「Restore Test Case」
H「How much did kotamanegi earn?」
I「Huge Bingo」
J「Nickname」
K「Square」, L「Re:Square」
M「The Lost World: Jigsaw Puzzle and Detective」