問題リンク：https://yukicoder.me/problems/no/2969

tester：hiro1729さん

最初は微分の実装問題で、[No.2186 冪乗の片側極限](https://yukicoder.me/problems/no/2186)の類題です。

微積分を学ぶ上で大事なことの１つは、極限を使って定義された無限的な操作でも問題設定を制限することで有限的な手続きで処理できることです。無限的な定義と有限的な計算方法の両方をバランス良く理解することで、微積分の応用性の高さを実感していくことができます。

有限的な計算方法は、問題設定が絞られていてかつその問題設定に合致したデータ管理方法が固定されて初めて有効になります。指数関数や単項式関数とは限らない一般の関数を管理する際はグラフ上の点群を表す無限個のデータが必要なため、当然その微分は有限的な方法で計算することができません。

先述した類題は指数関数に限られているため、その底のデータだけを管理することで微分が有限的な計算方法で求められるわけですね。追加のスパイスとして「有限的な計算方法を重視しすぎるあまりバグがあった時に無限的な定義を確認し直すことを失念してしまう」という大学１年生の微積分あるあるに陥っていないかどうかも確認できるように工夫しました。つまり想定している有限的な計算方法に穴があってWAを出した後に、その計算方法にこだわりすぎずきちんと問題文に書かれた定義に戻ってコーナーケースを潰せるかが問われています。

同様に今回は単項式関数に限られているため、その係数と指数の組で管理することで微分が有限的な計算方法で求められますね。追加のスパイスとしては「そのデータ管理方法において、微分の結果の表示方法は一意か（表示の相違から関数の相違が導けるようなデータ管理方法になっているか）」を問わせていただきました。

関数などの無限的なデータから有限的なデータを取り出して管理する際は、元のデータの比較が取り出したデータの比較に帰着されるかどうかが実用上は重要です。例えば有限次元線形空間の間の線形写像を管理する際に用いる行列表示は常に線形写像の比較が行列表示の比較に帰着される（従って有限的な計算方法で判定できる）ことが保証されていてとても便利です。

問題リンク：https://yukicoder.me/problems/no/2970

tester：Moss_Localさん

微積分が実用される問題の１つが、区分的に滑らかな（大雑把に言うと微分不可能な点がちょっとしかない連続な）関数の最大・最小値問題です。特にラグランジュの未定乗数法などを用いた最大・最小値問題の解法が注目されがちですが、多変数関数は難しいので大学１年生の微積分では苦戦する人が多いと思います。そこで、それよりもっと簡単な問題設定にして１変数関数の最小値を問いました。

最大・最小値問題を愚直に解くには各点での値を計算しなければならないので、定義域が無限集合であれば当然無限に時間がかかります。しかし有界変動な関数の最大・最小値問題は十分多くのサンプル点での値を計算問題に帰着できますし、より強く区分的に滑らかな１変数関数の最大・最小値問題は

• 定義域の境界点
• 上記以外の、微分不可能点
• 上記以外の、導関数の零点

を調べる問題に帰着できます。今回は区分的に滑らかな１変数関数なのでどちらのアプローチも可能ですね。

前者のアプローチをする際は、端点で最小値を取る場合に注意しましょう。端点は変動が大きいので、サンプル点の取り方次第では精度が悪くなってしまいます。例えば端点を必ず通るようにサンプリングすれば安心です。後者のアプローチをする際は、多項式の次数が小さくなる場合に注意しましょう。次数が$2$次の時に$1$次である導関数にうっかり$2$次方程式の解の公式を適用すると正しく零点が求まりません。

なお一般論として、後者のアプローチは実用上のケースでは調べるべき点の集合の次元的なものが$1$次元から$0$次元に下がります。実は多変数でもアイデアがほとんど同じだ、ということが気付ければ多変数関数の最大・最小値問題も乗り越えやすくなると思います。

問題リンク：https://yukicoder.me/problems/no/2971

tester：hiro1729さん

微分絡みの問題が続きましたが、今度は積分です。積分もまた無限的な操作で定義されていますが、問題設定を絞り込めば有限的な計算が可能になったり、誤差を許せば精度を保証した近似計算も可能です。

今回は小数誤差許容問題なので、近似計算が要求されていることが分かりますね。シンプルにモンテカルロ法などの典型アルゴリズムを適用しましょう。

問題リンク：https://yukicoder.me/problems/no/2972

tester：Moss_Localさん

★2.5からは考察を重くしていきます。小数誤差許容の確率計算問題なので愚直に乱択をしたくなりますが、マルチテストケースなのでそう簡単にはいきません。各テストケースを高速に処理する必要があります。そこで役立つのが、薬物や感染症の検査で重要なベイズの定理です。ここでベイズの定理を復習してみましょう。

ベイズの定理を知らない場合は、一旦乱択を書いたつもりで考察してみましょう。乱択で答えを求める時、結局何を何で割った値を出力しているのかを考えてみることで答えの明示式を得ることが可能です。ベイズの定理の再発見ですね。

問題リンク：https://yukicoder.me/problems/no/2973

tester：遭難者さん

率直に極限を計算する問題です。背景で説明した通り、こう見えてこれも積分です。最初は留数定理を知らないと難しいと思ったので★3をつけていましたが、留数定理を使わない漸化式による解法をtesterさんに教えていただき競技プログラマーならばそちらが先に思い浮かびそうだなということで★2.5に変更させていただきました。

実際の解け具合は……、Dとの間に明確な崖ができてしまいました。。すみません、またしても難易度評価失敗かもしれません……。

この問題は出力形式の調整に苦戦しました。最初は分数表示を出力させるスペシャルジャッジでなく厳密な小数表示を出力させる通常ジャッジにしていて、その趣旨はdouble型で処理した時に誤差が出てWAとなる（$0.0 \cdots 0$を付け足す処理を文字列で行う必要がある）という部分を問うためでした。しかしこれだと不快感が大きいかもしれないと思い、少し緩めて冗長な$0$が末尾に来ることを許す程度のスペシャルジャッジを検討しました。

しかしこれでも不快感はあまり変わらなさそうだったので、文字列で処理する部分を問うのは止めて誤差許容問題に変更しました。すると絶対誤差の許容範囲を$10^{-20}$よりも小さくにしないと$|N|$の大きいケースが無意味になってしまうのでそうしてみたら、作問当時は実はyukicoderの誤差ジャッジが$10^{-20}$のレベルでは壊れていてうまくいかなかったり（運営さんに報告済み＆運営さんが修正済み）。

そして誤差許容にしても実はあまりACしやすさが変わらないことに気付き、不快感が減らなさそうであったので今の分数表示のスペシャルジャッジに落ち着きました。この辺の調整でtesterさんにたくさんご助言いただき大変お世話になりました。

問題リンク：https://yukicoder.me/problems/no/2974

tester：hiro1729さん, binapさん

E問題に引き続き数学色の濃い問題です。一見CHTのような複雑な処理が必要なようで、よく考えると折れ線の加算更新をしていくだけの問題です。とはいえ実装は重め。

８問の中で完成までに一番苦労したのがこの問題です。難易度評価で何度も揺れてしまいまして。最初★3をつけていたのですが、★3.5の可能性もありそうとのことで追加testerさんを募集して難易度のご意見を伺い、あれやこれや相談しているうちに「フェニック木想定の問題としてはむしろ素直な部類なのでは？」となり★2.5で意見がまとまっていきました。

そして実際の解け具合はどうだったかと言うと……、こちらもE同様あまり解かれませんでした……。崖が２つ並んで手の施しようがなくなってしまい、申し訳ない気持ちでいっぱいです。

問題リンク：https://yukicoder.me/problems/no/2975

tester：hamamuさん

E,Fと数学寄りの問題が続きましたが、ここで競技プログラミング典型詰め合わせ問題です。丁寧に立式をして解きましょう。

ちょっとしたスパイスとして、いつもの動的modに加えて、メモリ制限に引っかかやすい制約にさせていただきました。背景として、本問ではデータ構造が問われていませんが、データ構造高速化を用いたinplace DPの考察がなかなか身につかないのでNext DPの練習が足りてないかなと思ったところで、そもそもNext DPが問題に要求されている問題がそこまで多くないということに気付き、データ構造高速化を用いたinplace DPまでは要求せずにNext DPのみを要求する問題を作ってみようと思ったという動機があります。

なお考察寄りのコンテストの中では際立って典型寄りだったせいか、E,Fを飛ばしてGに行く人が多いの何の。実際にE,Fより簡単だったのかどうか気になるところです。

問題リンク：https://yukicoder.me/problems/no/2976

tester：ecotteaさん

多点評価の高階版。名前のインパクトがありますね。元々は★4のボス問想定だったのですが、tester解が想定外なテクニックであまりにもシンプルだったので★3に下方修正し、しかしながらそのテクニックは少なくともここ最近ではそこまで典型考察ではなさそうとのことでやっぱり★3.5に上方修正して現在に至ります。

本番で解けた人は１人だけだったので、★3のままでなくて正解でした……。もし★3にしていたらこちらがG問題になっていたことになり、EFGで崖が３連続するところでした。ヒヤヒヤですね。

writer解のように解析的関数の代数的関係式を使った変換テクニックは、結構色々な問題に応用できるので今後もちょくちょく出題していきたいと思います。

ちなみに今回は小数誤差許容問題が$5$問でした。小数誤差許容問題の作問が難しい理由の１つは、テスト出力の設定が大変なことです（詳しくはこちらなどをご参照ください）。

参加者にも出力が正解となる必要十分条件が明確になるような問題を作りたい場合はどうすれば良いかが気になるわけですが、これに関してはそこまでノウハウが共有されていない気もします。というわけで、解説には作問者向けにテスト出力を設定するために行ったことも明示しておきましたので参考になれば幸いです。