Hatena::Grouptopcoder

反省会。

 | 

2012-06-11 Monday

SRM545 Division I 00:13

Level One - StrIIRec (275)

  • 転倒数の最小値と与えられた置換(一部)以降で辞書順最小のものを求める
  • とりあえず置換を埋める
  • 転倒数OKならそれ返す
  • あとは転倒数増やす方針にした
  • 後ろから適当に入れ替える…だめ。辞書順最小になってない
  • 入れ替えるところが見つかったら戻る…これもだめ
  • 入れ替えたら一旦辞書順に並び替えないとだめなのか?
  • 方針がまずい気がする
  • 残り10分。ちょっと間に合わないか…
  • Challenge用のケース作る
  • 明らかに通ってないものの提出

Challenge

  • 自分と似たようなことをやってるコードを見つける
  • 後ろから順番に並び替えるだけだとだめなんだよな…自分含め。
  • 成功。+50
  • もう1つ似たようなの発見
  • こっちは通って失敗-25。入れ替えが地味に違うな…

結果

http://community.topcoder.com/stat?c=coder_room_stats&rd=14737&rm=313279&cr=23072275

その後

  • 一応解いた
  • 転倒数しか見てないからダメなのであって、辞書順に次のを求めるようにする
  • c[i-1]<c[i] となる最大のiを求める
  • 辞書順で次 → c[i-1]<c[j](j>=i)となる最大のj*1を持ってきて入れ替えてi以降をソート*2
  • まともにやると全然間に合わない
  • c[i-1]<c[j](j>=i) となる最大のjを持ってきて入れ替えた時点で、転倒数は+1。辞書的に次から入れ替え直後までのものはすべて転倒数がこれより小さい*3ので、調べる必要なし。ソート外す。
import java.util.ArrayList;

public class StrIIRec {

  public String recovstr(int n, int minInv, String minStr) {
    ArrayList<Character> l = new ArrayList<Character>();
    for(int i=0; i<n; i++) {
      l.add((char)('a'+i));
    }
    for(int i=0; i<minStr.length(); i++) {
      l.remove(Character.valueOf(minStr.charAt(i)));
    }
    String str = minStr;
    for(Character d:l) {
      str += d.toString();
    }
    char[] c=str.toCharArray();
    while(true) {
      if (count(c) >= minInv) {
        break;
      }
      if (!nl(c)) break;
    }
    
    return new String(c);
  }
  
  private int count(char[] c) {
    int cnt = 0;
    for(int i=0; i<c.length; i++) {
      for (int j=i+1; j<c.length; j++) {
        if (c[i] > c[j]) cnt++;
      }
    }
    return cnt;
  }
  private boolean nl(char[] c) {
    for (int i=c.length-1; i>0; i--) {
      if (c[i-1] < c[i]) {
        for (int j=c.length-1; j>=i; j--) {
          if (c[i-1] < c[j]) {
            char tmp = c[j];
            c[j] = c[i-1];
            c[i-1] = tmp;
            return true;
          }
        }
      }
    }
    return false;
  }
}

反省

  • 時間がかかりすぎたのは問題
  • Challenge用にケース用意しておいたのは○
  • もう年か…

*1:c[i-1]に一番近いc[j]

*2:逆順に並んでるのでreverseで良い

*3:逆順に並んでるものが最大だから

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/sankondenai/20120611
 |