AtCoder Beginner Contest 252C 間違っている箇所を知りたい

Question

AtCoder Beginner Contest 252C(こちら)が8AC,24WAとなってしまいます。
どの部分が間違っているかご教授いただけないでしょうか。

import java.util.*;
import java.util.Map.Entry;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        TreeSet<Integer> ts = new TreeSet<Integer>();
        int n = sc.nextInt();
        TreeMap<Integer,TreeSet<Integer>> map = new TreeMap<Integer,TreeSet<Integer>>();
        for(int i=0;i<n;i++){
            String s = sc.next();
            String[] sa = s.split("");
            for(int j=0;j<10;j++){
                int num = Integer.parseInt(sa[j]);
                if(map.containsKey(num)){
                    TreeSet<Integer> t = map.get(num);
                    t.add(j);
                    map.put(num,t);
                }else{
                    TreeSet<Integer> t = new TreeSet<Integer>();
                    t.add(j);
                    map.put(num,t);
                }
            }
        }
        while(!map.isEmpty()){
            Entry<Integer, TreeSet<Integer>> e=map.firstEntry();
            ts.add(e.getValue().last()+10*(n-e.getValue().size()));
            map.remove(e.getKey());
        }
        System.out.println(ts.first());
    }
}

Comments

[jimbe]

ご提示のコードはどのようなアルゴリズムを基に作られたのでしょうか。

それと AtCoder をやったことが無いので分からないのですが、具体的にどのような入力時にダメなのでしょう。

[jimbe]

例えば、

4
0123456789
9876543210
0123456789
9876543210

というデータの場合、"0" を揃えるとしたらどの何秒目にどのスロットを止めると何秒で揃えられるでしょうか。
(0秒目,1スロット)
(9秒目,2スロット)
(10秒目,3スロット)
(19秒目,4スロット)
= 19 秒
です。
ご質問のコードでは 29 秒となるのではないでしょうか。

[den7]

ありがとうございます！解決できました🙇‍♀️

Answer 1

間違っているのは以下の計算です。重複している位置が末尾だけならこの計算でよいのですが、そうなるとは限りません。

            ts.add(e.getValue().last()+10*(n-e.getValue().size()));

例えば、こちらの入力例で、正しい出力は10(0秒後1番目、1秒後3番目、10秒後2番目)ですが、このコードだと11が返ります。

3
0123456789
0123456789
9012345678

Comments

[den7]

ありがとうございます！解決できました🙇‍♀️