第144回【Python】ドーナツ

現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 144 回目です。

ドライブをよくします。運転することは苦になりません。むしろ好きです。リビングに持ち込みたくない夫婦の話をすることもあります。LunaSaki（嫁）は助手席で寝てしまえる人なので、イラっとすることもありますが、必ず一緒です。

それでは、今日も頑張ってみようと思います。

ドーナツ

あなたはドーナツ屋 paiza の店員です. この店では, チョコが埋め込まれた四角のドーナツが名物となっています.

H x W cm^2 の生地があります. これは 1 cm^2 ごとに区画されており, H x W 個の区画を持っています.
また, それぞれの区間には既にいくつかのチョコが散りばめられています.

この 1 枚の生地から四角いドーナツの形を 1 つ切り出すことができます.
具体的には次の工程をおこないます.

1. 上から y 番目、 左から x 番目の区間を中心に一辺が B cm の正方形の切れ目を入れる。
2. 上から y 番目、 左から x 番目の区間を中心に一辺が S cm の正方形の切れ目を入れることでドーナツ状の切れ目を完成させる。（S < B であることが保証されています）

生地を成す H*W 個の各区画について、その区画に含まれるチョコの数と、作る N 個のドーナツについての情報が与えられるので、各ドーナツにチョコがいくつ含まれることになるかを求めてください。
なお、 N 枚の生地について、含まれるチョコの分布は全て同じであることがわかっています。

例として、入力例 1 では、生地は 3 × 3 cm^2 であり、次の通り区画されています。

また、入力の情報から、生地には次の通りチョコが乗っていることがわかります。

左から 2 番目、上から 2 番目の区画を中心とする 3 × 3 の正方形をくり抜くと、次の図の水色の部分になります。

また、そこからさらに左から 2 番目、上から 2 番目の区画を中心とする 1 × 1 の正方形をくり抜くと、次のようなドーナツができあがります。

このドーナツに乗っているチョコの数は 40 個であるので、答えとして 40 を出力してください。

H W N
C[1][1] ... C[1][W]
...
C[H][1] ... C[H][W]
y_1 x_1 B_1 S_1
...
y_N x_N B_N S_N

・1 行目では、ドーナツの生地の縦の長さ H(cm) と横の長さ W(cm) と作るドーナツの数 N が与えられます。
・続く H 行では、生地の 1 cm^2 に含まれるチョコの数が左上から順に見た目の通りに半角スペース区切りで与えられます。
・続く N 行のうち、i 行目では、i 番目に作るドーナツの中心の生地の上からの距離 y_i (cm) と左からの距離 x_i (cm) とドーナツの外側の一辺の長さ B_i (cm) と 内側の一辺の長さ S_i (cm) が与えられます。

期待する出力

ans_1
...
ans_N

・i 行目に i 個目のドーナツに含まれるチョコの数 ans_i を出力してください。
・また、出力の末尾には改行を入れてください。

すべてのテストケースにおいて、以下の条件をみたします。

・3 ≦ H , W ≦ 1,000
・1 ≦ N ≦ 100,000
・0 ≦ C[i][j] < 10 (1 ≦ i ≦ H , 1 ≦ j ≦ W)
・1 ≦ y_i ≦ H (1 ≦ i ≦ N)
・1 ≦ x_i ≦ W (1 ≦ i ≦ N)
・0 ≦ S_i < B_i ≦ min(H,W) (1 ≦ i ≦ N)
・S_i , B_i は奇数
・くり抜けないようなドーナツの入力は与えられないことが保証されている

入力例

3 3 1
1 2 3
4 5 6
7 8 9
2 2 3 1

出力例

40

何が知りたいのだろうか。1 個のドーナツに含まれるチョコの量？ チョコの最大量や最小量を調べて、原価を計算するとか？

Python
def calc_sum(X,a,b,c):
    d = c // 2
    return X[a+d][b+d] - X[a+d][b+d-c] - X[y+d-c][b+d] + X[y+d-c][b+d-c]
    
H,W,N = map(int,input().split())
C = [[int(x) for x in input().split()] for _ in range(H)]
D = [[0] * (W+1)  for _ in range(H+1)]

for i in range(1,H+1):
    D[i] = [0] + C[i-1][:]
    for j in range(1,W+1):
        D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1]

for _ in range(N):
    y,x,B,S = map(int,input().split())
    outer = calc_sum(D,y,x,B)
    inner = calc_sum(D,y,x,S)
    print(outer - inner)

模範解答とは多少異なっていました。こっちの方がわかりやすいと思っています。個人的に。

いつも通り、手元で図を書きながら、ここからこれを引いたらここの値が出て～、とかやってました。

VBA
Sub query_primer__dount()

    HWN = Split(Cells(1, 1), " ")
    h = Val(HWN(0))
    w = Val(HWN(1))
    N = Val(HWN(2))
    
    Dim D() As Long
    ReDim D(h, w)
    
    For i = 1 To h
        temp = Split(Cells(i + 1, 1), " ")
        For j = 1 To w
            D(i, j) = temp(j - 1)
        Next
    Next
    
    For i = 1 To h
        For j = 1 To w
            D(i, j) = D(i, j) + D(i, j - 1) + D(i - 1, j) - D(i - 1, j - 1)
        Next
    Next
    
    For i = 1 To N
        temp = Split(Cells(i + h + 1, 1), " ")
        y = Val(temp(0))
        X = Val(temp(1))
        b = Val(temp(2))
        s = Val(temp(3))
        outer = calc_sum(D, y, X, b)
        inner = calc_sum(D, y, X, s)
        Debug.Print outer - inner
    Next
    
End Sub

Private Function calc_sum(L, a, b, c) As Long

    half = Application.WorksheetFunction.RoundDown(c / 2, 0)
    y = a + half
    X = b + half
    calc_sum = L(y, X) - L(y, X - c) - L(y - c, X) + L(y - c, X - c)
    
End Function

いつもの如く、境界値データテストでは、約 92 秒。Debug.Print しなければ、約 1.7 秒。

最後に

相変わらず、頑張れば、Python のコードと VBA のコード、似たようなものが書ける。いつも、結構新鮮な驚きを持って取り組めています。

実際に図を書いてみて、外側と内側の右下端がわかれば、答えを導くことができる、と気づいたときは、模範解答通りの答えを書いたつもりだったんです。違ってましたけどね。まぁ、初見で何をしているか理解するのはかなり困難かもしれません。たぶん、他の人が書いたこのコードを見せられたら、LeoSaki（旦那）は理解までにかなりの時間が必要かと思います。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki