AtCoder Beginner Contest 106 D - AtCoder Express 2

目次

結論

• 制約が小さいことを利用して，区間（1次元）を座標（2次元）に置き換える．

• 二次元累積和を利用する．

はじめに

• AtCoderで出題された問題を復習しています．

• 公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います．

想定読者

• 解説を読んで解き方はわかったものの，なぜその方法を思いつけるのか？と思った方．

筆者の実力

• AtCoderのレートで茶色．

記事の特徴

• なぜその発想に至ったのか，どうしたら解法を詰められるかといった点について，筆者なりの解釈をつづります．

• 試行錯誤した過程から，得られた前提知識や着眼点を言語化していきます．

• 間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．

  • 連絡先：@k_hiro1818

問題のリンク

D - AtCoder Express 2 (400点)

発想・解法とそれらを引きだすための方法・解釈

この問題の難しいところ

• 個のクエリを高速に処理する必要がある．

最初の一歩は?

• サンプルを使って，手を動かしてみる．

• 愚直解を書いてみて，同じ処理をしている部分を特定する．

考察のキモ（Key Insight）は?

• 制約が小さいこと()を利用して，区間（1次元）を座標（2次元）に置き換える．

• 二次元累積和を利用する．

どうしたら思いつけそうか?

• 制約が小さいものに着目する．類題を解くことで，考察の引き出しを増やす．

• 特定の区間において，条件を満たす個数を求めるとき，全体から一部を除くことができるかを試す．

実装のポイントは?

• 二次元累積和の添字をバグらせやすいため，お気持ちを理解できるようにする．

PyPy3によるAC解の一例

# -*- coding: utf-8 -*-


def main():
    n, m, q = map(int, input().split())
    summed = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for _ in range(m):
        li, ri = map(int, input().split())
        summed[li][ri] += 1

    # 二次元累積和を求める
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            summed[i][j] += summed[i - 1][j]
            summed[i][j] += summed[i][j - 1]
            summed[i][j] -= summed[i - 1][j - 1]

    ans = list()

    for _ in range(q):
        pi, qi = map(int, input().split())
        count = summed[qi][qi] - summed[pi - 1][qi] - summed[qi][pi - 1] + summed[pi - 1][pi - 1]
        ans.append(count)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

得られた知識・知見

• 制約が小さいこと()を利用して，区間（1次元）を座標（2次元）に置き換える．

• 二次元累積和を利用する．

感想

• 数直線の情報を座標に置き換える発想が必要なことに，400点問題の壁を感じました．

• 二次元累積和のお気持ちについても，以前より理解できたように思います．

参考

• 公式解説

• 公式解説放送

qiita.com

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが，@k_hiro1818までご一報ください．

更新履歴

• 2019/06/28 作成
• 2019/0x/xx 更新