二次元座標平面上につの点
がある。
点の座標は
、点
の座標は
、点
の座標は
、点
の座標は
である。
この点を結ぶ四角形の面積を求めよ。なお、四角形の面積は整数となることが保証される。
点の
座標は共に
なので、
軸で上下
つの三角形に分割することができます。 よってそれぞれの面積を求めて足した結果を出力すればよいのですが、計算途中の面積が整数とならない場合があるため除算は最後に行いましょう。
頂点の木があり、頂点
は色
で塗られている。
以下のようなクエリが回にわたって与えられる。順に処理せよ。
まず木を頂点を根とした根付き木として見ます。
次に各頂点について、「現在の色」、「親の頂点番号」、「親の色」、「直接つながっている頂点の｛色:個数｝の連想配列」を用意します。このとき、連想配列のサイズが答えるべき色の種類数です。
更新処理をする際、隣接する頂点をすべて見てしまうと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) \ $で解くことができました。
