B - Hit and Blow Editorial by Nyaan
この問題は for 文の練習問題です。for 文の使い方に慣れておらずこの問題を解けなかった方は、この問題の解法を理解して for 文をうまく使えるようになりましょう。
問題文で求められているものは次の \(2\) つでした。
- \(A_i = B_i\) を満たす整数 \(i\) の個数。
- \(A_i = B_j, i \neq j\) を満たす整数の組 \((i, j)\) の個数。
このうち 1. は次のような for 文によって計算できます。計算量は \(N\) 回の for-loop が回るので \(\mathrm{O}(N)\) です。
for i in range(N):
if A[i] == B[i]:
answer1 += 1
次に 2. ですが、こちらは \(i,j\) を添え字とした 2 重の for-loop によって計算することができます。
for i in range(N):
for j in range(N):
if A[i] == B[j] and i != j:
answer2 += 1
このように for を 2 重にするのがポイントです。
計算量を考えます。外側のループが \(N\) 回で、内側のループも \(N\) 回回るので、最も内側の if 文は \(N^2\) 回評価されます。よって計算量は \(\mathrm{O}(N^2)\) となります。
この問題は \(N \leq 1000\) なので、 \(\mathrm{O}(N^2)\) ならばAC するのに十分高速に動作します。(一般に \(\mathrm{O}\) の中身が \(10^7\) 以下ならば十分余裕を持って AC できると言われています。) よってこの問題を解くことができました。
以下に Python での実装例を貼ります。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
answer1 = 0
answer2 = 0
for i in range(N):
if A[i] == B[i]:
answer1 += 1
for i in range(N):
for j in range(N):
if A[i] == B[j] and i != j:
answer2 += 1
print(answer1, answer2, sep="\n")
また、より高速な解法として、連想配列を利用した \(\mathrm{O}(N)\) での解法もあります。解法を簡潔に説明すると、 B の要素を連想配列で記録して「 \(x\) が \(B\) のどの位置に含まれているか?」を 計算量 \(\mathrm{O}(1)\) で取得できるようにすることで、先ほどの 2 重ループを 1 重で済ませる、という解法です。
C 問題以降の正解を目指す方はこちらの解法も思いつけるようになるとよいでしょう。
以下に Python での \(\mathrm{O}(N)\) 解法の実装例を貼ります。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
answer1 = 0
answer2 = 0
B_dict = dict()
for i, b_i in enumerate(B):
B_dict[b_i] = i
for i in range(N):
if A[i] == B[i]:
answer1 += 1
for i in range(N):
if A[i] in B_dict:
if B_dict[A[i]] != i:
answer2 += 1
print(answer1, answer2, sep="\n")
posted:
last update: