2012年2月28日火曜日

TopCoder SRM337 Div2 250Pts

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

回文というのは、文字を右から読んでも左から読んでも同じになる文字列を指す。sという文字列が与えられたとき、sを最小限変えることで回文を作成せよ。文字を変えるというのは、ある場所の文字を置き換えるということである。文字を削ることや付け加えることは認められていない。もし回答が複数あるなら、アルファベット順で最も早く来る物を返せ。

私の解答はこちら。

public class Palindromize2 {

 public String minChanges(String s) {
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<s.length(); i++ ){
   // headとtailから順にi番目を比較して、先に来る方をcとする
   char h = s.charAt(i);
   char t = s.charAt(s.length()-i-1);
   char c = h > t ? t : h;
   sb.append(c);
  }
  return sb.toString();
 }

}

得点は236.12/250、中央値は約228点。実は文字の交換回数が最小とかは関係ないというオチ。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計