Hatena::Grouptopcoder

tochukasoの日記

2016-05-07

GCJ2016 Qual

19:43

久しぶりに競技プログラミングコンテストに参加できる時間が取れたので参戦

結果:45点

10797位

3時間も使ってこの結果だったので、不甲斐ないけどQualは次のラウンドへの足切りなので良しとする。

A問題

0から9までの全ての数を数えるまでに必要な回数を出力する。

ある数が与えられるので、

1から順番にN倍することが出来る。

N倍した結果に含まれる数字を数えることが出来る。

        int n = Integer.parseInt(element);
        
        String NONE = "INSOMNIA";
        
        boolean[] isClearNums = new boolean[10];
        
        first: for(int i = 1 ; i <= 999999; i++) {
            int calc = n * i;
            while(calc > 0) {
                int d = calc % 10;
                isClearNums[d] = true;
                calc /= 10;
            }
            
            for(boolean b : isClearNums) {
                if(!b) continue first;
            }
            
            return String.valueOf(n * i);
        }
        
        return NONE;
B問題

'+','-'で構成される文字列が渡される。

以下の操作を行って最小の回数で+に文字列を揃える。

・先頭から連続する'+','-'のいずれかを反転させて、文字列の末尾、または先頭に並べ替えることが出来る。

    private String compress(String s) {
        StringBuilder sb = new StringBuilder();
        char b = ' ';
        for(char c : s.toCharArray()) {
            if(c != b) {
                sb.append(c);
                b = c;
            }
        }
        
        return sb.toString();
    }
    
    private String solveProblem(String element) {
        
        Set<String> isChecked = new HashSet<>();
        Queue<String> que = new ArrayDeque<>();
        element = compress(element);
        que.add(element);
        isChecked.add(element);
        
        
        for(int i = 0 ; i < 1000; i++) {
            Queue<String> nextQue = new ArrayDeque<>();
            
            while(!que.isEmpty()) {
                String now = que.poll();
                char[] checks = now.toCharArray();
                boolean isClear = true;
                for(char c : checks) {
                    if(c != '+') {
                        isClear = false;
                        break;
                    }
                }
                if(isClear) return String.valueOf(i);
                
                int minus = now.indexOf("-");
                int plus = now.indexOf("+");
                
                if(plus == -1 ) plus = now.length();

                if(minus < plus) {
                    {
                        String next = compress(now.substring(plus) + repeat('+', (plus - minus)));
                        if(isChecked.add(next)) {
                            nextQue.add(next);
                        }
                    }
                    
                    {
                        String next = compress(repeat('+', (plus - minus)) + now.substring(plus));
                        if(isChecked.add(next)) {
                            nextQue.add(next);
                        }
                    }
                    
                } else {
                    {
                        String next = compress(now.substring(minus) + repeat('-', (minus - plus)));
                        if(isChecked.add(next)) {
                            nextQue.add(next);
                        }
                    }

                    {
                        String next = compress(repeat('-', (minus - plus)) + now.substring(minus));
                        if(isChecked.add(next)) {
                            nextQue.add(next);
                        }
                    }
                }
            }
            
            que = nextQue;
        }
        
        throw new RuntimeException(String.format(" no search %s", element));
    }

Qualではsmallしか解けなかった。

後からcompressのメソッドを追加して圧縮することを試したら通るようになった。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/java123java123/20160507