Javaの実行時間制限超過の改善策

Question

前提・実現したいこと

AtCoderの問題で解答はあっているのですが実行時間が超過してしまいます。
2秒以下に抑えたいです。アドバイスお願い致します。

AtCoderの問題
https://atcoder.jp/contests/abc142/tasks/abc142_c

発生している問題・エラーメッセージ

実行時間制限超過

該当のソースコード

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int A[] = new int[N+1];
		int B[] = new int[N+1];
		int C[] = new int[N+1];
		for (int i = 1;i <= N;i++) {
			A[i] = scanner.nextInt();
		}
		for (int i = 1;i <= N;i++ ) {
			for (int j = 1;j <= N;j++) {
				if (i == A[j]) {
					B[i] = A[j];
					C[i] = j;
				}
			}
			System.out.print(C[i] + " ");
		}
	}
}

試したこと

for文が入れ子になっているのが怪しいと思ったのですが、改善策がわかりませんでした。

補足情報（FW/ツールのバージョンなど）

jdk-8u201-windows-x64

Comments

[y_waiwai]

なにをするコードなのでしょうか。

[junpeihamasaki]

AtCoderのC問題です。以下のリンクをご参照ください。
https://atcoder.jp/contests/abc142/tasks/abc142_c
コードを提出した時にコードテストをされるのですが、実行時間超過となってしまいます。
コードはあっていると思います。

Answer 1

AtCoderの制限時間をクリアするには 10**7 程度の計算量におさえないといけません。

Nは最大 10**5 まであり得るので二重forを実施すると 10**10 となり間に合いません。

C問題以降はforを2重( O(n**2) )以上行った時点で詰むと考えて下さい。

正解は公式から解答が公開されているので読んで下さい。

また他の参加者のJavaによるAC回答が参考になるのではないでしょうか。

https://atcoder.jp/contests/abc142/submissions?f.Task=abc142_c&f.Language=3016&f.Status=AC&f.User=

Comments

[junpeihamasaki]

詳しい御回答ありがとうございます。
AtCoderの仕様について理解出来ました。

[swordone]

Oの使い方間違ってる

[退会済みユーザー]

指摘ありがとうございます。
差し支えなければより詳しく教えて頂けないでしょうか。

[swordone]

Oの括弧内に1以外の数値が入ることはまずありません。O(n)やO(log n)のように、nの式が入ります。

[退会済みユーザー]

確かに私のような書き方は見たことがないですね。
ありがとうございます。

[swordone]

この記号の定義上、O(1)もO(10**10)も定数になりますし…

Answer 2

公式解答は見ていませんが, 配列は1つでループも入力と出力の別々の2つだけで済むように思います.
配列の"添え字"と"値"の対応の組み合わせかたの工夫でしょうか.