![A-問題概要
● N個の得点 S[0], S[1], … が与えられる
● 平均が A, 最大と最小の差がBとなるように線形
変換せよ
– 線形変換とはある実数P,QにたいしてXをPX+Qに
する変換](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-2-320.jpg)
![B-考察
● 4つではなくて2つの場合はどうか？
– 2つのうち小さい方が X である場合の数 A[x] を求
めたい
– 大きい方となれるのは 2X 以上の値
– よって A[x] は2X以上の値の数の個数
– 予めソートしていれば容易に求めることが出来る
● 二分探索 (最悪O(logN))
● しゃくとり法 (平均O(1))](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-10-320.jpg)
![B-考察
● 4つではなくて2つの場合はどうか？
– 2つのうち大きい方が X である場合の数 B[x] を求
めたい
– A[x]と全く同様の方法で求めることが出来る
● 二分探索 (最悪O(logN))
● しゃくとり法 (平均O(1))](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-11-320.jpg)
![B-部分点1
● 2番目に小さい値 x と3番目に小さい値 y を全
通り試す
– この2つが固定されている時、選び方の通り数は
2x ≦ y ならば B[x] × A[y]
そうでないならば 0
– xとyの組は全部でO(N^2)ある
● 計算量は O(N^2)
● 部分点 (50点) 獲得](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-12-320.jpg)
![B-考察
● 部分点解法は何か無駄がありそう
– 以下のように言い換えることが出来る
● 2番目に小さい値 xを固定する
– 2x ≦ yとなるすべてのyに対して
B[x] × A[y]
の総和をとる
– 2x ≦ yとなるすべてのyに対するA[y]の総和を
Asum[2x]とすると
B[x] × Asum[2x]](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-13-320.jpg)
![B-考察
● Asum[2x]が高速で求まればO(N)で答えを求め
ることが出来る
● Asumはsumの累積和なので、O(N)で全要素を
前計算することが出来る
– Asum[max(y)] = sum[max(y)]
– Asum[x] = Asum[x + 1] + Asum[x]](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-14-320.jpg)
![B-満点解法
● x ≦ y を満たすyに対する A[y]の総和 Asum[y]を
累積和で前計算する
● 2番目に小さい値 x を固定した時の場合の数は
B[x] × Asum[y]
● すべての x に対して計算して総和を取る](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-15-320.jpg)
![C-問題概要
● [1,2,..,N]を並び替えたものを「順列」という
● 2つの順列の「転倒距離」とは2つで順序が入
れ替わっている数字の組の個数である
● 2つの順列A,Bが与えられるので、どちらとも転
倒距離が等しい順列を1つ挙げよ
● N ≦ 10^5](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-17-320.jpg)
![C-考察2
● 数字の大小は転倒距離とは関係ないので、Aが
[1,2,…,N]となるように数字を置換しても構わ
ない
● 例
– A:[3, 1, 4, 2, 5], B:[2, 5, 1, 3, 4]
– 3→1, 1→2, 4→2, 2→3, 5→5というふうに変換
– A:[1, 2, 3, 4, 5], B[3, 5, 2, 1, 2]](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-21-320.jpg)
![C-考察2
● Aが[1, 2, … ,N]になったのでBとの転倒距離が
計算しやすくなった
– 各数字について、それ以左にあるそれ以上の数字の
個数を数えれば良い
● これはBの転倒数
– バブルソートにおける交換回数と一致することで有
名
– つまりBをバブルソートしていくと少しずつAとの
転倒距離が縮み、元のBとの転倒距離が伸びる](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-22-320.jpg)
![C-満点解法
● バブルソートにおける「隣り合う2つの要素の
交換」をいちいちやらずに、いくつかまとめて
処理する
● バブルソートをダイジェストで見ると以下のよ
うになる
– [6, 1, 4, 2, 3, 5]
– [1, 6, 4, 2, 3, 5]
– [1, 2, 6, 4, 3, 5]
– [1, 2, 3, 6, 4, 5]
– [1, 2, 3, 4, 6, 5]
– [1, 2, 3, 4, 5, 6]
1回交換
2回交換
2回交換
1回交換
1回交換
↓これらの値がわかっていれば交換の操作を
スキップできる
実はxを正しい位置まで
動かすときの交換回数
は、初めの数列におけ
るx以左のxより大きい
値の個数と一致する](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-24-320.jpg)
![C-考察
● ある数列における x 以左のxより大きい値の個
数を高速に求める有名なデータ構造があった
– BITやセグメントツリー
● 上記データ構造で以左に現れたかどうかのフラ
グを管理しながら左から順番に走査する
● [3, 5, 4, 2, 6, 1]を例に実際に走査してみる](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-25-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 0 0 0 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-26-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 0 0 0 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
0
確定
総和 = 0](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-27-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 1 0 0 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
0
更新](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-28-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 1 0 0 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
0 0
確定
総和 = 0](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-29-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 1 0 1 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
0 0
更新](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-30-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 1 0 1 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
0 1 0
確定
総和 = 1](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-31-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 1 1 1 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
0 1 0
更新](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-32-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 0 1 1 1 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
3 0 1 0
確定
総和 = 3](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-33-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 1 1 1 1 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
3 0 1 0
更新](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-34-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 1 1 1 1 0
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
3 0 1 0 0
確定
総和 = 0](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-35-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 1 1 1 1 1
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
3 0 1 0 0
更新](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-36-320.jpg)
![C-考察
● [3, 5, 4, 2, 6, 1]
↑
以左に現れたかどうかのフラグ
1 2 3 4 5 6
0 1 1 1 1 1
x以左に現れたxより大きい値の個数
1 2 3 4 5 6
5 3 0 1 0 0
確定
総和 = 5](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-37-320.jpg)
![D-問題概要
● 数直線上で原点からの距離が1以上N以下の整
数である場所に空き家がある
● M世帯の家族を1つの家に複数の世帯が割り当
てられないように振り分ける
– i番目の家族がA[i]に割り振られたとする
● i世帯目の家族の構成人数をP[i]とする
● (1 ≦ i, j ≦ M)を満たすすべての対(i, j)に対する
|A[i] – A[j]| * P[i] * P[j]の総和が最大になるよう
に割り振った時のその値を求めよ](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-40-320.jpg)
![D-式変形
● |A[i] - A[j]| * P[i] * P[j]
● 空き家達を以下のように捉える](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-43-320.jpg)
![D-式変形
● |A[i] - A[j]| * P[i] * P[j]
● 空き家達を以下のように捉える
– A[i]とA[j]の間には|A[i] – A[j]|個の「辺」がある](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-44-320.jpg)
![D-式変形
● |A[i] - A[j]| * P[i] * P[j]
● 空き家達を以下のように捉える
– A[i]とA[j]の間には|A[i] – A[j]|個の「辺」がある
– それぞれにP[i] * P[j] を足すと考えてみる](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-45-320.jpg)
![D-式変形 整理
● 各辺について、以左の総和と以右の総和の積を
とる
● さらにその総和をとれば求めるもの
● i番目の家以左にいる人の総和を sum[i]、すべ
ての家族を合わせた人数をAllとすると求める値
は
– Σ sum[i] * (All - sum[i])](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-50-320.jpg)
![D-帰着される問題
● 正整数列A(1-index)が与えられる。総和はSum
である。
● S[i] = A[1] + A[2] + … + A[i] とする
● Aを並び替えたときの以下の値の最大値を求め
よ
Σ S[i] * (Sum - S[i])](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-52-320.jpg)
![D-考察
● a < b > c が成立している時、bはどちらか一方
と交換することが出来る
– a < b > c となる部分を含まないような最適解が存
在する
● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n]
となるような最適解が存在する](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-59-320.jpg)
![D-考察
● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n]
● このパターンの並び替えを探索する一般的なテ
クニックがある
● DP[i][x] = Aの中で大きい方からi番目までを左
右に振り分けて、左側の総和がxのときの何ら
かの値の最大(小)値
● Aの中で大きい物から順番に左もしくは右に振
り分けていくイメージ](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-60-320.jpg)
![D-考察
● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n]
● このパターンの並び替えを探索する一般的なテ
クニックがある
● DP[i][x] = Aの中で大きい方からi番目までを左
右に振り分けて、左側の総和がxのときの何ら
かの値の最大(小)値
● Aの中で大きい物から順番に左もしくは右に振
り分けていくイメージ](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-61-320.jpg)
![D-考察
● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n]
● このパターンの並び替えを探索する一般的なテ
クニックがある
● DP[i][x] = Aの中で大きい方からi番目までを左
右に振り分けて、左側の総和がxのときの何ら
かの値の最大(小)値
● Aの中で大きい物から順番に左もしくは右に振
り分けていくイメージ
どんな値？](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-62-320.jpg)
![D-帰着される問題（再掲）
● 正整数列A(1-index)が与えられる。総和はSum
である。
● S[i] = A[1] + A[2] + … + A[i] とする
● Aを並び替えたときの以下の値の最大値を求め
よ
Σ S[i] * (Sum - S[i])](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-63-320.jpg)
![D-帰着される問題（再掲）
● 正整数列A(1-index)が与えられる。総和はSum
である。
● S[i] = A[1] + A[2] + … + A[i] とする
● Aを並び替えたときの以下の値の最大値を求め
よ
Σ S[i] * (Sum - S[i])](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-64-320.jpg)
![D-満点解法
● DP[i][x] = Aの大きい方からi番目までを左右に
振り分けて左側の総和がxで在るときのもう定
まってる S[i] * (Sum - S[i])の総和の最大値](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-65-320.jpg)
![D-満点解法
● DP[i][x] = Aの大きい方からi番目までを左右に
振り分けて左側の総和がxで在るときのもう定
まってる S[i] * (Sum - S[i])の総和の最大値
– DP[i][x]は以下の様な全ての状態の中で「決まって
いるS[i] * (Sum – S[i])の総和」の最大値](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-66-320.jpg)
![D-満点解法
● DP[i][x] = Aの大きい方からi番目までを左右に
振り分けて左側の総和がxで在るときのもう定
まってる S[i] * (Sum - S[i])の総和の最大値
– DP[i][x]は以下の様な全ての状態の中で「決まって
いるS[i] * (Sum - S[i])の総和」の最大値](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-67-320.jpg)
![D-満点解法
● DP[N][0], DP[N][1], … ,DP[N][Sum] の中で最大
の物を探せば良い？
– 残念ながらNのオーダーは10^6なので間に合わな
い](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-68-320.jpg)
![D-満点解法
● DP[N][0], DP[N][1], … ,DP[N][Sum] の中で最大
の物を探せば良い？
– 残念ながらNのオーダーは10^6なので間に合わな
い
● 実はほとんどが0人家族である
– A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n]
この制約のために0人家族は真ん中のあたりに固
まっている
– これらだけ別処理すれば良い
– NがMまで減る（Mのオーダーは10^3)](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-69-320.jpg)
![D-満点解法
● 0人家族の別処理
– 以下のように0人家族のあたりの辺には全く同じ値
が足される
– この値はxから求まるのでDP[m][x]ごとに別々に計
算してやればDP[n][x]に相当するものが求まる](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-72-320.jpg)
![D-満点解法まとめ
● DP[i][x] = 大きいほうからi番目までで左の総和
がxになるように置いた時の値が決まっている
辺の総和の最大値
● DP[m][x]まで求めて、0人家族の辺は別処理
– mのオーダーは10^3, xのオーダーは10^5なので配
列を普通に確保するとMLEしてしまう
– I に関しては昇順に操作し、更新時 i – 1しか参照し
ないのでメモリをリサイクルできる
– 空間計算量はO(10^5)
– 時間計算量はO(10^8)](https://image.slidesharecdn.com/arc043upload-150815133010-lva1-app6891/85/AtCoder-Regular-Contest-043-73-320.jpg)
More Related Content
What's hot (20)
Viewers also liked (20)
Similar to AtCoder Regular Contest 043 解説 (9)
More from AtCoder Inc. (20)
Recently uploaded (6)
AtCoder Regular Contest 043 解説
- 2. A-問題概要 ● N個の得点 S[0], S[1], … が与えられる ● 平均が A, 最大と最小の差がBとなるように線形 変換せよ – 線形変換とはある実数P,QにたいしてXをPX+Qに する変換
- 3. A-考察 ● すべてをP倍すると – 平均 P倍される – 最大と最小の差 P倍される ● すべてにQ足すと – 平均 Q足される – 最大と最小の差 変わらない
- 4. A-解法 ● 最大と最小の差がBになるように適切なPを探 す – その後すべてをP倍する ● 平均がAになるように適切なQを探す – その後すべてにQを足す ● すべての得点が適切に変換できている – O(N)
- 5. A-具体的数式 ● 変換前の得点の平均をE,最大と最小の差をDと すると ● P = B / D ● Q = A – (EP) = A – (EB/D)
- 6. A-注意点 ● 変換前の得点の平均をE,最大と最小の差をDと すると ● P = B / D ● Q = A – (EP) = A – (EB/D)
- 7. A-割り算には要注意 ● 変換前の得点の平均をE,最大と最小の差をDと すると ● P = B / D ● Q = A – (EP) = A – (EB/D) ● D = 0のとき、つまり全得点が同じ時、適切なP が存在しない – コーナーケース
- 9. B-問題概要 ● 要素数 N の正数列が与えられる ● 次の条件をみたすように 4 つ要素を選ぶ方法の 通り数を求めよ – 2番目に小さい値は1番目に小さい値の 2 倍以上 – 3番目に小さい値は2番目に小さい値の 2 倍以上 – 4番目に小さい値は3番目に小さい値の 2 倍以上 ● MOD 1,000,000,0007 ● N ≦ 10^5
- 10. B-考察 ● 4つではなくて2つの場合はどうか？ – 2つのうち小さい方が X である場合の数 A[x] を求 めたい – 大きい方となれるのは 2X 以上の値 – よって A[x] は2X以上の値の数の個数 – 予めソートしていれば容易に求めることが出来る ● 二分探索 (最悪O(logN)) ● しゃくとり法 (平均O(1))
- 11. B-考察 ● 4つではなくて2つの場合はどうか？ – 2つのうち大きい方が X である場合の数 B[x] を求 めたい – A[x]と全く同様の方法で求めることが出来る ● 二分探索 (最悪O(logN)) ● しゃくとり法 (平均O(1))
- 12. B-部分点1 ● 2番目に小さい値 x と3番目に小さい値 y を全 通り試す – この2つが固定されている時、選び方の通り数は 2x ≦ y ならば B[x] × A[y] そうでないならば 0 – xとyの組は全部でO(N^2)ある ● 計算量は O(N^2) ● 部分点 (50点) 獲得
- 13. B-考察 ● 部分点解法は何か無駄がありそう – 以下のように言い換えることが出来る ● 2番目に小さい値 xを固定する – 2x ≦ yとなるすべてのyに対して B[x] × A[y] の総和をとる – 2x ≦ yとなるすべてのyに対するA[y]の総和を Asum[2x]とすると B[x] × Asum[2x]
- 14. B-考察 ● Asum[2x]が高速で求まればO(N)で答えを求め ることが出来る ● Asumはsumの累積和なので、O(N)で全要素を 前計算することが出来る – Asum[max(y)] = sum[max(y)] – Asum[x] = Asum[x + 1] + Asum[x]
- 15. B-満点解法 ● x ≦ y を満たすyに対する A[y]の総和 Asum[y]を 累積和で前計算する ● 2番目に小さい値 x を固定した時の場合の数は B[x] × Asum[y] ● すべての x に対して計算して総和を取る
- 16. ARC043解説 C:転倒距離
- 17. C-問題概要 ● [1,2,..,N]を並び替えたものを「順列」という ● 2つの順列の「転倒距離」とは2つで順序が入 れ替わっている数字の組の個数である ● 2つの順列A,Bが与えられるので、どちらとも転 倒距離が等しい順列を1つ挙げよ ● N ≦ 10^5
- 18. C-考察1 ● A,Bの転倒距離をT(A,B)と書くとする ● T(A,C) = T(B,C)となるCがあるならばT(A,B)は 偶数 ● 数字の組について考えると – A,CでもB,Cでも逆 – A,Cで逆だがB,Cでは同じ – A,Cで同じだがB,Cでは逆 – A,CでもB,Cでも同じ ● それぞれx1, x2, x3, x4組ずつあったとする
- 19. C-考察1 ● 逆逆:x1組 逆同x2組 同逆 x3組 同同 x4組 ● このとき以下が成り立つ – T(A, C) = x1 + x2 – T(B, C) = x1 + x3 – T(A, B) = x2 + x3 ● よって T(A, B) = T(A, C) + T(B, C) – 2*x1 ● T(A,C) = T(B,C)なのでT(A, B)は偶数 – (Q.E.D)
- 20. C-考察1 ● T(A,C)=T(B,C)なるCがあるならばT(A,B)は偶数 対偶を取ると ● T(A,B)が奇数ならばT(A,C)＝T(B,C)なるCはな い – 今回の问题で言う-1を出力するパターン
- 21. C-考察2 ● 数字の大小は転倒距離とは関係ないので、Aが [1,2,…,N]となるように数字を置換しても構わ ない ● 例 – A:[3, 1, 4, 2, 5], B:[2, 5, 1, 3, 4] – 3→1, 1→2, 4→2, 2→3, 5→5というふうに変換 – A:[1, 2, 3, 4, 5], B[3, 5, 2, 1, 2]
- 22. C-考察2 ● Aが[1, 2, … ,N]になったのでBとの転倒距離が 計算しやすくなった – 各数字について、それ以左にあるそれ以上の数字の 個数を数えれば良い ● これはBの転倒数 – バブルソートにおける交換回数と一致することで有 名 – つまりBをバブルソートしていくと少しずつAとの 転倒距離が縮み、元のBとの転倒距離が伸びる
- 23. C-部分点 ● あらかじめA,Bの転倒距離を求める – Tとする – Tが奇数なら-1を返す (∵ 考察1) ● A,Bとの転倒距離がおなじになるまでBをバブル ソートしていく – T/2回交換したら停止して出力 ● バブルソートの計算量はO(N^2) – N≦3000なので間に合う 部分点獲得
- 24. C-満点解法 ● バブルソートにおける「隣り合う2つの要素の 交換」をいちいちやらずに、いくつかまとめて 処理する ● バブルソートをダイジェストで見ると以下のよ うになる – [6, 1, 4, 2, 3, 5] – [1, 6, 4, 2, 3, 5] – [1, 2, 6, 4, 3, 5] – [1, 2, 3, 6, 4, 5] – [1, 2, 3, 4, 6, 5] – [1, 2, 3, 4, 5, 6] 1回交換 2回交換 2回交換 1回交換 1回交換 ↓これらの値がわかっていれば交換の操作を スキップできる 実はxを正しい位置まで 動かすときの交換回数 は、初めの数列におけ るx以左のxより大きい 値の個数と一致する
- 25. C-考察 ● ある数列における x 以左のxより大きい値の個 数を高速に求める有名なデータ構造があった – BITやセグメントツリー ● 上記データ構造で以左に現れたかどうかのフラ グを管理しながら左から順番に走査する ● [3, 5, 4, 2, 6, 1]を例に実際に走査してみる
- 26. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 0 0 0 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6
- 27. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 0 0 0 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 0 確定 総和 = 0
- 28. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 1 0 0 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 0 更新
- 29. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 1 0 0 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 0 0 確定 総和 = 0
- 30. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 1 0 1 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 0 0 更新
- 31. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 1 0 1 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 0 1 0 確定 総和 = 1
- 32. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 1 1 1 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 0 1 0 更新
- 33. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 0 1 1 1 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 3 0 1 0 確定 総和 = 3
- 34. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 1 1 1 1 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 3 0 1 0 更新
- 35. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 1 1 1 1 0 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 3 0 1 0 0 確定 総和 = 0
- 36. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 1 1 1 1 1 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 3 0 1 0 0 更新
- 37. C-考察 ● [3, 5, 4, 2, 6, 1] ↑ 以左に現れたかどうかのフラグ 1 2 3 4 5 6 0 1 1 1 1 1 x以左に現れたxより大きい値の個数 1 2 3 4 5 6 5 3 0 1 0 0 確定 総和 = 5
- 38. C-満点解法 ● バブルソートにおける「隣り合う2つの要素の 交換」をいちいちやらずに、いくつかまとめて 処理する ● T/2回を超えないようにスキップしながらバブ ルソートをシミュレート – スキップするための値は先述のデータ構造が実装 ● スキップできなくなったら、交換回数がT/2に 達するまで普通にバブルソートをする – スキップがO(N)回の交換のまとめなので、たかだ かO(N)回で終了する ● 合計でO(NlogN) 満点獲得
- 39. ARC043解説 D:引っ越し
- 40. D-問題概要 ● 数直線上で原点からの距離が1以上N以下の整 数である場所に空き家がある ● M世帯の家族を1つの家に複数の世帯が割り当 てられないように振り分ける – i番目の家族がA[i]に割り振られたとする ● i世帯目の家族の構成人数をP[i]とする ● (1 ≦ i, j ≦ M)を満たすすべての対(i, j)に対する |A[i] – A[j]| * P[i] * P[j]の総和が最大になるよう に割り振った時のその値を求めよ
- 41. D-部分点解法 ● 全ての振り分けを試せば良い ● N≦10なのでN!通りの全探索が可能 ● 各振り分けの住民の距離の値はO(N^2)で求め ることが出来る ● O(N!×N^2) 10点獲得
- 43. D-式変形 ● |A[i] - A[j]| * P[i] * P[j] ● 空き家達を以下のように捉える
- 44. D-式変形 ● |A[i] - A[j]| * P[i] * P[j] ● 空き家達を以下のように捉える – A[i]とA[j]の間には|A[i] – A[j]|個の「辺」がある
- 45. D-式変形 ● |A[i] - A[j]| * P[i] * P[j] ● 空き家達を以下のように捉える – A[i]とA[j]の間には|A[i] – A[j]|個の「辺」がある – それぞれにP[i] * P[j] を足すと考えてみる
- 50. D-式変形 整理 ● 各辺について、以左の総和と以右の総和の積を とる ● さらにその総和をとれば求めるもの ● i番目の家以左にいる人の総和を sum[i]、すべ ての家族を合わせた人数をAllとすると求める値 は – Σ sum[i] * (All - sum[i])
- 51. D-考察 ● 空き家の扱いがすこし面倒 – 家族に振り分けられる空き家と、そうでない空き家 がある ● 0人家族が沢山存在するとみなせば、すべての 家に1家族ずつ振り分けることが出来る – 0人家族はいくら追加しても結果にかかわらない – 並び替えの問題として扱うことが出来る
- 52. D-帰着される問題 ● 正整数列A(1-index)が与えられる。総和はSum である。 ● S[i] = A[1] + A[2] + … + A[i] とする ● Aを並び替えたときの以下の値の最大値を求め よ Σ S[i] * (Sum - S[i])
- 56. D-考察 ● aとbの間の辺のみ考えれば良い ● (L+a) × (b+R) が (L+b) × (a+R) ● 整理すると(R - L) × (b – a)だけ増える事がわか る
- 57. D-考察 ● 以下のように a, b, cが並んでいたとする – さらに a < b, b > c を仮定する ● a,bを交換すると((R-L) +c)× (b - a)増える ● b,cを交換すると((L-R) +a) ×(b - c)増える
- 58. D-考察 ● 以下のように a, b, cが並んでいたとする – さらに a < b, b > c を仮定する ● a,bを交換すると((R-L) +c)× (b - a)増える ● b,cを交換すると((L-R) +a) ×(b - c)増える ● 以下に注意 – a, c, b-a, b-cはすべて正である – (R-L)もしくは(L-R)の少なくとも一方が負ではない ● どちらかの交換は結果が悪化しない
- 59. D-考察 ● a < b > c が成立している時、bはどちらか一方 と交換することが出来る – a < b > c となる部分を含まないような最適解が存 在する ● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n] となるような最適解が存在する
- 60. D-考察 ● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n] ● このパターンの並び替えを探索する一般的なテ クニックがある ● DP[i][x] = Aの中で大きい方からi番目までを左 右に振り分けて、左側の総和がxのときの何ら かの値の最大(小)値 ● Aの中で大きい物から順番に左もしくは右に振 り分けていくイメージ
- 61. D-考察 ● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n] ● このパターンの並び替えを探索する一般的なテ クニックがある ● DP[i][x] = Aの中で大きい方からi番目までを左 右に振り分けて、左側の総和がxのときの何ら かの値の最大(小)値 ● Aの中で大きい物から順番に左もしくは右に振 り分けていくイメージ
- 62. D-考察 ● A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n] ● このパターンの並び替えを探索する一般的なテ クニックがある ● DP[i][x] = Aの中で大きい方からi番目までを左 右に振り分けて、左側の総和がxのときの何ら かの値の最大(小)値 ● Aの中で大きい物から順番に左もしくは右に振 り分けていくイメージ どんな値？
- 63. D-帰着される問題（再掲） ● 正整数列A(1-index)が与えられる。総和はSum である。 ● S[i] = A[1] + A[2] + … + A[i] とする ● Aを並び替えたときの以下の値の最大値を求め よ Σ S[i] * (Sum - S[i])
- 64. D-帰着される問題（再掲） ● 正整数列A(1-index)が与えられる。総和はSum である。 ● S[i] = A[1] + A[2] + … + A[i] とする ● Aを並び替えたときの以下の値の最大値を求め よ Σ S[i] * (Sum - S[i])
- 65. D-満点解法 ● DP[i][x] = Aの大きい方からi番目までを左右に 振り分けて左側の総和がxで在るときのもう定 まってる S[i] * (Sum - S[i])の総和の最大値
- 66. D-満点解法 ● DP[i][x] = Aの大きい方からi番目までを左右に 振り分けて左側の総和がxで在るときのもう定 まってる S[i] * (Sum - S[i])の総和の最大値 – DP[i][x]は以下の様な全ての状態の中で「決まって いるS[i] * (Sum – S[i])の総和」の最大値
- 67. D-満点解法 ● DP[i][x] = Aの大きい方からi番目までを左右に 振り分けて左側の総和がxで在るときのもう定 まってる S[i] * (Sum - S[i])の総和の最大値 – DP[i][x]は以下の様な全ての状態の中で「決まって いるS[i] * (Sum - S[i])の総和」の最大値
- 68. D-満点解法 ● DP[N][0], DP[N][1], … ,DP[N][Sum] の中で最大 の物を探せば良い？ – 残念ながらNのオーダーは10^6なので間に合わな い
- 69. D-満点解法 ● DP[N][0], DP[N][1], … ,DP[N][Sum] の中で最大 の物を探せば良い？ – 残念ながらNのオーダーは10^6なので間に合わな い ● 実はほとんどが0人家族である – A[1] ≧ A[2] ≧ … ≧ A[i] ≦ A[i+1] ≦ … A[n] この制約のために0人家族は真ん中のあたりに固 まっている – これらだけ別処理すれば良い – NがMまで減る（Mのオーダーは10^3)
- 72. D-満点解法 ● 0人家族の別処理 – 以下のように0人家族のあたりの辺には全く同じ値 が足される – この値はxから求まるのでDP[m][x]ごとに別々に計 算してやればDP[n][x]に相当するものが求まる
- 73. D-満点解法まとめ ● DP[i][x] = 大きいほうからi番目までで左の総和 がxになるように置いた時の値が決まっている 辺の総和の最大値 ● DP[m][x]まで求めて、0人家族の辺は別処理 – mのオーダーは10^3, xのオーダーは10^5なので配 列を普通に確保するとMLEしてしまう – I に関しては昇順に操作し、更新時 i – 1しか参照し ないのでメモリをリサイクルできる – 空間計算量はO(10^5) – 時間計算量はO(10^8)