AtCoder Beginner Contest 137受験記

AtCoder Beginner Contest 137

f:id:repenguin:20190810230342p:plain うわあああああああああああああああああああああああああああああああああああああああああああああああああああああ

A - +-x

Math.max を二回するだけ

B - One Clue

始点:X - K + 1

終点:X + K - 1

を出力するだけ

C - Green Bin

TLE祭り

アナグラムかどうかはいろいろな比較方法がある

①Mapにアルファベットごとに個数とともに格納し比較

②文字列をソートして比較

だがこの問題はアナグラムか比較する方法が大事なわけではない

普通にやると二重ループになる計算量をどう落とすかが問題である

回答としてはMapを使う

①ソート済み文字列をMapに個数分格納する

②今回は組み合わせの数を求めないといけないので個数が2以上である(複数個存在する)ものに関して組み合わせを計算しカウントする

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int N = sc.nextInt();
    Map<String, Integer> m = new HashMap<String, Integer>();
    long cnt = 0;
    for (int i = 0; i < N; i++) {
        String s = sortStr(sc.next());
        if (m.containsKey(s)) {
            m.put(s, m.get(s) + 1);
        } else {
            m.put(s, 1);
        }
    }
    Iterator<Map.Entry<String, Integer>> itr2 = m.entrySet().iterator();
    while (itr2.hasNext()) {
        Map.Entry<String, Integer> entry = itr2.next();
        if (entry.getValue() != 1) {
            cnt += get(entry.getValue());
        }
    }
    System.out.println(cnt);
 }
public static String sortStr(String str) {
    char[] list = new char[str.length()];
    list = str.toCharArray();
    Arrays.sort(list);
    return new String(list);
}   
public static long get(int n) {
    long ret = 0;
    for (int i = n - 1; i > 0; i--) {
        ret += i;
    }
    return ret;
}

レート更新

f:id:repenguin:20190810231627p:plain f:id:repenguin:20190810231655p:plain