![14
●満点解法
? Si の所が 1 でそれ以外が 0 であるような配列 A を考える
? すると、各 i について、A[Si] ~ A[Ti]の和を求めればいい
? 「ある区間の和」を高速に求めたい
? → 累積和](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-14-320.jpg)
![15
●満点解法
? B[i] = A[0] ~ A[i] の和
? という配列 B を計算しておくと、
? A[L] ~ A[R] の和 = B[R] - B[L-1]
? として区間の和を求めることができる](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-15-320.jpg)
![20
●部分点解法（40点）
? dp[i] = S の i 文字目までを作るときの最小コスト
? というDPをする
for (i = 0~N-1) {
for (j = 1~N-i) { // 使う回文の長さ
if (S[i]~S[i+j-1] が回文) {
dp[i+j] = min(dp[i+j], dp[i]+C[j])
}
}
}](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-20-320.jpg)
![22
●満点解法
? ここを O(1) で計算できるようにしたい
for (i = 0~N-1) {
for (j = 1~N-i) { // 使う回文の長さ
if (S[i]~S[i+j-1] が回文) {
dp[i+j] = min(dp[i+j], dp[i]+C[j])
}
}
}](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-22-320.jpg)
![23
●満点解法
? A[L][R] = S[L]~S[R] が回文かどうか
? というテーブルを前計算しておく
for (center = 0~N-1) {
L = R = center
while (L,R が範囲内かつ S[L] == S[R]) {
A[L][R] = 回文である
}
L = center, R = center+1
while (L,R が範囲内かつ S[L] == S[R]) {
A[L][R] = 回文である
}
}](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-23-320.jpg)
![24
●満点解法
? あるいは、メモ化再帰にする
bool isOK(L, R) {
if (すでに計算した) return メモした結果
if (L > R) return true
if (S[L] != S[R]) return false
return isOK(L+1, R-1)
}](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-24-320.jpg)
![33
●問題概要
? 色々な高さの身長を持つ社員がN人が一列に並んでいる
? 各人について，自分の左には自分の身長未満の人しかいない
状況にしたい
? 隣り合う2人は入れ替わることができる
→そのとき身長の小さいほうの身長値だけのコストがかかる
? 並び替えにかかる最小の合計コストを出力
? もしそのような状況が存在しないなら-1を出力
? 1 ≦ N ≦ 10^5
? 1 ≦ 各人の身長H[i] ≦ 10^8](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-33-320.jpg)
![35
●部分点解法(30点)
? 1≦N≦1000という部分点制約がある
? 隣接する要素H[i],H[i+1]の入れ替えにmin(H[i],H[i+1])の
コストがかかるバブルソート問題に帰着
? 無駄な入れ替えを行わない隣接要素を入れ替えるタイプの
整列プログラム(例えばバブルソート)を書けば間に合う
for(int i = 0 ; i < N-1 ; i++){
for(int j = 0 ; j+1 < N-i ; j++){
if( H[j] > H[j+1] ){
ans += H[j+1];
swap(H[j],H[j+1]);
}
}
}](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-35-320.jpg)
![38
●解法
? H[1],H[2],…,H[N]を座標圧縮する．そして各値が何番目に
来るかをX[1],X[2],…,X[N]としておく．
? セグ木のインデックスにその座標圧縮値を対応させ，
[a,b]に対する計算クエリがH[a]以上H[b]以下の要素の数に
なるように実装する．
? i=1..Nの順番に以下の処理を行う
1. H[i]より大きい値の数(セグ木の[X[i]+1,N]の区間和)を計算
2. (その計算値)×H[i]を全体的な答えに加算
3. セグ木のX[i]番目を+1する
? 全体的な答えを出力
? 算術オーバーフローに気をつけること](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-38-320.jpg)
![39
●解法
? セグ木の実装はBinary Indexed Treeが簡単
■計算量
? 座標圧縮はただのソートとユニーク処理，二分探索なので
合計でO(N log N)
? セグ木構築の空間計算量はO(N)
(※明らかに 1≦X[i]≦N (1-indexedの場合)なので)
? セグ木へのクエリにかかる時間計算量は合計でO(N log N)
? やっぱり全体として見ても
? 空間計算量 O(N)
? 時間計算量 O(N log N)](https://image.slidesharecdn.com/indeednow-finalb-150331032028-conversion-gate01/85/Indeed-B-39-320.jpg)
Indeedなう B日程 解説
- 2. 2 A: Counting on a Triangle
- 3. 3 ●問題概要 ? 上記のように，正三角形状に座標が割り振られている(無限に 広がっている) ? 座標(?, ?)の重み = ? ? ?と定義 ? A段目からB段目の範囲に含まれる座標の重みの総和を出力 ? 答えは大きくなるので109 + 7で余りを取ってください ? 1 ≦ ? ≦ ? ≦ 106 （１，１） （２，１）（２，２） （３，１）（３，２）（３，３） （４，１）（４，２）（４，３）（４，４） :
- 4. 4 ●部分点解法(20点) ? A段目からB段目の間に含まれる全ての座標を列挙 → 座標は ? + (? + 1) + … ? 個ある ? 特に最悪ケース(? = 1)では，1 + 2 + ? + ? = ? ?+1 2 個ある ? 部分点制約(1 ≦ ? ≦ ? ≦ 2000)なら間に合う （１，１） （２，１）（２，２） （３，１）（３，２）（３，３） （４，１）（４，２）（４，３）（４，４） :
- 6. 6 ●考察 ? 積の形にしてみた（足し算記号は省略） １×１ ２×１ ２×２ ３×１ ３×２ ３×３ ４×１ ４×２ ４×３ ４×４ ：
- 7. 7 ●考察 ? くくってみた ? (k段目の座標の重みの和) = k×(1+…+k) ? ここまで分かれば，高々100万回ループ回せばよさそう １×（１） ２×（１＋２） ３×（１＋２＋３） ４×（１＋２＋３＋４） ：
- 8. 8 ●解法 ? ［解法１］1からkの総和をナイーブに計算しつつ， A≦k≦Bの範囲で，総和にkをかけたものを答えに足す for文を書く ? ［解法２］k=A..Bの範囲で? × ?(?+1) 2 を足すfor文を書く (総和の公式を使っている 余りを取るタイミングに注意) ? 時間計算量はどちらも O(B) ? ［解法３］1段目からN段目までの総和S(N)の公式は 頑張ったら計算できるのでそれを用いてS(B)-S(A-1)を出力． 今回は必要ない． ? 時間計算量は O(1)
- 9. 9 ●ところで ? 今回，人によっては式に ?(?+1) 2 や ? × ?(?+1) 2 が出てきた人が いると思います． ? これらの計算結果はkが大きいと32bit整数型から溢れます． ? 64bit整数型を用いましょう． ? たとえばC++なら符号付き64bit整数型としてlong long という型が用意されています．
- 10. 10 B: How are you?
- 11. 11 ●問題概要 ? N人の社員がいる ? 社員 i は時刻 Si に出社し、時刻 Ti に退社する ? 自分がオフィスにいる間に入社した社員に対して “How are you?” と聞く ? 各社員が何回 “How are you?” と聞くかを求めよ ? 1 ≦ N ≦ 10^5 ? 1 ≦ Si < Ti ≦ 2N
- 12. 12 ●部分点解法（30点） ? N ≦ 2000 ? 素直に求める ? i,j の二重ループを回し、各 i について、 Si < Sj < Ti を満たすような j の個数を求める
- 13. 13 ●満点解法 ? N ≦ 10^5
- 14. 14 ●満点解法 ? Si の所が 1 でそれ以外が 0 であるような配列 A を考える ? すると、各 i について、A[Si] ~ A[Ti]の和を求めればいい ? 「ある区間の和」を高速に求めたい ? → 累積和
- 15. 15 ●満点解法 ? B[i] = A[0] ~ A[i] の和 ? という配列 B を計算しておくと、 ? A[L] ~ A[R] の和 = B[R] - B[L-1] ? として区間の和を求めることができる
- 16. 16 ●満点解法 ? 計算量は、 ? 前処理：O(N) ? 各 i に対する計算：それぞれ O(1) ? となり間に合う
- 18. 18 ●問題概要 ? 回文をいくつか繋いで、文字列 S を作りたい ? 長さ i の回文を使うとコストが Ci かかる ? 文字列 S を作るための最小コストは？ ? 1 ≦ N ≦ 5000
- 19. 19 ●部分点解法（40点） ? N ≦ 200
- 20. 20 ●部分点解法（40点） ? dp[i] = S の i 文字目までを作るときの最小コスト ? というDPをする for (i = 0~N-1) { for (j = 1~N-i) { // 使う回文の長さ if (S[i]~S[i+j-1] が回文) { dp[i+j] = min(dp[i+j], dp[i]+C[j]) } } }
- 21. 21 ●満点解法 ? N ≦ 5000
- 22. 22 ●満点解法 ? ここを O(1) で計算できるようにしたい for (i = 0~N-1) { for (j = 1~N-i) { // 使う回文の長さ if (S[i]~S[i+j-1] が回文) { dp[i+j] = min(dp[i+j], dp[i]+C[j]) } } }
- 23. 23 ●満点解法 ? A[L][R] = S[L]~S[R] が回文かどうか ? というテーブルを前計算しておく for (center = 0~N-1) { L = R = center while (L,R が範囲内かつ S[L] == S[R]) { A[L][R] = 回文である } L = center, R = center+1 while (L,R が範囲内かつ S[L] == S[R]) { A[L][R] = 回文である } }
- 24. 24 ●満点解法 ? あるいは、メモ化再帰にする bool isOK(L, R) { if (すでに計算した) return メモした結果 if (L > R) return true if (S[L] != S[R]) return false return isOK(L+1, R-1) }
- 25. 25 ●満点解法 ? 計算量は、 ? 前処理：O(N^2) ? DP：O(N^2) ? となり間に合う
- 26. 26 D: Game on a Grid
- 27. 27 ●問題概要 ? W×Hマスの二次元盤面がある ? 各マスには非負整数の得点が割り当てられている ? 上下左右に移動可能で，スタートとゴールが決まっている (別にゴールに入っても移動し続けてよい) ? あるマスを初めて訪問するとき， 1. (直前に居たマスの点数)×(そのマスの点数) 2. (そのマスの点数) の両方を得点として得る ? 達成できる最大得点を出力せよ． ? 1≦H,W≦100 ? 0≦各マスの得点≦100
- 28. 28 ●考察１ 全てのマスを辿る必要があるか？ ? 全部のマスを辿ったほうが良さそう？ →正しい 全得点が非負なので損することはない ? 得点が0のマスを辿る必要はないことがあるが， 辿ったと考えて損はしない ? とりあえず全マス辿るので， Σ(全マスの点数)は確保 ? 移動についてはまだ考えていない 1 1 0 1 2 3 2 2 3 ゴール地点 スタート地点 (いちおう適当な盤面の例)
- 29. 29 ●考察２ 得点の発生する移動(1) ? 得点の発生した移動のみを視覚化してみると必ず木になる ? どんな頂点から始めても任意のグリッドグラフの全域木が 作れるのでは？しかも辺の重みは無向？ →どちらも正しい(木の形をどのように仮定しても作れる) ? スタートとゴールはどうでもよい 1 1 0 1 2 3 2 2 3 ゴール地点 スタート地点 (いちおう適当な盤面の例)
- 30. 30 ●考察２ 得点の発生する移動(2) ? 移動で得られる最大得点はグリッドグラフの最大全域木 のコストに等しい(当然，辺のコストは2マスの点数の積) ? 最大全域木を求めるには，最小全域木アルゴリズムでの 大小関係を真逆にして行えばよいことが知られている ? Prim法でもKruskal法でもよい 1 1 0 1 2 3 2 2 3 ゴール地点 スタート地点 (いちおう適当な盤面の例)
- 31. 31 ●解法 ? マスを頂点，辺のコストを隣接する2マスの点数の積とした 無向グラフを考える ? 最大全域木のコストを何かしらのアルゴリズムで求める ? 最大全域木のコストにΣ(全マスの点数)を足したものを出力 ? Kruskal法を用いる場合，辺のソートをバケットソートで 行えば時間計算量 O(WH×A(WH)) ※A(n):=アッカーマン関数の逆関数 ? 通常のKruskal法でもPrim法でも O(WH log (WH))でも十分間に合う
- 32. 32 E: Line up!
- 33. 33 ●問題概要 ? 色々な高さの身長を持つ社員がN人が一列に並んでいる ? 各人について，自分の左には自分の身長未満の人しかいない 状況にしたい ? 隣り合う2人は入れ替わることができる →そのとき身長の小さいほうの身長値だけのコストがかかる ? 並び替えにかかる最小の合計コストを出力 ? もしそのような状況が存在しないなら-1を出力 ? 1 ≦ N ≦ 10^5 ? 1 ≦ 各人の身長H[i] ≦ 10^8
- 34. 34 ●自明な考察 ? 同じ身長の組が存在すれば-1を出力 ? もしそうでないとき，身長は全員相異なり 各人が昇順に並んだ状況のみが唯一の答え ? 以降のスライドでは全员の身长が相异なるものとして解説
- 35. 35 ●部分点解法(30点) ? 1≦N≦1000という部分点制約がある ? 隣接する要素H[i],H[i+1]の入れ替えにmin(H[i],H[i+1])の コストがかかるバブルソート問題に帰着 ? 無駄な入れ替えを行わない隣接要素を入れ替えるタイプの 整列プログラム(例えばバブルソート)を書けば間に合う for(int i = 0 ; i < N-1 ; i++){ for(int j = 0 ; j+1 < N-i ; j++){ if( H[j] > H[j+1] ){ ans += H[j+1]; swap(H[j],H[j+1]); } } }
- 36. 36 ●考察 ? 無駄なくバブルソートすることを考えると， ある要素の自分より大きい要素との交換回数は入れ替えの 仕方に関わらず一定 ? 先ほどのソースコードを見ても分かるように 「ある要素の自分より大きい要素との交換回数」 ×「その要素の値」 の総和が求まればよい ? 結局，実際に整列をシミュレーションしなくても，各要素に ついて，「初期状態で自分より手前にある自分より大きい 要素の数」がその要素の交換回数
- 37. 37 ●解法 ? その要素の交換回数（＝自分より手前にある自分より大き い値の要素の数）を求めていく． ? 先頭からの逐次計算であれば，これは Segment Tree(*) と 呼ばれるデータ構造を用いると高速に計算できる． (*)ここでは，「区間和の計算」「ある要素への加算クエリ」 を行える Segment Treeを指す．以降セグ木と呼ぶ．
- 38. 38 ●解法 ? H[1],H[2],…,H[N]を座標圧縮する．そして各値が何番目に 来るかをX[1],X[2],…,X[N]としておく． ? セグ木のインデックスにその座標圧縮値を対応させ， [a,b]に対する計算クエリがH[a]以上H[b]以下の要素の数に なるように実装する． ? i=1..Nの順番に以下の処理を行う 1. H[i]より大きい値の数(セグ木の[X[i]+1,N]の区間和)を計算 2. (その計算値)×H[i]を全体的な答えに加算 3. セグ木のX[i]番目を+1する ? 全体的な答えを出力 ? 算術オーバーフローに気をつけること
- 39. 39 ●解法 ? セグ木の実装はBinary Indexed Treeが簡単 ■計算量 ? 座標圧縮はただのソートとユニーク処理，二分探索なので 合計でO(N log N) ? セグ木構築の空間計算量はO(N) (※明らかに 1≦X[i]≦N (1-indexedの場合)なので) ? セグ木へのクエリにかかる時間計算量は合計でO(N log N) ? やっぱり全体として見ても ? 空間計算量 O(N) ? 時間計算量 O(N log N)
- 40. 40 ●最後に 今回は，座標圧縮の方法やセグメントツリーの実装方法に ついては長くなるので省きました． 必要となる知識である ? 座標圧縮 ? セグメントツリー ? SegmentTreeを用いたバブルソートの交換回数の計算 この３つの全ての実装方法がプログラミングコンテスト チャレンジブックに載っているので参考にするとよいでしょう