Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
About累積和
Search
Catupper
August 22, 2013
How-to & DIY
0
1.6k
About累積和
ぷろ
しゅみ
るいせいき
わ
Catupper
August 22, 2013
Tweet
Share
More Decks by Catupper
See All by Catupper
ants' roots
catupper
1
2.4k
Trianguler
catupper
0
190
sort conference
catupper
2
99
計算量の話
catupper
0
1.1k
Graph is Fun
catupper
0
130
For You
catupper
1
150
Other Decks in How-to & DIY
See All in How-to & DIY
ミニ四駆ベースのAIカー TatamiRacerの製作
covao
1
130
いぬぬウォッチャー - オレトク賞オンライン決勝 #ヒーローズリーグ
n0bisuke2
0
180
スクフェス福岡前夜祭 LT
pokotyamu
0
240
GreenPAK 初心者向けハンズオン資料
aoisaya
2
360
テストも、国際化も! 小中高生クリエータ支援プログラム『未踏ジュニア』を支える技術
yasulab
PRO
1
150
JAWS-UGについて JAWS-UG TOHOKU [青森] 弘前開催
awsjcpm
0
150
カフェでノートPCが盗難されたかどうかを検知するIoT #linedc #iotlt #obniz #protoout
n0bisuke2
1
370
AIお菓子ロッカー
keicafeblack
0
130
さらなるアウトプットに、Let's ライトニングトーク! ― LTのやり方
ma2shita
2
1k
ラズパイカメラ向け ケーブル延長基板・ハウジングの開発
koheimasaki
PRO
1
240
LT(Lightning Talk)のドキドキ感を共有する IoT ぼっとキーホルダ!
scbc1167
0
330
JAWS-UGのご紹介 JAWS-UGとは?
awsjcpm
0
5k
Featured
See All Featured
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
31
1.1k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
19
1.1k
Reflections from 52 weeks, 52 projects
jeffersonlam
349
20k
Fireside Chat
paigeccino
37
3.4k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.4k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
52
2.4k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
9
760
Site-Speed That Sticks
csswizardry
5
500
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
13
1.4k
StorybookのUI Testing Handbookを読んだ
zakiyama
29
5.6k
Transcript
なつやすみは突然に ひとなつの 競技プログラミング講座
ぱちぱちー 累積和
問題 • 長さ100,000の数列があります • いろいろな区間についてそこの合計を聞くので答えて – 100,000くらい聞く • 例: {1,
4, -1, 2, 5, 9, 10, -4, 5, 0} – 0〜7は? → 26 – 2〜4は? → 6 – 3〜9は? → 27 – …
愚直にやると? • 聞かれるたびにいちいち足して計算する – 最悪100,000 * 100,000で 10^10 – 遅い
そこまでの和をもつの • 累積和という概念をつかうとうまく行く – どこかからどこかまでの和のこと – 今回は一番左からそこまでの和 • 要素A[i]以左の要素の総和をS[i]とする •
A[l] + A[l + 1] + A[l + 2]... A[r] = S[r] – S[l – 1] • S[i]をすべて保存しておけば一回引き算するだけ – 計算は100,000回だけになる
これこそが 累積和
基本概念 • 連続した範囲の総和を持つこと • それを使うことで計算量を減らす • どう使うかはあなたが考える
たったの これだけ
演習問題 • AOJ0549 • 一直線上に宿屋がたくさんならんでいる • 旅人がその宿屋をある順番でめぐる • そのときの総移動距離を求めよ •
簡単なので考えてみて
Thinking Time • 3分で答えを考えてください • コードは実装しなくていいです
例題 • 最初は全部0の数列があります – サイズは10,000くらい • 連続した範囲に1足す操作をたくさんします – 10,000回くらい •
操作を全部し終わった後の数列の状態を教えて
わかりやすい図
ためされる頭脳 どうやってとくのか
逆転の発想 • さっきまでは、状態の累積和をとっていた • 今度はなにかの累積和が状態になるように考える • 元の状態を変えると累積和がどう変わるか考えてみる
+1してみる • 累積和する前のもの • 累積和をとった後
考察 • 累積和前の数列に1を足すとそれ以降全てが一様にたさ れる • 連続した範囲に一様に値を足すことの代わりになる – だけど余計なところまでたされてしまう • 余計なところは-1して帳尻をあわせる
-1でちょうじりあわせ • 累積和する前のもの • 累積和をとった後
これが港でゆうめいな いもす法
演習問題 • AOJ0231 • 重量制限がある崩れそうなヤバイ橋(ヤ橋)がある • その橋を何人かが渡ります – それぞれの渡り始め、渡り終わりの時刻 –
それぞれの体重 – が与えられる • 崩れるか崩れないか判断してください • 崩れるならいつ崩れるか教えてください
Thinking Time • 5分で答えを考えてください • コードは実装しなくていいです – ちょっとむずいです • わかった人は前に出て発表
– 先着1名
次元をこえて 2次元への応用
考え方はいっしょ • 累積和のつよみ – 1次元配列よりも2次元配列で本領を発揮する • 考え方は変わらないのでとりあえず例題
応用問題 • AOJ0560 • Jangle, Ocean, Iceの3種類の地形からなる地図が与えら れる – 2次元 1000
* 1000のマス目状 • ある長方形の範囲の中のJ,O,Iの数を教えてください – ということを100,000回します • うまく処理して
参考までに愚直解 • 聞かれるたびにいちいち答えるとクソおそいです – 1,000 * 1,000 * 100,000 =
10^11 – 数分かかる • 今回の問題はO(10^6)でとけます – がんばって考えよう
Thinking Time • 5分で答えを考えてください • コードは実装してもいいです – 時間かかるのでせんでもいいです • わかった人は前に出て発表
– 先着1名
答え • (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)
ちなみに 日本情報オリンピック 2010 本選第一問
宣伝 • 夏休みおわった直後くらいに申し込み始まります • 応募してちょ – 無料 – 参加は家から可能 –
予選を通れば東京にタダでいける – 代表に選ばれれば台湾にタダでいける – 来年はカザフスタン
その他応用問題たち • AOJ0509 – Sheets – メモリの工夫が必要 • AOJ0574 –
Nails – DPでもとけます • AOJ0580 – Fish – 座標圧縮が必要