【paiza問題集 解説】
スタック・キューメニュー

N = int(input())
A = [int(input()) for _ in range(N)]
print(N, *A, sep='\n')

スタックやキューは、空の状態を含むリストの両端から値を出し入れするデータの操作法なのですが、これについては後の問題で説明されます。

ここでは要は、与えられたデータをその為に使うリストに入れるという前知識というか前準備というか……そんなのです。😓

Q = int(input())

len_A = 0
A = []
for _ in range(Q):
    query = map(int, input().split())
    if next(query) == 1:
        A.append(next(query))
        len_A += 1

print(len_A, *A, sep='\n')

PUSH とは、値をリストの末尾に入れる事で、スタックの専門用語です。Python3 では .append() メソッドを使って追加する事に当たります。

『最初の数値が 1 のとき PUSH 、 2 のとき STAY を表します。』とありますので、一応数値に変換して処理します。

受け取る指示は２種類だけですが、受け取る値の数が不揃いですので、値をイテレータとして受け取り、都度 next() 関数で呼び出して使っています。よくわからない場合は paiza の解答コード例のほうを参考にして進めていってください。

STAY の時は「何もしない」なので、else文を省略しましたが、

else:
    pass

を付けて何もしないことを明示してもよいでしょう。今後「何もしない」から何かすることとなった時の為にも変更場所が見つけやすくなります。

Q = int(input())

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

POPも PUSH 同様にスタックの専門用語です。Python3 でも .pop() メソッドを使います。

POP は削除するというより「値を取りだす」という意味になります。取り出した値を使わなければそのまま削除したことと同義となりますので、削除するときにも使われます。

今回は削除する目的で使いますので、単に A.pop() とだけ書きます。この .pop() メソッドはリストの末尾から要素を１つ取り出します。メソッド名そのままの機能です。

Q = int(input())

A = []
for _ in range(Q):
    query = iter(input().split())
    if int(next(query)) == 1:
        A.append(next(query))
    else:
        print(A.pop())
    
    print(*A)

今度は .pop() したものを画面に出力します。末尾から取り出した値を使って画面に出力するのです。画面に出力したら取り出した値はそのまま消滅します。

from collections import deque

Q = int(input())

A = deque()
for _ in range(Q):
    query = iter(input().split())
    if int(next(query)) == 1:
        A.append(next(query))
    else:
        A.popleft()
    
    print(*A)

「PUSH」「POP」とありますが、キューの場合はそれぞれ「ENQUEUE (エンキュー)」「DEQUEUE (デキュー)」と言います。双方向キューの deque とは読みが同じですが意味は異なります。

Python では ENQUEUE は .append() ですが、DEQUEUE は .popleft() になります。 .popleft() は collections モジュールの deque をインポートしないと使えませんので、プログラムの頭に from collections import deque を書き加えておきます。

キューは向きが特に決められていませんので、ENQUEUE に .appendleft() を使い、DEQUEUE に .pop() を使うこともできます。リストと同じデータ配列のほうがわかりやすいので前者を使うことがほとんどだと思いますが、左から入れて右から出す問題の時は逆向きでわかりにくくなったりもしますので、その時は後者を使うこともできます。

空のdequeは deque() で作れます。

from collections import deque

Q = int(input())

A = deque()
for _ in range(Q):
    query = iter(input().split())
    if int(next(query)) == 1:
        A.append(next(query))
    else:
        print(A.popleft())
    
    print(*A)

step 1 と同じ様に組み、違いは A.popleft() を画面に出力するところだけです。

クエリの数が 100未満と少ないので .pop(0) でもよいのですが、キューの場合はなるべく deque をインポートしてそれを使っていきましょう。

next() 関数で呼び出した値を変数に代入せずに横着してそのまま使ってきましたが、できる限り変数に代入して使いましょう。😅

from collections import deque

Q = int(input())

A = [deque() for _ in range(2)]
len_A = [0, 0]
for _ in range(Q):
    query = map(int, input().split())

    op = next(query)
    if op == 1:
        K, X = next(query) - 1, next(query)
        A[K].append(X)
        len_A[K] += 1
    elif op == 2:
        K = next(query) - 1
        print(A[K].popleft())
        len_A[K] -= 1
    else:
        print(*len_A)

キューを２つ用意するのですが、別々の変数で用意するよりもリストにしたほうが扱いやすいので、空の deque をリスト内に作成します。

相変わらずクエリの受け取りが面倒ですが、その場その場で必要な分だけ next() 関数で呼び出して変数に代入して使っていきます。

len_A という現在の リストA の要素数を記録する変数を用意し、値が追加されるごとに +1、削除されるごとに -1 していますが、SIZE の指示のときに len() 関数を使って要素数を数えても問題にはならないと思います。
もしクエリの処理が断続的であった場合、処理が終わった直後に発生するインターバル(次の指示を受け付けるまでの間ま)にカウントしておけば、SIZE の時にカウントしておいた要素数をただ表示するだけで済みますので効率がいいかなと思います。人の手で入出力処理をするとどうしてもコンピュータが何もしない時間が発生しますので、後でまとめて処理するよりはそのインターバル中に処理させたほうが人の待ち時間を短縮できます。「今のうちにトイレ行ってくる！」みたいな感じです。違うか。😅

from collections import deque

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

queue = deque(A[:X-1])
max_sum = -float('inf')
sum_ = sum(queue)

for i in range(X-1, N):
    queue.append(A[i])
    sum_ += A[i]

    if sum_ > max_sum:
        max_sum = sum_
        left_num = queue[0]
    
    sum_ -= queue.popleft()

print(max_sum, left_num)

長さが X に固定されています。このプログラムでは例えば X = 5 の時、先頭から４つ目までを予め deque queue に格納しておきます。その際、４つ目までの総和も求めておきます。

次の 文からが問題文が求めるプログラムになります。やっていることは paiza の解説で説明されていることと同じなのですが、要するに、

1. .append() で追加した数を足す (要素数 X)
2. 最大値と現在の総和を比較する
3. .popleft() で削除した数を引く (要素数 X-1)

を リストA の最後まで繰り返していくだけです。

求める最大値の区間は『ただし、要素の和の最大となる区間が複数ある場合はそのうちもっとも先頭の値を出力してください。』とありますので、

if sum_ > max_sum:

とします。逆にもっとも後方の値と指示された場合は、

if sum_ >= max_sum:

とします。

ループを抜けたら、最後に区間の最大値と、最大値が求められた区間の先頭の値を画面に出力して完了です。

_ = input()
A = input().split()

stack = []
for a in A:
    if a == '+':
        r, l = stack.pop(), stack.pop()
        stack.append(l + r)
    elif a == '-':
        r, l = stack.pop(), stack.pop()
        stack.append(l - r)
    else:
        stack.append(int(a))

print(*stack)

_ = input()
A = input().split()

stack = []
for a in A:
    if a.isdigit():
        stack.append(int(a))
    else:
        r, l = stack.pop(), stack.pop()
        num = eval(f"l{a}r")
        stack.append(num)

print(*stack)

変数 r と l は、スタックの状態ではそれぞれ「上」「下」となっていて、これを横にすると引き算では「下 - 上」の順になります。足し算は順不同なので、引き算と同じ順で表記できます。

例２は、 .isdigit() メソッドで「文字列が数値に変換できるかどうか」をチェックして、数値の時は整数に変換して PUSH 、できない時は + か - なので、これを使って計算します。

f文字列で 'l-r' の文字列の形にし、その文字列をそのまま eval() 関数を使って計算します。f文字列でなくても普通の文字列でも構いません。

r = 2, l = 1, a = '+' の時

num = eval(f"l{a}r")

num = eval(f"l{'+'}r")

num = eval("l+r")

num = l+r

num = 3

不思議な挙動をしますが、文字列の構文をそのままプログラムとして実行する機能です。ですので、最後の画面出力の処理を、

s = 'print(*stack)'
eval(s)

としてもそのとおりに正しく処理されます。 eval() 関数の常用乱用はお勧めできかねるのですが、試すだけ試してみてください。😉

_ = input()
S = input()

num = 0
for s in S:
    num += (1 if s == '(' else -1)
    if num < 0:
        break

print('Yes' if num == 0 else 'No')

_ = input()
S = input()

stack = []
for s in S:
    if s == '(':
        stack.append(s)
    elif s == ')' and stack:
        stack.pop()
    else:
        stack.append(-1)
        break

print('No' if stack else 'Yes')

例１はスタックを使わずに ( が出現したら 1 を足し、) が出現したら 1 を引くという単純なことをしています。例２はスタックを使っていますが、例１のほうが圧倒的にわかりやすいですね。😅

if s == '(':

( をスタックに PUSH します。

elif s == ')' and stack:

スタックに ( がある時、( を POP します。

else:

elif s == ')' and not stack: と同等で、スタックが空なのに ( を POP しようとした時は -1 を追加してループを抜けます。

ループ終了後に、スタックに ( が残っている時は ) の数が足りない、スタックが -1 の時は ) の数が多い、スタックが空になっている時は ( と ) の数が等しいということになります。
-1 というのは、画面出力する結果の整合性をとる為に何かしらスタックに要素を入れておくためだけのダミーですので、ここは値であれば何でも構いません。値が無いという意味の値 None でもイケます。

例１は ( の数を +1, -1 してカウントしていましたが、例２はスタックの中の ( の数でカウントしています。

from collections import deque

def move(x, t, total):
    queue.append(x)
    return t+1, total - queue.popleft() + x


_, K = map(int, input().split())
A = map(int, input().split())

queue = deque([0] * K)
t, total = 0, 0
for a in A:
    while t < a:
        t, total = move(0, t, total)

    t, total = move(1, t, total)

    print(total)

まるでリアルタイムで仕事をしているエスカレーターそのもののような処理です。

人が乗る時刻だけが入力で与えられています。それ以外の時刻は人が乗らないのでループで 0 を追加し続けます。

人が乗る時刻がやってくるとループを抜け、人が１人乗る処理がされます。ネコはカウントされないのかな？

人が乗っても乗らなくても常に先頭の値は DEQUEUE します。それが move()関数の中にある .popleft() です。人がいない時は 0、人が１人降りる時は 1 が入っています。ついでに return の所で乗降人数の足し引きもしています。

すべて 0 と 1 だけで処理できますのでシンプルなプログラムになりました。😊

from collections import deque

_ = input()
A = deque(map(int, input().split()))

balls = [A.popleft()]
balls_len = 1
while A:
    balls.append(A.popleft())
    balls_len += 1

    while balls_len > 1 and balls[-1] == balls[-2]:
        balls[-2] *= 2
        balls.pop()
        balls_len -= 1

print(*balls[::-1], sep='\n')

_ = input()
A = map(int, input().split())

balls = []
balls_len = 0
for ball in A:
    balls.append(ball)
    balls_len += 1

    while balls_len > 1 and balls[-1] == balls[-2]:
        balls[-2] *= 2
        balls.pop()
        balls_len -= 1

print(*balls[::-1], sep='\n')

例１は、リアルっぽく A にあるボールを取り出して箱の中に移動しています。ボールを取り出すたびに A の要素が減っていきます。そのため、deque A が空になるとループを処理を終えます。
例２は A を参照しているだけです。文を使ってボールを取り出して(はいないけど)います。

「スタック・キューメニュー」の最終問題に相応しいのは例１でしょう。しかし注目すべきはそこではありません。

問題文にある絵図では上から入れて上から取り出しています。PUSH & POP です。横にすると後方から入れて後方から取り出しています。
ボールを入れるとそこの要素番号は -1 です。１つ前は -2 です。その２つのボールを比較して、数が同じなら要素番号 -2 の数を２倍にして、今入れた要素番号 -1 のボールを削除すると「結合」した形になります。

しかしこれで終わりではありません。結合した数とその前の数がまた同じになった場合は再び結合します。これを箱の底のボールに到達するまで全て調べていきます。

balls = [4, 2] ← 2 を入れる
↓
balls = [4, 2, 2]
↓
balls = [4, 4]
↓
balls = [8]

落ちゲーみたいですね。😊

ではここで私から課題を差し上げます。

プログラム例では後方から入れて後方から取り出す方式ですが、これを前方から入れて前方から取り出す方式に書き換えてください。

そうすると、最後は逆順にしないでそのまま画面に出力できるようになります。出来上がったらそれも提出してみましょう。