回答編集履歴
2
コード微修正
answer
CHANGED
|
@@ -49,9 +49,6 @@
|
|
|
49
49
|
|
|
50
50
|
# 引数 todo: 訂正すべき数
|
|
51
51
|
def solve(begin, end, todo):
|
|
52
|
-
if todo == 0 or begin == end:
|
|
53
|
-
return
|
|
54
|
-
|
|
55
52
|
middle = (begin + end) / 2
|
|
56
53
|
tmp_array = [0] * LENGTH
|
|
57
54
|
for i in range(begin, middle):
|
1
改善案追記
answer
CHANGED
|
@@ -10,4 +10,75 @@
|
|
|
10
10
|
`010000` -> 3
|
|
11
11
|
`100000` -> 3
|
|
12
12
|
|
|
13
|
-
てな感じにやりまして、全部0のときより増えてればそこは`1`、減ってりゃ`0`でありんす。
|
|
13
|
+
てな感じにやりまして、全部0のときより増えてればそこは`1`、減ってりゃ`0`でありんす。
|
|
14
|
+
|
|
15
|
+
---------
|
|
16
|
+
|
|
17
|
+
■追記: 改善方法、長考した結果
|
|
18
|
+
|
|
19
|
+
あんま綺麗なコードじゃなくて恐縮なんですが、二分探査的に置き換えていって、連続した`0`または`1`を検出したらそこで足切りする方法試してみました。
|
|
20
|
+
|
|
21
|
+
長さ 1000 で 10 回計測したところ、クエリ回数が平均 717.5 となりました。
|
|
22
|
+
|
|
23
|
+
```
|
|
24
|
+
# coding: utf-8
|
|
25
|
+
import random
|
|
26
|
+
|
|
27
|
+
def make_string(int_array):
|
|
28
|
+
return "".join(map(str, int_array))
|
|
29
|
+
|
|
30
|
+
LENGTH = 1000
|
|
31
|
+
REAL_ANSWER = make_string([random.randint(0, 1) for i in range(LENGTH)])
|
|
32
|
+
|
|
33
|
+
print "REAL_ANSWER:\t" + REAL_ANSWER
|
|
34
|
+
|
|
35
|
+
count = 0
|
|
36
|
+
|
|
37
|
+
def check(query):
|
|
38
|
+
global count
|
|
39
|
+
count += 1
|
|
40
|
+
print "query (" + str(count) + "):\t" + query
|
|
41
|
+
ret = 0
|
|
42
|
+
for i in range(0, len(query)):
|
|
43
|
+
if query[i] == REAL_ANSWER[i]:
|
|
44
|
+
ret += 1
|
|
45
|
+
return ret
|
|
46
|
+
|
|
47
|
+
NUM_OF_ZERO = check(make_string([0] * LENGTH))
|
|
48
|
+
my_answer = [0] * LENGTH
|
|
49
|
+
|
|
50
|
+
# 引数 todo: 訂正すべき数
|
|
51
|
+
def solve(begin, end, todo):
|
|
52
|
+
if todo == 0 or begin == end:
|
|
53
|
+
return
|
|
54
|
+
|
|
55
|
+
middle = (begin + end) / 2
|
|
56
|
+
tmp_array = [0] * LENGTH
|
|
57
|
+
for i in range(begin, middle):
|
|
58
|
+
tmp_array[i] = 1
|
|
59
|
+
tmp_score = check(make_string(tmp_array))
|
|
60
|
+
|
|
61
|
+
left_todo = (tmp_score - NUM_OF_ZERO + middle - begin) / 2
|
|
62
|
+
right_todo = todo - left_todo
|
|
63
|
+
|
|
64
|
+
if (left_todo == 0):
|
|
65
|
+
pass
|
|
66
|
+
elif (left_todo == middle - begin):
|
|
67
|
+
for i in range(begin, middle):
|
|
68
|
+
my_answer[i] = 1
|
|
69
|
+
else:
|
|
70
|
+
solve(begin, middle, left_todo)
|
|
71
|
+
|
|
72
|
+
if (right_todo == 0):
|
|
73
|
+
pass
|
|
74
|
+
elif (right_todo == end - middle):
|
|
75
|
+
for i in range(middle, end):
|
|
76
|
+
my_answer[i] = 1
|
|
77
|
+
else:
|
|
78
|
+
solve(middle, end, right_todo)
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
solve(0, LENGTH, LENGTH - NUM_OF_ZERO)
|
|
82
|
+
print "my_answer:\t" + make_string(my_answer)
|
|
83
|
+
print make_string(my_answer) == REAL_ANSWER
|
|
84
|
+
```
|