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