SRM 423 Level1 TheTower

contest

参加できなかった前回のTopCoder SRM、遅ればせながらPractice Roomでやりました。噂ではかなり難しかったらしい。


時間を75分計ってやってみたところ、Level1（300点問題）は35分くらいでsubmitできました。システムテストも通って152pt。これは確かにいつものLevel1よりかなり難しい。普段は単純にさっさと書くだけの問題のことが多いけれど、今回はアルゴリズムをある程度自分でひらめかないといけない。難しくもいい問題だったと思います。
Level2（500点問題）は途中まで。こっちもけっこう難しめでした。あとで他の人の解答を見る。


以下Level1の解説をつらつらと。

問題

格子点上にあるコマがN個（N<=50）与えられる。コマを格子に沿って移動させて、どこか一点に決められた数のコマを集めたい。どの点に集めてもいいし、どのコマを使ってもいい。集める数が1〜Nのそれぞれに対して、最小の移動距離を求めよ。

例

条件：各コマのx座標{1, 2, 4, 9}、各コマのy座標{1, 1, 1, 1}
解答：{0, 1, 3, 10}


解説：2個集めるときは、(1,1)を(2,1)へ移動させるだけなので移動距離1。
3個集めるときは、(1,1)を(2,1)へ、(4,1)も(2,1)へ移動させて合計の移動距離3。
4個集めるときは、全部を(2,1)へ移動させて合計の移動距離10。

ポイント
移動距離が最小となる点のx座標は、どれかのコマの初期x座標と同じところのみを考えればよい。y座標も同じ。つまり、N×N個の点だけを調べれば十分。
理由
格子上の移動なので、xとyは別々に考えて良い。のでx座標だけ考える。
(X1, X2, ... , Xn)を座標Xに集めるとする。ここで一般性を失わずに（Xi <= Xi+1）としておく。
このときの移動距離は Σ|X - Xi|。これは[Xi, Xi+1]間ではただのXの一次関数で、図に書くと各Xiで傾きが変わる折れ線グラフになる。なので、最小値を取る位置の候補としてはXiだけを考えればよい。


N×N個の候補点それぞれに対して、以下を行います。

  • 各コマとの距離を計算する
  • 距離の小さいものから順に足していく
  • これで、その点でコマを1個、2個、…、N個集めるときの最小移動距離が分かる

この最小移動距離を候補点ごとに記憶しておきます。都合、N×N×Nの配列になる。
配列の名前をaryとすると、ary[i][j][k]が表すのは、「点 (コマiの初期x座標, コマjの初期y座標) に、k個コマを集めるときの最小移動距離」です。


あとは、コマを集める数が1個、2個、…、N個のそれぞれに対して、記憶した中から最小の移動距離のものを探せばOK。


少ないコード量で済んだので貼っときます。

import java.util.Arrays;

public class TheTower {

  public int[] count(int[] x, int[] y) {
    int N = x.length;
    int[][][] s = new int[N][N][N]; // これに候補点ごとの最短移動距離を記憶する
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        int[] a = new int[N];
        for (int k = 0; k < N; k++) {
          a[k] = Math.abs(x[k] - x[i]) + Math.abs(y[k] - y[j]); // 各コマとの距離
        }
        Arrays.sort(a);
        int ac = 0;
        for (int k = 0; k < N; k++) {
          ac += a[k]; // 近いものから順に足していく
          s[i][j][k] = ac;
        }
      }
    }
    int[] ret = new int[N];
    for (int n = 0; n < N; n++) {
      int min = Integer.MAX_VALUE;
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          // 記憶した中から最短のものを探す
          min = Math.min(min, s[i][j][n]);
        }
      }
      ret[n] = min;
    }
    return ret;
  }

}


【追記】nitoyonさんの解説のほうがわかりやすそう。