HOJ 1285 - 文章力が、無い。

問題URL

問題概要

$\large \displaystyle \sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } (|A - i| + |B - j|) \bmod 998244353$ を求めよ。

制約

• $1 \leq N,M \leq 10^9$
• $1 \leq A \leq N$
• $1 \leq B \leq ​M​$

解説

$\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } (|A - i| + |B - j|) \bmod 998244353 \ $は $(\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |A - i|) + (\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |B - j|) \bmod 998244353 \ $というように分割することができます。
$\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |A - i| \ $というのは、$M \times \sum_{ i = 1 }^{ N } |A - i| \ $というように変形できます。 また、$\sum_{i = 1}^{N} |A - i| \ $は$(\sum_{i = 0}^{A - 1} i) + (\sum_{i = 0}^{N - A + 1} i) \ $というように変形できます。
この値は簡単な計算で求めることができ、$\sum_{ i = 1 }^{ N } \sum_{ j = 1 }^{ M } |B - j| \ $も同じように変形させる事が出来ます。
よって、この問題は計算量$ \ O(1) \ $で解くことができます。

HOJ 1279 - Sequence Sum

問題URL

問題概要

長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $が与えられる。
次の条件を満たす数列$ \ B \ (b_1,b_2,\ldots,b_N) \ $を求めよ。

• 数列$ \ B \ $の$ \ i \ (1 \leq i \leq N) \ $番目の要素$ \ b_i \ $は数列$ \ A \ $の中で$ \ a_i \ $よりも値の大きい要素の総和である。

制約

• $1 \leq N \leq 10^5$
• $0 \leq a_i \leq 10^9$

解説

各$ \ b_i \ $を愚直に求めようとした場合計算量は$ \ O(N^2) \ $となりTLEです。 より高速に$ \ b_i \ $を求める必要があります。

解法はいくつか存在しますが、累積和と二分探索を用いることで高速に答えを求めることができます。
$A \ $を降順に並べ替えたものを$ \ A' \ $とすると、 $A'_k \gt A_i \ $を満たす最大の$ \ k \ $について、$A'_1 \ $から$ \ A'_k \ $までの総和が$ \ b_i \ $となります。 このような$ \ k \ $は二分探索により$ \ O(\log N) \ $で求めることができ、$A'_1 \ $から$ \ A'_k \ $までの総和は累積和で高速に求められます。
よってこの問題は計算量$ \ O(N \log N) \ $で解くことができます。

HOJ 1278 - Eating NAMEKUZI

問題URL

問題概要

山本君は$ \ N \ $匹のナメクジを$ \ D \ $日間にわたって$ \ M \ $匹ずつ食べる。
山本君の食べることのできるナメクジな何匹か。

制約

• $1 \leq N,M,D \leq 100$

解説

$D \ $日間$ \ M \ $匹ずつ食べるため、$D \times M \leq N \ $であれば毎日$ \ M \ $匹ずつ食べられます。よって$ \ D \times M \ $を出力します。
そうでなければ持っているナメクジを全て食べることになるため$ \ N \ $を出力します。

HOJ 1276 - Median Find

問題URL

問題概要

$N \ $個の整数$ \ a_1,a_2,\ldots,a_N \ $がある。
各整数$ \ i \ (1 \leq i \leq N) \ $について$ \ a_1,a_2,\ldots,a_i \ $の中央値を小数点以下切り捨てで求めよ。

制約

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq a_i \leq 10^9$

解説

優先度付きキューを$ \ 2 \ $つ使用します。ここでは$ \ 2 \ $つのキューを$ \ que_1,que_2 \ $とします。
$que_1 \ $には$ \ A \ $の中央値以下の値が、$que_2 \ $には中央値以上の値が入ってるようにします。 また、$que_1の要素​数 \leq que_2の要素​数 \ $が常に成り立つようにします。
このとき$ \ A \ $の中央値は、$A \ $の要素​数が偶数のとき$ \ \frac{que_1の最大値 + que_2の最小値}{2}$。 奇数のとき$ \ \frac{que_1の最大値}{2} \ $となります。

$a_i \ $を追加する際に、$i \ $が奇数であれば追加後の$ \ A \ $の要素​数は偶数です。
$a_i \ $が$ \ que_2 \ $の最小値より大きいのであれば$ \ a_i \ $を$ \ que_2 \ $に追加します。 ただし、要素​数の条件を満たすようにするため、まず$ \ que_2 \ $の最小値を削除し、$que_1 \ $に追加します。 その後$ \ a_i \ $を$ \ que_2 \ $に追加します。
そうでない場合$ \ a_i \ $は$ \ que_1 \ $に追加します。

$a_i \ $を追加する際に、$i \ $が奇数であれば追加後の$ \ A \ $の要素​数は奇数です。
$a_i \ $が$ \ que_1 \ $の最大値より大きいのであれば$ \ a_i \ $を$ \ que_1 \ $に追加します。 ただし、要素​数の条件を満たすようにするため、まず$ \ que_1 \ $の最大値を削除し、$que_2\ $に追加します。 その後$ \ a_i \ $を$ \ que_1 \ $に追加します。
そうでない場合$ \ a_i \ $は$ \ que_2 \ $に追加します。

このようにこの問題は計算量$ \ O(N \log N) \ $で解くことができます。

HOJ 1275 - Robot Movement History

問題URL

問題概要

$H \ $階建てのビルに$ \ N \ $台のロボットが配置されている。
$i \ $台目のロボットは$ \ f_i \ $階に設置されており、同じ階に複数のロボットが配置されていることはない。

ロボットの移動命令が$ \ Q \ $回にわたって与えられる。すべての命令を処理した後の各ロボットの位置を求めよ。
命令は$ \ 3 \ $つの整数$ \ k_i,d_i,r_i \ $からなり、$k_i \ $番目までのロボットが$ \ r_i \ $回以下のような移動を繰り返す。

• $d_i = 1 \ $のとき、現在いる階が$ \ H \ $階でないならば$ \ 1 \ $つ上の階へ移動する。
• $d_i = 0 \ $のとき、現在いる階が$ \ 1 \ $階でないならば$ \ 1 \ $つ下の階へ移動する。

また、同じ階にいる他のロボットが上下の階へ移動をしたとき、自身も共に移動する。

制約

• $1 \leq N \leq 10^5$
• $N \leq H \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq f_i \leq H$
• $1 \leq k_i \leq N$
• $0 \leq d_i \leq 1$
• $1 \leq r_i \leq H$

解説

この問題の重要な点は複数のロボットが同じように移動するという点です。 これらのロボットを全て処理するのは無駄です。 これはUnionFindTree(DisjointSet)を使うことで1つのグループとして管理できます。
ロボットの移動とそれに伴うグループの併合は、C++の場合std::setを使うと簡単に実装できます。

計算量は$ \ O(( N + Q ) \log N) \ $となります。

HOJ 1274 - String Replacement

問題URL

問題概要

長さ$ \ L \ $の*のみからなる文字列$ \ S \ $がある。
以下のようなクエリが$ \ Q \ $回にわたって与えられる。全て処理した後の文字列$ \ S \ $を求めよ。

• $S \ $の$ \ l_i \ $文字目から$ \ r_i \ $文字目までを文字$ \ c_i \ $に置き換える。

制約

• $1 \leq L \leq 10^3$
• $0 \leq Q \leq 10^3$

解説

$N,Q \ $の最大値が$ \ 10^3 \ $とそれほど大きくないため、各クエリをそのまま処理すればよいです。
よってこの問題計算量$ \ O(QN) \ $で解くことができます。

HOJ 1264 - Sum of multiples

問題URL

問題概要

$N \ $以下の正整数のうち、$M \ $の倍数であるものの総和を$ \ 998244353 \ $で割った余りを求めよ。

制約

• $1 \leq N \leq 10^{18}$
• $1 \leq M \leq N$

解説

求める値は初項$ \ 0 \ $、末項$ \ [ \frac{N}{M} ] \times M \ $、公差$ \ M \ $、項数を$ \ [ \frac{N}{M} ] + 1 \ $とした等差数列の総和であると言えます。 この数列は$ \ 0,M,2M,3M,\ldots \ $と表せます。
末項を$ \ kM \ $とすると、数列は$ \ 0,M,2M,\ldots,kM \ $となり、この数列を反転させて元の数列に足すと$ \ 0 + kM,M + ( k - 1 ) M, 2M + (k-2)M,\ldots,kM + 0 = kM,kM,kM,\ldots,kM \ $となります。 よって、これらの総和は$ \ \frac{末項 \times (項数)}{2} \ $で求められます。