AtCoder Beginner Contest 106 D - AtCoder Express 2
目次
結論
制約が小さいことを利用して,区間(1次元)を座標(2次元)に置き換える.
二次元累積和を利用する.
はじめに
想定読者
- 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.
筆者の実力
- AtCoderのレートで茶色.
記事の特徴
なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.
試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.
間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).
- 連絡先:@k_hiro1818
問題のリンク
発想・解法とそれらを引きだすための方法・解釈
この問題の難しいところ
個のクエリを高速に処理する必要がある.
最初の一歩は?
サンプルを使って,手を動かしてみる.
愚直解を書いてみて,同じ処理をしている部分を特定する.
考察のキモ(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点問題の壁を感じました.
二次元累積和のお気持ちについても,以前より理解できたように思います.
参考
記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.
更新履歴
- 2019/06/28 作成
- 2019/0x/xx 更新