![C-部分点1
● 蛍光灯をl_iが小さい順にソートする
– 以降iにはこのソート後のインデックスを採用する
● dp[i][j] = i番目以前の蛍光灯を使って西から距離
ｊのところまでの全体を照らす費用の最小値
– という値を動的計画法で求める
● もしjがl_iとr_iの間にあるならば
dp[i][j] = min{dp[i-1][k] + c_i (kはl_iとr_iの間)}
ないならば
dp[i][j] = dp[i – 1][j]
という漸化式が成り立つ](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-15-320.jpg)
![C-DPの更新の仕方
● l_iとr_iの間のjに対して
dp[i][j] = min{dp[i-1][k] + c_i (kはl_iとr_iの間)}
● kをl_iからr_iまで順番に動かすときに、今まで
通過したdp[i-1][k]の最小値を更新していく
– dp[i][k] = その最小値 + c_iとなる
● dp[i]を全て求めるのにO(L)
● iはN種類なので、合計でO(NL)
– 部分点1(N,L≦3,000)が得られる](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-16-320.jpg)
![C-DP擬似コード
for(int i = 0;i < n;i++){
//dp[i-1][k]の最小値を保存する変数tmpmin
int tmpmin = 99999999;
for(int j = 0;j <= L;j++){
if(j < l[i] || k > r[j]){
dp[i][j] = dp[i - 1][j];
}
}
for(int k = l[i];k <= r[i];k++){
dp[i][k] = min(dp[i][k], tmpmin + c[i]);
tmpmin = min(tmpmin, dp[i][k]);
}
}](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-17-320.jpg)
![C-考察
● 先ほどのDPは2次元配列を使っているが、dp[i]
はdp[i – 1]しか参照しない
– 1次元配列で管理することができる
● 新しいdp配列
– dp[i] = 西端から距離iのところまでの全体を照らす
のに必要な費用の最小値](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-18-320.jpg)
![C-擬似コード2
for(int i = 0;i < n;i++){
//dp[i]の最小値を保存する変数tmpmin
int tmpmin = 99999999;
for(int k = l[i];k <= r[i];k++){
tmpmin = min(tmpmin, dp[i][k]);
}
dp[r[i]] = min(dp[r[i]], tmpmin + c[i]);
}](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-20-320.jpg)
![C-高速化
● 操作の種類は
– dp[r[i]]の更新
– dp[l[i] ～ r[i]]のなかの最小値を求める
● これはRMQなのでセグメントツリーがうまく
利用できる](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-21-320.jpg)
![C-擬似コード3
for(int i = 0;i < n;i++){
int tmp = getmin(l[i], r[i])
//dp[l[i]～r[i]]の最小値をsegtree等で求める
setnum(r[i], min(r[i], tmp + c[i]));
//dp[r[i]]の値を更新
}](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-22-320.jpg)
![C-高速化
● 各蛍光灯についてO(logL)でdp[r[i]]を更新する
● 計算量はO(NlogL)
– 満点が得られる](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-33-320.jpg)
![C-参考
● 実はmin(l[i], r[i]) は min(l[i], L)としてもよい
– 予めソートしてあるので、i番目の蛍光灯を見てい
る時、l[j] > l[i]となる蛍光灯jはまだ処理されてい
ない
– l[i] ～ Lと重なっている蛍光灯は、l[i] ～ r[i] と重
なっている蛍光灯のみであり、その他余計な蛍光灯
は重なっていない
● よってL側を片端とするBITでACすることがで
きる
● 計算量はセグメントツリーと同様](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-35-320.jpg)
![連結判定 方法１
? 適当な頂点を選び、その頂点を含む連結成分の大き
さをDFSなどで計算し、それがNであれば連結
bool used[N]; // falseで初期化
int dfs(int v){
if(used[v]) return 0;
used[v] = true;
int count = 1;
for(Edge e : vから出ている辺){
count += dfs(e.to);
}
return count;
}
連結成分の大きさを求める例：
3/13](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-39-320.jpg)
![Union Find 木
? 実装例 (ならし計算量O(α(N)))
int parent[N];
void init(){
for(int i = 0; i < N; ++i) parent[i] = -1;
}
int root(int x){
if(parent[x] == -1) return x;
return parent[x] = root(parent[x]);
}
void unite(int x, int y){
x = root(x); y = root(y);
if(parent[x] < parent[y]) swap(x,y);
if(parent[x] == parent[y]) parent[x]--;
parent[y] = x;
}
6/13](https://image.slidesharecdn.com/arc026-140628083000-phpapp01/85/AtCoder-Regular-Contest-026-42-320.jpg)
AtCoder Regular Contest 026 解説
- 1. AtCoder Regular Contest 026 解説 AtCoder株式会社 2014/6/28 1
- 3. 問題概要 ? 高橋君は１問の問題を解くのに ?普段：A分かかる ?ダイナミックなポーズをとりながら：B分かかる ? 体力の消耗が激しいので、ダイナミックなポーズを とりながら解ける問題は５問まで。 ? N問の問題を解くのにかかる最短時間は？ ? 1 N 10, 1 B < A 60 1/4
- 4. 解法 ? B < Aなので、可能な限りダイナミックなポーズを とりながら解いたほうが良い。 ? じゃあ答えは、5*B+(N-5)*A？ （５問をダイナミックなポーズをとりながら解き、 残りの問題を普段通りに解く） →?それは間違い 2/4
- 5. 解法 ? 5*B+(N-5)*A はダメ。 ? Nが5より小さい時はダイナミックなポーズはN回し かしなくて良い。 ? というようにNが５より大きいか小さいか、 つまり、５回の上限までダイナミックなポーズをと るかどうかで場合分けをしてあげればいい。 if(N < 5) answer = N*B; else answer = 5*B+(N-5)*A; 3/4
- 6. 別のやり方 ? のようにダイナミックなポーズをとる回数を計算し てから答えを計算するというような方法も考えられ ます。 num_dynamic = min(N,5); answer = num_dynamic*B + (N-num_dynamic)*A; 4/4
- 8. B-問題概要 ● 与えられた整数 が完全数か、不足数か、過剰 数か、判定せよ ● 部分点1 ● 部分点2 N 1≤N≤10 5 1≤N≤10 10
- 9. B-基本的発想 ● 約数を全て調べて、総和を求めて、元の数字と の大小を調べたい ● 約数を出来るだけ速く全列挙するのが目標 ● 「自分以外の約数」というのが少し厄介 ● 自分を含めた約数の総和を求めて自分の2倍と の大小を比べれば面倒な処理はしなくて良い
- 10. B-約数の全列挙1 ● 整数 の約数は 以下なので、 以下の全ての整 数について、それが の約数かどうかを調べれ ば良い ● 計算量は – 部分点1が得られる N N N N N O(N)
- 11. B-約数の全列挙2 ● が の約数ならば、 も の約数 ● か の片方がわかれば、もう片方もすぐに 分かる。 – 小さい方だけを調べれば良い ● となる条件は ● √ 以下の約数を調べるだけで良い ● 計算量は (√ ) – 満点が得られる A A A≤N / A A N N / A N N / A A 2 ≤N N NO
- 12. B-注意点 ● が平方数の時 となる が存在する – 誤って を2回足さないように気をつけなければな らない ● 小課題2の入力が明らかにint型に収まらないの で、C等の言語を使っている方は気をつけま しょう N A=N / A A A
- 13. ARC024解説 C:蛍光灯
- 14. C-問題概要 ● 長さがLの廊下にN個の蛍光灯がある ● i番目の蛍光灯はc_iの費用で点ける事ができる ● i番目の蛍光灯をつけると西からの距離がl_i以上 r_i以下の範囲が照らされる ● 廊下全体を照らすための最小費用を求めよ ● 1 ≦ N ≦ 100,000 ● 1 ≦ L ≦ 100,000 ● 1 ≦ c_i ≦ 100,000
- 15. C-部分点1 ● 蛍光灯をl_iが小さい順にソートする – 以降iにはこのソート後のインデックスを採用する ● dp[i][j] = i番目以前の蛍光灯を使って西から距離 ｊのところまでの全体を照らす費用の最小値 – という値を動的計画法で求める ● もしjがl_iとr_iの間にあるならば dp[i][j] = min{dp[i-1][k] + c_i (kはl_iとr_iの間)} ないならば dp[i][j] = dp[i – 1][j] という漸化式が成り立つ
- 16. C-DPの更新の仕方 ● l_iとr_iの間のjに対して dp[i][j] = min{dp[i-1][k] + c_i (kはl_iとr_iの間)} ● kをl_iからr_iまで順番に動かすときに、今まで 通過したdp[i-1][k]の最小値を更新していく – dp[i][k] = その最小値 + c_iとなる ● dp[i]を全て求めるのにO(L) ● iはN種類なので、合計でO(NL) – 部分点1(N,L≦3,000)が得られる
- 17. C-DP擬似コード for(int i = 0;i < n;i++){ //dp[i-1][k]の最小値を保存する変数tmpmin int tmpmin = 99999999; for(int j = 0;j <= L;j++){ if(j < l[i] || k > r[j]){ dp[i][j] = dp[i - 1][j]; } } for(int k = l[i];k <= r[i];k++){ dp[i][k] = min(dp[i][k], tmpmin + c[i]); tmpmin = min(tmpmin, dp[i][k]); } }
- 18. C-考察 ● 先ほどのDPは2次元配列を使っているが、dp[i] はdp[i – 1]しか参照しない – 1次元配列で管理することができる ● 新しいdp配列 – dp[i] = 西端から距離iのところまでの全体を照らす のに必要な費用の最小値
- 19. C-考察 ● 実際に費用が最小になる蛍光灯の置き方を考え てみる ● 必ずr_iがとなりの蛍光灯の区間（両端含む）と 重なる – 诲辫では谤冲颈の位置のみ更新すれば良い
- 20. C-擬似コード2 for(int i = 0;i < n;i++){ //dp[i]の最小値を保存する変数tmpmin int tmpmin = 99999999; for(int k = l[i];k <= r[i];k++){ tmpmin = min(tmpmin, dp[i][k]); } dp[r[i]] = min(dp[r[i]], tmpmin + c[i]); }
- 21. C-高速化 ● 操作の種類は – dp[r[i]]の更新 – dp[l[i] ～ r[i]]のなかの最小値を求める ● これはRMQなのでセグメントツリーがうまく 利用できる
- 22. C-擬似コード3 for(int i = 0;i < n;i++){ int tmp = getmin(l[i], r[i]) //dp[l[i]～r[i]]の最小値をsegtree等で求める setnum(r[i], min(r[i], tmp + c[i])); //dp[r[i]]の値を更新 }
- 23. 颁-入出力例3図解
- 24. 颁-入出力例3図解
- 25. 颁-入出力例3図解
- 26. 颁-入出力例3図解
- 27. 颁-入出力例3図解
- 28. 颁-入出力例3図解
- 29. 颁-入出力例3図解
- 30. 颁-入出力例3図解
- 31. 颁-入出力例3図解
- 32. 颁-入出力例3図解
- 34. C-参考 ● セグメントツリーに似たデータ構造でBITとい うものがある – 比較的楽に実装できる ● BITは基本的にRMQはできないが、いくつかの 制約のもとで処理できる 1.値の更新は、もとより値が小さくなるもののみ 2.求める範囲の左端は0でなければならない ● 今回1つめの条件は満たしている ● 2つめの条件を満たすようにすればBITを使うこ とができる
- 35. C-参考 ● 実はmin(l[i], r[i]) は min(l[i], L)としてもよい – 予めソートしてあるので、i番目の蛍光灯を見てい る時、l[j] > l[i]となる蛍光灯jはまだ処理されてい ない – l[i] ～ Lと重なっている蛍光灯は、l[i] ～ r[i] と重 なっている蛍光灯のみであり、その他余計な蛍光灯 は重なっていない ● よってL側を片端とするBITでACすることがで きる ● 計算量はセグメントツリーと同様
- 36. D問題 道を直すお仕事
- 37. 問題概要 ? N頂点M辺のグラフが与えられる ? 各辺はC,Tの二つの値を持っている ? グラフが連結になるように辺を選ぶとき、 Cの総和/Tの総和 の最小値は？ ? 1 N,M 10^4, 1 Ci,Ti 10^6 1/13
- 38. 20点解法 (M 16) ? それぞれの辺を修理するかどうかを全て試す ? 各辺につき、する/しないの２通りがあるので全部 で2^M通りのパターンがあり得る ? グラフが連結になるような辺の選び方のうち、 Cの和/Tの和が最小となるものが答え 2/13
- 39. 連結判定 方法１ ? 適当な頂点を選び、その頂点を含む連結成分の大き さをDFSなどで計算し、それがNであれば連結 bool used[N]; // falseで初期化 int dfs(int v){ if(used[v]) return 0; used[v] = true; int count = 1; for(Edge e : vから出ている辺){ count += dfs(e.to); } return count; } 連結成分の大きさを求める例： 3/13
- 40. 連結判定 方法２ ? 以下のアルゴリズムのように、連結成分を集合とし て管理する ? これを実現するためのデータ構造として、 Union Find 木を使う 各頂点に対し、その頂点のみを含む集合を作る for(Edge e : 修理することにした辺){ e.fromが属する集合とe.toが属する集合を合併する } 全ての頂点が同じ集合に属しているかをチェックする 4/13
- 41. Union Find 木 ? 以下の２つの操作が出来るデータ構造 ?ある要素がどの集合に属しているかを調べる ?２つの集合を合併する ? 要素を頂点とした木構造で集合を管理する ? 各頂点は親への辺を持っておく ? 根の要素をその集合の代表と考える ? 詳細は以下のスライドが分かりやすいと思います http://www.slideshare.net/iwiwi/ss-3578491 5/13
- 42. Union Find 木 ? 実装例 (ならし計算量O(α(N))) int parent[N]; void init(){ for(int i = 0; i < N; ++i) parent[i] = -1; } int root(int x){ if(parent[x] == -1) return x; return parent[x] = root(parent[x]); } void unite(int x, int y){ x = root(x); y = root(y); if(parent[x] < parent[y]) swap(x,y); if(parent[x] == parent[y]) parent[x]--; parent[y] = x; } 6/13
- 43. 20点解法 (M 16) ? 辺の選び方を全て試すためにはビット演算を利用す ると書きやすい ? あわせて計算量はO(2^M * N)となり、この部分点 を得ることが出来ます for(int i = 0; i < 1<<M; ++i){ // 選び方を全て試す for(int j = 0; j < M; ++j){ if((i>>j&1) == 1) j本目の辺は今選ばれている } } 7/13
- 44. 満点解法 (M 10000) ? 答えで二分探索 ? ΣCi / ΣTi x となるような最小のxが答え ? 小数の二分探索は収束判定が難しいので、 50回だけ探索するというようにすると良い。 8/13
- 45. 二分探索 ? ΣCi / ΣTi x を式変形をすると??? ? ΣCi / ΣxTi 1 → ΣCi ΣxTi → ΣCi-xTi 0 ? 辺ごとに独立して計算できるようになる！ 9/13
- 46. 二分探索 ? ΣCi-xTi 0 を満たすような辺の選び方があるかど うかを判定したい ? Ci-xTi 0となる辺は全て選んで良い ? グラフが連結になるように、残ったCi-xTi > 0の辺 からいくつかの辺を選ぶ。 → 最小全域木問題のアルゴリズムが使えそう 10/13
- 47. クラスカル法 ? クラスカル法：最小全域木を求めるアルゴリズム 連結成分の管理にはUnion Find 木を使うと良い answer = 0 for(Edge e : 辺をコストの昇順に){ if(e.fromとe.toが違う連結成分に属している){ answer += e.cost e.fromの連結成分とe.toの連結成分を合併する } } 11/13
- 48. 最小コストを求める ? 今回の問題は最小全域木問題とは少しだけ違います が、似たようなアルゴリズムで解くことが出来ます answer = 0 for(Edge e : 辺をコストの昇順に){ // コスト = c-xt if(e.fromとe.toが違う連結成分に属している または e.cost < 0){ answer += e.cost e.fromの連結成分とe.toの連結成分を合併する } } 12/13
- 49. 満点解法 (M 10000) ? 二分探索で探索する回数をKとすると、 ? 計算量はO(K M log M)となり、Kが100程度でも 満点を得ることが出来る。 13/13