コンテンツにスキップ

切り捨て除算

タグ「切り捨て除算」の記事 2 件

SamCoding Round 7 (Div. 2) C - Digitless Keyboard

nn 個の整数 a1,…,ana_1, \ldots, a_n が与えられるので、最大値と最小値の平均を切り捨てて出力する問題です(2≤n≤1052 \le n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9)。ただし、ソースコードのどこにも数字 0〜9 を使ってはいけません。

計算は ⌊max⁡A+min⁡A2⌋\left\lfloor \frac{\max A + \min A}{2} \right\rfloor です。問題は 22 で割るところで、// 2 と書くと数字を使ってしまいます。

そこで、22 で割って切り捨てる代わりに、右に 11 ビットシフトします。シフト量の 11 には True を使います。Python では True が整数の 11 として扱われるからです。

右シフトは負の数でも切り捨て(負の無限大方向への丸め)になるので、和が負のときもそのまま正しい答えになります。たとえば −4≫1=−2-4 \gg 1 = -2、−3≫1=−2-3 \gg 1 = -2 です。

Python
N = int(input())
A = list(map(int, input().split()))
print((max(A) + min(A)) >> True)

>> True が 22 で割って切り捨てる処理です。

ABC478 A - Grapes

MM 粒のぶどうを、人 1,2,…,N1, 2, \ldots, N の順に 1 粒ずつ繰り返し配るとき、各人がもらう粒数を求める問題です(N≤100N \le 100、M≤104M \le 10^4)。

jj 粒目 (1≤j≤M1 \le j \le M) をもらうのは、j≡k(modN)j \equiv k \pmod N となる人 kk です。人 kk がもらう粒数は、11 以上 MM 以下で NN で割ると kk 余る(人 NN なら割り切れる)整数の個数なので

⌊M−k+NN⌋\left\lfloor \frac{M - k + N}{N} \right\rfloor

です。MM が小さいので実際に配るシミュレーションでも間に合いますが、式で一発で出せます。

コードでは i=N−ki = N - k として、i=N−1,…,0i = N - 1, \ldots, 0 の順に ⌊(M+i)/N⌋\lfloor (M + i) / N \rfloor を出力しています。

Python
N, M = map(int, input().split())
for i in reversed(range(N)):
print((M + i) // N)
Uiua
≡&p⇌⌊÷⟜(+⇡)°⊟⊜⋕⊸≠@ &sc

&sc で 1 行読み、⊜⋕⊸≠@ で空白区切りの数値にして °⊟ で NN と MM に分けます。⟜(+⇡) で M+[0,1,…,N−1]M + [0, 1, \ldots, N - 1] を作り、⌊÷ で NN で割って切り捨て、⇌ で逆順にして ≡&p で 1 行ずつ出力しています。Python 版と同じ計算です。