反復練習が必要な問題

• AC A07 - Event Attendance
• TLE A08 - Two Dimensional Sum
• TLE A09 - Winter in ALGO Kingdom

反省会

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

まとめ

A12 - Printer

• ある重めの短調増加関数 f(n) の値が K より大きくなる最小の x を求める問題（n は1以上 1,000,000,000 以下の整数）
• n = 1 から順番に線形探索する方法もあるが、n がとりうる値の範囲が決まっていることを活かして二分探索をすると効率よく解ける場合がある
• 二分探索の境界値まわりのミスが出やすいので繰り返し解いて慣れておいたほうがよい