コンテンツにスキップ

切り上げ除算

タグ「切り上げ除算」の記事 2 件

ABC480 C - Self-Stopping Shower

シャワーのボタンを時刻 tt に押すと、時刻 tt から t+Kt + K までお湯が出ます(お湯が出ている間に押した場合も、最後に押した時刻から KK 秒間出ます)。NN 人の青木君が、それぞれ時刻 AiA_i にボタンを押します。時刻 00 から TT までずっとお湯が出ているようにするために、高橋君がボタンを押す回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、1≤K,T≤1091 \le K, T \le 10^9、0≤Ai≤1090 \le A_i \le 10^9)。

お湯が出ている時刻は、誰かがボタンを押した時刻 tt についての区間 [t,t+K][t, t + K] の和集合です。したがってこの問題は、青木君の区間 [Ai,Ai+K][A_i, A_i + K] に長さ KK の区間をいくつか足して、[0,T][0, T] を覆うときの、足す区間の個数の最小値を求める問題になります。

青木君の区間だけでは覆われない部分は、いくつかのすき間に分かれます。すき間の長さが gg なら、長さ KK の区間は少なくとも ⌈g/K⌉\lceil g / K \rceil 個必要で、すき間の左端から KK ずつずらして置けばちょうどその個数で覆えます。また、1 つの区間が 2 つのすき間にまたがることはありません。2 つのすき間の間には青木君の区間が丸ごと入っていて、またぐには長さが KK より大きくなければならないからです。よって、すき間ごとの ⌈g/K⌉\lceil g / K \rceil の和が答えです。

すき間は、青木君の押す時刻を小さい順に見ていけば求められます。今までの区間で覆われている右端を pp とします(はじめは p=0p = 0 です)。次の時刻 bb が p<bp < b なら、pp から bb までの長さ b−pb - p のすき間があります。最後に、TT を時刻の列に加えておくと、TT までに残ったすき間も同じように扱えます。TT 以上の時刻に押される分は [0,T][0, T] を覆うのに関係ないので、取り除いておきます。

計算量はソートがいちばん重く、O(Nlog⁡N)O(N \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, K, T);
VL(A, N);
vl B = {T};
for (ll a : A)
if (a < T)
B.push_back(a);
sort(B);
ll ans = 0, p = 0;
for (ll b : B) {
if (p < b)
ans += ceildiv(b - p, K);
chmax(p, b + K);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

B は、TT と、TT より前の青木君の時刻を並べてソートした列です。p が今まで覆えている右端で、b の前にすき間があれば ceildiv(b - p, K)(⌈(b−p)/K⌉\lceil (b - p) / K \rceil)回押します。そのあと b に押された分で、右端は b + K まで伸びます。Ai=0A_i = 0 の青木君がいないときは、最初のすき間に時刻 00 も含まれるので、高橋君が時刻 00 に押すことになります。

使用ライブラリ:cpp_include@9c33ee7

SamCoding Round 7 (Div. 2) E - Park Lamps

n×mn \times m のマス目があり、マスの境界(長さ 11 の道)の中央にランプを置けます。ランプはその道を挟む 22 マスを照らします(外周の道なら 11 マスだけ)。すべてのマスを照らすのに必要なランプの最小個数を求める問題です(1≤n,m≤1051 \le n, m \le 10^5)。

答えは ⌈nm2⌉\left\lceil \frac{nm}{2} \right\rceil です。

  • これより少なくはできない: ランプ 1 個で照らせるのは高々 22 マスなので、nmnm マスを照らすには nm2\frac{nm}{2} 個以上必要です。
  • この個数で照らせる: マス目は、隣り合う 22 マスの組(ドミノ)で、高々 11 マスを残して敷き詰められます。たとえば各行を左から 22 マスずつ組にし、各行の余りは縦に 22 マスずつ組にします。各ドミノの間の道にランプを置き、残った 11 マスがあればその周りの道に 11 個置けば、⌈nm2⌉\left\lceil \frac{nm}{2} \right\rceil 個ですべてのマスを照らせます。
Python
N, M = map(int, input().split())
print((N * M + 1) // 2)

(N * M + 1) // 2 で nm2\frac{nm}{2} の切り上げを計算しています。