Upgrade to Pro — share decks privately, control downloads, hide ads and more …

About累積和

Catupper
August 22, 2013

 About累積和

ぷろ
しゅみ
るいせいき

Catupper

August 22, 2013
Tweet

More Decks by Catupper

Other Decks in How-to & DIY

Transcript

  1. そこまでの和をもつの • 累積和という概念をつかうとうまく行く – どこかからどこかまでの和のこと – 今回は一番左からそこまでの和 • 要素A[i]以左の要素の総和をS[i]とする •

    A[l] + A[l + 1] + A[l + 2]... A[r] = S[r] – S[l – 1] • S[i]をすべて保存しておけば一回引き算するだけ – 計算は100,000回だけになる
  2. 演習問題 • AOJ0231 • 重量制限がある崩れそうなヤバイ橋(ヤ橋)がある • その橋を何人かが渡ります – それぞれの渡り始め、渡り終わりの時刻 –

    それぞれの体重 – が与えられる • 崩れるか崩れないか判断してください • 崩れるならいつ崩れるか教えてください
  3. 応用問題 • AOJ0560 • Jangle, Ocean, Iceの3種類の地形からなる地図が与えら れる – 2次元 1000

    * 1000のマス目状 • ある長方形の範囲の中のJ,O,Iの数を教えてください – ということを100,000回します • うまく処理して
  4. 参考までに愚直解 • 聞かれるたびにいちいち答えるとクソおそいです – 1,000 * 1,000 * 100,000 =

    10^11 – 数分かかる • 今回の問題はO(10^6)でとけます – がんばって考えよう
  5. 答え • (0,0)を頂点にする全ての長方形の結果を持っておく – 1,000 * 1,000個 → O(10^6) –

    A[i][j]を長方形(0,0) (i, j)の結果とする • 長方形(a,b) (c,d)の結果は – A[c, d] - A[a, d] – A[c, b] + A[a, b] – 一回の計算で出せる – O(100,000)
  6. 宣伝 • 夏休みおわった直後くらいに申し込み始まります • 応募してちょ – 無料 – 参加は家から可能 –

    予選を通れば東京にタダでいける – 代表に選ばれれば台湾にタダでいける – 来年はカザフスタン
  7. その他応用問題たち • AOJ0509 – Sheets – メモリの工夫が必要 • AOJ0574 –

    Nails – DPでもとけます • AOJ0580 – Fish – 座標圧縮が必要