回答編集履歴
2
コード微修正
test
CHANGED
|
@@ -100,12 +100,6 @@
|
|
|
100
100
|
|
|
101
101
|
def solve(begin, end, todo):
|
|
102
102
|
|
|
103
|
-
if todo == 0 or begin == end:
|
|
104
|
-
|
|
105
|
-
return
|
|
106
|
-
|
|
107
|
-
|
|
108
|
-
|
|
109
103
|
middle = (begin + end) / 2
|
|
110
104
|
|
|
111
105
|
tmp_array = [0] * LENGTH
|
1
改善案追記
test
CHANGED
|
@@ -23,3 +23,145 @@
|
|
|
23
23
|
|
|
24
24
|
|
|
25
25
|
てな感じにやりまして、全部0のときより増えてればそこは`1`、減ってりゃ`0`でありんす。
|
|
26
|
+
|
|
27
|
+
|
|
28
|
+
|
|
29
|
+
---------
|
|
30
|
+
|
|
31
|
+
|
|
32
|
+
|
|
33
|
+
■追記: 改善方法、長考した結果
|
|
34
|
+
|
|
35
|
+
|
|
36
|
+
|
|
37
|
+
あんま綺麗なコードじゃなくて恐縮なんですが、二分探査的に置き換えていって、連続した`0`または`1`を検出したらそこで足切りする方法試してみました。
|
|
38
|
+
|
|
39
|
+
|
|
40
|
+
|
|
41
|
+
長さ 1000 で 10 回計測したところ、クエリ回数が平均 717.5 となりました。
|
|
42
|
+
|
|
43
|
+
|
|
44
|
+
|
|
45
|
+
```
|
|
46
|
+
|
|
47
|
+
# coding: utf-8
|
|
48
|
+
|
|
49
|
+
import random
|
|
50
|
+
|
|
51
|
+
|
|
52
|
+
|
|
53
|
+
def make_string(int_array):
|
|
54
|
+
|
|
55
|
+
return "".join(map(str, int_array))
|
|
56
|
+
|
|
57
|
+
|
|
58
|
+
|
|
59
|
+
LENGTH = 1000
|
|
60
|
+
|
|
61
|
+
REAL_ANSWER = make_string([random.randint(0, 1) for i in range(LENGTH)])
|
|
62
|
+
|
|
63
|
+
|
|
64
|
+
|
|
65
|
+
print "REAL_ANSWER:\t" + REAL_ANSWER
|
|
66
|
+
|
|
67
|
+
|
|
68
|
+
|
|
69
|
+
count = 0
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
def check(query):
|
|
74
|
+
|
|
75
|
+
global count
|
|
76
|
+
|
|
77
|
+
count += 1
|
|
78
|
+
|
|
79
|
+
print "query (" + str(count) + "):\t" + query
|
|
80
|
+
|
|
81
|
+
ret = 0
|
|
82
|
+
|
|
83
|
+
for i in range(0, len(query)):
|
|
84
|
+
|
|
85
|
+
if query[i] == REAL_ANSWER[i]:
|
|
86
|
+
|
|
87
|
+
ret += 1
|
|
88
|
+
|
|
89
|
+
return ret
|
|
90
|
+
|
|
91
|
+
|
|
92
|
+
|
|
93
|
+
NUM_OF_ZERO = check(make_string([0] * LENGTH))
|
|
94
|
+
|
|
95
|
+
my_answer = [0] * LENGTH
|
|
96
|
+
|
|
97
|
+
|
|
98
|
+
|
|
99
|
+
# 引数 todo: 訂正すべき数
|
|
100
|
+
|
|
101
|
+
def solve(begin, end, todo):
|
|
102
|
+
|
|
103
|
+
if todo == 0 or begin == end:
|
|
104
|
+
|
|
105
|
+
return
|
|
106
|
+
|
|
107
|
+
|
|
108
|
+
|
|
109
|
+
middle = (begin + end) / 2
|
|
110
|
+
|
|
111
|
+
tmp_array = [0] * LENGTH
|
|
112
|
+
|
|
113
|
+
for i in range(begin, middle):
|
|
114
|
+
|
|
115
|
+
tmp_array[i] = 1
|
|
116
|
+
|
|
117
|
+
tmp_score = check(make_string(tmp_array))
|
|
118
|
+
|
|
119
|
+
|
|
120
|
+
|
|
121
|
+
left_todo = (tmp_score - NUM_OF_ZERO + middle - begin) / 2
|
|
122
|
+
|
|
123
|
+
right_todo = todo - left_todo
|
|
124
|
+
|
|
125
|
+
|
|
126
|
+
|
|
127
|
+
if (left_todo == 0):
|
|
128
|
+
|
|
129
|
+
pass
|
|
130
|
+
|
|
131
|
+
elif (left_todo == middle - begin):
|
|
132
|
+
|
|
133
|
+
for i in range(begin, middle):
|
|
134
|
+
|
|
135
|
+
my_answer[i] = 1
|
|
136
|
+
|
|
137
|
+
else:
|
|
138
|
+
|
|
139
|
+
solve(begin, middle, left_todo)
|
|
140
|
+
|
|
141
|
+
|
|
142
|
+
|
|
143
|
+
if (right_todo == 0):
|
|
144
|
+
|
|
145
|
+
pass
|
|
146
|
+
|
|
147
|
+
elif (right_todo == end - middle):
|
|
148
|
+
|
|
149
|
+
for i in range(middle, end):
|
|
150
|
+
|
|
151
|
+
my_answer[i] = 1
|
|
152
|
+
|
|
153
|
+
else:
|
|
154
|
+
|
|
155
|
+
solve(middle, end, right_todo)
|
|
156
|
+
|
|
157
|
+
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
+
solve(0, LENGTH, LENGTH - NUM_OF_ZERO)
|
|
162
|
+
|
|
163
|
+
print "my_answer:\t" + make_string(my_answer)
|
|
164
|
+
|
|
165
|
+
print make_string(my_answer) == REAL_ANSWER
|
|
166
|
+
|
|
167
|
+
```
|