😽

【Python】paizaラーニングレベルアップ問題集「特殊な探索」【線形探索】後編

2023/07/25に公開

Python

こちらの続きです。

今回はコード全体を掲載します。

ローカルでコーディングし、標準入出力は使いません。テストケースは外部テキストファイルで準備しておき、プログラムから読み込みます。ジャッジ提出ではimportからファイル読み込み部までを削除する他、f.readline()をinput()に置き換えます。

点と点の距離

名前と点数をメンバ変数とした構造体…を模したクラスPointを作成します。

manhattan()は、自身ともう一つのPointオブジェクトとのマンハッタン距離（定義は問題文中にあります）を求めるメソッドです。

デバッグ用に点座標を返すgetPoint()メソッドも作ってありますが、もちろん解答には使わないので、提出時に消しても構いません。

点nと点nのマンハッタン距離は0であり、k以下であることは比較せずとも自明のため、カウント用変数cntの初期値を1にして計算ループからはずしました。

# -*- coding: utf-8 -*-

import os

testfile = "test1.txt"
f = open(os.path.dirname(__file__) + "/" + testfile, "r")


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    # getPoint() is for debug
    def getPoint(self):
        return (self.x, self.y)

    def manhattan(self, other):
        return abs(self.x - other.x) + abs(self.y - other.y)


n = int(f.readline())
points = []
for _ in range(n):
    a, b = map(int, f.readline().split())
    p = Point(a, b)
    points.append(p)

# print(points[-1].getPoint())  # for debug

k = int(f.readline())

cnt = 1    # 点n自身をカウントしておく
for i in range(n - 1):
    d = points[i].manhattan(points[-1])
    # print(points[i].getPoint(), d, d<=k)  # for debug
    if d <= k:
        cnt += 1

print(cnt)

長方形に含まれる点

点データのクラスPointと、長方形クラスRectangleを用意します。

Rectangleクラスのinvolves()メソッドでは、戻り値の初期値をTrueにしておき、上下左右のいずれかが範囲外であれば即座にFalseを返すようにしました。

# -*- coding: utf-8 -*-

import os

testfile = "test1.txt"
f = open(os.path.dirname(__file__) + "/" + testfile, "r")


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


class Rectangle:
    def __init__(self, top, bottom, left, right):
        """
        上端Y座標top、下端Y座標bottom、左端X座標left、右端X座標rightから
        長方形を作成する。
        """
        self.top = top
        self.bottom = bottom
        self.left = left
        self.right = right

    def involves(self, p: Point):
        """
        点p（Point型オブジェクト）が長方形の内部または辺上にあるかどうかを返す。
        """
        flag = True
        if p.x < self.left or p.x > self.right:
            flag = False
        if p.y < self.bottom or p.y > self.top:
            flag = False
        return flag


n = int(f.readline())
points = []
for _ in range(n):
    a, b = map(int, f.readline().split())
    p = Point(a, b)
    points.append(p)

xs, xt = map(int, f.readline().split())
ys, yt = map(int, f.readline().split())
rect = Rectangle(yt, ys, xs, xt)

cnt = 0
for point in points:
    if rect.involves(point):
        cnt += 1

print(cnt)

成績優秀者の列挙1

名前を格納するnameと、点数を格納するscoreをメンバ変数としたSeisekiboクラスを使って解きます。

# -*- coding: utf-8 -*-

import os

testfile = "test1.txt"
f = open(os.path.dirname(__file__) + "/" + testfile, "r")


class Seisekibo:
    def __init__(self, name, score):
        self.name = name
        self.score = score


n = int(f.readline())

seiseki = []

for _ in range(n):
    name, score = f.readline().split()
    score = int(score)
    seiseki.append(Seisekibo(name, score))

border = int(f.readline())

for data in seiseki:
    if data.score >= border:
        print(data.name)

FINAL:成績優秀者の列挙2

合格ボーダーに上限と下限があるという点以外は、前の問題とコードは同じです。

（略）

border_low, border_high = map(int, f.readline().split())

for data in seiseki:
    if data.score >= border_low and data.score <= border_high:
        print(data.name)

点と点の距離

長方形に含まれる点

成績優秀者の列挙1

FINAL:成績優秀者の列挙2

Discussion