【paiza問題集解説】クエリメニュー

ソートと検索 (query)

STEP: 1 指定の位置への要素の追加

指定の位置への要素の追加

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(N)]
A.insert(K, Q)
print(*A, sep='\n')

数列A は１番目から始まっていますので、１番目の後ろということは要素番号 1 のことです。K 番目はそのまま要素番号 K となりますので上記プログラム例の書き方のとおりになります。

ただ、条件を見ると『1 ≦ N ≦ 100,000』と、数が大きいです。
これについては後の STEP 4 で説明します。

STEP: 2 指定要素の検索

指定要素の検索

N, K = map(int, input().split())
A = {int(input()) for _ in range(N)}
print('YES' if K in A else 'NO')

数列A とありますので、一旦入力をすべて受け取ってから文で探しますが、問題文に『重複した要素の無い数列 A』、条件に『1 ≦ N ≦ 100,000』とありますので、データの保存はセット型を使うと効率が良いです。

STEP: 3 指定要素の検索 (query)

指定要素の検索 (query)

N, Q = map(int, input().split())
A = {int(input()) for _ in range(N)}
K = [int(input()) for _ in range(N)]
for K_i in K:
    print('YES' if K_i in A else 'NO')

『 A に K_i が含まれていれば』なので、K_i を先頭から１つずつ数列A から探します。
A はセットのほうが良いですが、K はリストにします。

STEP: 4 先頭の要素の削除

先頭の要素の削除

例１

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

例２

from collections import deque

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

例１はリストの先頭の要素を削除します。この方法を使うと次の様に処理されます。

A = [1, 2, 3, 4, 5]

要素番号	0	1	2	3	4
A	1	2	3	4	5

↓ 先頭の要素を削除する

要素番号	0	1	2	3	4
A		2	3	4	5

↓ 後方の要素を１つずつ前にずらしていく

要素番号	0	1	2	3	4
A	2		3	4	5

↓

要素番号	0	1	2	3	4
A	2	3		4	5

↓

要素番号	0	1	2	3	4
A	2	3	4		5

↓

要素番号	0	1	2	3
A	2	3	4	5

要素数が 5 の時、先頭の要素を削除(処理 1回)して後方の要素を前に詰めていく(処理 4回)という処理をしますので、処理回数が計 5 回なされます。これだと100万要素あると100万回処理がされてしまうことになりますし、挿入の場合も同様に後ろに詰めていく処理が発生します。

例２ではそれを解消する為に deque (デキュー) というモジュールを使います。これは 双方向キュー(dequeのこと) という「リストのようでただのリストでないデータ構造」のもので、これを使う目的は主に先頭の要素の追加削除です。

双方向キューを使うと、先頭の要素の削除の処理が以下の様になります。

A = deque([1, 2, 3, 4, 5])

要素番号	0	1	2	3	4
A	1	2	3	4	5

↓ 先頭の要素を削除する .popleft()

要素番号	0	1	2	3
A	2	3	4	5

一瞬です。一回の処理で先頭の要素が削除されます。
この「先頭の要素を削除する」という処理は幅優先探索アルゴリズムなどでよく使うことになりますので、こんな場面に出合ったらこのモジュールを使いましょう。
欠点としては両端は高速ですが、中央に寄るほど効率が悪くなります。

deque の機能は以下の通りです。

メソッド	機能
.popleft()	先頭の要素を取り出す
.appendleft()	先頭に要素を追加する
.pop()	末尾の要素を取り出す
.append()	末尾に要素を追加する
.rotate(n) .rotate(-n)	双方向リストの要素を n 回回転する

特に .rotate() メソッドは面白い機能で、使うと次の様な動作をします。

A = deque([1, 2, 3, 4, 5])
A.rotate(1)

要素番号	0	1	2	3	4
A	5	1	2	3	4

A = deque([1, 2, 3, 4, 5])
A.rotate(-1)

要素番号	0	1	2	3	4
A	2	3	4	5	1

A = deque([1, 2, 3, 4, 5])
A.rotate(2)

要素番号	0	1	2	3	4
A	4	5	1	2	3

.rotate() メソッドを使わなくても、

for _ in range(n):
    A.appendleft(A.pop())

とすればよいのですが、せっかく deque をインポートしたのですからメソッドを使ってしまいましょう。😊

それとインポートする際の行頭の一文は憶えましょう。横着して漢字かな変換システムに単語登録して使わないように。(覚えるまではいいけど👍)

よかったら STEP 1 のプログラムも deque を使ったやり方に書き換えてみてください。

STEP: 5 先頭の要素の削除(query)

先頭の要素の削除(query)

from collections import deque

N, K = map(int, input().split())
A = deque([int(input()) for _ in range(N)])

for _ in range(K):
    S = input()
    if S == 'pop' and A:
        A.popleft()
    elif A:
        print(*A, sep='\n')

１つ前の問題のクエリ版です。deque のいい練習台になったのではないでしょうか。😊

STEP: 6 連想配列

連想配列

N, K = map(int, input().split())
dic = {num: ID for _ in range(N) for num, ID in [input().split()]}

for _ in range(K):
    Q = input()
    print(dic[Q])

連想配列とは、Pythonでいう「辞書」のことです。辞書と呼ぶ Python のほうがレアで、正式には「連想配列」といいます。

ただの辞書を扱う問題ですので、さらりとクリアしたかと思います。😊

STEP: 7 連想配列(query)

連想配列(query)

N, K = map(int, input().split())
dic = {num: ID for _ in range(N) for num, ID in [input().split()]}

for _ in range(K):
    S = iter(input().split())
    query, num = next(S), next(S)
    
    if query == 'call':
        print(dic[num])
    elif query == 'leave':
        dic.pop(num)
    else:
        dic[num] = next(S)

入力が不揃いのクエリ処理がめんどくさくて iter() 関数を使ってしまいました。
これはリストなどのデータをイテレータに変換する機能で、イテレータの先頭から next(iter) 関数で要素を１つ呼び出す機能で、仕組みは異なりますが .popleft() みたいなものです。イテレータなので呼び出し方は文と同じですが、 next() 関数を使って好きなところで値を順に呼び出せるメリットがあります。この使い勝手は .popleft() と同じです。
ただ、イテレータの末尾を超えて呼び出そうとするとエラーになります。その点だけ要注意です。

N が 100000 と大きいですが、辞書はセットと同じ様な構造していますので、要素の削除は高速です。ですので要素数が多くても気にする必要は無いでしょう。

辞書の要素の削除は .pop() で出来ます。 .remove() は存在しません。

STEP: 8 ソートと検索

ソートと検索

N, X, P = map(int, input().split())
A = [int(input()) for _ in range(N)]

a = sorted(A + [X, P])
print(a.index(P) + 1)

X と P は .append() で追加しなくとも、sorted() 関数内でリストにしてリストA と繋げることもできます。ただしこの時、リストA に X と P は追加されていませんので注意。

また、直接リストA に追加する場合でも .extend() メソッドで複数の要素を一度に追加できます。

N, X, P = map(int, input().split())
A = [int(input()) for _ in range(N)]

A.extend([X, P])
A.sort()
print(A.index(P) + 1)

.append() の場合はリストごと追加してしまい、

[181, 177, 113, [188, 174]]

というような変なリストになりますが、 .extend() を使うと

[181, 177, 113, 188, 174]

と、要素だけを追加してくれます。要素の追加方法は他にもありますし、使用頻度はそんなに高くないと思いますが、機会があったら使ってみてください。

FINAL問題ソートと検索 (query)

ソートと検索 (query)

N, K, P = map(int, input().split())
A = [int(input()) for _ in range(N)]
a = sorted(A + [P])
paiza = a.index(P) + 1

for _ in range(K):
    query = iter(input().split())
    event = next(query)
    
    if event == 'sorting':
        print(paiza)
    else:
        num = int(next(query))
        paiza += (num < P)

やっぱイテレータ、ラクでいいわぁ。😆

以前 ChatGPT 3.5 にプログラムの改善を求めて見せたらイテレータがまるごと消されて添字を使った方法に書き直されてしまったのですが、やってることは同じじゃないか！と思って度々使うようになりました。世間様がどうお考えになられようと、わたくしの知ったことではございませんことよ！どうせ生涯独りでプログラムを組んでいくわけだし～。

でもたまに iter() が役立つこともあります。このメニューの最後の問題「点の幅」がその一例です。

最後の一文の

paiza += (num < P)

も、一般的な書き方ではないから推奨しないよと ChatGPT 3.5 に言われたのですが、それじゃあ私が積極的に使って世界の常識にしてやろうじゃないの！と、場合に依りますが割と使っています。
これがわかりにくいと言う人って、ただ True と False をよく理解していないだけじゃないかと思いますし。

もしあなたが将来 IT業界に身を置くことになり、そこでこの様な書き方をしたが為に先輩や上司にこっぴどく叱られたとしたら、その時はどうぞ私のせいにしてください。

場合によっちゃ交通費貴方様負担で殴り込みに行きますよ！(これは冗談)

Vtuber

STEP: 1 アイドルグループ

アイドルグループ

N, K = map(int, input().split())
names = {input() for _ in range(N)}

for _ in range(K):
    S = input()
    
    if S == 'handshake':
        print(*sorted(names), sep='\n')
    else:
        q, name = S.split()
        
        if q == 'join':
            names.add(name)
        else:
            names.remove(name)

ソート回数が最大で 10回までとありますので、 sorted() 関数でソートしても処理にそれほど負荷をかけることもないかと思われます。

リストよりもセットのほうが向いています。追加はともかく、削除の処理速度には差が出ます。

STEP: 2 歴史を作る時間

歴史を作る時間

N, K = map(int, input().split())
for _ in range(N):  # 入力 S の部分
    input()

writers = [[int(Y), C] for _ in range(K) for Y, C in [input().split()]]

for _, name in sorted(writers):
    print(name)

問題文に『 1 人の生徒が複数の出来事の記事を担当することがある点に注意してください。』、期待する出力欄に『同じ年に複数の出来事があった場合は、名前が辞書順になるように出力してください。』とあります。辞書で作ろうとするとどちらもキーが重複する場合が生じますので、ここはリストが適しています。

入力が無事済ませられれば、あとはソートして結果を画面に出力するだけです。

入力S は全く使いませんので、この部分の入力はメモリにも残さず、消し炭にしました。😼

しかし辞書でも組めないことはありません。

N, K = map(int, input().split())
for _ in range(N):
    input()

writers = {}
for _ in range(K):
    Y, C = [[int(Y), C] for Y, C in [input().split()]][0]
    writers[Y] = writers.get(Y, []) + [C]

for _, name in sorted(writers.items(), key=lambda x:(x[0], x[1].sort())):
    print(*name, sep='\n')

辞書の中身を見るとこちらのほうが管理されててわかりやすいのですが、プログラムは複雑になります。

N, K = map(int, input().split())
for _ in range(N):
    input()

writers = {}
for _ in range(K):
    Y, C = [[int(Y), C] for Y, C in [input().split()]][0]
    writers[Y] = writers.get(Y, []) + [C]

print(writers)

例）

{2058: ['yuki'], 645: ['nao', 'hiro', 'nao'], 374759: ['nao']}

なにごとも場に応じてということで。😊

STEP: 3 銀行

銀行

N, K = map(int, input().split())
# C = 企業名, P = 暗証番号 , D = 口座額
co_infos = {C:[P, int(D)] for _ in range(N) for C, P, D in [input().split()]}

for _ in range(K):
    # G = 企業名 , M = 暗証番号 , W = 出金額
    G, M, W = input().split()

    if co_infos[G][0] == M:      # [0] は暗証番号
        co_infos[G][1] -= int(W) # [1] は口座額

for k, v in co_infos.items():
    print(k, v[1])  # 口座額のみ出力

顧客の暗証番号を聞き出すとか、完全アウトな銀行ですね！🙅

データをどの様な形式に保存するかでプログラムの組み方が大きく変わってきてしまいます。N の値が大きいのでここでは辞書を使い、値をリストにして扱うと上記プログラム例の様になります。

STEP: 4 経理

経理

N, K = map(int, input().split())
receipts = {input():[] for _ in range(N)}

for _ in range(K):
    # a = 部署名 , p = 注文番号 , m = 購入額
    a, p, m = input().split()
    receipts[a].append([p, m])

for key, value in receipts.items():
    print(key)
    for v in value:
        print(*v)
    
    print('-' * 5)

領収書は１つ１つそのまま入力して管理されるようなので、K が大きいのですがリストを使います。

辞書に各部署をキーとして、値には領収書の情報をリストに保存し、それを部署ごとに分類して出力するという流れです。リストにリストを追加できれば、他は難しくないと思います。

FINAL問題 Vtuber

Vtuber

N = int(input())
super_chats = {}
memberships = set()

for _ in range(N):
    name, query, tmp = input().split(maxsplit=2)
    
    if query == 'give':
        money, _ = tmp.split()
        super_chats[name] = super_chats.get(name, 0) + int(money)
    else:
        memberships.add(name)

sorted_chats = sorted(super_chats.items(), key=lambda x:x[1], reverse=True)
for k, _ in sorted_chats:
    print(k)

print(*sorted(memberships), sep='\n')

ソートがちょっと難しくないかな？と思って paiza の解答コード例を見てみたら全く同じだったので、これで解説します。

まずは無名関数 lambda で、~~御捻り~~superchatの金額をターゲットにして昇順ソートします。
それからリスト全体を reverse=True で降順ソートすると、金額が降順ソート、名前も降順ソートされ、問題文の通りの並びになります。これは実際に引数をいじってみればわかると思います。

条件に『アカウント名に重複はないことが保証されている。』とありますので、リストよりもセットを使うとよいでしょう。最後にソートしますので順番は関係ありませんし。

真ん中へんにある .get() メソッドの使い方は「２章辞書を使いこなす機能一覧」で学習できます。

安易に野良犬にエサを与えちゃダメだよ！！つけあがるから！！💢

平方分割

STEP: 1 累積和

累積和

例１

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

cum_sum = [0] + A
for i in range(N):
    cum_sum[i+1] += cum_sum[i]

for _ in range(K):
    q = int(input())
    print(cum_sum[q] - cum_sum[0])

例２

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

cum_sum = [0]
for i in range(N):
    cum_sum.append(cum_sum[i] + A[i])

for _ in range(K):
    q = int(input())
    print(cum_sum[q] - cum_sum[0])

例３

N, K = map(int, input().split())

cum_sum = [0]
for i in range(N):
    cum_sum.append(cum_sum[i] + int(input()))

for _ in range(K):
    q = int(input())
    print(cum_sum[q] - cum_sum[0])

例３よりも、一度内包表記で入力をすべて取り込んでから累積和を作っている例２のほうが高速です。
.append() を使っている例２よりも、累積和用に予めゼロマップを用意してから累積和を作っている例１のほうが高速です。

「累積和って何？」と疑問に思った方は、問題集「定番アルゴリズム」の「累積和メニュー」を先にやってみてください。
「累積和メニュー」の解説もありますので是非！

STEP: 2 区間和

区間和

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

cum_sum = [0] + A
for i in range(N):
    cum_sum[i+1] += cum_sum[i]

for _ in range(K):
    l, r = map(int, input().split())
    print(cum_sum[r] - cum_sum[l-1])

区間和と言っても開始位置が入力で新たに指定されただけなので、最後の二行以外は１つ前の「累積和」と同じです。

STEP: 3 二次元累積和

二次元累積和

H, W, N = map(int, input().split())
cum_sum = [[0] * (W+1) for _ in range(H+1)]

for h in range(H):
    A = list(map(int, input().split()))
    for w in range(W):
        cum_sum[h+1][w+1] = cum_sum[h][w+1] + cum_sum[h+1][w] - cum_sum[h][w] + A[w]

for _ in range(N):
    y, x = map(int, input().split())
    print(cum_sum[y][x])

二次元累積和を作ったら、入力で与えられた y x の位置の値を出力するだけです。二次元累積和を作るだけの問題でした。

数列の入力を一行ずつ読み込みながら一行ずつ二次元累積和を作っています。こんな方法でも作れるよというだけです。

STEP: 4 二次元区間和

二次元区間和

H, W, N = map(int, input().split())
cum_sum = [[0] * (W+1) for _ in range(H+1)]

for h in range(H):
    A = list(map(int, input().split()))
    for w in range(W):
        cum_sum[h+1][w+1] = cum_sum[h][w+1] + cum_sum[h+1][w] - cum_sum[h][w] + A[w]

for _ in range(N):
    a, b, c, d = map(int, input().split())
    ans = cum_sum[c][d] - cum_sum[c][b-1] - cum_sum[a-1][d] + cum_sum[a-1][b-1]
    print(ans)

左上と右下の長方形の範囲の総和を求める基本形です。行列さえイメージできれば怖いものはありません。

『は？』と思ったら「累積和メニュー」でじっくりと学んでおいてください。このあと使うよ！

STEP: 5 平方分割のバケット

平方分割のバケット

N = 10000
nums = [int(input()) for _ in range(N)]
x = int(pow(N, 0.5))

# ルートN に小数(端数)が出たら要素を 1 足して要素数を調整
# 今回は √10000 = 100 なので、無くても動く
x += int(N % x != 0)

srd_maxes = [max(nums[i*x:(i+1)*x]) for i in range(x)]

print(*srd_maxes, sep='\n')

このプログラムの要かなめは srd_maxes の中の nums[i*x:(i+1)*x] の部分です。この x が $\sqrt{N}$ です。
$\sqrt{10000}$ = 100 なので、100個のバケット (１バケットはx 個分の区間) が作られます。そして各バケットの中から最大値を求めます。

すると最終的に各バケットから求められた 100個の最大値が入っている一次元リストが出来上がります。

この問題ではそれら 100個の最大値を改行区切りで画面に出力すれば完了となります。

ルート(平方根)の求め方は三行目の

x = int(pow(N, 0.5))

です。これは $\sqrt{N} = N^{0.5}$ = N**0.5 = pow(N, 0.5) です。pow() 関数で求める累乗は ** で求める累乗よりずっと高速に計算できます。特に第２引数が大きくなる時は威力を発揮します。しかし今回は 0.5 と小さいので N**0.5 でも問題ありません。

今回は使わなかった、

# ルートN に小数(端数)が出たら要素を 1 足して要素数を調整
# 今回は √10000 = 100 なので、無くても動く
x += int(N % x != 0)

ですが、もし N が 9999 だったときは、x が int(99.994999) = 99 となり、100個用意すべきバケットが１つ足りなくなってしまいます。

N = 10000 の時、x = 100
[1, …, 100], …, [9901, …, 10000]

N = 9999 の時、x = 99
[1, …, 100], …, [9901, …, 9999]
10000 の時も 9999 の時も x = 100 個必要。

その為に必要な一文です。今回は N が 10000 の定数なので不要ですが、変数の場合は必要となります。けど如何なる時も付けておいたほうが無難ですし、これを定型文としておけたほうが安心でしょう。

要するにこれは「小数点以下切り上げ」なのですが、これは math モジュールの ceil() 関数がその機能を持っています。

from math import ceil, sqrt

N = 10000
A = [int(input()) for _ in range(N)]
x = ceil(sqrt(N))  # ← ココ
mos_A = [max(A[i*x:(i+1)*x]) for i in range(x)]

print(*mos_A, sep='\n')

平方根を求める sqrt() も math モジュールの中にある機能の１つなのですが、詳しくは知らないのですが、これが最も正確な平方根を求めてくれるそうです。
モジュールにある機能は、使い慣れる為にも積極的に使っていって良いと思います。

こんな書き方もできますよという紹介でした。お好きな方法でどうぞ。

FINAL問題平方分割

平方分割

ﾑｽﾞｲ _(:3」∠)_

K = int(input())    # 最大値の検索回数
N = 10000
x = int(pow(N, 0.5))
A = [int(input()) for _ in range(N)]

# ルートN に小数(端数)が出たら要素を 1 足して要素数を調整
# 今回は √10000 = 100 なので、無くても動く
x += int(N % x != 0)

srd_maxes = [max(A[i*x:(i+1)*x]) for i in range(x)]

for _ in range(K):
    left, right = [[int(l_i)-1, int(r_i)-1] for l_i, r_i in [input().split()]][0]

    max_ = A[left]
    while left <= right:
        if (left % x == 0) and (left + x-1 <= right):
            max_ = max(max_, srd_maxes[left // x])
            left += x  # 次のバケットの先頭へ飛ぶ

        else:  # バケットの範囲外の時は、1つずつ調べていく
            max_ = max(max_, A[left])
            left += 1

    print(max_)

# (left % x == 0) ＝ 平方分割して区切ったブロックに到達し、
# そのブロックの最後の位置が right 以下
# (ブロック全ての要素を含む場合、平方分割して求めておいた値が使える)

私はこのメニューの中でこの問題がずっと解けませんでした。最後の問題の「点の幅」も。わかるようになった今でもプログラム化するのは難しいですね。何度も使って書き方を覚えるまではまたすぐに忘れてしまいます。なのでこのプログラムはメモしています。

前半は１つ前のプログラムと同じです。今回は文以下の部分が追加の問題となります。

入力 l_i r_i は 1 番目から数えていますので、これを要素番号に変換する為にここで 1 を引いておきます。

最大値を left から順に探していきますので、max_ の初期値は A[left] にしておきます。ここから A[right] までを調べていきます。while left <= right:

else:  # バケットの範囲外の時は、1つずつ調べていく
    max_ = max(max_, A[left])
    left += 1

申し訳ない。先に else文のほうから説明します。

ここでは平方分割して予め最大値を求めておいたバケットの範囲外の所を調べています。単純に最初に取得した数列A を使って１つずつ最大値を見つけて更新していきます。

A = [1, 2, 3, …, 98, 99, 100]
srd_maxes = [10, 20, …, 90, 100]
left = 7, right = 52 の時

8, 9, 10, {20, 30, 40, 50}, 51, 52, 53

初めは max_ には 8 が入っています。left += 1 しながら最大値を更新していきます。
10 に到達したら、この次は { } で囲まれている部分「平方分割」して予め最大値を求めておいた数列 srd_maxes を使って最大値を見つけていきます。

while left <= right:
    if (left % x == 0) and (left + x-1 <= right):
        max_ = max(max_, srd_maxes[left // x])
        left += x  # 次のバケットの先頭へ飛ぶ

この部分が平方分割を利用した最大値の探索方法です。

A = [1, 2, 3, …, 98, 99, 100]
srd_maxes = [10, 20, …, 90, 100]
left = 7, right = 52 の時

8, 9, 10, {20, 30, 40, 50}, 51, 52, 53

現在 left = 10 (値 10 の次の所)

left % x == 0: left は 10、x は 100**0.5 = 10 なので、
10 % 10 = 0
left + x-1 <= right: 10 + 10 - 1 <= 53

どちらも True なので、srd_maxes を使って最大値を求めます。

max_ = max(max_, srd_maxes[left // x])

srd_maxes = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

max_ = max(max_, srd_maxes[10 // 10])

max_ = max(max_, srd_maxes[1])

max_ = max(max_, 20)
left += 10

条件式が False になるまで、これを繰り返していきます。

max_ = max(max_, srd_maxes[20 // 10])

max_ = max(max_, srd_maxes[2])

max_ = max(max_, 30)
left += 10

(´ω`)

max_ = max(max_, srd_maxes[30 // 10])

max_ = max(max_, srd_maxes[3])

max_ = max(max_, 40)
left += 10

(ﾟзﾟ)

max_ = max(max_, srd_maxes[40 // 10])

max_ = max(max_, srd_maxes[4])

max_ = max(max_, 50)
left += 10

(*ﾉωﾉ)

ここで、left = 50 となります。

left + x-1 <= right: 50 + 10 - 1 <= 53 … False

この続きはまた else文のほうで処理します。

else:  # バケットの範囲外の時は、1つずつ調べていく
    max_ = max(max_, A[left])
    left += 1

A = [1, 2, 3, …, 98, 99, 100]
srd_maxes = [10, 20, …, 90, 100]
left = 7, right = 52 の時

8, 9, 10, {20, 30, 40, 50}, 51, 52, 53

現在 left = 50 で、A[50] の値は 51 です。また left += 1 しながら最大値を更新していきます。そして while left <= right: の評価が False となった時には max_ には指定された範囲の最大値が求められています。1 から順に並んでいるので当然 53 が入っているわけですけれども。😅

本来は 11 ～ 50 までも順に調べていくと全部で 46回調べることになります。平方分割を用いると 10回で済みます。
この問題の様に N = 10000 となるとさらに差が出ますし、N = 1000000 となるとさらにさらに差が出ますし、検索回数が 10万回ともなるとさらにさらにさらにさらに差が出ます。累積和と同じように予め１回作成しておけば何度でも使えますし、値が更新されたとしても都度書き換えた所の範囲だけ最大値を求めなおせば一瞬です。

なんて偉そうなことを言いましたが、また少し時間が経てば忘れるでしょう。だからこそソースプログラムのメモは大事！このサイトの説明でわかるようでしたら、必要に応じて利用していただけたら作成した甲斐があり、幸いに思います。

〆っぽい感じになりましたけど、まだ問題は続きます。😅

点の幅

STEP: 1 'I' の数

'I' の数

def main(N, K, cum_sum):
    for _ in range(K):
        a_l, a_r, b_l, b_r = map(int, input().split())
        a_point = calc_point(a_l, a_r, N, cum_sum)
        b_point = calc_point(b_l, b_r, N, cum_sum)
    
        print(judge(a_point, b_point))

def calc_point(left, right, N, cum_sum):
    if (right - left + 1) < N / 3:
        return cum_sum[right] - cum_sum[left-1]
    else:
        return -1

def judge(a, b):
    return 'A' if a > b else 'B' if a < b else 'DRAW'

def setup():
    N, K = map(int, input().split())

    return N, K, make_cumulative_sum(N)

def make_cumulative_sum(N):
    cum_sum = [0] + [int(input()) for _ in range(N)]
    for i in range(N):
        cum_sum[i+1] += cum_sum[i]

    return cum_sum
    
if __name__ == '__main__':
    main(*setup())

関数型で書いて、各機能を分けました。

main(): メインプログラム。プレイヤー A と B が掴んだ先頭と末尾のページの入力を受け取り、ゲームを進行する。
calc_point(): 掴んだページ数が有効かどうかを判定し、結果を返す。
judge(): A と B の勝敗を判定する。
setup(): 入力の受け取りと、作成した累積和の値を返す。
make_cumulative_sum(): 記録した各ページの 'I' の数から累積和を作成する。

この問題は最大で 100000 / 3 頁の 'I' の数の計算を二人分、そしてこれを 100000回ゲームを行ないますので、累積和を用いて計算量を大幅に削減することがカギとなります。

プログラムの内容自体は目で追っていけばわかるかと思います。ただ、 calc_point() 関数の中にある文の条件式が唯一の悩み処かと思われます。

def calc_point(left, right, N, cum_sum):
    if (right - left + 1) < N / 3:
        return cum_sum[right] - cum_sum[left-1]
    else:
        return -1

例えば、１頁から３頁を掴むと計３頁ですが、3 - 1 = 2 になってしまうので 1 を足して帳尻を合わせます。そして、

『ただし、 N/3 ページ以上掴んだ人は反則負け』

とありますので、その掴んだページ数が本全体のページ数の３分の１未満であれば、累積和から 'I' の数を求め、その数を返します。反則した場合は judge() 関数で必ず負けと判定されるように -1点として返します。反則していなければ 'I' の数は必ず 0 以上になりますので、0 未満であればいくつでも、 -float('inf') としても反則と判定されます。

この３分の１の判定は、N // 3 ではなく N / 3 と、計算結果を浮動小数にしておくことも大切です。小数を切り捨てると判定にミスが起こる場合が想定されます。

これがわかれば、ここまで問題を進めてきた方なら、あとはすべて理解できるでしょう。

STEP: 2 ドーナツ

ドーナツ

H, W, N = map(int, input().split())

cum_sum = [[0] * (W+1) for _ in range(H+1)]

for y in range(H):
    C = list(map(int, input().split()))
    for x in range(W):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + C[x]

for _ in range(N):
    y, x, B, S = map(int, input().split())

    yy = y + B // 2
    xx = x + B // 2
    choco = cum_sum[yy][xx] - cum_sum[yy-B][xx] - cum_sum[yy][xx-B] + cum_sum[yy-B][xx-B]

    yy = y + S // 2
    xx = x + S // 2
    choco -= cum_sum[yy][xx] - cum_sum[yy-S][xx] - cum_sum[yy][xx-S] + cum_sum[yy-S][xx-S]
    
    print(choco)

ざっくり手順。

二次元累積和をつくる
ドーナツの型をとる
ドーナツに穴を空ける

この問題は全て二次元累積和で解決できます。

まずはチョコの数を二次元累積和にします。

cum_sum = [[0] * (W+1) for _ in range(H+1)]

for y in range(H):
    C = list(map(int, input().split()))
    for x in range(W):
        cum_sum[y+1][x+1] = cum_sum[y+1][x] + cum_sum[y][x+1] - cum_sum[y][x] + C[x]

先の問題「二次元累積和」と同じ方法で作ります。

問題の入力例2 を利用します。

2
5 5 4
7 8 9 8 5
4 2 6 2 1
2 5 3 9 1
1 3 3 2 3
2 3 2 6 6
3 4 3 1  ← 解説にココを使います
2 3 3 1
2 4 3 1
3 3 5 3

【二次元累積和】

0  0  0  0  0  0
0  7 15 24 32 37
0 11 21 36 46 52
0 13 28 46 65 72
0 14 32 53 74 84
0 16 37 60 87 103

ドーナツの型をとります。

for _ in range(N):
    y, x, B, S = map(int, input().split())

    yy = y + B // 2
    xx = x + B // 2
    choco = cum_sum[yy][xx] - cum_sum[yy-B][xx] - cum_sum[yy][xx-B] + cum_sum[yy-B][xx-B]

今までは二次元区間和の範囲が入力で与えられていましたが、今回はドーナツの中心の位置と一辺の長さだけしか与えられていません。その為、計算して各位置を割り出す必要があります。

y と x はドーナツの中心の位置です。B は一辺の長さなので、それを２で割った商を求めて y と x にそれぞれ足すと、ドーナツの右下の位置が求められます。

例えば１辺の長さが 5 の時、5 // 2 = 2 になります。ドーナツの中心から下へ y + 2、右へ x + 2 の位置がドーナツの右下の位置になり、これがそれぞれ y + B // 2 x + B // 2 です。

● ● ● ● ●
● ● ● ● ●
● ● ㊥ ● ●
● ● ↓ ● ●
● ● ② → ② 👈[yy][xx]

条件に『S_i , B_i は奇数』とありますが、 B // 2 で商を求めれば、必ず余りが 1 になります。この余りの 1 がドーナツの中心です。
「S_i , B_i も奇数」であることで必ず中心ができ、ドーナツやドーナツの穴の大きさが偶数になる(中心がずれる)せいで、いびつな形のドーナツになったりすることはありませんという保証になっています。

ドーナツの右下の位置 yy, xx から y 方向と x 方向共に B を引くとドーナツの外側の位置が求められます。

0  0  0  0  0  0
0  7 15 24 32 37
0 11 21 36 46 52
0 13 28 46 65 72
0 14 32 53 74 84
0 16 37 60 87 103

y, x, B, S = 3, 4, 3, 1
yy = y + B // 2 = 4
xx = x + B // 2 = 5
cum_sum[4][5] が型を取ったドーナツ右下の 84

cum_sum[yy-B][xx]
yy - B = 4 - 3 = 1
cum_sum[1][5] の 37

cum_sum[yy][xx-B]
xx - B = 5 - 3 = 2
cum_sum[4][2] の 32

これを、

choco = cum_sum[yy][xx] - cum_sum[yy-B][xx] - cum_sum[yy][xx-B] + cum_sum[yy-B][xx-B]

で不要な部分を引き、型を取ったドーナツの部分のチョコの数だけを抽出します。

0  0  0  0  0  0
0  7 15 24 32 37
0 11 21 36 46 52
0 13 28 46 65 72
0 14 32 53 74 84
0 16 37 60 87 103

choco = 84 - 37 - 32 + 15
↓
choco = 30

最後にドーナツに穴を空けます。

    yy = y + S // 2
    xx = x + S // 2
    choco -= cum_sum[yy][xx] - cum_sum[yy-S][xx] - cum_sum[yy][xx-S] + cum_sum[yy-S][xx-S]

B が S になっただけで、ドーナツの型をとった時と同様の方法で穴を空けられます。穴を空けると穴の分のチョコが減りますので、そのチョコの分を引きます。

0  0  0  0  0  0
0  7 15 24 32 37
0 11 21 36 46 52
0 13 28 46 65 72
0 14 32 53 74 84
0 16 37 60 87 103

choco -= 65 - 46 - 46 + 36
↓
choco -= 9
↓
choco = 30 - 9
↓
choco = 21

無事、出力例2 の結果と同じになりました。
二次元累積和だけで求められるので、解れば簡単ですよね。👍

残りの入力例も目で確認しながら計算して結果を求めてみてください。

FINAL問題点の幅

点の幅

class Player:      # srd = Square Root Decomposition
    def __init__(self):
        self.score = -float('inf')
        
    def get_score(self):
        return self.score
        
    def game(self, left, right):
        if right - left + 1 > self.half_N:
            self.score = -1
            return
        
        max_ = -float('inf')
        min_ = float('inf')
        while left <= right:
            if self.is_within_srd_data(left, right):
                max_ = max(max_, self.srd_maxes[left // self.x])
                min_ = min(min_, self.srd_mins[left // self.x])
                left += self.x
            else:
                max_ = max(max_, self.S[left])
                min_ = min(min_, self.S[left])
                left += 1
        self.score = max_ - min_

    def is_within_srd_data(self, left, right):
        is_top = (left % self.x == 0)
        is_within_section = (left + self.x - 1 <= right)
        
        return is_top and is_within_section
        
    @classmethod
    def initialize(cls, N, S, x, srd_maxes, srd_mins):
        cls.half_N = N / 2
        cls.S = S
        cls.x = x
        cls.srd_maxes = srd_maxes
        cls.srd_mins = srd_mins
        
        
def main(K, players):
    for _ in range(K):
        lr = map(int, input().split())
        for player in players:
            player.game(next(lr)-1, next(lr)-1)
            
        print(judge(players[0].get_score(), players[1].get_score()))

def judge(a, b):
    return 'A' if a > b else 'B' if a < b else 'DRAW'

def setup():
    N, K = map(int, input().split())
    S = [int(input()) for _ in range(N)]
    x = int(pow(N, 0.5))
    x += int(N % x != 0)
    srd_maxes = [max(S[i*x:(i+1)*x]) for i in range(x)]
    srd_mins = [min(S[i*x:(i+1)*x]) for i in range(x)]
    Player.initialize(N, S, x, srd_maxes, srd_mins)
    players = [Player() for _ in range(2)]
    
    return K, players


if __name__ == '__main__':
    main(*setup())

クラス型で組んだということもあって長～～～～～くなりましたけど、プログラムの中枢は .game() メソッドで、ここに注目すれば全体が繋がって見えるようになると思います。
そしてここは先の「平方分割」で見覚えがあるプログラムになっていますね。😊

順を追って解説していきます。

setup() 関数

def setup():
    N, K = map(int, input().split())
    S = [int(input()) for _ in range(N)]  # 生徒のテストの得点リスト
    x = int(pow(N, 0.5))  # 平方分割のバケットの数
    x += int(N % x != 0)  # バケットの数の調整
    srd_maxes = [max(S[i*x:(i+1)*x]) for i in range(x)]
    srd_mins = [min(S[i*x:(i+1)*x]) for i in range(x)]
    Player.initialize(N, S, x, srd_maxes, srd_mins)  # クラス変数にまとめて代入
    players = [Player() for _ in range(2)]
    
    return K, players


if __name__ == '__main__':
    main(*setup())

平方分割で用意するリストは「最大値用」「最小値用」の２つです。ここまでは「平方分割」の時と書き方は変わりませんので、それを見本にして書くことができます。

今回はクラスメソッドを使ってクラス変数を初期化しています。

ほとんどの値をクラスメソッドに送りましたので、main() 関数行きの変数は K とインスタンスが入っている players の２つだけになります。

クラスメソッド

@classmethod
def initialize(cls, N, S, x, srd_maxes, srd_mins):
    cls.half_N = N / 2
    cls.S = S
    cls.x = x
    cls.srd_maxes = srd_maxes
    cls.srd_mins = srd_mins

setup() 関数からクラス変数へと送られてきた各値をクラス変数に格納します。
cls.half_N = N / 2 は『選べる生徒の数はお互い N/2 人以下』の N/2 です。これは .game() メソッドに N を引数として渡したくなかったのでここで作りました。たった一カ所使う為だけに可読性を下げたくなかったのです。ただの私の偏ったこだわりです。

クラスメソッドを作るときは @classmethod を最初に書きます。メソッドを作るごとに必ず１つ書く必要があります。それと self の代わりに cls と書きます。

ここで作られたクラス変数も「クラス変数」なのですが、クラスメソッドでクラス変数を作ると、インスタンスからは値を直接書き換えることができなくなります。値を書き換える場合はセッターを用意して、それを通じて書き換えなければなりません。これはオブジェクト指向の概念の重要な要素の１つ「カプセル化」の機能の１つだそうです。なるほど～とは思いましたが、それ以上詳しくは知りません。😅
ちなみに値を直接書き換えようとしてもエラーも何も起こりません。値に変化もなく、完全に無視されます。この性質を知らないと、デバッグ時に気付けませんので十分注意してください。

いつの間にか書き換えられるようになっていました。直接クラス名からでも self でもどちらでも書き換え可能となっています。カプセル化じゃなかったの？😅

クラスメソッドにクラス変数を作る理由は他にも「値を引数に与えてまとめて渡せる」のと、「クラス名の代わりに self. でインスタンス内から参照できるようになる」というメリットがあります。

これで準備は整いました。次は main() 関数です。

main() 関数

def main(K, players):
    for _ in range(K):
        lr = map(int, input().split())
        for player in players:
            player.game(next(lr)-1, next(lr)-1)
            
        print(judge(players[0].get_score(), players[1].get_score()))

イテレータを使って l と r を引数に振り分けています。map() 関数の戻り値も next() 関数で呼び出せるんだね。おいちゃん知らなかったよ。
このおかげで随分とスッキリした見た目になって満足です。🤗

この部分はどのように組んだらよいか少し考えたことでしょう。まずは正しく動けばどのように組んでも構わないのですが、何より自分自身がわかりにくくなってしまっては後々ストレスとなってしまいます。クセのある入力が与えられたときは iter() 関数と next() 関数を使ってみてください。😉

そしてついにゲームが開始します。

.game() メソッド

def game(self, left, right):
    if right - left + 1 > self.half_N:
        self.score = -1
        return

まずこの部分は『選べる生徒の数はお互い N/2 人以下』の判定を行なう所です。self.half_N には N / 2 が入っていて、「N/2 を超えた場合は失格」で、点数を -1点にして終了します。

N/2 以下の場合はゲーム続行です。

    max_ = -float('inf')
    min_ = float('inf')
    while left <= right:
        if self.is_within_srd_data(left, right):
            max_ = max(max_, self.srd_maxes[left // self.x])
            min_ = min(min_, self.srd_mins[left // self.x])
            left += self.x
        else:
            max_ = max(max_, self.S[left])
            min_ = min(min_, self.S[left])
            left += 1
    self.score = max_ - min_

先の問題「平方分割」と比較するとほぼ同じですね。😊
ただ、条件式は別のメソッドに移してあります。その条件式が何なのかを言葉にしたかったからです。

def is_within_srd_data(self, left, right):
    is_top = (left % self.x == 0)
    is_within_section = (left + self.x - 1 <= right)
    
    return is_top and is_within_section

それぞれの条件式にも名前をつけて、(平方分割を忘れてしまった未来の自分に)わかるようにしています。私はクラス内で条件式が長くなったり複雑すぎてわかりにくい時にはこういう書き方をしています。わかりやすい時はこういう書き方は避けます。見てすぐ理解できるものにこんなことをしても意味ありませんから。

self.score = max_ - min_

『生徒たちの (最高点 - 最低点) の値が大きい方が勝ち』ということですので、この式でゲームの点数が得られます。目立たないけどここ大事！

print(judge(players[0].get_score(), players[1].get_score()))

def judge(a, b):
    return 'A' if a > b else 'B' if a < b else 'DRAW'

最後に両者の得点を比較して勝敗を宣言します。これらを K 回勝負してゲームは終了します。

クエリ処理は入力を受け取り、その値に従って処理をするのみなのですが、処理量が膨大で時間がかなりかかってしまったり、入力値が常にわかりやすいものとは限りません。「ドーナツ」のように点と線から位置を推理🕵しなければならなかったり、入力が不規則で変数に割り振るのに苦労するのはこのメニューをこなしてきて身に染みたことでしょう。既知のアルゴリズムも必要になります。

しかしそれを考えまくってうまく処理できるようになると気持ちがいいです。方法は１つではないのでいろいろなやり方を試して経験し、柔軟な思考をもって自分なりの最適解を見つけられるようになると楽になります。あえてニッチなやり方にも挑戦してみるのも全然アリですので、たくさん改造して遊びましょう！魔改造が一番身に付きますよ！