《アルゴリズムを学ぶ》2.配列

Overview

データアクセスや基本的なループ処理をまとめました。
1.配列（リスト）の基本
2.配列のループ処理
3.配列の基本操作
4.配列の便利な処理
5.典型問題を解いてみる

1. 配列（リスト）の基本

Pythonでは「配列」は list で扱う。

参考：《アルゴリズムを学ぶ》1.リスト

2. 配列のループ処理

forループでの走査

arr = [10, 20, 30, 40, 50]
for num in arr:
    print(num) # ループ内での操作を記述

インデックス付きのループ（enumerate の利用）

arr = [10, 20, 30, 40, 50]
for i, num in enumerate(arr):
    print(f"Index {i}: Value {num}")

出力

Index 0: Value 10
Index 1: Value 20
Index 2: Value 30
Index 3: Value 40
Index 4: Value 50

whileループでの走査

i = 0
while i < len(arr):
    print(arr[i])
    i += 1

3. 配列の基本操作

要素の追加

arr.append(60)   # 末尾に追加
arr.insert(2, 25) # 2番目の位置に25を挿入

要素の削除

arr.pop()        # 末尾の要素を削除
arr.pop(2)       # 2番目の要素を削除
arr.remove(30)   # 値が30の要素を削除

4. 配列の便利な処理

リスト内包表記

リストを作成する際に for を使う代わりに簡潔に書くことがでる。

squares = [x**2 for x in range(10)]  # [0, 1, 4, ..., 81]
evens = [x for x in arr if x % 2 == 0]  # 偶数のみ取得

5. 典型問題を解いてみる

例題1: 特定の要素の出力

問題：N 個の整数配列 A が与えられ、X 以下の要素を全て出力せよ。

参考：ABC342B - Filter

回答　

N, X = map(int, input().split())
A = list(map(int, input().split()))

for num in A:
    if num <= X:
        print(num, end=" ")

例題2: 逆順の出力

問題: N 個の整数配列 A が与えられ、それを逆順に出力せよ。

参考：ABC339C - Reverse Array

回答　

N = int(input())
A = list(map(int, input().split()))

print(*A[::-1])

例題3: 特定の要素のカウント

問題: N 個の文字列が与えられ、その中から特定の条件を満たす文字列の数を数えよ。

参考：ABC287B - Qualification Contest

回答　

N = int(input())
S = [input() for _ in range(N)]

count = sum(1 for s in S if s.startswith("ABC"))
print(count)

例題4. 配列の動的更新

問題: N 段の階段を 1 段または 2 段ずつ上る方法の数を求めよ（1,000,000,007で割った余りを出力）。

参考：ABC129 C - Typical Stairs

回答　

N, M = map(int, input().split())
broken = set(int(input()) for _ in range(M))

MOD = 10**9+7
dp = [0] * (N+1)
dp[0] = 1

for i in range(1, N+1):
    if i in broken:
        continue
    dp[i] = dp[i-1] + (dp[i-2] if i > 1 else 0)
    dp[i] %= MOD

print(dp[N])

例題5. リスト内包表記を用いた文字列のフィルタリング

問題: 文字列 S が与えられ、連続する母音があるかどうかを判定せよ。

参考：ABC344 A - Strings with Consecutive Vowels

回答　

S = input()
vowels = {"a", "e", "i", "o", "u"}

# 連続する母音があるかをチェック
has_consecutive_vowel = any(S[i] in vowels and S[i+1] in vowels for i in range(len(S)-1))

print("Yes" if has_consecutive_vowel else "No")

6. リスト操作に関する詳細な解説