回答編集履歴
2
追加
answer
CHANGED
|
@@ -1,3 +1,3 @@
|
|
|
1
|
-
今回のNの制約は最大で3 * 10 5です。テストケースの中にlen(lis)が本当にその長さのものがあったとき、ご提示のコードでは a = 0 で lis[0] <= b <= lis[N - 1], a = 1 でlis[1] <= b <= lis[N - 1], ...となりループによる計算の数だけで(N * (N + 1) // 2) 回 >> 10 8となり、これはTLEとなって当然でしょう。
|
|
1
|
+
今回のNの制約は最大で3 * 10 5です。テストケースの中にlen(lis)が本当にその長さのものがあったとき、ご提示のコードでは a = 0 で lis[0] <= b <= lis[N - 1], a = 1 でlis[1] <= b <= lis[N - 1], ...となりループによる計算の数だけで(N * (N + 1) // 2) 回 >> 10 8となり、定数倍計算による処理時間も考慮するとこれはTLEとなって当然でしょう。
|
|
2
2
|
|
|
3
3
|
対処法を、と言う話ですが、これがAtCoderはじめ競技プログラミングの本質です。上のような考え方は最初から競プロのどの世界でも「完全にダメな答案」の扱いであり、これをどのようにいじる云々の問題ではなく、アルゴリズムの世界では何をどの場面でどのように活用するかが試されます（今回であれば、例えば配列をソートしてみたらどのような見やすさが生じるか、さらに配列のソートによって問題の答えにどう影響が出るか、そこからどのようにして多重ループを減らすか、など）。ただそうは言っても、最初はC問題レベルの内容だとそんなんわかるわけないと思われると思うので、まずは数多とある過去問に取り組んでください。初歩的なアルゴリズムの学習では、最低限のパターンと言うのはやはり高が知れているので、それらを網羅できるように思考法と知識を整理するように取り組んでください。少なくともこちらで質問されるのでしたら、そういった計算量を意識したコーディングを出来るようになってからが良いかと思われます（その頃には回答者視点でも答えやすい内容の質問になっていると考えられますので）。
|
1
訂正
answer
CHANGED
|
@@ -1,3 +1,3 @@
|
|
|
1
|
-
今回のNの制約は最大で3 * 10
|
|
1
|
+
今回のNの制約は最大で3 * 10 5です。テストケースの中にlen(lis)が本当にその長さのものがあったとき、ご提示のコードでは a = 0 で lis[0] <= b <= lis[N - 1], a = 1 でlis[1] <= b <= lis[N - 1], ...となりループによる計算の数だけで(N * (N + 1) // 2) 回 >> 10 8となり、これはTLEとなって当然でしょう。
|
|
2
2
|
|
|
3
3
|
対処法を、と言う話ですが、これがAtCoderはじめ競技プログラミングの本質です。上のような考え方は最初から競プロのどの世界でも「完全にダメな答案」の扱いであり、これをどのようにいじる云々の問題ではなく、アルゴリズムの世界では何をどの場面でどのように活用するかが試されます（今回であれば、例えば配列をソートしてみたらどのような見やすさが生じるか、さらに配列のソートによって問題の答えにどう影響が出るか、そこからどのようにして多重ループを減らすか、など）。ただそうは言っても、最初はC問題レベルの内容だとそんなんわかるわけないと思われると思うので、まずは数多とある過去問に取り組んでください。初歩的なアルゴリズムの学習では、最低限のパターンと言うのはやはり高が知れているので、それらを網羅できるように思考法と知識を整理するように取り組んでください。少なくともこちらで質問されるのでしたら、そういった計算量を意識したコーディングを出来るようになってからが良いかと思われます（その頃には回答者視点でも答えやすい内容の質問になっていると考えられますので）。
|