【paiza問題集解説】線形探索メニュー

【指定された値の探索】指定された値の位置 3

STEP: 1 指定された値の個数

指定された値の個数

n = int(input())
a = list(map(int, input().split()))
k = int(input())

cnt = 0
for a_i in a:
    if a_i == k:
        cnt += 1

print(k)

メソッドを使わずに値の出現回数をカウントします。ここは「線形探索メニュー」ですから～。線形探索はたいてい「 + 」がセットとなります。ここではこの組み合わせでプログラム例を書いていきます。
メニューを終えたら、今度はそのプログラムを関数やメソッドを駆使した簡潔な方法に書き換えてみましょう。これでもかというくらいまでにね。

ただ数えるだけなら.count() メソッドでいいですが、なにかを処理した後にカウントを増やしたり減らしたりする場合にこの書き方をします。カウント処理の基本形です。

STEP: 2 指定された値の位置 1

指定された値の位置 1

n = int(input())
a = list(map(int, input().split()))
k = int(input())

for i in range(n):
    if a[i] == k:
        print(i+1)
        break
else:
    print(0)

最初に見つけた所で break します。目的の値が見つからずにそのままループを抜けると 0 を出力します。

STEP: 3 指定された値の位置 2

指定された値の位置 2

n = int(input())
a = list(map(int, input().split()))
k = int(input())

idx = -1
for i in range(n):
    if a[i] == k:
        idx = i

if idx >= 0:
    print(idx+1)
else:
    print(0)

今度は break しないで最後まで探索します。すると idx は『最後に現れる k』の位置になっています。

idx の初期値が -1 なので、idx が 0 以上の時はどこかしら k が見つかっている状態ですので、その位置+1 を画面に出力します。idx が -1 のままなら 0 を出力します。

FINAL問題【指定された値の探索】指定された値の位置 3

【指定された値の探索】指定された値の位置 3

n = int(input())
a = list(map(int, input().split()))
k = int(input())

for i in range(n):
    if a[i] == k:
        print(i+1)

見つかった位置をすべて出力するだけですので、これが一番ラクですね。😸

【最大最小】n 変数の最大最小

STEP: 1 2変数の最大最小

2変数の最大最小

a_1, a_2 = map(int, input().split())

if a_1 >= a_2:
    print(a_1, a_2)
else:
    print(a_2, a_1)

以降で明らかに max() と min() を使わせようとしていますが、そうは問屋が卸しません。関数を使わずに比較式を使いましょう。

STEP: 2 10変数の最大最小

10変数の最大最小

a = list(map(int, input().split()))

max_ = -float('inf')
min_ = float('inf')
for a_i in a:
    if a_i > max_:
        max_ = a_i
    if a_i < min_:
        min_ = a_i

print(max_, min_)

線形探索メニューなのに、関数に線形探索をやらせてどうすんだと思える問題です。

自力で線形探索をして最大値と最小値を見つけていきます。

FINAL問題【最大最小】n 変数の最大最小

【最大最小】n 変数の最大最小

_ = input()
a = list(map(int, input().split()))

max_ = -float('inf')
min_ = float('inf')
for a_i in a:
    if a_i > max_:
        max_ = a_i
    if a_i < min_:
        min_ = a_i

print(max_, min_)

入力値 n が増えただけで以降は変化ありません。n すら使わないし。
n を使うならのところを range(n) にした書き方にするとよいです。

他人のプログラムを改造しまくるのもまた学習においてとても有効な手段です。

【特殊な探索】成績優秀者の列挙 2

STEP: 1 偶数の探索

偶数の探索

例１

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    if a[i] % 2 == 0:
        print(i+1)
        break

例２

n = int(input())
a = list(map(int, input().split()))

for i, a_i in enumerate(a, start=1):
    if a_i % 2 == 0:
        print(i)
        break

これまでの問題の k が偶数になっただけですね。

STEP: 2 奇数の探索

奇数の探索

n = int(input())
a = list(map(int, input().split()))

idx = 0
for i in range(n):
    if a[i] % 2 == 1:
        idx = i

print(idx+1)

例２

n = int(input())
a = list(map(int, input().split()))

for i, a_i in enumerate(a, start=1):
    if a_i % 2 == 1:
        print(i)
        break

偶数が奇数になっただけですね。😉

STEP: 3 条件付き最小値

条件付き最小値

例１

n = int(input())
a = list(map(int, input().split()))
k = int(input())

min_ = float('inf')
for a_i in a:
    if a_i >= k:
        if a_i < min_:
            min_ = a_i

print(min_)

例２

n = int(input())
a = list(map(int, input().split()))
k = int(input())

min_ = float('inf')
for a_i in a:
    if a_i >= k and a_i < min_:
        min_ = a_i
    
print(min_)

文が２つ続いた時にはだいたい and で繋げて一文で書くことができます。

不等号の向きにだけ注意すれば、あとは問題文のとおりに書くだけです。

STEP: 4 条件付き最大値

条件付き最大値

例１

n = int(input())
a = list(map(int, input().split()))
k = int(input())

max_ = -float('inf')
for a_i in a:
    if a_i <= k:
        if a_i > max_:
            max_ = a_i

print(max_)

例２

n = int(input())
a = list(map(int, input().split()))
k = int(input())

max_ = -float('inf')
for a_i in a:
    if a_i <= k and if a_i > max_:
        max_ = a_i

print(max_)

STEP: 5 点と点の距離

点と点の距離

n = int(input())
locs = [list(map(int, input().split())) for _ in range(n)]
k = int(input())

cnt = 0
x_i, y_i = locs[-1]
for x_j, y_j in locs:
    mhtn_dist = abs(x_i - x_j) + abs(y_i - y_j)
    if mhtn_dist <= k:
        cnt += 1

print(cnt)

比較する基点となる座標は、座標リストの一番最後 locs[-1] です。これを x_i y_i に振り分けて後に使います。
マンハッタン距離が k 以下の時にカウントアップします。

STEP: 6 長方形に含まれる点

長方形に含まれる点

n = int(input())
locs = [list(map(int, input().split())) for _ in range(n)]
xs, xt = map(int, input().split())
ys, yt = map(int, input().split())

cnt = 0
for x, y in locs:
    if (xs <= x <= xt) and (ys <= y <= yt):
        cnt += 1

print(cnt)

問題文と入力値を見て気が遠くなった一人です。(´ω`)ノ

平面図にしてみるとこうなります。
locs = [[-9, 5], [0, 4], [2, -6], [7, -4], [-3, -1]]
(xs, ys) = (-5, -5)
(xt, yt) = (5, 5)

	-9	-3	0	2	7
-6				2
-5
-4					3
-3
-2
-1		4
0
1
2
3
4			1
5	0

平面上の 0 ～ 4 は locs の要素番号に対応しています。そして locs の要素番号 0 から順に、その座標の点が長方形の内部に含まれているかを文で調べていきます。

cnt = 0
for x, y in locs:
    if (xs <= x <= xt) and (ys <= y <= yt):
        cnt += 1

locs = [[-9, 5], [0, 4], [2, -6], [7, -4], [-3, -1]]
(xs, ys) = (-5, -5)
(xt, yt) = (5, 5)

【要素番号 0】
x: -5 <= -9 <= 5 → False

【要素番号 1】
x: -5 <= 0 <= 5
y: -5 <= 4 <= 5 → True
cnt = 1

【要素番号 2】
x: -5 <= 2 <= 5
y: -5 <= -6 <= 5 → False

【要素番号 3】
x: -5 <= 7 <= 5 → False

【要素番号 4】
x: -5 <= -3 <= 5
y: -5 <= -1 <= 5 → True
cnt = 2 ← 結果

となります。

STEP: 7 成績優秀者の列挙 1

成績優秀者の列挙 1

n = int(input())
points = {s: int(t) for _ in range(n) for s, t in [input().split()]}
k = int(input())

for s, t in points.items():
    if t >= k:
        print(s)

辞書での線形探索です。リストでもできますが、ここは辞書を使います。

二行目の入力方法については「３章標準入力」を参照してください。

.items() メソッドについては「２章辞書を使いこなす機能一覧」で学習できます。

FINAL問題【特殊な探索】成績優秀者の列挙 2

【特殊な探索】成績優秀者の列挙 2

n = int(input())
points = {s: int(t) for _ in range(n) for s, t in [input().split()]}
k, l = map(int, input().split())

for s, t in points.items():
    if k <= t <= l:
        print(s)

条件式が変わっただけで他は同じです。

【第 k 要素の探索】k番目に大きな値

STEP: 1 2番目に大きな値

2番目に大きな値

_ = input()
a = list(map(int, input().split()))

ranks = [-float('inf')] * 3
for a_i in a:
    for j in range(2):
        if a_i > ranks[j]:
            ranks[j], ranks[j+1] = a_i, ranks[j]
            break

print(ranks[1])

セットやソートを使えば簡単なのですが、ここは「線形探索メニュー」ってことで、きちんと線形探索して解決していきます。

ranks というのは、最大値から 2 番目まで大きな数を記録しておくリストです。
3 番目はダミーです。(後述)

次に初めので数列を先頭から見ていきます。
その次ので、a_i と ranks の最大値から順に(2 番目まで)比較し、文で値の更新が発生した時に、

その順位の値を一つ下の順位に写す
その順位の値を a_i に書き換える

ことをします。言葉だけではわかりにくいですね。😓

a = [-9, 10, 6, 0, -3] の時

ranks = [-∞, -∞, -∞]

リストa

-9

-3

↓

ranks = [-9, -∞, -∞]

リストa

-9

-3

最大値の -∞ を 2 番目に移し、-9 を最大値に記録
↓
ranks = [10, -9, -∞]

リストa

-9

-3

-9 を 2 番目に移し、10 を最大値に記録
↓
ranks = [10, 6, -9]

リストa

-9

-3

最大値は変更なし
-9 を 3 番目に移し、6 を 2 番目に記録
↓
ranks = [10, 6, -9]

リストa

-9

-3

0 は最大値と 2 番目よりも小さいので何もしない
↓
ranks = [10, 6, -9]

リストa

-9

-3

-3 は最大値と 2 番目よりも小さいので何もしない

以上で、最後に ranks[1] を画面に出力して完了となります。

ダミーは ranks[j+1] で out of range エラーにならないようにするためだけに存在していますので、どのような数値であっても関係ありません。

FINAL問題【第 k 要素の探索】k番目に大きな値

【第 k 要素の探索】k番目に大きな値

_ = input()
a = list(map(int, input().split()))
k = int(input())

ranks = [-float('inf')] * (k+1)
for a_i in a:
    for j in range(k):
        if a_i > ranks[j]:
            ranks[j], ranks[j+1] = a_i, ranks[j]
            break

print(ranks[k-1])

2 番目が k 番目になっただけで、それ以外に変わりはありません。

線形探索は、わざわざ意識して学ばなくとも、線形探索が使われたプログラムを読んだり書いたりしていくうちに当たり前のようにできるようになるものです。
「線形探索メニュー、難しかったなぁ」と感じていても、そのうちいつの間にか当たり前にできるようになっています。

線形探索メニューは学習というよりは「力試し」として、今回問題を解くのに苦労した方は、また数か月後にでも再挑戦してどのくらいプログラミングスキルが上がったかを試してみてください。一度やったことがある問題をもう一度やることもスキルアップには有効です。一からプログラムを学ぶより、既製のプログラムを自分で打ち込んで写して動かし、さらに改造しまくってエラーを出しまくりながら動かしてみるほうが理解が早いです。爆速で上達します。その為にも他人のプログラムをたくさん読むことが大切です。英語学習の多読と同じです。多読どころか、全てが英語の学習方法と通じています。(英語わからないけどね、私)