リアルイベント問題セット | paizaラーニング Python解答例

paizaでPythonを学ぼう
スポンサーリンク

はじめに

この記事ではpaizaラーニングのレベルアップ問題集にあるリアルイベント問題セットのPython解答例を掲載する。解答例へのリンク一覧はpaizaでPythonを学ぼうに掲載。

この問題セットはどれも難しいので、初心者のうちは分からなくても気にしないで大丈夫。

ハノイの塔(Aランク)

ハノイの塔は再帰関数を使う問題としてプログラミングの世界では有名らしい。最終結果だけ出力すればいい単純なハノイの塔問題とは少し違って、この問題は途中経過(回数t)を出力するというのがポイント。

筆者は最初全く分からなかった。「paiza ハノイの塔」で検索すると吉岡氏のスライドが出てくるので読み解いてみたが、サンプルコードがPythonでは無いので良く分からない。必死に考えて出来たのが下のコード。コメントアウトしてあるprintを出力すれば途中経過が逐一出力される。

def show():
    for i in (a, c, b):
        if len(i) == 0:
            print('-')
        else:
            output = map(str, i)
            print(' '.join(output))
    return


def move_one(disc, frm, to):
    global counter
    counter += 1
    # print('this move is t = ' + str(counter))
    # print('move_disc ' + str(disc) + ' from ' + str(frm) + 'to' + str(to))
    disc_to_move = frm.pop(-1)
    to.append(disc_to_move)
    if counter == m:
        show()
        return


def hanoi(disc, frm, to, stay):
    if disc == 0:
        return
    hanoi(disc - 1, frm, stay, to)
    move_one(disc, frm, to)
    hanoi(disc - 1, stay, to, frm)


n, m = map(int, input().split())
counter = 0
a = [int(_) for _ in range(n, 0, -1)]
b, c = [], []

hanoi(n, a, b, c)

山折り谷折り (Aランク)

アルゴリズム自体は難しくないが、問題が何を求めているのか把握するのが鍵となる。パターンの癖を発見できるかどうかの問題なので、プログラミングの問題というよりも算数的パズルとしての性格が強い。そのため、そういう方面に興味がない人はさっさと答えを見てしまって構わないと思う。

paizaの公式ブログに詳しい解説が載っている。下のコードはそれを少し改変してwhile文にしたもの。

n = int(input())
orime = '0'
counter = 1
while True:
    if counter == n:
        print(orime)
        break

    lst1 = list(orime)

    for i in range(len(lst1)):
        if lst1[i] == '0':
            lst1[i] = '1'
        else:
            lst1[i] = '0'

    orime_tmp = ''.join(lst1)
    orime_tmp_rev = orime_tmp[::-1]
    orime += '0' + orime_tmp_rev
    counter += 1

本の整理 (Aランク)

バケットソート(bucket sort)の問題。paizaのブログに解説が載っている。バケットソートは動画で処理過程を見ると感覚的に分かりやすいかもしれない。

n = int(input())
l1 = [int(_) - 1 for _ in input().split()]
l2 = [0] * n

for i in range(n):
    l2[l1[i]] = i

t = 0
for i in range(n):
    if l1[i] != i:
        t += 1
        tmp = l2[i]
        l2[i], l2[l1[i]] = l2[l1[i]], l2[i]
        l1[i], l1[tmp] = l1[tmp], l1[i]

print(t)

雪だるま作り (Aランク)

この問題はAランク問題の中ではかなり優しい問題という印象。Bランクぐらいの問題が解ければ、自力で解ける人も多いはず。

n, k = map(int, input().split())
l1 = [int(_) for _ in input().split()]
l1 = sorted(l1)
t1 = 0

while True:
    high = l1.pop(-1)
    while True:
        low = l1.pop(0)
        if high + low >= k:
            t1 += 1
            break
        else:
            if len(l1) < 1:
                break

    if len(l1) < 2:
        break

print(t1)

最小の運賃 (Aランク)

ダイクストラ法を使って解答した。classを使うので少し難しいかもしれない。個人的にはこの問題セットの中で一番の難問だと思う。初見で考えても分からない場合、別途扱うダイクストラ法の問題集で考え方を覚えてから再挑戦すれば良い。初心者のうちに分からない問題で考えすぎても時間の無駄なので、後回しにするのも大事。

import heapq


class State:
    def __init__(self, node, cost):
        self.node = node
        self.cost = cost

    def __lt__(self, state):
        return self.cost < state.cost


def dijkstra():
    total_costs = [float('inf') for _ in range(v)]
    open_que = []
    closed_que = set()
    state = State(s, 0)  # node,cost
    heapq.heappush(open_que, state)

    while len(open_que) > 0:
        state = heapq.heappop(open_que)
        if state in closed_que:
            continue
        closed_que.add(state)

        for i in range(v):
            if g[i][state.node] == 'NA':
                continue
            next_cost = state.cost + g[state.node][i]
            if total_costs[i] <= next_cost:
                continue
            total_costs[i] = next_cost
            heapq.heappush(open_que, State(i, next_cost))

    return total_costs[t]


s = 0
e, v, t = map(int, input().split())
g = [["NA"] * v for _ in range(v)]

for _ in range(e):
    tmp1, tmp2, tmp3 = map(int, input().split())
    g[tmp1][tmp2] = tmp3
    g[tmp2][tmp1] = tmp3

answer = dijkstra()
print(answer)

文字列収集 (Sランク)

この問題の解説はpaizaの公式ブログに載っている。解き方は2通りあるが、解説で2番目に紹介された方針を採用しているためコードも殆ど同じ。方針さえ理解できれば、コード化するのはさほど難しくないと思う。

n, m = map(int, input().split())
d1 = {}

for i in range(n):
    s, p = input().split()
    for j in range(len(s)):
        subs = s[0:j + 1]
        if subs in d1:
            d1[subs] += int(p)
        else:
            d1[subs] = int(p)
for k in range(m):
    q = input()
    if q in d1:
        print(d1[q])
    else:
        print(0)

十億連勝 (Sランク)

公式の解説に方針が載っているのでそれを参考にした。実装例のC++は全く分からないので、自分でコードを書くのに少し苦労した。ネット上で検索しても誰も解答例を出していないので解けた時は嬉しかった。

基本的には公式解説に載っている方針通りだが、場合分けを頭の中でイメージするのが大変かもしれない。条件式を上手く使うことができれば解答にたどり着く。「最小の運賃」よりも楽だと思う。deepcopyとcopyの違いは理解しておいた方が良い。

from copy import deepcopy

n, x = map(int, input().split())
list1 = [int(input()) for _ in range(n)]

dict0 = {}
for i in range(x + 1):
    dict0[(i, False)] = 0
    dict0[(i, True)] = 0
dict1 = deepcopy(dict0)
dict1[0, False] = 1

counter = 1
for i in list1:
    counter += 1
    dict2 = deepcopy(dict1)
    dict1 = deepcopy(dict0)
    for j in dict2:
        if j[0] + i <= x:
            dict1[(j[0] + i, j[1])] += dict2[(j[0], j[1])]
            dict1[(0, j[1])] += dict2[(j[0], j[1])] * i
        elif j[0] + i > x:
            dict1[(0, True)] += dict2[(j[0], j[1])]
            dict1[(0, j[1])] += dict2[(j[0], j[1])] * (x - j[0])

ans = 0
for i, j in dict1.items():
    if i[0] == x:
        ans += dict1[i]
    elif i[1]:
        ans += dict1[i]

print(ans % 1000000000)

コメント

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

Please disable your adblocker or whitelist this site!

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