2年3ヶ月ぶりに青コーダーに復帰( TopCoder SRM 551 Div2 )

1151→1238．2年3ヶ月ぶりの青コーダー！
もう今年の目標は達成できました(志が低い

Level One, Twoを解いたらもうThreeを解く時間はなかったので、残り時間でチャレンジを考える．
チャレンジ3つ成功．

Level One

入力に含まれる文字の種類数が1ならreturn 1、2ならreturn 2、それ以外ならreturn 0。
簡単な問題なのですが、問題文がわかりづらかったです……。

問題文を読み間違えて、3以上をreturnしてしまうコードがあったので3撃墜。
一つのコードはnext_permutationを使っていて、最長の入力を投げたらそもそもTime Limit Exceededでした。

import java.util.HashMap;
 
public class ColorfulBricks {
 
  public int countLayouts(String bricks) {
    HashMap<Character, Integer> s = new HashMap<Character, Integer>();
    for(char c : bricks.toCharArray()) {
      if(s.containsKey(c)) {
        s.put(c, s.get(c));
      } else {
        s.put(c, 0);
      }
    }
    if(s.size() == 1) {
      return 1;
    }
    if(s.size() == 2) {
      return 2;
    }
    return 0;
  }
 
}

Level Two

最大maxSwaps回の隣接した要素の入れ替えができるときに、与えられた文字列の中で連続した同じ文字の最大数を答える。

方針は、列中のある位置iからその前後を見ていって、交換に必要なコストでソートすればiに関しての最長の結果が得られる。
これをすべての位置iについて計算して、最大値を求める。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
 
public class ColorfulChocolates {
 
  public int maximumSpread(String chocolates, int maxSwaps) {
    int len = chocolates.length();
    int max = 0;
    for(int i = 0; i < len; i++) {
      int tempSwaps = maxSwaps;;
      char key = chocolates.charAt(i);
      int fore = i;
      int back = i;
      int count = 1;
      ArrayList<Integer> canDo = new ArrayList<Integer>();
      for(int j = i + 1; j < len; j++) {
        if(chocolates.charAt(j) == key) {
          if(Math.abs(j - fore) == 1) {
            canDo.add(0);
            fore++;
          } else if(Math.abs(j - fore) - 1 <= tempSwaps) {
            canDo.add(Math.abs(j - fore) - 1);
            System.out.println("add_fore:" + i + ", " + j + ", " + (Math.abs(j - fore) - 1));
            fore++;
          }
        }
      }
      for(int j = i - 1; j >= 0; j--) {
        if(chocolates.charAt(j) == key) {
          if(Math.abs(j - back) == 1) {
            canDo.add(0);
            back--;
          } else if(Math.abs(j - back) - 1 <= tempSwaps) {
            canDo.add(Math.abs(j - back) - 1);
            System.out.println("add_back:" + i + ", " + j + ", " + (Math.abs(j - back) - 1));
            back--;
          }
        }
      }
      Collections.sort(canDo);
      for(int cand: canDo) {
        if(tempSwaps >= cand) {
          tempSwaps -= cand;
          count++;
        }
        System.out.println(i + ", " + cand + ", " + tempSwaps);
      }
      if(count > max) {
        max = count;
      }
    }
    return max;
  }
 
}