頂点の木があり、頂点
は色
で塗られている。
以下のようなクエリが回にわたって与えられる。順に処理せよ。
まず木を頂点を根とした根付き木として見ます。
次に各頂点について、「現在の色」、「親の頂点番号」、「親の色」、「直接つながっている頂点の｛色:個数｝の連想配列」を用意します。このとき、連想配列のサイズが答えるべき色の種類数です。
更新処理をする際、隣接する頂点をすべて見てしまうとTLEになってしまいます。そのため、親に対してのみ更新を行うことにします。
各頂点について、子の頂点の色が更新された場合はその時に更新されるため問題ないです。親の頂点が更新された場合は、自分の知っている親の色と実際の親の色が異なる場合連想配列の値を更新します。
このように更新処理を行うことでクエリ当たりで処理を行うことができます。
よってこの問題はで解くことができました。
$N \ $個のボールが横一列に並んでおり、始めすべてのボールは白く塗られている。
以下のような$ \ Q \ $個のクエリが与えられる。
各クエリ後のボールについて、白く塗られたボールが連続して最大何個並んでいるか求めよ。
連続した白いボールをUnionFindで管理したくなりますが、UnionFindでは削除するという処理ができません。
そこで、クエリをすべて処理し終えた状態から始め、各クエリを逆に処理していきます。
すべて処理し終えた状態においての答えは簡単に求めることができ、クエリは黒く塗られたボールを白く塗りなおす処理とすることができるのでUnionFindで処理が可能です。
よってこの問題は計算量$ \ O(Q \alpha(N)) \ $で解くことが出来ました。
※$ \ a(N) \ $はアッカーマン関数の逆関数
$N \ $個のボールがあり、$i \ $番目のボールには整数$ \ A_i \ $が書かれている。
これらのボールを青または赤で塗るとき、青いボールの値の総和が赤いボールの値の総和と等しくなる塗り分け方を$ \ 998244353 \ $で割った余りを求めよ。
値の総和が等しくなるということは、青の総和$ \ = \ $赤の総和$ \ = \frac{\sum A_i}{2} \ $です。
そのため、全体の総和が奇数の場合答えは$ \ 0 \ $です。そうでない場合、$DP[i][j] \ $を$ \ i \ $番目のボールまでを塗り分けたとき、青の総和が$ \ j \ $となるような選び方の総数とした動的計画法で答えを求めることができます。
よってこの問題は計算量$ \ O(N \sum A_i) \ $で解くことができました。
二次元座標平面上に$ \ N \ $個の点があり、$i \ $番目の点の座標は$ \ (x_i,y_i) \ $である。
次の条件を満たす整数$ \ i,j \ $の組の個数を求めよ。
整数$ \ i,j \ (i \lt j) \ $が条件を満たすとき以下のことが成り立ちます。
よって、上記の条件を満たすペアを数え上げればよいです。これは求めた値をソートし連続する同じ値の個数から求める方法や、C++ならばstd::mapを使う方法があります。
長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $が与えられる。
以下のようなクエリが$ \ Q \ $回にわたって与えられる。
$i \ $番目までのクエリを処理した時点での数列$ \ A \ $を数列$ \ A_i \ $としたとき、$A_1,A_2,\ldots,A_Q \ $のうち広義単調増加であるものの個数を求めよ。
$(1 \leq i \leq N - 1) \ $を満たす整数$ \ i \ $について、$a_i \leq a_{i + 1} \ $を満たすならば、数列$ \ A \ $は広義単調増加であると言えます。
そのため、予め上記の条件を満たす$ \ i \ $の個数を数えておき、各クエリにおいて更新された箇所の値をその前後の値と比較することでこの個数を更新すればよいです。
よってこの問題は$ \ O(N + Q) \ $で解くことができました。
$N \ $問のコンテストに$ \ M \ $人の部員が参加している。
$i \ $番目の部員のレーティングは$ \ R_i \ $であり、$l_i \ $番目から$ \ r_i \ $番目までの問題を解いた。
各問題について、その問題を解いた部員についてのレーティングの平均値を求めよ。
各問題について、その問題を解いた部員のレーティングの総和と解いた人の人数が分かればよいです。
愚直に計算すると$ \ O(NM) \ $となりTLEですが、各部員の解いた問題が区間となっていることに注目するといもす法が使えることが分かります。
よってこの問題は$ \ O(N + M) \ $で解くことができました。
$N \ $個の整数$ \ a_1,a_2,\ldots,a_N \ $が与えられる。
各$ \ a_i \ $について、$a_i \times k \ $が素数となる最小の正整数$ \ k \ $を求めよ。
ただし、そのような$ \ k \ $が存在しないならばNAを出力せよ。
各$ \ a_i \ $に対する答えは、$a_i \ $が素数である場合は$ \ 1 \ $。$a_i \ $が$ \ 1 \ $である場合は$ \ 2 \ $。素数でも$ \ 1 \ $でもない場合はNAとなります。 ただし、通常の素数判定法では$ \ a_i \ $が素数かどうか判定するのに$ \ O(\sqrt{a_i}) \ $かかってしまいます。エラトステネスの篩を用いて$ \ O(1) \ $で判定しましょう。
よってこの問題は、$max_a \ $を$ \ \max({a_1,a_2,\ldots,a_N}) \ $としたとき、計算量$ \ O(N + max_a \log \log max_a) \ $で解くことができます。
