🔙
🔝

【paiza問題集 解説】
データセット選択メニュー

動的配列

動的配列

STEP: 1 ランダムアクセス

ランダムアクセス

    _, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(A[M-1])
    

    M番目というのは、1 から数えて M番目ということです。リストの要素番号は 0 から数える為、M から 1 を引かなければなりません。

    M番目 1 2 3 4 5
    要素番号 0 1 2 3 4
STEP: 2 複数回のランダムアクセス

複数回のランダムアクセス

    _ = input()
    A = list(map(int, input().split()))
    _ = input()
    B = list(map(int, input().split()))
    
    for i in B:
        print(A[i-1])
    

    B をイテラブルとしてにかけると B_i番目が順に得られるようになります。

    B_i番目というのは、1 から数えて i番目ということです。リストの要素番号は 0 から数える為、i から 1 を引かなければなりません。

    M番目 1 2 3 4 5
    要素番号 0 1 2 3 4
STEP: 3 最大値と最小値

最大値と最小値

  • 例1

  • A, B, C = map(int, input().split())
    print(max(A, B, C) - min(A, B, C))
    
  • 例2

  • nums = list(map(int, input().split()))
    print(max(nums) - min(nums))
    

    便利な関数を使います。

    max(データ)
    データの中から最大値を取得します。
    min(データ)
    データの中から最小値を取得します。

    (A, B, C の最大値) - (A, B, C の最小値) が、例1のプログラムで求められます。

    max(A, B, C) を max([A, B, C]) とリスト化しても同様の結果が得られます。(例2)

    単に最大値と最小値を求めて計算するだけなので、tuple() や set() を使ってもかまいません。

  • タプル

  • nums = tuple(map(int, input().split()))
    print(max(nums) - min(nums))
    
  • セット

  • nums = set(map(int, input().split()))
    print(max(nums) - min(nums))
    
FINAL問題 動的配列

動的配列

    _, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    for _ in range(Q):
        query = list(map(int, input().split()))
    
        if query[0] == 0:
            A.append(query[1])
        elif query[0] == 1:
            A.pop()
        else:
            print(*A)
    

    query = list(map(int, input().split())) の所で、要素数が不規則(動的配列)でも、とりあえずまるごとリスト化して変数(query)に収めます。

    query[0] 0 (push_back)
    1 (pop_back)
    2 (print)
    の、いずれかの数値が入っている
    query[1] push_back の時だけ、x が入っている
    query[0] が 0 の時
    リストA の末尾に値を追加する .append()メソッドを使います。
    ここで query[1] の値 x を、リストA の末尾に追加します。
    query[0] が 1 の時
    リストA の末尾の要素を削除する為に、リストの末尾の要素を取り出す .pop()メソッドを使います。del A[-1] でも末尾の要素を削除できます。
    query[0] が 2 の時
    リストA のリストをアンパック(展開)して画面に出力します。

    例)A = [1, 2, 3, 10, 12] の時
    print(*A)
    
    print(*[1, 2, 3, 10, 12])
    
    print(1, 2, 3, 10, 12)
    
    1 2 3 10 12

    以上を与えられた操作回数(Q)分をで繰り返します。

文字列の配列

文字列の配列

STEP: 1 とても大きな数値の入力

とても大きな数値の入力

    N = input()
    print(N)
    

    「とても大きな数値 N が与えられます。」と言いつつ、print()の出力は文字列となるので、標準入力を文字列で受け取り、そのまま文字列で出力すればOKのようです。

    Python3 で数を扱う場合、実質 -∞ 〜 ∞ の範囲で扱えるため、int(input()) としても問題ありませんが、print() で文字列に変換されて出力されるので無駄となってしまいます。

STEP: 2 とても小さな数値の入力

とても小さな数値の入力

    N = input()
    print(N)
    

    「とても小さな数値 N が与えられます。」と言いつつ、print()の出力は文字列となるので、標準入力を文字列で受け取り、そのまま文字列で出力すればOKのようです。


    整数の場合は扱える値に上限下限はありませんが、小数の場合は注意がいります。

    浮動小数は、扱える桁数に限りがあります。

    N = 1.234567890123456789
    print(N)
    
    1.2345678901234567

    print(10 / 3)
    
    3.3333333333333335

    最後の 5 ってなんだよ...。😂

    コンピュータは小数の扱いが苦手なので気をつけてくださいね。

FINAL問題 文字列の配列

文字列の配列

  • 例1

  • H, _, r, c = map(int, input().split())
    S = [input() for _ in range(H)]
    
    if S[r-1][c-1] == '#':
        print('Yes')
    else:
        print('No')
    
  • 例2

  • H, _, r, c = map(int, input().split())
    S = [input() for _ in range(H)]
    
    print('Yes' if S[r-1][c-1] == '#' else 'No')
    

    問題文で説明されていないのですが、r は「Row (行)」、c は「Column (列)」のことで、(縦, 横)、つまり S[r][c] となります。

    これも直接問題文には書かれていないのですが、「条件」の所を見ると、r c 共に 1 以上とあります。リストの要素番号も文字列の位置番号も共に 0 から始まりますので、変数 rc のそれぞれから 1 を引きます。

    その位置が # なら 'Yes'、そうでないなら 'No' を出力するということになります。

商品の検索

商品の検索

STEP: 1 数値の出現率

数値の出現率

    _ = int(input())
    A = list(map(int, input().split()))
    
    nums = [0] * 10
    for i in A:
        nums[i] += 1
    
    print(*nums)
    

    0 以上 9 以下 ということは、要素番号 0 から始まるリストをそのまま使えます。
    出現した数を要素番号に紐付けて、要素の値を出現回数にするとシンプルなプログラムになります。

STEP: 2 英小文字の出現率

英小文字の出現率

  • リストを使う場合

  • _ = int(input())
    S = input()
    
    counts = [0] * 26
    for s in S:
        counts[ord(s)-97] += 1
    
    print(*counts)
    

  • 辞書を使う場合

  • _ = int(input())
    S = input()
    
    alphabets = {chr(i+97): 0 for i in range(26)}
    
    for s in S:
        alphabets[s] += 1
    
    print(*alphabets.values())
    

    辞書を使うほうが簡単ですが、まだ辞書が理解出来ていないという場合はリストでも同様の結果を得ることが出来ます。

    chr()関数は、unicodeを文字に変換するという機能です。

    unicode(10進数) 97 98 99 100 101 120 121 122
    unicode文字 a b c d e x y z

    変数 alphabets を初期化する際、で 0 〜 25 まで順にループさせて、i に文字 a のunicode 97 を足していくことで a 〜 z を作っています。順に作ったアルファベットは、順番を書き換えない限り維持されます。

    辞書を使った場合、文字をキーとしているので、出現した文字を添字にしてその値に 1 を足していきます。
    リストを使った場合、出現した文字をchr()関数と反対のord()関数を使って文字を unicode に変換し、その値から 97 を引くとそのまま該当する要素番号になります。
    また、97ord('a') にするとよりわかりやすくなります。

    code_a = ord('a')
    for s in S:
        counts[ord(s) - code_a] += 1
    

    最後にカウントしたリストをアンパックし、出力すれば完了です。辞書の場合は.values()で辞書の値のみがリストで返りますので、それをアンパックします。

    paiza の解答コード例はrange()に直接 ord('a') ord('z') を充てています。このほうが毎回 97 を足す計算をしなくて済みますので効率が良いです。その際 ord('z') に +1 しておかないと、a 〜 y までしか作られなくなってしまいますので気をつけてください。 理解出来たら paiza の解答コード例のほうをお薦めします。


    ord()chr()共に時々使いますので、覚えておくと便利です。

STEP: 3 文字列の出現率

文字列の出現率

  • if を使う場合

  • N = int(input())
    
    dic = {}
    for _ in range(N):
        S = input()
    
        if S in dic:
            dic[S] += 1
        else:
            dic[S] = 1
    
    for k, v in sorted(dic.items()):
        print(k, v)
    

    .get()メソッドを使う場合

    N = int(input())
    
    dic = {}
    for _ in range(N):
        S = input()
        dic[S] = dic.get(S, 0) + 1
    
    for k, v in sorted(dic.items()):
        print(k, v)
    

    辞書を使います。
    リストでも出来ることは出来ますが、面倒でわかりにくくなりますので、この際辞書を習得しておきましょう。
    前半の解説は「2章 辞書型」のリンク先で学べばわかりますので省略します。

    後半の sorted(dic.items()) は、dic.items() を引数にするとキーでソートされます。
    .items()を付けないと dic.keys() と同等になってしまい、値が存在しなくてエラーとなりますので気をつけてください。

    for k, v in sorted(dic)
        print(k, v)
    
    Traceback (most recent call last):
      File "Main.py", line 8, in 
        for k, v in sorted(dic):
    ValueError: not enough values to unpack (expected 2, got 1)
    
STEP: 4 価格の算出

価格の算出

    N, M = map(int, input().split())
    A = {k: int(v) for _ in range(N) for k, v in [input().split()]}
    
    for _ in range(M):
        S = input()
        print(A[S] if S in A else -1)
    

    受け取った商品名をキーとした辞書から価格となる値を取り出して、最後に画面に出力するという流れになります。

    内包表記で書かれた部分を重点的に解説します。
    for k, v in [input().split()] で入力したデータを値にする際、k:int(v)v だけ整数型に変換します。

    
        eraser 50
    
    A = {k: int(v) for k, v in [input().split()]}
    
    A = {k: int(v) for k, v in ['eraser 50'.split()]}
    
    A = {k: int(v) for k, v in [['eraser', '50']]}
    
    A = {k: int(v) for k='eraser', v='50' in [['eraser', '50']]}
    
    A = {'eraser': int('50') for k='eraser', v='50' in [['eraser', '50']]}
    
    A = {'eraser': 50 for k='eraser', v='50' in [['eraser', '50']]}
    
    A = {'eraser': 50}
    
    この方法を使って for _ in range(N) で N回繰り返すと、一気に辞書が完成します。
    [input().split()] の [] は必要です。これが無いと ['eraser', '50'] となって 'eraser''50' の順でループしてしまい、要素数が合わずにエラーとなってしまいます。
    この方法は「3章 標準入力」で学習できます。

    最後は「標準入力で受け取った商品名(S)が辞書にあればその商品の価格を、なければ -1 を画面に出力」します。これを買い物の数、M回繰り返します。

    内包表記は「2章 内包表記」で学習できます。

FINAL問題 商品の検索

商品の検索

  • 例1

  • N, Q = map(int, input().split())
    
    S = {}
    for j in range(N):
        s = input()
        if s not in S:
            S[s] = j + 1
    
    for _ in range(Q):
        t = input()
        if t in S:
            print(S[t])
        else:
            print(-1)
    
  • 例2

  • N, Q = map(int, input().split())
    
    S = {}
    for j in range(N):
        S.setdefault(input(), j+1)
    
    for _ in range(Q):
        print(S[t] if (t:=input()) in S else -1)
    
  • 例3

  • N, Q = map(int, input().split())
    
    S = [input() for _ in range(N)]
    
    for _ in range(Q):
        t = input()
        print(S.index(t)+1 if t in S else -1)
    

    例1は、paiza の解答コード例とほぼ同じです。解説はそちらを参照してください。

    例2は、便利ワザを使って例1を簡潔に書いたものです。
    .setdefault()メソッドは「2章 辞書を使いこなす機能一覧」で学習でき・・・るかな?😓
    (t:=input()) については「3章 補足」で学習できます。

    例3は文字列(S)をリストに集めてから、後でその中から最小の位置を調べる方法です。
    .index()メソッドを使うと引数と同じ値を見つけた時、その要素番号を返します。要素番号は 0 から始まるので、取得した要素番号に 1 を足します。
    見つからなかった時はそのままだとエラーになりますので、文で値を探して見つけてから.index()を使って要素番号を取得します。

    ただ、この方法は効率が悪いです。
    線形探索といって、先頭から順番に1つずつ値を照合しながら目的の値を探していく探索法なのですが、.index()メソッドも同じく線形探索です。文で線形探索して目的の値を見つけてから、.index()でもまた先頭から線形探索するのは無駄です。

    .index()で目的の値を見つけてその場で要素番号を取得できれば問題ないのですが、もし目的の値が見つからなかった場合はエラーになってしまいますので文を使わざるを得なく、もどかしいところです。


    ちなみに例1の様に、辞書型で if s not in S: で値を探すと、線形探索ではなく、目的の値をほぼ一発で探し当てます。こちらはハッシュ探索といいます。セット型も一発です。でもリストだと線形探索になります。
    おそらく.setdefault()も一発のはずです。

    この問題は辞書を使う方法が賢明のようです。辞書の習得がまだの方は頑張ってモノにしてください。😼

集合の結合

集合の結合

STEP: 1 集合の探索

集合の探索

    _, B = map(int, input().split())
    A = set(map(int, input().split()))
    
    print('Yes' if B in A else 'No')
    

    「集合の探索」なので、言葉通り集合(セット)を使います。と言っても、プログラムの一部がいつものlist()からset()に変わっただけです。

    ただし文の探索方法はハッシュ探索なので、リストの線形探索よりはるかに高速です。

STEP: 2 重複の削除

重複の削除

  • 例1

  • _ = input()
    A = set(map(int, input().split()))
    
    print(*sorted(A))
    
  • 例2

  • _ = input()
    A = map(int, input().split())   # list() は不要
    
    tmp = 0   # tmp = -float('inf') でも可
    a = []
    for i in A:
        if i != tmp:
            a.append(i)
            tmp = i
    
    print(*a)
    

    例1は簡単で見れば解ると思いますので、例2のセットもソートも使わずに解く方法を解説します。

    数列は昇順に並んでいることが保証されています。文で数列の先頭から順に調べていって、現在チェックしている数と tmp に入っている数が異なる場合、初めて登場する数となるので、これを リストa に追加します。
    その後、tmp の値を現在の値 i に更新してループします。

  • A = [1, 2, 3, 3, 4, 5] の時

  • i 1 2 3 3 4 5
    tmp 0 1 2 3 3 4
    リストa 1 2 3 4 5

    i != tmp の時、リストa に i が追加される。

    最後まで行くと リストa には昇順のまま重複の無い数列が出来上がっています。これをアンパックして画面に出力すれば完了です。

    簡潔に書くと次のようになります。

    _ = input()
    A = map(int, input().split())
    
    tmp = 0
    a = [tmp:=i for i in A if i != tmp]
    
    print(*a)
    

    tmp:=i については「3章 補足」で学習できます。

STEP: 3 重複の判定 1

重複の判定 1

  • 例1

  • N = int(input())
    A = list(map(int, input().split()))
    
    for i in range(1, N):
        print('Yes' if A[i] in A[:i] else 'No')
    
  • 例2

  • N = int(input())
    A = list(map(int, input().split()))
    
    memo = {A[0]}
    for i in range(1, N):
        if A[i] in memo:
            print('Yes')
        else:
            memo.add(A[i])
            print('No')
    

    例2は、paiza の解答コード例とほぼ同じにしてあります。

    問題文をわかりやすい文章にしてみます。

    『数列A の 二番目から順に見ていき、現在見ている位置の数がそれより前にある場合は Yes、無い場合は No を画面に出力してください。』

    例2では、一度処理して作り出したことがある値がメモした中にある場合は Yes、無い場合は No を画面に出力します。

    例1では if A[i] in A[:i] の部分をループする度に先頭から線形探索で調べています。何度も何度も同じ所を無駄に調べてしまっています。
    数を数える時に「いちっ!いちにっ!いちにっさんっ!」と1つ数える度に1からまた数え直していくようなものです。
    今回はリストの中を何度も線形探索する無駄を省くためにセットを使い、常にメモに値があるかチェックするだけで何度も先頭から調べることをしなくて済むようにします。もちろん例1のプログラムでも問題の解答としては正解です。

    A = [1, 2, 3, 2, 5, 3, 3, 10, 2] の場合

    数列A 1 2 3 2 5 3 3 10 2
    memo 1 2 3 5 10
    判定 N N Y N Y Y N Y

    数列の二番目から開始しますので、その時点では memo の中身は数列の先頭の 1 のみです。これを memo に初期値として入れておきます。memo = {A[0]}
    二番目の 2 はそれより前、つまり memo の中にありませんので、memo2 を追加して No を出力します。次の 3 も同様の処理です。
    四番目の 2 は memo の中にあります。なので Yes を画面に出力して次のループに移ります。

    常に memo の中に現在の数があるかないかをチェックするだけで Yes か No かを判定することができるようになります。探索もセットなのでハッシュ探索です。ちょっ早です。

    余力があれば paiza 問題集の解答例2も理解してみましょう。

STEP: 4 重複の判定 2

重複の判定 2

    N = int(input())
    A = list(map(int, input().split()))
    
    memo = {A[0]}
    for i in range(1, N):
        if A[i] in memo:
            print('Yes')
        else:
            memo.add(A[i])
            print('No')
    

    【STEP: 3 重複の判定 1】の例1も例2もそのまま使えますが、例1は効率が悪いです。例2(上記)を理解しましょう。

FINAL問題 集合の結合

集合の結合

  • 例1

  • _ = input()
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    set_union = set(A + B)
    print(*sorted(set_union))
    
  • 例2

  • _ = input()
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    set_union = A | B
    print(*sorted(set_union))
    

    例1は、リストとリストを連結してからセット型に変換して重複を削除しています。
    例2は標準入力をセット型にして受け取り、和集合演算で例1と同じ結果を得ています。

    集合演算については「2章 セットさんは重複を許さない」で学習できます。

    セット型は要素の順番が保証されていないので、最後にsorted()関数でソートする必要があります。