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

tester：Takaさん

サイクルであって通る頂点の集合が $\{v_0,v_1,v_2\}$ でないものを探す問題です。背景は $2$ 次元単体複体のホモロジカルに非自明なサイクルの検出ですが、実際にやるべきことはシンプルです。

一般のサイクルの検出はそれなりに実装が面倒ですが、今回は $G$ のサイズが小さいことからサイクルを全探索すれば楽です。個々のサイクルに対し、通る頂点の集合を計算して $\{v_0,v_1,v_2\}$ と一致するか否かを判定しましょう。

最初から数値データとして与えられているデータならば全探索は思いつきやすいですが、グラフのサイクルのように数値データそのものではないと失念しやすいです。全探索できそうな対象を、しっかり数値データに翻訳して全探索できるかを問う問題でした。

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

tester：hiro1729さん

数学で幾何を定式化するには様々な方法があり、A問題で扱ったグラフ（およびそれを一般化した単体複体）もその１つです。そしてこの問題で扱うのが、恐らく最も主流な定式化の１つである、位相です。

問題文に書かれている条件の判定をそのまま実装しようと思うと計算量が大きすぎます。どの条件判定の計算量が大きいかをきちんと見極め、その条件を同値変形して簡単な処理に落とし込みましょう。

同値変形や等式変形は一見「人間に見た目が変わるだけで何もやっていない」と思われがちですが、見た目が変わることにこそ意味があります。より正確には、条件や式にはその値だけでなくexpressionそのものというメタな情報があり、例えばそのexpressionそのものから直接得られる計算方法は値だけでは定まらないexpression依存の情報です。計算方法ごとに依存性や計算量が異なるからこそ、同値変形や等式変形には意味があるわけですね。

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

tester：Moss_Localさん

★2.5からは素朴なアルゴリズムの改善に加えて、非自明な典型考察が要求されがちです。まず連結成分数取得なので幅優先探索か素集合データ構造に注目できますね（もちろん★2.5なのでdynamic connectivityとかは要求されません）。そして辺の状態が動的に変わっていく問題設定であるため素集合データ構造と相性が良さそうです。

そこまで気づけば、後は素集合データ構造に処理可能な操作に翻訳していけばいいですね。具体的には典型考察の、逆順操作を検討しましょう。逆順操作で処理するためには適宜クエリ先読みしてソートすればよいことが分かりますね。

想定よりかなりdifficultyは低かったようです。典型とはいえyukicoderで最近出題されていなかったテクニックだったのでもう少しdifficultyが高いかなと見積もっていました。★2であまり出題されない★2.5頻出アルゴリズムでも考察典型度が高いと★2くらいの解け具合になっちゃうんですね。

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

tester：AngrySadEightさん

ダイクストラ法の理解度チェック問題です。迷路の最短経路問題というよくある設定ですが、最小化すべき値が $2$ つあるため、抽象化されていないダイクストラ法をそのまま貼るだけでは解けません。

そこで要求されるのが、ダイクストラ法の正当性の証明の理解です。ダイクストラ法の正当性の証明を思い出せば、抽象化されていないダイクストラ法を少しアレンジするだけで解くことができます。この問題が解ければダイクストラ法の抽象化も簡単にできると思うので、ダイクストラ法の抽象化に未挑戦な人の足掛かりになれば幸いです。

C問題同様こちらも想定よりかなりdifficultyは低かったようです。ダイクストラ法は★2ではあまり問われない★2.5頻出アルゴリズムですが、このくらいの解け具合ならちょっと捻ったダイクストラ法くらいなら★2で出題されるようになっていくかもしれませんね。

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

tester：Shirotsumeさん

負閉路検出と言えばベルマンフォード法。今回は正閉路検出なので、重みを$-1$倍にすればよいですね。……と思いきや計算量が大きすぎます。別の方法を考えましょう。

正閉路がないということは、$2$ 点間を結ぶ経路の重みの総和が一定ということ。つまり重みと整合的なポテンシャル（スカラー場）が存在するということです。重みと整合的なポテンシャルの有無の判定にはポテンシャル付き素集合データ構造が使えますね。

この問題のように進行方向を逆転させる辺の重みが$-1$倍でかかる設定（例えば非常に特殊な連立一次方程式など）ではポテンシャル付き素集合データ構造が使えること、を問う問題でした。

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

tester：Shirotsumeさん

E問題と似たような問題設定ですが、今度は辺の重み付けに関して少し制約が変わっており、正閉路がないことが保証されています。$N$が小さいので今度こそベルマンフォード法！　……と言いたいところですが$Q$が大きいとやはり計算量が大きくなります。

ここで注目すべきは、クエリごとにグラフの辺の重みが変わらず、辺の削除と追加が起こるだけという点です。これはフローなどで残余ネットワークを考える時と似た状況ですね。

そして実際にPrimal Dual法の実装では負辺を許す状況でも工夫してダイクストラ法が使われていたことを思い出せば、同様にポテンシャルを用いたダイクストラ法で高速に処理できることが分かります。

というわけで実質Primal Dual法の理解を問う問題だったというわけですね。Primal Dual法は★3で基本的に問われませんが、No.2604 Initial Motionという前例があるのでそのupsolveの前準備として役立てていただければ幸いです。

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

tester：binapさん

F問題と同様、何度も最短経路長計算が要求される問題です。適切な前計算で各クエリ処理を高速化したいところです。しかし今度は辺の重みが移動中に変わっていく設定。となるとD問題で復習した要件に合わないのでダイクストラ法すら使えなさそうなのが難点です。

意外にもそこで役立つのが、ダイクストラ法とはまた違った要件を持つワーシャルフロイド法。ワーシャルフロイド法と言えば全頂点間の最短経路長計算ですが、要件さえ合えば別に全頂点間でなくてももちろん使ってよいですね。

とはいえ実はダイクストラ法でも工夫すれば解けることをtesterさんに教えてもらいました。しかも実装が自然なので、正当性が分からなくてもとりあえず投げてみて通る人も多そうです。そのため、元々は★3.5想定でしたが★3に変更です。実際tester解に気付いた人が多かったようで、G問題はかなり解かれてしまいました。difficultyは若干E,Fと反転してしまいましたが、もしE問題辺りに置いていたらtester解を未証明で投げて通す人がもっと多かったかもしれないので、結果を踏まえてもG問題で良かったかなと思います。

幾何アルゴリズムの理解のための問題を作る過程で、逆に作問者が理解を深めさせていただきました。

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

tester：hotman78さん

ボス問は★4です。G問題を★3.5から★3に落としたので表示上の難易度勾配が急になってしまいすみません。

競技プログラミングのグラフといえば木が典型。最後の最後に木の数え上げ問題です。もちろんケーリーの公式だけでは解けず、一捻りする必要のある問題設定です。法が固定でないところもお約束。ぜひ楽しんでいただければ幸いです。