TopCoder SRM340 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題についておおまかに説明する。

アルファベットの小文字のみからなる同じ長さの文字列AとBが与えられる。二つの文字の距離というのを、差の絶対値で定義される。文字列AとBの距離はAとBの同じ位置にある文字の距離の和として定義する。例えば"abcd"と"bcda"の距離は6となる(aとbの距離は1、dとaの距離は3などとして求められる)。Aの文字のうち、K文字を変えなければならない。このとき、AとBの文字の距離を最小値を返せ。

私の解答はこちら。

import java.util.Arrays;

public class ChangingString {

 public int distance(String A, String B, int K) {
  int[] diff = new int[A.length()];
  int dist = 0;
  // ひとまず1文字ごとに距離計算
  for( int i=0 ; i<A.length() ; i++ ){
   diff[i] = Math.abs(A.charAt(i)-B.charAt(i));
  }
  Arrays.sort(diff);
  // 距離の大きい方からK個の値を変更
  for( int i=0 ; i<K ; i++ ){ 
   int idx = diff.length-i-1;
   if( diff[idx] > 0 ){
    diff[idx] = 0;
   }else{
    diff[idx] = 1;
   }
  }
  // 距離の合計を計算
  for( int i=0 ; i<diff.length ; i++ ){
   dist += diff[i];
  }
  return dist;
 }

}

得点は241.67/250、中央値は約196点。距離の大きさで順に並び替えて、大きい方からK個の距離を0にすればよい。もし、距離の大きいK個の値に0が含まれていたら、それは1とすればよい。Aの文字をK個強制的に変えなければならないので、0のままではダメということである。