コンテンツにスキップ

数学

タグ「数学」の記事 5 件

DOJ Beginner Contest 11 C - Farewell

整数列 A1,A2,…,ANA_1, A_2, \dots, A_N があります。要素を 1 つ選んで削除すると、その左にあった要素はすべて 11 増え、右にあった要素はすべて 11 減ります。

要素が 1 つになるまで削除を繰り返したとき、最後に残る値の最大値を求める問題です。値は負になってもかまいません。

最後に残す要素を AiA_i と決めます(1-indexed)。

AiA_i より左の要素を削除すると、AiA_i は削除した要素の右にあるので 11 減ります。AiA_i より右の要素を削除すると 11 増えます。左には i−1i - 1 個、右には N−iN - i 個の要素があり、どれもいつかは削除されるので、削除の順番によらず最後の値は

Ai−(i−1)+(N−i)A_i - (i - 1) + (N - i)

です。これを ii について最大化すれば答えです。O(N)O(N) で求まります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = -float("inf")
for i in range(N):
ans = max(ans, A[i] - i + N - i - 1)
print(ans)

コードでは 0-indexed なので、左に ii 個、右に N−i−1N - i - 1 個の要素があります。

DOJ Beginner Contest 7 A - 49

国語を含む NN 個の試験を受けます。どの試験も満点は 100100 点ですが、国語だけは 4949 点を超えられません。合計点の最大値を求める問題です。

国語以外の N−1N - 1 個の試験で 100100 点、国語で 4949 点をとるのが最大です。答えは

100(N−1)+49=100N−51100(N - 1) + 49 = 100N - 51

です。

Python
for _ in range(int(input())):
N = int(input())
print(N * 100 - 51)

DOJ Beginner Contest 9 G - Pi Problem

正の整数 a,ba, b に対して、aa の十進表記を bb 回つなげた整数を rep(a,b)\mathrm{rep}(a, b) とします。たとえば rep(31,4)=31313131\mathrm{rep}(31, 4) = 31313131 です。

長さ NN の正整数列 AA が与えられるので、

∏1≤i<j≤Nrep(Ai,Aj)\prod_{1 \le i < j \le N} \mathrm{rep}(A_i, A_j)

を 998244353998244353 で割った余りを求める問題です。Ai≤109A_i \le 10^9 で、NN の総和は 2×1052 \times 10^5 以下です。

aa が kk 桁のとき、aa を bb 回つなげることは、aa に 1+10k+102k+⋯+10(b−1)k1 + 10^k + 10^{2k} + \dots + 10^{(b-1)k} を掛けることと同じです。等比数列の和を使うと

rep(a,b)=a⋅10kb−110k−1\mathrm{rep}(a, b) = a \cdot \frac{10^{kb} - 1}{10^k - 1}

です。以下、kk 桁の数を bb 回つなげたときに掛かる部分を fk(b)=10kb−110k−1f_k(b) = \dfrac{10^{kb} - 1}{10^k - 1} と書きます。

AiA_i の桁数を kik_i とすると、求める積は

∏i<jAi⋅fki(Aj)=(∏i<jAi)(∏i<jfki(Aj))\prod_{i < j} A_i \cdot f_{k_i}(A_j) = \left( \prod_{i < j} A_i \right) \left( \prod_{i < j} f_{k_i}(A_j) \right)

と分けられます。

前半では、AiA_i は自分より後ろの jj の個数だけ掛かるので、∏iAiN−i\prod_i A_i^{N - i} です。

後半は、jj ごとにまとめます。Ai≤109A_i \le 10^9 なので桁数 kk は 11 から 1010 までしかありません。i<ji < j で桁数が kk のものの個数を cj,kc_{j,k} とすると、後半は

∏j∏k=110fk(Aj)cj,k\prod_j \prod_{k=1}^{10} f_k(A_j)^{c_{j,k}}

です。cj,kc_{j,k} は桁数ごとの個数を数えながら jj を動かせば求まります。fk(Aj)f_k(A_j) は 11 つの jj につき 1010 通りしかないので、全体で O(10Nlog⁡A)O(10 N \log A) 回程度の計算で済みます。

fk(b)f_k(b) を 998244353998244353 で割った余り

Section titled “fk(b)f_k(b)fk​(b) を 998244353998244353998244353 で割った余り”

fk(b)f_k(b) は割り算を含みます。10k−110^k - 1 の逆元を使ってもよいのですが、解答コードでは逆元を使わずに計算しています。

M=998244353M = 998244353、d=10k−1d = 10^k - 1、X=10kb−1X = 10^{kb} - 1 とします。XX は dd で割り切れます。XX を dMdM で割った余りを rr とすると、X=q⋅dM+rX = q \cdot dM + r と書けて、rr も dd で割り切れます。両辺を dd で割ると

Xd=qM+rd\frac{X}{d} = qM + \frac{r}{d}

なので、Xd\dfrac{X}{d} を MM で割った余りは rd\dfrac{r}{d} を MM で割った余りと同じです。つまり、10kb10^{kb} を dMdM を法として計算し、11 を引いてから dd で割れば、fk(b)f_k(b) を MM で割った余りが求まります。

Python
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 1
d = [0] * 11
for i in range(N):
ans *= pow(A[i], N - i - 1, MOD)
ans %= MOD
d[len(str(A[i]))] += 1
for i in reversed(range(N)):
d[len(str(A[i]))] -= 1
for j in range(1, 11):
if d[j] == 0:
continue
b = 10**j - 1
x = pow(10, j * A[i], b * MOD)
x -= 1
x %= b * MOD
assert x % b == 0
x //= b
ans *= pow(x, d[j], MOD)
ans %= MOD
print(ans)

最初のループで前半の積を計算し、桁数ごとの個数 d を数えます。2 つ目のループでは後ろから見ていき、d から自分を引くことで、d[j] が「自分より前にある jj 桁の数の個数」になるようにしています。

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} の切り上げを計算しています。

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 版と同じ計算です。