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

tester：なし

A問題は考察のあまりいらない実装問題です。

とはいえ競技プログラミングに初挑戦の人だと愚直に二重ループを書いてしまうかもしれません。

TLEになった場合にもすぐに解決方法が思い付けそうな、実行時間に目を向けるきっかけになりうる問題を目指しました。

ちなみにこれは$3$年以上前に作問した問題で、本セットの中では$2$番目に古い問題です。

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

tester：なし

上の難易度帯の典型テクニックを出題することで、参加者が強制的に新たな勉強機会を得ることがあります。

よく「過去数年★2で出題されたことのないテクニックが★2で出題される」的なことがyukicoderで起こるのもきっとwriterさんがそういった効果を狙っているのでしょうね。

筆者もそういった教育効果のある問題を出題してみたいという思いはありますが、一方で運営さんの「難易度は、ヘルプのものに合わせようプロジェクト」を踏まえると問題の難易度は「最近の出題頻度」のような時々刻々と変化しうる要因に依存しない方が良さそうかな、と考えて自制しています。

そこで代わりに思いついたのが、★2.5のテクニックを知らずにも★2のテクニックで解けるが、それを抽象化すると★2.5のてクックが得られる問題を出題するという方向性です。その抽象化を余談として解説で触れれば、意欲のある人には★2.5の勉強の足がかりになるかもしれない、という狙いですね。

というわけで★2では典型でない半分全列挙を、★2のテクニックだけで解けるように具体化したものを作ってみたのが今回の問題でした。

ちなみにこれは$2$年半前に作問した問題で、本セットの中では$3$番目に新しい問題です。

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

tester：なし

転倒数の期待値計算は典型ですね。ただ答えだけ覚えていても解けないように、きちんと証明に戻って考察していただくために少し捻って隣接項のswapだけを数える設定にしてみました。

追加のスパイスとして合成数modでの出力を要求します。ただし合成数modでの割り算は★2.5典型でないので、ヒントとして割り算ができる必要十分条件は問題文に明記しておきました。

必要十分条件さえ分かれば、有理数modの定義に戻ることで割り算の結果を思いつくことができます。定義を忘れて素数modの場合の実装方法だけ何とか合成数modに対応させようと思うと詰まってしまうかもしれません。定義大事にですね。

ちなみにこれも$2$年半前に作問した問題で、本セットの中では$4$番目に新しい問題です。

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

tester：なし

累積和が苦手（よく考察漏れをしてフェニック木を使って余計な$\log$を付けてしまう）なので、練習のために累積和の強みを意識する問題を作問してみました。正確には累積和というか乗法なので累積積ですが。

累積和や累積積は、それ単体ではなく連想配列と組み合わせたり区間を始切片の差で表すテクニックと組み合わせたり、複合的な考察で現れがちなのが苦手なところです。

今回はそれら両方のテクニックを使う問題ですが、Zero-Sum Rangesを理解していれば考察の負担は少ないかなと思います。

ちなみにこれも$2$年半前に作問した問題で、本セットの中では$2$番目に新しい問題です。

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

tester：なし

よくある頂点倍化の問題の延長で、頂点$B$倍化を要求する問題です。

頂点倍化でmod $2$の方程式が解ける原理さえ分かっていれば頂点$B$倍化を思い付くのはさほど難しくないだろうとは思いますが、ただ解の構築となるとmod $2$とmod $B$でだいぶ違って見えるのではないかと思います。

特にNGな連結成分とOKな連結成分の構造はそこそこ非自明なので、未証明ACをした場合はぜひ証明も考えてみましょう。

ちなみにこれは$3$年前に作問した問題で、本セットの中では$4$番目に古い問題です。

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

tester：なし

今回一番設定に悩んだ問題です。原案は集合の問題ではなく、もはや面影すら残っていません。

元々★3の平方分割の問題を作ろうとしてこの問題を考えたのですが、平方分割の問題は（遅延）セグメント木を落とすためにモノイドでないマグマの区間作用を考えるか一点取得や一点更新を多めに要求すること辺りを意識する必要があると思っています。

しかし前者は区間作用自体が★3典型でないのであまり良くなさそうです。後者はMoのアルゴリズムが★3典型でないので、それ以外の方法で一点取得か一点更新を多用させなければならないわけです。そこで幅に制限のある区間で非自明な（一定値でない）代入更新や加算更新をする案や、何かの約数をずらした位置の成分の更新をする案を試し、どちらもあまりいい感じに仕上がらなかったので最終的に今の更新クエリに落ち着いた感じです。

分子を固定した分数のfloorの像列挙は★3典型ですが、問われるのは主に総和計算などの添字なので実際に像に入っているか否かはあまり気にする必要がない（像に入っていない場合は総和への寄与が結果的に$0$になる）問題設定が多いと思います。今回はきっちり像に入っているかどうかを気にしなければいけないのがやや考察の難しいところかなと思いますが、制約が小さい影響でその辺を気にせずとも結果的にACになると思います。

なので未証明ACだった方々はぜひ像の考察も詰めてみると良い経験になるかもしれません。

ちなみにこれも$3$年前に作問した問題で、本セットの中では$3$番目に古い問題です。

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

tester：なし

他の問題と比べると典型色が薄めの考察問題です。

制約で強調されている「高々$2$回」に注目すると各変数が両側から抑えられている場合のみ考えれば良いことは分かりますが、そこからどうするかを考えなければなりません。

不等式の変数消去はあまり見慣れないかもしれませんが、整数変数が整数しか値を取らない項で両側から挟まれている時の解の有無が両側の不等式に帰着されることにさえ気づければ、後はすんなり解けると思います。

それに気付くためには一旦変数の個数が少ないケースで考察をするのが良いですが、サンプルは弱いので自分で非自明な小さケースを作ってみることで手掛かりが掴みやすくなると思います。

ちなみにこれは$3$年以上前に作問した問題で、本セットの中では$1$番古い問題です。長い間いつか出題したいと思っていたので出題できて嬉しいです。

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

tester：なし

シンプルな問題設定の割に考察は結構大変です。最小費用流は通らない想定だったのですが……あれ通ってる？？　何故……。

絶対値を$\pm 1$倍に変換する考察は競技プログラミングを始めたばかりの頃から何度も遭遇していますが、出題頻度としては高くないので毎回見落としていました。絶対値周りはテクニックが多くて外れ考察を繰り返してしまうのですよね。

そこで考察自動化ライブラリーを更に充実させ、実際に作問をすることでこの手の考察に慣れていきたいと思い生まれたのがこの問題です。

添字のシフトを行わない単純なnext DPを落とすために実行時間が厳しく設定されているので低速な言語だとやや不利かもしれません。想定解と同じ計算量オーダーでTLEとなってしまったら申し訳ございません。

ちなみにこれは$1$年前に作問した問題で、本セットの中では$1$番新しい問題です。