質問編集履歴
5
urlの記載
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -44,7 +44,10 @@
|
|
|
44
44
|
}
|
|
45
45
|
```
|
|
46
46
|
「競技プログラミングの鉄則 米田優峻[著]」3.3 しゃくとり法の問題A13から引用
|
|
47
|
-
|
|
47
|
+
問題:
|
|
48
|
+
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_m
|
|
49
|
+
解答コード:
|
|
50
|
+
https://github.com/E869120/kyopro-tessoku/blob/main/codes/cpp/chap03/answer_A13.cpp
|
|
48
51
|
---
|
|
49
52
|
私の考えではこのしゃくとり法の計算量は(forループの計算量(1)) * (最も内側のwhileのループの計算量(2))が(n - 1)*(n - ?)のような形になり、O(n^2)となるように思います。これは結局、(n - 1)*(n - ?)< n^2ってことで、だから、O(n^2)にはならず、O(n)だという話なのでしょうか？
|
|
50
53
|
|
4
問題文の訂正
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -7,7 +7,7 @@
|
|
|
7
7
|
https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4
|
|
8
8
|
https://qiita.com/drken/items/ecd1a472d3a0e7db8dce
|
|
9
9
|
## 自分で考えたこと(追記)
|
|
10
|
-
以下のコードは「N個の小さい順に並んだ整数A1, A2, A3,...,ANの中から2つの整数のペアを選ぶ方法の中から差がKとなる選び方は何通りあるか」という問題を解くコードです。
|
|
10
|
+
以下のコードは「N個の小さい順に並んだ整数A1, A2, A3,...,ANの中から2つの整数のペアを選ぶ方法の中から差がK以下となる選び方は何通りあるか」という問題を解くコードです。
|
|
11
11
|
<制約>
|
|
12
12
|
・1 <= N <= 100000
|
|
13
13
|
・1 <= K <= 10^9
|
|
@@ -43,11 +43,14 @@
|
|
|
43
43
|
return 0;
|
|
44
44
|
}
|
|
45
45
|
```
|
|
46
|
-
## 引用元
|
|
47
46
|
「競技プログラミングの鉄則 米田優峻[著]」3.3 しゃくとり法の問題A13から引用
|
|
47
|
+
|
|
48
48
|
---
|
|
49
49
|
私の考えではこのしゃくとり法の計算量は(forループの計算量(1)) * (最も内側のwhileのループの計算量(2))が(n - 1)*(n - ?)のような形になり、O(n^2)となるように思います。これは結局、(n - 1)*(n - ?)< n^2ってことで、だから、O(n^2)にはならず、O(n)だという話なのでしょうか？
|
|
50
|
+
|
|
51
|
+
|
|
50
52
|
---
|
|
51
53
|
私の考えにどんな間違いがあるのか、なぜ計算量O(n)となるのかを教えてくださると幸いです。私自身混乱しているところも多くあると思いますので、そこも含めてご指摘お願いいたします。
|
|
52
54
|
|
|
53
55
|
|
|
56
|
+
|
3
引用元の明記
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -43,6 +43,9 @@
|
|
|
43
43
|
return 0;
|
|
44
44
|
}
|
|
45
45
|
```
|
|
46
|
+
## 引用元
|
|
47
|
+
「競技プログラミングの鉄則 米田優峻[著]」3.3 しゃくとり法の問題A13から引用
|
|
48
|
+
---
|
|
46
49
|
私の考えではこのしゃくとり法の計算量は(forループの計算量(1)) * (最も内側のwhileのループの計算量(2))が(n - 1)*(n - ?)のような形になり、O(n^2)となるように思います。これは結局、(n - 1)*(n - ?)< n^2ってことで、だから、O(n^2)にはならず、O(n)だという話なのでしょうか？
|
|
47
50
|
---
|
|
48
51
|
私の考えにどんな間違いがあるのか、なぜ計算量O(n)となるのかを教えてくださると幸いです。私自身混乱しているところも多くあると思いますので、そこも含めてご指摘お願いいたします。
|
2
実例となるコードを添付しました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -7,8 +7,44 @@
|
|
|
7
7
|
https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4
|
|
8
8
|
https://qiita.com/drken/items/ecd1a472d3a0e7db8dce
|
|
9
9
|
## 自分で考えたこと(追記)
|
|
10
|
-
|
|
10
|
+
以下のコードは「N個の小さい順に並んだ整数A1, A2, A3,...,ANの中から2つの整数のペアを選ぶ方法の中から差がKとなる選び方は何通りあるか」という問題を解くコードです。
|
|
11
|
+
<制約>
|
|
12
|
+
・1 <= N <= 100000
|
|
13
|
+
・1 <= K <= 10^9
|
|
14
|
+
・1 <= A1 < A2 < ... < AN <= 10^9
|
|
15
|
+
```C++
|
|
16
|
+
#include <iostream>
|
|
17
|
+
using namespace std;
|
|
18
|
+
|
|
19
|
+
int N, K;
|
|
20
|
+
int A[100009], R[100009];
|
|
21
|
+
|
|
22
|
+
int main() {
|
|
23
|
+
// 入力
|
|
24
|
+
cin >> N >> K;
|
|
25
|
+
for (int i = 1; i <= N; i++) cin >> A[i];
|
|
26
|
+
|
|
27
|
+
// しゃくとり法
|
|
28
|
+
for (int i = 1; i <= N - 1; i++) { //---(1)
|
|
29
|
+
// スタート地点を決める
|
|
30
|
+
if (i == 1) R[i] = 1;
|
|
31
|
+
else R[i] = R[i - 1];
|
|
32
|
+
|
|
33
|
+
// ギリギリまで増やしていく
|
|
34
|
+
while (R[i] < N && A[R[i] + 1] - A[i] <= K) { //---(2)
|
|
35
|
+
R[i] += 1;
|
|
36
|
+
}
|
|
37
|
+
}
|
|
38
|
+
|
|
39
|
+
// 出力
|
|
40
|
+
long long Answer = 0;
|
|
41
|
+
for (int i = 1; i <= N - 1; i++) Answer += (R[i] - i);
|
|
42
|
+
cout << Answer << endl;
|
|
43
|
+
return 0;
|
|
44
|
+
}
|
|
45
|
+
```
|
|
46
|
+
私の考えではこのしゃくとり法の計算量は(forループの計算量(1)) * (最も内側のwhileのループの計算量(2))が(n - 1)*(n - ?)のような形になり、O(n^2)となるように思います。これは結局、(n - 1)*(n - ?)< n^2ってことで、だから、O(n^2)にはならず、O(n)だという話なのでしょうか？
|
|
11
47
|
---
|
|
12
|
-
|
|
48
|
+
私の考えにどんな間違いがあるのか、なぜ計算量O(n)となるのかを教えてくださると幸いです。私自身混乱しているところも多くあると思いますので、そこも含めてご指摘お願いいたします。
|
|
13
49
|
|
|
14
50
|
|
1
自分で考えたことを追記
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -6,6 +6,8 @@
|
|
|
6
6
|
以下の2つのサイトの内容を読みましたが、私はしっかりと理解することができませんでした。
|
|
7
7
|
https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4
|
|
8
8
|
https://qiita.com/drken/items/ecd1a472d3a0e7db8dce
|
|
9
|
+
## 自分で考えたこと(追記)
|
|
10
|
+
最も内側のループではn-1回以下の操作が行われ、それをその外側のループでn回実行するので、(n-1)*nより、私はしゃくとり法の計算量はO(n^2)だと考えています。
|
|
9
11
|
---
|
|
10
12
|
初学者にも分かりやすく教えていただけると幸いです。
|
|
11
13
|
|