AtCoder Regular Contest 176 （Sponsored by Mynavi）

　Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 176 （Sponsored by Mynavi） Cまで三完。
A (j-i)%NをM個選び斜めにおいていく。
B M=K+1の場合は別に計算。N<Mなら答えは2^N。そうでないとき、K=0に帰着。2^N%(2^M+1)は2^(N-M)%(2^M+1)と一致する。
C Cが小さい方から見て頑張って場合分け（ABより考え方は楽だと思った）

— titia (@titia_til) April 21, 2024

D - Swap Permutation

　けんちょんさんの解説記事を参考にAC。

　解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか？　という遷移を考えてしまい、上手くできなかった。

　index i, i+1が最終的にどの数字になっているか？　に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。

E - Max Vector

　解説AC。

　問題を読んでフロー（最小カット、燃やす埋める）じゃないかとは思ったが、どうやってグラフを作れば良いのか。

　とりあえず、

・Nが多いことはあまり本質的ではない。N=1の場合に関するグラフを構築すれば、一般のNでのグラフも（今回は）同じように構築できる。

・X_i+Y_iなどというのはフローで扱いにくそうだし、X_j, Y_j, A_ijが500以下という条件があるので、各数字に関する頂点を作りそう。

　というあたりを手がかりにすれば良かったか。

　ただ、劣モジュラ関数についての一般的な知識は得ていた方が良いのは間違いない。theory and meさんのこの記事を理解すべきだよね……。