AtCoder:ABC106-D(AtCoder Express 2)を解いた-ぐぐりらにっき

D - AtCoder Express 2

電車が何本か走ってて、それぞれ走る区間が与えられている。

そこで、いくつかの質問に答える問題。

質問は、

ある区間の間に完全に含まれる電車の本数は？

というもの。

## 考察

問題の理解のために数直線みたいなものを書いて実験するも、よくわからず。

区間ごとに通る電車の本数をいもす法みたいな感じで足していったら何かに使えるんじゃ、とか考えたりしたけど全然違った。

今回の問題は、区間の端っこが重要な問題なので、区間に対して本数を足していくのは、その情報が失われるから使いそうにない、みたいにあたりをつけられるようになりたい。

解説を読んで、数直線ではなく二次元配列上で考えると簡単な問題に置き換わります、といわれて、はあそうですか、となった。

こんなん気付かんよ、、、と言いたくなりましたがぐっとこらえて精進。

昔から解説見てから復習として問題を解き直すときが一番メンタルやられてつらいので、やりたくないですが、次も間違えるのはもっと嫌なので復習。。。

二次元配列上に置き換えると、クエリは枠線に置き換えられて、この枠の中にある要素の和が答えになると。なるほど。

## 実装

解説にあるように、各クエリに対して$O(N)$で答えたら$O(NQ)$ですが、今回の制約なら通る！と書いてあったのでそう書いたらTLEしました。

```python
N, M, Q = map(int, input().split())
A = [[0] * N for _ in range(N)]
for _ in range(M):
    l, m = map(int, input().split())
    A[l - 1][m - 1] += 1

questions = []
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append((p - 1, q - 1))

D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

for question in questions:
    print(sum([D[i][question[1]] for i in range(question[0], question[1] + 1)]))

```

なぜ。。。
pythonだからですか？(すぐpythonのせいにする)

前処理の中でsumまでとってやればクエリに答えるときは$O(1)$でいけるようになるので、それで書き直したら間に合いました。

解説では、$(p,q)$が与えられた時は$(p,p)(p,q)(q,p)(q,q)$の4点からなる四角形に囲まれる領域(水色)に含まれる電車の本数の和、と書いてありましたが、

$(p,0)(p,q)(N,0)(N,q)$(緑色)でも別にいいはずです。

電車の区間の制約から$L_i \le R_i$なので、どうせ入っていないので。

ということで、二回累積和を計算することで前処理をしておいて、クエリに答えるときは$O(1)$で答えるようにしました。

Dを計算するところまでは上のコードと一緒で、その後先ほどsumをとっていたところを前処理しておいてTというテーブルを作っておきます。

最初に0を入れておくのは、インデックスが一個ずれるのに対応するためです。

(多分逆側から累積和をとれば引き算もしなくてすむし0をいれとくとか謎のコードを書かなくて済むはず。)

```python
T = []
for r in range(N):
    s = 0
    t = [0]
    for l in range(N):
        s += D[l][r]
        t.append(s)
    T.append(t)

for question in questions:
    print(T[question[1]][N] - T[question[1]][question[0]])

```

## 追記

Tの計算時、逆順から累積和をとる方法に直して提出してACでした

```python
T = []
for r in range(N):
    s = 0
    t = []
    for l in range(N):
        s += D[N - l - 1][r]
        t.append(s)
    T.append(list(reversed(t)))

for question in questions:
    print(T[question[1]][question[0]])

```

AtCoder:ABC106-D(AtCoder Express 2)を解いた

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT