回答編集履歴
2
計算量について加筆
test
CHANGED
|
@@ -9,3 +9,7 @@
|
|
|
9
9
|
1. B1,B2,B3で三角形が作れるか調べます。作れる場合、その和が答えになります。
|
|
10
10
|
|
|
11
11
|
2. 作れない場合、B1を使うどの組み合わせも三角形を作れないので、B2,B3,B4で作れるか調べます。作れる場合、その和が答えになります。作れない場合、B3,B4,B5、というように、添字を1つづつ増やして同様に調べ、Bnを使っても作れない場合、0が答えになります。
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
全ての組み合わせを調べた場合、計算量はO(n^3)ですが、このアルゴリズムの場合、計算量はO(nlogn)になります。
|
1
途中で誤って投稿してしまったため加筆
test
CHANGED
|
@@ -2,12 +2,10 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
0. Aiを大きい順に並べ替え
|
|
5
|
+
0. Aiを大きい順に並べ替えた数列Bjを考えます。
|
|
6
6
|
|
|
7
7
|
|
|
8
8
|
|
|
9
|
-
1. B1,B2,B3で三角形が作れるか調べます。作れる場合、
|
|
9
|
+
1. B1,B2,B3で三角形が作れるか調べます。作れる場合、その和が答えになります。
|
|
10
10
|
|
|
11
|
-
2. 作れない場合、B1を使うどの組み合わせも三角形を作れないので、B2,B3,B4で作れるか調べます。作れる場合、
|
|
11
|
+
2. 作れない場合、B1を使うどの組み合わせも三角形を作れないので、B2,B3,B4で作れるか調べます。作れる場合、その和が答えになります。作れない場合、B3,B4,B5、というように、添字を1つづつ増やして同様に調べ、Bnを使っても作れない場合、0が答えになります。
|
|
12
|
-
|
|
13
|
-
3. 作れたBj,B(j+1),B(j+2)に対応するAの添字を、fの逆置換を考えることで求めます。その3つの数字が最大の長さを
|