![問題概要
配列を値の交換によってソートしたい。
i と j を交換するのに C[i][j] のコストが必要になる。
順列 p をソートするのに必要な最小コスト =: f(p)
f(p) の最大値を求める。](https://image.slidesharecdn.com/sort-120318040827-phpapp01/85/Sort-2-320.jpg)
![グラフとして見る
0, 1, 2 0, 2, 1 1, 0, 2
1, 2, 0 2, 0, 1 2, 1, 0
C[0][1]
C[0][2]
C[1][2]](https://image.slidesharecdn.com/sort-120318040827-phpapp01/85/Sort-5-320.jpg)
![[DL輪読会]“Submodular Field Grammars Representation” and “Deep Submodular Functi...](https://cdn.slidesharecdn.com/ss_thumbnails/190329dlver2-190329005549-thumbnail.jpg?width=560&fit=bounds)
![[DL Hacks] Deterministic Variational Inference for RobustBayesian Neural Netw...](https://cdn.slidesharecdn.com/ss_thumbnails/adobepdffile2-190628001736-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Clebsch–Gordan Nets: a Fully Fourier Space Spherical Convolutional Neu...](https://cdn.slidesharecdn.com/ss_thumbnails/20181214clebschgordanmizuta-181214051939-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Viewers also liked (18)
Similar to Sort (20)
![[DL輪読会]Convolutional Conditional Neural Processesと Neural Processes Familyの紹介](https://cdn.slidesharecdn.com/ss_thumbnails/20191220readingpaperconvcnp-191220034420-thumbnail.jpg?width=560&fit=bounds)
Sort
- 2. 問題概要 配列を値の交換によってソートしたい。 i と j を交換するのに C[i][j] のコストが必要になる。 順列 p をソートするのに必要な最小コスト =: f(p) f(p) の最大値を求める。
- 3. 着眼点 f(p) を効率よく求めるのは案外大変 ( 参考 : Silly Sort ) 最も愚直にコストを求めるには、 p からソートされた 状態へ Dijkstra を使う。 f(p) を求めるのに N! 程度のコストが必要になり、 全ての p について求めると (N!)^2 で TLE する。 逆に、ソートされた状態からの距離を考えれば Dijkstra を 1 回行うだけでよい。
- 4. 解法 N! 通りの全ての順列をノードとするグラフを考える。 ソートされた順列を始点として Dijkstra 法などで各 ノードまでの距離を求める。 距離の最大値が答えとなる。
- 5. グラフとして見る 0, 1, 2 0, 2, 1 1, 0, 2 1, 2, 0 2, 0, 1 2, 1, 0 C[0][1] C[0][2] C[1][2]
- 6. 実装 各順列までの距離をどのようなデータ構造で持つ か？ 1. 連想配列で配列をキーにする 2. 順列をビット列に落とす (3 * 7 bit あれば十分 ) 3. 順列に対する最小完全ハッシュ関数を利用す る ( 変換に N^2 かかるのがネック ) 1 や 3 だと実装次第で TLE することもあるようで す。定数が重いとかではなく計算量が増加します。
- 7. 解答例 宮村 (C++) 95 行 1644 byte 橋本 (Java) 90 行 1800 byte