自分が作問し 2023 年に公開された問題を振り返り、 upsolve を勧誘する記事です。
ICPC 2023 国内予選 D 「効率的な問題セット」(原案のみ)
オンラインジャッジ: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1667&lang=ja
大昔から作問ストックに入っていたのですが機会がないまま放置しており、今回たまたま公開できました(国内予選の少し前に ABC の配点が毎回変わるようになったので、時事ネタとして問題爆破が起きないかヒヤヒヤしていました)。
ちなみに、こちらの問題では の制約で出題していますが、ごく丁寧に書くことで くらいでも十分高速に解けるはずです(実装量も特に大変なことにはならないはず)。
ICPC 2023 国内予選 E 「改竄された史料」
オンラインジャッジ: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1668&lang=ja
大昔から作問ストックに入っていたのですが機会がないまま放置しており、今回たまたま公開できました。(2)
元ネタはスフィアの「らくがきDictionary」で、曲名からほぼそのまま作っています。元々は長さ の文字列が 個ある設定でストックしていたのですが、実装が面倒だったり非想定解法と区別するのが難しかったりしたためいつの間にか になり、辞書感が薄れています。
解法を言われてしまえば素直な DP なのですが、なかなか見えにくいという感想を目にすることが多く、不思議な問題という印象があります。
ICPC 2023 Asia Yokohama I 「Liquid Distribution」
元ネタはスリーズブーケの「Mix shake!!」で、色々と問題設定を考えた中で特に綺麗に解けたものを出題しました。自分は問題を立ててから解けるまで数日以上かかっています。
yukicoder Advent Calendar Contest 2023 V 「Mix shake!!」
上述の「Liquid Distribution」の解法を思いついた日に就寝しようとしたら突然このバージョンでもうまく解けることに気づいたので出題しました。
プログラミングコンテストというよりは数学パズルのような問題ですが、解法を直観的に理解するには高校数学レベルで十分であったり、問題の見た目と想定解のギャップが(主観的に)大きかったり、実は計算量もうまく抑えられていたりと、自分が今まで作問・出題してきたなかでは最も気に入っている問題です。よかったら解説冒頭の想定解も読んでみてください。
DEGwer さんの D 論応援コンテスト C 「binarydigit」
問題設定から作問して、自力では多項式時間には落とせなかったのですが、指数オーダーのなかではかなり高速化できたので、この改善を問うても良いかと考え出題しました。計算量の区別がシビアなので、かなり実行時間制限が厳しめになってしまい、ここで苦しんだ方がいたら申し訳ないです......。
想定解では加算と乗算しか登場しないのと、テストケースハックが少しでもやりづらくなるかと考え mod 合成数で出題したのですが、コンテスト中に heno239 さんから mod 素数のケースで適切に動作する多項式時間解法の提出があり本当にびっくりしました。 mod 合成数で解けるかという点は自分にとって真に問いたいことではないので、この提出は本当は満点(かそれ以上)として評価されてほしいという気持ちもあり、 mod 素数で出題すれば良かったと後悔しました。
twitter.comhttps://t.co/tdWtuBT9bj
— heno (@heno_code) 2023年12月2日
(小さくない)素数の時に通っているコード
O(H^4W^3)
なお本問題で数え上げている対象そのものが OEIS A180985 - OEIS に存在し、 が小さい範囲の答えは載っているようです。
DEGwer さんの D 論応援コンテスト H 「Incomplete Notes」
元ネタは SPR5 の「インコンプリートノーツ」の曲名で、wildcard pattern matching を捻った形で出題しようと考えて作りました。かなり解法ドリブンな問題な気がします。
作問者としてはテストケース作りで苦しみました。愚直な アルゴリズムを枝刈りした解法(や、それを工夫した解法)に対して強く十分複雑なケースがあまり思いつかなかったので、 や の上限を引き上げることでごまかして(?)います。コンテストではその他様々な解法で解いていただけて興味深かったです。
おわりに
いずれも一捻りある問題だと思っているので、お暇でしたら是非 upsolve してやっていただけると幸いです。また、2024 年以降もどこかしらで問題を出していければと思っており、その際はよろしくお願いします。