paizaラーニング線形探索メニュー「点と点の距離」について

スポンサーリンク

paizaラーニングの問題集に追加された線形探索メニューは比較的易しい問題が多いのだが、「【特殊な探索】 成績優秀者の列挙 2」の「STEP: 5 点と点の距離」だけは正解率が低い。もしかしたら誰かの役に立つかもしれないので簡単に補足を書いておく。まず問題文の引用から。

整数 n と、二次元平面上の点 1 ~ n の座標 (x_1, y_1), … , (x_n, y_n), 整数 k が与えられます。

n 個の点 (点 n 含む) のうち、点 n とのマンハッタン距離が k 以下であるような点の数を求めてください。

なお、この問題において、2点間のマンハッタン距離とは、2点の各座標の差の絶対値の総和を指します。つまり、点 (x_i, y_i) と点 (x_j, y_j) のマンハッタン距離は、| x_i - x_j | + | y_i - y_j | です。

線形探索メニュー 点と点の距離 

サンプルの入力値と出力値は以下の通り。

入力例1
5
-9 5
0 4
2 -6
7 -4
-3 -1
10

出力例1
3

私自身が問題文に少し戸惑ったのだが、点 nというのは入力例1における「-3 -1」のことである。他の入力例でもx_n y_nを点nとして、そこからのマンハッタン距離を測るコードを書けば良い。例えば、点nと-9 5のマンハッタン距離は|-3 – -9| + |-1 – 5| = 12になる。なお点n自身も含めた数を出力する点に注意。点nと点nの距離は0なので、出力値は必ず1以上になる。

私が書いたPython3のサンプルコードは以下の通り。あくまで初心者のコードなのでご参考まで。

def function1(n1, a1, k1):
    counter = 0
    x_n, y_n = a1[n1-1][0], a1[n1-1][1]
    for i in range(n1):
        x0, y0 = a1[i][0], a1[i][1]
        x_abs = abs(x0 - x_n)
        y_abs = abs(y0 - y_n)
        tmp = x_abs + y_abs
        if tmp <= k1:
            counter += 1

    print(counter)


n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
k = int(input())
function1(n, a, k)

コメント

当ブログのコンテンツが気に入ったら広告ブロックの解除(ホワイトリスト化)をご検討下さい。

Please disable your adblocker or whitelist this site!

タイトルとURLをコピーしました