回答編集履歴
5
見出しを太字にした
test
CHANGED
|
@@ -17,9 +17,9 @@
|
|
|
17
17
|
```
|
|
18
18
|
一応、問題点についても説明しておきます。自力で解きたいなら読み飛ばしてください。
|
|
19
19
|
|
|
20
|
-
1. 条件を満たす場合に停止判定をしていない
|
|
20
|
+
1. **条件を満たす場合に停止判定をしていない**
|
|
21
21
|
最初に挙げた入力例が無限ループとなる原因。
|
|
22
22
|
条件を満たす場合の停止判定を追加するか、条件を満たさないことが確実な値(`A[0]-1`など)を`left`の初期値に入れれば解決。
|
|
23
|
-
2. 条件を満たすのが、最大のおもちゃと同じ大きさの箱だけだった場合、`ans`が0のまま更新されない
|
|
23
|
+
2. **条件を満たすのが、最大のおもちゃと同じ大きさの箱だけだった場合、`ans`が0のまま更新されない**
|
|
24
24
|
今回挙げた入力例が無限ループとなる原因。
|
|
25
25
|
そもそも27～35行の判定を通っている時点で、最大のおもちゃと同じ大きさの箱が条件を満たすのは明らかなので、`ans`の初期値を`A[N-1]`にすれば解決。(そうすると、`ans`と`right`が常に等しくなるので、`ans`自体不要となる)
|
4
文言変更
test
CHANGED
|
@@ -19,7 +19,7 @@
|
|
|
19
19
|
|
|
20
20
|
1. 条件を満たす場合に停止判定をしていない
|
|
21
21
|
最初に挙げた入力例が無限ループとなる原因。
|
|
22
|
-
条件を満たす場合の
|
|
22
|
+
条件を満たす場合の停止判定を追加するか、条件を満たさないことが確実な値(`A[0]-1`など)を`left`の初期値に入れれば解決。
|
|
23
23
|
2. 条件を満たすのが、最大のおもちゃと同じ大きさの箱だけだった場合、`ans`が0のまま更新されない
|
|
24
24
|
今回挙げた入力例が無限ループとなる原因。
|
|
25
25
|
そもそも27～35行の判定を通っている時点で、最大のおもちゃと同じ大きさの箱が条件を満たすのは明らかなので、`ans`の初期値を`A[N-1]`にすれば解決。(そうすると、`ans`と`right`が常に等しくなるので、`ans`自体不要となる)
|
3
もう一つの問題の説明追加
test
CHANGED
|
@@ -6,3 +6,20 @@
|
|
|
6
6
|
```
|
|
7
7
|
|
|
8
8
|
二分探索は意外とバグりやすいので、「[めぐる式二分探索](https://x.com/meguru_comp/status/697008509376835584)」を使うことをお勧めします(下のコードでも使われています)。「[二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜](https://qiita.com/drken/items/97e37dd6143e33a64c8c)」の解説が分かりやすいと思います。
|
|
9
|
+
|
|
10
|
+
#### 追記
|
|
11
|
+
|
|
12
|
+
上のコードには、問題点が2つあります。上記入力例だと、そのうちの1つしか分からないので、もう1つの問題が分かる入力例も挙げておきます。こちらも無限ループに陥ります。
|
|
13
|
+
```
|
|
14
|
+
2
|
|
15
|
+
1 2
|
|
16
|
+
1
|
|
17
|
+
```
|
|
18
|
+
一応、問題点についても説明しておきます。自力で解きたいなら読み飛ばしてください。
|
|
19
|
+
|
|
20
|
+
1. 条件を満たす場合に停止判定をしていない
|
|
21
|
+
最初に挙げた入力例が無限ループとなる原因。
|
|
22
|
+
条件を満たす場合の条件判定を追加するか、条件を満たさないことが確実な値(`A[0]-1`など)を`left`の初期値に入れれば解決。
|
|
23
|
+
2. 条件を満たすのが、最大のおもちゃと同じ大きさの箱だけだった場合、`ans`が0のまま更新されない
|
|
24
|
+
今回挙げた入力例が無限ループとなる原因。
|
|
25
|
+
そもそも27～35行の判定を通っている時点で、最大のおもちゃと同じ大きさの箱が条件を満たすのは明らかなので、`ans`の初期値を`A[N-1]`にすれば解決。(そうすると、`ans`と`right`が常に等しくなるので、`ans`自体不要となる)
|
2
めぐる式二分探索の紹介追加
test
CHANGED
|
@@ -4,3 +4,5 @@
|
|
|
4
4
|
1 2
|
|
5
5
|
2
|
|
6
6
|
```
|
|
7
|
+
|
|
8
|
+
二分探索は意外とバグりやすいので、「[めぐる式二分探索](https://x.com/meguru_comp/status/697008509376835584)」を使うことをお勧めします(下のコードでも使われています)。「[二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜](https://qiita.com/drken/items/97e37dd6143e33a64c8c)」の解説が分かりやすいと思います。
|
1
文言変更
test
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
上のコード
|
|
1
|
+
上のコードに以下の入力を与えると、`ok`が`false`になることがないため、無限ループに陥ります。
|
|
2
2
|
```
|
|
3
3
|
2
|
|
4
4
|
1 2
|