どくしょめもきょうぎぷろぐらみんぐのてっそく

読書メモ: 競技プログラミングの鉄則

2023-03-11 08:42

2023-03-13 07:45

反復練習が必要な問題

一発で解けなかったり、AC となっても解法が良くなかったり、改善の余地があったりした問題リスト

反省会

A07 - Event Attendance

D 日間のイベントについて各参加者(N 人)がいつからいつまで参加するか入力として与えられるとき、各日の参加人数を出力する問題
直感的に日ごとの参加者数カウンタを用意し、各参加者の参加期間を加算していく方法で実装: O(N * D)

ベターな解法

参加者数の前日比カウンタを用意することにより O(N) にできる
初日から前日比カウンタをなめていけば各日の参加者数がわかる

パフォーマンスの差

C++ (GCC 9.2.1)	1000	786 Byte		162 ms	4032 KB	
C++ (GCC 9.2.1)	1000	396 Byte		944 ms	4036 KB

まとめ

累積和問題: 連続するそれぞれのデータポイントを集計したいとき、各データポイントの差分を保持する構造にすると計算量を減らせる場合がある

A08 - Two Dimensional Sum

HxW マスに数字 $X_{i,j}$ が振られている前提
マス: S(A, B), T(C, D) を角とする長方形領域の数値の総和を Q 回計算する問題
素直な実装は O(n^2) で TLE となった
- マスを配列で用意し振られた数字を素直に格納し保持
- 計算時は横方向: A → C、縦方向: B → D の二重ループで対象マスの数値の和をとるという実装

ベターな解法

下図のように普通に長方形の面積を計算するときと同じような思考をすると別のアルゴリズムが簡単に導き出せる
今回の場合、データ入力時に (0, 0) マスからの数値の和をデータとして保持しておき、算出したい座標のデータから余分なものを差し引けば O(1) で答えが計算できる
累積和は横方向の和をとったあと縦方向の和をとる形で事前計算できる（逆の順番でもよい）

パフォーマンスの差

言語	得点	コード長	結果	実行時間	メモリ	
C++ (GCC 9.2.1)	1000	1935 Byte		445 ms	13884 KB
C++ (GCC 9.2.1)	0	831 Byte		10753 ms	13932 KB

まとめ

二次元の累積和の考え方は面積計算から類推できる
逆に一次元の累積和は数直線上の長さ計算、三次元の累積和は体積計算に類推できる

A09 - Winter in ALGO Kingdom

$W$ x $H$ の領域に降った積雪量を求める問題
Q 個の降雪データが A, B, C, D の形式で与えられ、これは (A, B) および (C, D) を対角とする長方形領域に積雪が 1 あったことを示す
降雪データごとに積雪量をインクリメントする真っ直ぐな実装だと O(W・H・Q) となり TLE 判定

ベターな解法

ストレートに考えるとなかなか気づきにくい場合があるため累積和を用いるシチュエーション/パターンを覚えてしまったほうがよいかもしれない
- 1 次元の累積和としてデータを保持すると効率よく計算できる例
  - 長さ L の道路に対して N 台の車がそれぞれ Si 〜 Ei の区間通行しているとき各区間を走行した車の台数を求めよ
  - D 日間の日程の会議に対して N 人の参加者が S 日目〜 E 日目まで参加するとき各日程の参加者数を求めよ
- 2 次元の累積和としてデータを保持すると効率よく計算できる例
  - HxW のセルで表現される地域に対してセル P(A, B), Q(C, D) を対角とするエリアに雨が降った回数のデータが N 個提供されるとき、各セルで雨が降った回数を求めよ

パフォーマンスの差

C++ (GCC 9.2.1)	1000	2916 Byte		240 ms	23104 KB
C++ (GCC 9.2.1)	0	1293 Byte		11026 ms	15228 KB

まとめ

領域 [H, W] のうち、繰り返し与えられる (A, B), (C, D) の範囲に加減算を行いたい場合、演算結果を直接持つのではなく (A, B), (C+1, D+1) に演算、(A, D+1), (C+1, B) に逆演算をしたデータを蓄積し、縦横方向に累積和を取ると良い効率で問題を解けるケースがある