質問編集履歴
7
変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -10,19 +10,20 @@
|
|
|
10
10
|
|
|
11
11
|
#ソースコード
|
|
12
12
|
```Python
|
|
13
|
+
from itertools import accumulate
|
|
13
14
|
from bisect import bisect_left
|
|
14
15
|
|
|
15
16
|
N, Q = map(int, input().split())
|
|
16
17
|
A = list(map(int, input().split()))
|
|
17
18
|
|
|
18
|
-
check = [0] + A
|
|
19
|
+
check = [0] + [a for a in A]
|
|
19
|
-
li = [
|
|
20
|
+
li = [0] + list(accumulate([1 for _ in range(len(check) - 1)]))
|
|
20
|
-
#
|
|
21
|
+
#[0, 3, 5, 6, 7]
|
|
21
|
-
#
|
|
22
|
+
#[0, 1, 2, 3, 4]
|
|
22
23
|
|
|
23
24
|
def find_ind(k):
|
|
24
25
|
left = 1
|
|
25
|
-
right = 10 **
|
|
26
|
+
right = 10 ** 19
|
|
26
27
|
while right - left > 1:
|
|
27
28
|
mid = (left + right) // 2
|
|
28
29
|
if mid - li[bisect_left(check, mid) - 1] <= k:
|
|
@@ -30,7 +31,6 @@
|
|
|
30
31
|
else:
|
|
31
32
|
right = mid
|
|
32
33
|
return left
|
|
33
|
-
|
|
34
34
|
for _ in range(Q):
|
|
35
35
|
K = int(input())
|
|
36
36
|
print(find_ind(K))
|
6
追加
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
二分探索で例外が処理しきれない
|
|
1
|
+
AtCoder / 二分探索で例外が処理しきれない
|
body
CHANGED
|
File without changes
|
5
変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -37,4 +37,4 @@
|
|
|
37
37
|
```
|
|
38
38
|
|
|
39
39
|
#考えたこと・質問
|
|
40
|
-
何か見えない例外が発生し、本当の答えが実はleftではなくrightなのではないか？と言うことを考え、leftが条件式left - li[bisect_left(check, left) - 1] == kを満たさない場合はrightを代わりに出力するようにしても、やはり該当のテストケース2つでWAをくらったため、leftにもrightにも正解がないようなケースが発生していることがわかりました。どのような見落としが考えられ
|
|
40
|
+
何か見えない例外が発生し、本当の答えが実はleftではなくrightなのではないか？と言うことを考え、leftが条件式left - li[bisect_left(check, left) - 1] == kを満たさない場合はrightを代わりに出力するようにしても、やはり該当のテストケース2つでWAをくらったため、leftにもrightにも正解がないようなケースが発生していることがわかりました。どのような見落としが考えられるのでしょうか。自分で思いつくケースは色々と模索したものの一向に答えにたどり着く兆しが見えません。お力添え頂ける箇所がございましたら、ご教授のほど何卒よろしくお願い申し上げます。
|
4
変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -6,7 +6,7 @@
|
|
|
6
6
|
|
|
7
7
|
|
|
8
8
|
#方針
|
|
9
|
-
checkとliの1つのリストは、各Kの入力に対してそれに対応する今回の問題の答えが「check[i]より大きい時(iはそのような条件を満たす最小の値)、その答えの値からli[i]を引いたものがKである」と言う風に考え設定しました。例えば、「入力例1」で言うとK2にあたる5について言えば、それに対応する9が「check[4] = 7より大きい時、その答えの値からli[4] = 4を引いたもの(=5)がKである」といった要領です。この方針ではAC×21, WA×2でほとんどのテストケースには正解しているのですが、ごく一部のケースで間違いであるようです。昨日行われたばかりのコンテストであるため、テストケース自体は未だ公開されておりません。
|
|
9
|
+
checkとliの1つのリストは、各Kの入力に対してそれに対応する今回の問題の答えが「check[i]より大きい時(iはそのような条件を満たす最小の値)、その答えの値からli[i]を引いたものがKである」と言う風に考え設定しました。例えば、「入力例1」で言うとK2にあたる5について言えば、それに対応する答えの9が「check[4] = 7より大きい時、その答えの値からli[4] = 4を引いたもの(=5)がKである」といった要領です。この方針ではAC×21, WA×2でほとんどのテストケースには正解しているのですが、ごく一部のケースで間違いであるようです。昨日行われたばかりのコンテストであるため、テストケース自体は未だ公開されておりません。
|
|
10
10
|
|
|
11
11
|
#ソースコード
|
|
12
12
|
```Python
|
3
変更
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
二分探索
|
|
1
|
+
二分探索で例外が処理しきれない
|
body
CHANGED
|
File without changes
|
2
変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -15,7 +15,7 @@
|
|
|
15
15
|
N, Q = map(int, input().split())
|
|
16
16
|
A = list(map(int, input().split()))
|
|
17
17
|
|
|
18
|
-
check = [0] +
|
|
18
|
+
check = [0] + A
|
|
19
19
|
li = [i for i in range(len(check) - 1)]
|
|
20
20
|
#check = [0, 3, 5, 6, 7]
|
|
21
21
|
#li = [0, 1, 2, 3, 4]
|
1
追加
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -17,6 +17,8 @@
|
|
|
17
17
|
|
|
18
18
|
check = [0] + [a for a in A]
|
|
19
19
|
li = [i for i in range(len(check) - 1)]
|
|
20
|
+
#check = [0, 3, 5, 6, 7]
|
|
21
|
+
#li = [0, 1, 2, 3, 4]
|
|
20
22
|
|
|
21
23
|
def find_ind(k):
|
|
22
24
|
left = 1
|