はじめて問題として完成したものが、yukicoder contest 398(VRC競プロ部で作ったやつ)で出題されました。
Tester各位(特にあめんばーさん、PCTさん、Mizarさんには数週間に渡って議論してくださり)、本当にありがとうございました！

以降、問題のネタバレが含まれます。是非、先に問題を解いてからご覧ください！Easyだけでもいいので！

Udon Coupon (Easy) 
Udon Coupon (Hard)

自己紹介

「面白くて、楽しいことをしましょう！」GlinTFraulein (グリント フロイライン)です。VRの世界で生きています。VRC競プロ部には、はじめてABCに参加した時からお世話になっています。競プロ歴<VRC歴です。

競技プログラミングは2022年5月から始めていて、言語はC++を使っています。理由はAPG4bとかいうメチャクソに親切な教材がその辺に転がっていたからです。
AtCoderではA緑(978)、H緑(1108)です。Hはこの前のトヨタコンで当たり貪欲引いて爆伸びしました。UnionFindが好きで、実装難が苦手です。

Udon Coupon (Easy)

皆さんは、丸亀製麵を知っていますか？私は知っています。何を隠そう、本問題の元ネタは丸亀製麵の「うどん札」です。

ある日丸亀製麵でうどんを食べていた私は、「手持ちのうどん札の枚数に対して、最適な使い方って求められるのではないか？」と思いました。家に帰って少し考えたところ、これはDPを使えば求められることが分かり、実際に紙とペンを用いてDPをしていました。

サンプル1が、実際に丸亀製麵で行われている割引テーブルになります。
3枚で「トッピング」(90円)がひとつ無料。
5枚で任意の「天ぷら」が100円引き。
10枚で「うどん 並」(390円)が一杯無料。

とはいえ、実際に10枚集められることは家族で毎週以上丸亀製麵に通うとかしない限りないんですけどね。3枚の効率がかなりいいので、現実では「3枚集まったら使う」の貪欲が割と最適になりがちです。

問題としては、恐らくAtCoder緑以上が見たら1秒以内にDPと分かるでしょう。たまにはいいじゃないですか、ド典型。典型そのまますぎてAtCoderではいよいよ出ない感じですが、初学者にとっては「学んだことが出題されていることが分かる」というのは嬉しいものなのです。これ自己紹介です。

DPとして基本的でかなり易しめなので、★1.5って言われるかもしれませんが、それはyukicoderがインフレしすぎて大変なことになっているだけなので★2を主張することにします。

Udon Coupon (Hard)

旧Hard

草案と完成版が大きく変わった問題です。草案の制約を見てみましょう。

(Easy)では、O(N)のDPを行うことで問題を解くことができました。しかし、今回のNは最大で10^18であるため、同じ手法が使えません。これは困りました。

以降、A_iの全ての要素に対するLCMをLと置きます。

元々の想定としては、最適な「うどん札」の使い方はL枚ごとに"ループ"します。Lは必ずA_iで割り切れるため、「全てA_1の割引を使う」「全てA_2の割引を使う」「全てA_3の割引を使う」のいずれかが最適になります。Nが大きい時、この「全てA_iの割引を使う」を何度も適用することになるため、"ループ"と呼んでいるわけです。

すなわち、この問題は適当な方法で⌊N/L⌋回の"ループ"と、残りN%L枚の最適な使い方を求めればよいことになります。

計算量はO(L)です。
ボトルネックは"ループ"の最適をDPで求める部分、もしくはN%L枚の最適な使い方を求める部分のDPになりますが、A_iの制約よりLは高々10^6です。よって、これは十分高速です。
想定難易度は★2.5でした。

※この考察にはコーナーケースがあります！みんなも考えてみよう！

※もう少し下にコーナーケースがあります！

あめんばーさん「これでだめかも」

ぐりんと「ﾐ゜」

上記の考察通りに考えると、L=6であるため、
・"ループ"最適になる割引額は301*2=602円
・残り1枚を1円割引に使う
・結果、603円の割引を受ける

真の答えは
・301円の割引を受ける
・200円の割引を受ける
・200円の割引をもう一度受ける
・結果、701円の割引を受ける

となります。終わりです。
どうやら、最後の2Lか3Lは愚直に調べた方がいいみたいです。しかし、これを証明することは叶いませんでした。
コーナーケースがヤバすぎて、想定難易度を★3としました。

殺伐とした作問検討に、突如レッドコーダーのPCTProbablityさんが参戦！

PCTさん「おそらくO(A^2)で解けます」
ぐりんと「？？？？？」

PCTさん「解けました」
ぐりんと「？？？？？？？？？？」

出題版Hard

変更された制約がこちら。

更に異常高速化のプロMizarさんが参戦！

Mizarさん「N≤10^9だと2秒強で回せてしまいます」
ぐりんと「？？？？？？？？？？？？？？？」

この辺から、「TL/MLどうするか問題」があめんばーさん、PCTさん、Mizarさんを中心に繰り広げられますが、いよいよ分からなくなってしまいました……。
主に、Pythonが遅いのをどうすればいいか、というのを、制約の微調整や考察のし直し、異常高速化、「実はPythonはPypyで通ればいいや」とする、などを経て、一般的なTL/MLになりました。だと思います。

想定難易度は★3以上です。なぜなら、難しすぎて分からないからです。

最終的に、PCTさんが「今の星 3 のなかだと C < F <= D << E くらいの感覚です」「Eは3.5でもいいかな…… 3で出ても違和感はないです」ということだったので、思い切って★3.5にしました。上目に書いておいた方がいいと公式も言っている。

当初の問題とは、考察の過程も難易度もかなり変わりました。でもまぁ、最終的に「難しめにする方針で！」って言ったのは私でしたねそういえば。私が全部悪いじゃん！ｗ

解説も、Mizarさんがほぼほぼ書き直してくれました。あめんばーさんも問題文のレイアウトとか整えてくれました。

という感じで結果的に、GlinT×あめんばーさん×PCTさん×Mizarさん、みたいな感じのVRC競プロ部合作問になっていました。目の前で繰り広げられる問題の変化は、少し怖くもありましたがワクワクするものでした。色々議論してくださってすごく嬉しくて、それと並行でVRC側で色々しているのが忙しくてあまり目を付けられていなくて申し訳ない気持ちも大きかったです。

おわりに

いかがでしたか？

改めてTester各位、本当にありがとうございました……！

作問、やってみると結構面白いので、今後もやっていきたいな～と思いました。というわけで、次回未定です！ｗ