ARC174が簡単で自分でも4つなんとか解けるレベルだったので、せっかくなのでブログに
atcoder.jp
いきなり簡単だけど、「すばやく」実装するとなると手間取りそうなやつ。
こういうの手早く実装できるようになりたいね。
ようするに、元々の数列の総和に、選んだ連続する数列の部分だけ(c-1)倍して加算するということ
この時点で、c-1の正負で場合分けがいるとわかる
連続する部分については、(rまでの累積和) - (l-1までの累積和)で求められる
考え方としては、rを選んだ時に最適なlの選び方は何かというのが自分がスタートしたところ
c - 1 > 0 なら、ここまでの累積和のうち累積和が最小になるindex
c - 1 < 0 なら、ここまでの累積和のうち累積和が最大になるindex
なので、累積和を計算しながら「ここまでの累積和の最大と最小を記録する配列」を用意して、累積和 - 最大累積和 , 累積和 - 最小累積和 を計算して c-1 倍。あとはrを動かして、最大と最小を見て終わり
N,C = map(int, input().split())
A = list(map(int, input().split()))
sumA = sum(A)
cumsumA = [0] * (N + 1)
cumsumAmin = [0] * (N + 1)
cumsumAmax = [0] * (N + 1)
for i in range(N):
cumsumA[i+1] = cumsumA[i] + A[i]
cumsumAmin[i+1] = min(cumsumAmin[i], cumsumA[i])
cumsumAmax[i+1] = max(cumsumAmax[i], cumsumA[i])
diffAmin = [0] * (N + 1)
diffAmax = [0] * (N + 1)
for i in range(N + 1):
diffAmin[i] = cumsumA[i] - cumsumAmin[i]
diffAmax[i] = cumsumA[i] - cumsumAmax[i]
ans = sumA
if C > 1:
ans += (C-1)*max(diffAmin)
else:
ans += (C-1)*min(diffAmax)
print(ans)
atcoder.jp
過学習気味でよくないと思うんだけど、基本的に「小数」を扱っていいことはないっていうのを競プロで自分は学んでいる
なので、分母を払ってから計算しましょう
そうすると今回の問題は、x,yを星4レビューの数、星5レビューの数として、
minimize P[星4] * x + P[星5] * y
subject to x + 2y >= 3*(現在の合計レビュー数) - (現在のレビュー数)
と変形できる。pulpとか使ってもいいんだけど、一次制約一個だけだし、ありえるの全列挙して比べて解いた
x を少なくして y を多くする
x を多くしてyを少なくする
の両パターンで、境界の端点となりうる候補を全部目的関数に代入して、一番小さいのが答えというゴリラ解法で解いた
今見直したけど、one5remain4 は不要です
実際問題解いてる時って怖いから余計なのまでやっちゃうっていう例だね
elif inferior == 1 は別にいらないはずだし、最適化されていないコードです
T = int(input())
# a/b の天井関数
def jisaku_ceil(a,b):
return (a+b-1)//b
def solveB(A, P):
tmppoint = 0
for i in range(5):
tmppoint += (i+1)*A[i]
tmprev = sum(A)
inferior = 3*tmprev - tmppoint
if inferior <= 0:
print(0)
elif inferior == 1:
print(min(P[3], P[4]))
else:
only4 = P[3] * inferior
one4remain5 = P[3] + P[4] * jisaku_ceil(inferior-1, 2)
only5 = P[4]*jisaku_ceil(inferior, 2)
one5remain4 = (inferior - 2) * P[3] + P[4]
print(min(only4, one4remain5, only5, one5remain4))
for _ in range(T):
A = list(map(int, input().split()))
P = list(map(int, input().split()))
solveB(A, P)
atcoder.jp
しばらくなんか変なことしてTLEが取れなかったけど、TLE解消するために色々やってたらやたら早くなったコード
基本的には期待値の線形性がわかっていないと話にならない
Xを数字nが出た直後に、すぐ手番が回ってくる人が次の数字が出るまでに支払う罰金の期待値と定義します
すると、Xi を i回目に罰金を支払ったら1、それ以外は0という確率変数だとすると、
X = X1 + X2 + ... (infinity)
となる。これは無限級数の和で、公比は次の手番が回ってくる確率である、(n/N)^2 です
そのため、先手後手それぞれの期待値が、先手iと後手iを
先手i = (i番目の数字が出た直後に最初に先手の人が先手である確率) * (i番目の数字が出た直後の人が払う罰金の期待値) + (i番目の数字が出た直後に最初に先手の人が後手である確率) * (i番目の数字が出た直後の人の次の手番の人が払う罰金の期待値)
後手i = (i番目の数字が出た直後に最初に先手の人が後手である確率) * (i番目の数字が出た直後の人が払う罰金の期待値) + (i番目の数字が出た直後に最初に先手の人が先手である確率) * (i番目の数字が出た直後の人の次の手番の人が払う罰金の期待値)
と定義すると、先手iと後手iの総和が先手と後手の期待値の総和になる
あとは高速化のために必要な数値をあらかじめ計算しておくこと
i番目の数字が出た直後に最初に先手の人が手番である確率 + i番目の数字が出た直後に最初に先手の人が手番でない確率 = 1
(i番目の数字が出た直後の人の次の手番の人が払う罰金の期待値) = (i番目の数字が出た直後の人が払う罰金の期待値) * i/N
に注意して、式変形して高速化すると早くなる
高速化すると2倍の速度になるんだけど、今回は説明用にあえて遅いの紹介します
BigPrime = 998244353
N = int(input())
# ac 合同 1 mod b となるcを互除法で求める
def modinv(a, b):
b0 = b
x0, x1 = 0, 1
while a > 1:
q = a // b
a, b = b, a % b
x0, x1 = x1 - q * x0, x0
if x1 < 0:
x1 += b0
return x1
def mod_time(a,b):
return (a*b) % BigPrime
# 高速化のために後で使う値を計算しておく
# M は N^2 mod BigPrime
# n は M の modinv
# m は n の modinv
# poweri[i] は i^2 mod BigPrime
# rate2jou[i] i^2/N^2 mod BigPrime
# timesiN_i[i] i*(N-i) mod BigPrime
# fractimesiN_i[i] i*(N-i)/N^2 mod BigPrime
# fraci[i] i/N mod BigPrime
# complementfraci[i] 1-(i/N) mod BigPrime
n = modinv(N, BigPrime)
M = (N ** 2) % BigPrime
m = modinv(M, BigPrime)
fraci = [0] * (N+1)
complementfraci = [0] * (N+1)
poweri = [0] * (N+1)
rate2jou = [0] * (N+1)
# i/N mod BigPrime
# 1-(i/N) mod BigPrime
for i in range(1, N+1):
fraci[i] = (fraci[i-1] + n) % BigPrime
complementfraci[i] = (BigPrime - fraci[i]+1) % BigPrime
# i^2 mod BigPrime
# i^2/N^2 mod BigPrime
for i in range(1, N+1):
poweri[i] = (i**2) % BigPrime
rate2jou[i] = mod_time(poweri[i], m)
# 初項と比
def limitPr(init, rate):
init = init % BigPrime
rate = rate % BigPrime
limval = mod_time(init, modinv(BigPrime+1 - rate, BigPrime))
return limval
# 今手番の人が次の数字で後手スタートになる確率
def first_to_second(i):
return limitPr(complementfraci[i], rate2jou[i])
# 今手番の人がこれから得る罰金の期待値
def val_first(i):
return limitPr(fraci[i],rate2jou[i])
ans = [0, 0]
Prob = [[0, 0] for _ in range(N+1)]
Prob[0] = [1, 0]
for i in range(N):
f_s = first_to_second(i)
# first_to_firstは一回i/Nはさんだあとのfirst_to_secondに等しいことに注意
f_f = mod_time(f_s, fraci[i])
Prob[i+1][0] = (mod_time(f_f, Prob[i][0]) + mod_time(f_s, Prob[i][1])) % BigPrime
Prob[i+1][1] = (BigPrime - Prob[i+1][0]+1) % BigPrime
v_f = val_first(i)
# 次手番の人の期待値は、確率がすべてi/N倍されるので期待値もi/N倍
v_s = mod_time(v_f, fraci[i])
ans[0] += (mod_time(v_f, Prob[i][0]) + mod_time(v_s, Prob[i][1])) % BigPrime
ans[0] %= BigPrime
ans[1] += (mod_time(v_s, Prob[i][0]) + mod_time(v_f, Prob[i][1])) % BigPrime
ans[1] %= BigPrime
print(*ans)
atcoder.jp
これ、証明抜きに答え予想してそれ実装すればいいだけだから、難易度A問題でいいと思う。証明するならDだけど。。。
証明抜きで答えだせるのが競プロの気持ち悪い所だなぁと思いつつ、今回はそれにあやかる。こういうときに証明した方が後に役立つと思うので、後でやる
とりあえず実験してみる（Pythonはstartwithとか使えば、文字列の接頭辞の判定が楽）
10^n = a として、
[a^2-a , a^2+a)
がOKとはすぐわかる。直感的にも10^2nがOKなので、その周辺がOKなのは予想がつく。
この問題がD問題なことがこの問題を簡単にしていて、D問題だったらこの程度の考察で終わるわけないから、なんか他のパターンを探す。
と、列挙した数に
80,9800
が出てくるので、あ、9^2-1と99^2-1やん、って自分は気づいて、999^2-1とか調べたら条件満たしたので、まぁ99...99系もOKってことにしてとりあえずコード提出するか。ってやったらなんかACになった。
いやー、よくないACだなあって自分でも思う
10^2n 周辺のチェックと9..9 ^2 -1 のチェックをしただけのコードだけ貼っときます
power10 = [1 for _ in range(19)]
nine_seq = [1 for _ in range(19)]
nine_power2_seq = [1 for _ in range(19)]
for i in range(1, 19):
power10[i] = power10[i-1] * 10
leftborder = [0 for _ in range(19)]
rightborder = [0 for _ in range(19)]
for i in range(1, 19):
tmp = power10[i]
leftborder[i] = tmp ** 2 -tmp
rightborder[i] = tmp ** 2 + tmp
for i in range(1, 19):
nine_seq[i] = power10[i] - 1
nine_power2_seq[i] = nine_seq[i] ** 2
def solve(N):
ans = 1
for i in range(1, 19):
tmpan = power10[i]
leftan = leftborder[i]
rightan = rightborder[i]
if rightan <= N:
ans += 2 * tmpan
elif leftan <= N:
ans += N - leftan + 1
else:
break
for i in range(1, 19):
if N >= nine_power2_seq[i] - 1:
ans += 1
return ans
T = int(input())
for _ in range(T):
N = int(input())
print(solve(N))
今回のARCのABCDについてだけみると、確かに競プロって数学かもしれないと思う内容だった。特にBCDが高校生の方が自分よりずっと早く解けそうって思えた。
