結果
問題 | No.1929 Exponential Sequence |
ユーザー |
|
提出日時 | 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 |
ソースコード
## https://yukicoder.me/problems/no/1929def 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_ = ak = 1while a_ * a <= S:k += 1a_ *= aprint(k)returnn1 = n // 2n2 = n - n1# 最大の指数の計算array = []for a in A:if a > S:print(0)returnelse:a_ = ak = 1while a_ * a <= S:k += 1a_ *= aarray.append(k)# 半分全列挙max_k_bit = 1for i in range(n1):max_k_bit *= array[i]n1_value_set = {}for k_bit in range(max_k_bit):x = 0is_ok = Truefor i in range(n1):k = k_bit % array[i]x += A[i] ** (k + 1)if x > S:is_ok = Falsebreakk_bit //= array[i]if is_ok:if x not in n1_value_set:n1_value_set[x] = 0n1_value_set[x] += 1n1_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 = 0for x, v in n1_value_array:cum_n1 += vcum_n1_value_array.append((x, cum_n1))# n2についての処理max_k_bit = 1for i in range(n2):max_k_bit *= array[n1 + i]answer = 0for k_bit in range(max_k_bit):x = 0is_ok = Truefor i in range(n2):k = k_bit % array[n1 + i]x += A[n1 + i] ** (k + 1)if x > S:is_ok = Falsebreakk_bit //= array[n1 + i]if is_ok:if cum_n1_value_array[0][0] + x > S:continuelow = 0high = len(cum_n1_value_array) - 1while high - low > 1:mid = (high + low) // 2if cum_n1_value_array[mid][0] + x <= S:low = midelse:high = midif 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()