回答編集履歴
9
fix answer
test
CHANGED
|
@@ -18,7 +18,7 @@
|
|
|
18
18
|
|
|
19
19
|
展開して`O(N^2 + NM)`及び`O(NM + M^2)`なので，`N, M`いずれも`10^5`だった場合`10^10`となります．C/C++では1秒間に`10^7`~`10^8`回程度しかループを回せないので100秒から1000秒近くかかる実装です．
|
|
20
20
|
|
|
21
|
-
一般に，貴回答のことを[愚直解](https://twitter.com/search?q=%E6%84%9A%E7%9B%B4%
|
|
21
|
+
一般に，貴回答のことを[愚直(実装)解](https://twitter.com/search?q=%E6%84%9A%E7%9B%B4%20atcoder)と呼びますが，**C問題で愚直解はほとんど通りません．**
|
|
22
22
|
|
|
23
23
|
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
|
24
24
|
現状，`X`に位置するアルゴリズム(22-25行目，31-24行目)が[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
8
fix context
test
CHANGED
|
@@ -18,7 +18,7 @@
|
|
|
18
18
|
|
|
19
19
|
展開して`O(N^2 + NM)`及び`O(NM + M^2)`なので，`N, M`いずれも`10^5`だった場合`10^10`となります．C/C++では1秒間に`10^7`~`10^8`回程度しかループを回せないので100秒から1000秒近くかかる実装です．
|
|
20
20
|
|
|
21
|
-
一般に，貴回答のことを愚直解と呼びますが，**C問題で愚直解はほとんど通りません．**
|
|
21
|
+
一般に，貴回答のことを[愚直解](https://twitter.com/search?q=%E6%84%9A%E7%9B%B4%E8%A7%A3)と呼びますが，**C問題で愚直解はほとんど通りません．**
|
|
22
22
|
|
|
23
23
|
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
|
24
24
|
現状，`X`に位置するアルゴリズム(22-25行目，31-24行目)が[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
7
fix ans
test
CHANGED
|
@@ -18,7 +18,7 @@
|
|
|
18
18
|
|
|
19
19
|
展開して`O(N^2 + NM)`及び`O(NM + M^2)`なので，`N, M`いずれも`10^5`だった場合`10^10`となります．C/C++では1秒間に`10^7`~`10^8`回程度しかループを回せないので100秒から1000秒近くかかる実装です．
|
|
20
20
|
|
|
21
|
-
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|
|
21
|
+
一般に，貴回答のことを愚直解と呼びますが，**C問題で愚直解はほとんど通りません．**
|
|
22
22
|
|
|
23
23
|
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
|
24
24
|
現状，`X`に位置するアルゴリズム(22-25行目，31-24行目)が[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
6
fix answer
test
CHANGED
|
@@ -1,7 +1,36 @@
|
|
|
1
|
-
`M, N`がそれぞれ`10^5`あるにも関わらず，21-26行目および30-35行目の操作がそれぞれ`O((N + M)N)`および`O((N + M)M)`なのでTLEになります．
|
|
1
|
+
`M, N`がそれぞれ`10^5`あるにも関わらず，21-26行目および30-35行目の操作がそれぞれ`O((N + M)N)`および`O((N + M)M)`なのでTLEになります．
|
|
2
2
|
|
|
3
|
+
```C++
|
|
4
|
+
for(i = 0; i < m + n; i++) { // O(N + M)
|
|
5
|
+
for(j = 0; j < n; j++) { // O(N)
|
|
6
|
+
if(a.at(j) == c.at(i)) cout << i + 1 << " ";
|
|
7
|
+
}
|
|
8
|
+
}
|
|
9
|
+
|
|
10
|
+
cout << endl;
|
|
11
|
+
|
|
12
|
+
for(i = 0; i < m + n; i++) { // O(N + M)
|
|
13
|
+
for(j = 0; j < m; j++) { // O(M)
|
|
14
|
+
if(b.at(j) == c.at(i)) cout << i + 1 << " ";
|
|
15
|
+
}
|
|
16
|
+
}
|
|
17
|
+
```
|
|
18
|
+
|
|
3
|
-
`10^5`
|
|
19
|
+
展開して`O(N^2 + NM)`及び`O(NM + M^2)`なので，`N, M`いずれも`10^5`だった場合`10^10`となります．C/C++では1秒間に`10^7`~`10^8`回程度しかループを回せないので100秒から1000秒近くかかる実装です．
|
|
20
|
+
|
|
4
21
|
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|
|
5
22
|
|
|
6
23
|
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
|
7
24
|
現状，`X`に位置するアルゴリズム(22-25行目，31-24行目)が[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
|
25
|
+
|
|
26
|
+
```C++
|
|
27
|
+
for(i = 0; i < m + n; i++) { // O(N + M)
|
|
28
|
+
// ここをO(N)未満で実装する
|
|
29
|
+
}
|
|
30
|
+
|
|
31
|
+
cout << endl;
|
|
32
|
+
|
|
33
|
+
for(i = 0; i < m + n; i++) { // O(N + M)
|
|
34
|
+
// ここをO(M)未満で実装する
|
|
35
|
+
}
|
|
36
|
+
```
|
5
fix answer
test
CHANGED
|
@@ -4,4 +4,4 @@
|
|
|
4
4
|
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|
|
5
5
|
|
|
6
6
|
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
|
7
|
-
現状，`X`に位置するアルゴリズムが[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
|
7
|
+
現状，`X`に位置するアルゴリズム(22-25行目，31-24行目)が[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
4
fix answer
test
CHANGED
|
@@ -4,3 +4,4 @@
|
|
|
4
4
|
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|
|
5
5
|
|
|
6
6
|
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
|
7
|
+
現状，`X`に位置するアルゴリズムが[線型探索](https://www.google.com/search?q=%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2)となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．
|
3
fix answer
test
CHANGED
|
@@ -1,4 +1,6 @@
|
|
|
1
|
-
`M, N`がそれぞれ`10^5`あるにも関わらず，21-2
|
|
1
|
+
`M, N`がそれぞれ`10^5`あるにも関わらず，21-26行目および30-35行目の操作がそれぞれ`O((N + M)N)`および`O((N + M)M)`なのでTLEになります．`N`の2乗時間または`M`の2乗時間では間に合わないのでアルゴリズムの改善が必要です．
|
|
2
2
|
|
|
3
3
|
`10^5`の2乗は`10^10`ですが，C/C++では1秒間に`10^7`~`10^8`回程度しかループを回せないので100秒から1000秒近くかかる実装です．
|
|
4
4
|
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|
|
5
|
+
|
|
6
|
+
したがって，2乗のループをどうにかして改善して`O((N + M)X)`の`X`を対数時間や定数時間で実装してください．
|
2
fix answer
test
CHANGED
|
@@ -1,3 +1,4 @@
|
|
|
1
1
|
`M, N`がそれぞれ`10^5`あるにも関わらず，21-25行目および30-35行目の操作がそれぞれ`O((N + M)N)`および`O((N + M)M)`なのでTLEになります．`N`の2乗時間または`M`の2乗時間では間に合わないのでアルゴリズムの改善が必要です．
|
|
2
2
|
|
|
3
|
+
`10^5`の2乗は`10^10`ですが，C/C++では1秒間に`10^7`~`10^8`回程度しかループを回せないので100秒から1000秒近くかかる実装です．
|
|
3
4
|
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|
1
fix answer
test
CHANGED
|
@@ -1,3 +1,3 @@
|
|
|
1
1
|
`M, N`がそれぞれ`10^5`あるにも関わらず，21-25行目および30-35行目の操作がそれぞれ`O((N + M)N)`および`O((N + M)M)`なのでTLEになります．`N`の2乗時間または`M`の2乗時間では間に合わないのでアルゴリズムの改善が必要です．
|
|
2
2
|
|
|
3
|
-
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解は通りません．
|
|
3
|
+
一般に，貴回答のことを愚直解と呼びますが，C問題で愚直解はほとんど通りません．
|