結果

問題 No.1929 Exponential Sequence
ユーザー LyricalMaestro
提出日時 2024-10-22 23:28:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 642 ms / 2,000 ms
コード長 2,552 bytes
コンパイル時間 592 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 82,628 KB
最終ジャッジ日時 2024-10-22 23:28:23
合計ジャッジ時間 6,399 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

## https://yukicoder.me/problems/no/1929
def main():
n, S = map(int, input().split())
A = list(map(int, input().split()))
if n == 1:
a = A[0]
if a > S:
print(0)
else:
a_ = a
k = 1
while a_ * a <= S:
k += 1
a_ *= a
print(k)
return
n1 = n // 2
n2 = n - n1
#
array = []
for a in A:
if a > S:
print(0)
return
else:
a_ = a
k = 1
while a_ * a <= S:
k += 1
a_ *= a
array.append(k)
#
max_k_bit = 1
for i in range(n1):
max_k_bit *= array[i]
n1_value_set = {}
for k_bit in range(max_k_bit):
x = 0
is_ok = True
for i in range(n1):
k = k_bit % array[i]
x += A[i] ** (k + 1)
if x > S:
is_ok = False
break
k_bit //= array[i]
if is_ok:
if x not in n1_value_set:
n1_value_set[x] = 0
n1_value_set[x] += 1
n1_value_array = [(x, v) for x, v in n1_value_set.items()]
n1_value_array.sort(key=lambda x : x[0])
cum_n1_value_array = []
cum_n1 = 0
for x, v in n1_value_array:
cum_n1 += v
cum_n1_value_array.append((x, cum_n1))
# n2
max_k_bit = 1
for i in range(n2):
max_k_bit *= array[n1 + i]
answer = 0
for k_bit in range(max_k_bit):
x = 0
is_ok = True
for i in range(n2):
k = k_bit % array[n1 + i]
x += A[n1 + i] ** (k + 1)
if x > S:
is_ok = False
break
k_bit //= array[n1 + i]
if is_ok:
if cum_n1_value_array[0][0] + x > S:
continue
low = 0
high = len(cum_n1_value_array) - 1
while high - low > 1:
mid = (high + low) // 2
if cum_n1_value_array[mid][0] + x <= S:
low = mid
else:
high = mid
if cum_n1_value_array[high][0] + x <= S:
answer += cum_n1_value_array[high][1]
else:
answer += cum_n1_value_array[low][1]
print(answer)
if __name__ == "__main__":
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0