公式

コンテスト全体の解説 by PCTprobability

ヒント集

A - 01 Matrix Again

ヒント 1 \(M=1\) のときの解法を考えてみましょう。
ヒント 2 \(1\) 個目の条件がないときの解法を考えてみましょう。
ヒント 3 上記 \(2\) 個の解法を組み合わせてみましょう。

B - Simple Math 4

ヒント 1 式変形を行うことで \(N\) が今より小さいケースに帰着することが出来ます。
ヒント 2 \(2^N\) から \(2^{N-M}(2^M - 2^K)\) を引くと何が起こるでしょうか？
ヒント 3 \(N\) が \(M\) 未満ならば、ほとんどの場合答えは \(2^N \bmod 10\) です。

C - Max Permutation

ヒント 1 \(C_i\) が全て等しいときの解法を考えてみましょう。
ヒント 2 \(C_i\) が全て等しいときの解法によって得られたアルゴリズムを一般の場合に適用するにはどうすればよいでしょうか？
ヒント 3 \(C_i\) の降順に適用することで一般の場合に応用することが出来ます。

D - Swap Permutation

解法 1

ヒント 1 \(|P_i - P_{i+1}|\) を、\(\min(P_i,P_{i+1}) \le k < \max(P_i,P_{i+1})\) を満たす整数 \(k\) の個数と言い換えます。
ヒント 2 上記を利用して \(k\) 以下の値を \(0\) に、\(k\) より大きい値を \(1\) にすることによってこの問題を \(0,1\) のみの問題に置き換えることが出来ます。(これを全ての \(k\) に対して行い答えの総和を取ります。)
ヒント 3 \(0,1\) のみの問題の場合、行列累乗で解くことが出来ます。

解法 2

ヒント 1 \(P_i,P_j\) が操作終了時に隣り合っているような操作列の個数を求めましょう。
ヒント 2 上記は、\(i = 1\) かどうか、\(i + 1 = j\) かどうか、\(j = N\) かどうかにのみ依存します。
ヒント 3 上記の \(3\) 個の条件のうちいずれかを満たす \((i,j)\) の個数は \(\mathrm{O}(N)\) 個です。

E - Max Vector

ヒント 1 最小カットを使うことによってこの問題を解くことが出来ます。
ヒント 2 \(X_i\) としてあり得る値は \(\max A\) 個ありますが、その全てに対して頂点を作りましょう。すると、この問題を最小カットに帰着出来ます。

F - Colorful Star

ヒント 1 ほとんどの木を作ることが出来ます。
ヒント 2 操作を逆から見ることである木を作ることが出来るかを判定しましょう。
ヒント 3 同じ色が隣接している個数が重要です。
ヒント 4 深さ \(1\) の頂点の色も重要です。

投稿日時:
最終更新: