回答編集履歴
1
おまけ追加
test
CHANGED
|
@@ -141,3 +141,57 @@
|
|
|
141
141
|
20件を超えると100万になるので瞬殺はこの辺がギリギリで、30件になると辛いと思います。
|
|
142
142
|
|
|
143
143
|
ただまぁ競技プログラミングなら兎も角、課題レベルだとそんなやばい条件は指定されないと思います。
|
|
144
|
+
|
|
145
|
+
|
|
146
|
+
|
|
147
|
+
---
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
151
|
+
【おまけ】 最強の回答を考える
|
|
152
|
+
|
|
153
|
+
|
|
154
|
+
|
|
155
|
+
計算量にこだわるなら、
|
|
156
|
+
|
|
157
|
+
人間がどうやったら最も楽に計算出来るかを考え、
|
|
158
|
+
|
|
159
|
+
その手順をなぞる事が重要です。
|
|
160
|
+
|
|
161
|
+
|
|
162
|
+
|
|
163
|
+
例えば、もし人間がこの問題を手計算で解いてくださいと言われたらこうやりますよね？
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
|
|
167
|
+
1. 給油せずにゴール出来るか否かを確認
|
|
168
|
+
|
|
169
|
+
2. 給油せずに最もゴールに近いガソリンスタンドへ寄る
|
|
170
|
+
|
|
171
|
+
3. 経路上のガソリンスタンドの内、「最も条件の良いスタンド」で給油
|
|
172
|
+
|
|
173
|
+
4. 給油後、ゴール出来るか否かを再計算
|
|
174
|
+
|
|
175
|
+
5. 2-4を繰り返してゴールして答えを求める
|
|
176
|
+
|
|
177
|
+
|
|
178
|
+
|
|
179
|
+
最も条件の良いスタンドというのは、
|
|
180
|
+
|
|
181
|
+
一言で言えば「タンクからガソリンが溢れずに最も沢山給油出来るスタンド」と定義できますね。
|
|
182
|
+
|
|
183
|
+
タンクサイズの指定が無いなら一番補給出来るリットル数が多いスタンドを脳死で選べば良いですね。
|
|
184
|
+
|
|
185
|
+
|
|
186
|
+
|
|
187
|
+
この2-4の手順を繰り返しての所で役に立つのが無限ループと再帰関数です。
|
|
188
|
+
|
|
189
|
+
|
|
190
|
+
|
|
191
|
+
これは私が考えた多分最善だろうという解き方であり、
|
|
192
|
+
|
|
193
|
+
他にもっと効率の良い手法があるかも知れません。
|
|
194
|
+
|
|
195
|
+
その場その場で考える必要があり、どういうコードを書けば良いかは都度考える必要があります。
|
|
196
|
+
|
|
197
|
+
この辺を詰めるのが競技プログラミングというジャンルで競技になる程に選択肢があって楽しい分野ではあります。
|