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のメソッドを追加して圧縮することを試したら通るようになった。

2014-08-12

天下一プログラマコンテスト予選A

| 17:09

1完

A問題

問題概要

・1~1000までを辞書順(1,10,100,1000,11,110・…999)で出力せよ

解き方

・3重ループ+1000を出力するための例外処理?を書く。

・Stringのlistに1~1000を突っ込んでArrays#sortで書いた方がよさそう。

    void solve() throws Throwable {
        
        for (int i = 1; i <= 9; i++) {
            pw.println(i);
 
            for (int j = 0; j <= 9; j++) {
                pw.println(i+""+j);
                for (int j2 = 0; j2 <= 9; j2++) {
                    pw.println(i+""+j+j2);
                        
                    if(i == 1 && j == 0 && j2 == 0) {
                        pw.println("1000");
                    }
                }
            }
            
        }      
    }

B問題

問題概要

・2種類の攻撃方法があって、攻撃毎に掛ける時間や、使用するエネルギー的なものの量が違う。

・また、コンボの概念もある。

解き方

・シミュレーションするだけ。

・のはずが、全く解けず。時間だけ過ぎる。。。

・32まではAC、、、、以降が全部×。

・なんだろうなぁ。組みなおしてみよう。C問題も不明。

300位ぐらい。ひどい結果だった

**AtCoder Regular Contest 27

| 17:09

3完

A問題

問題概要

・時間と分が引数で与えられる。

・18時まであと何分あるかを返却せよ

解き方
    void solve() throws Throwable {
        int H = (17 - readInt()) * 60;
        int M = 60 - readInt();
        pw.println(H+M);
    }

B問題

問題概要

・長さが同じ2つの文字列が与えられる。

・この2つの文字列は同一の数字を示す。

・アルファベットはそれぞれ0~9の可能性がある。

・矛盾をおこなさない数字の組み合わせが何通りあるかを答える。

解き方

・効率的な方法は分からないので愚直にシミュレーション

・部分点ゲット・・・・・

・うーん。改善方法が分からない。

・アルファベットの絞り込みを行っている個所を2重ループで回すように変更。

AC!! 嘘解法っぽいなぁ・・・

・アルファベットを絞り込んでいるときに関係性があるアルファベットの数字の可能性も消去しているはずだけど、

 漏れがあるのかも

    void solve() throws Throwable {
        
        int N = readInt();
        String string1 = readString();
        String string2 = readString();
        char[] s1 = string1.toCharArray();
        char[] s2 = string2.toCharArray();
        boolean[][] prohibitAlphabets = new boolean[26][10];
        
        for (int Z = 0; Z < 2; Z++) {
            
        for (int i = 0; i < N; i++) {
            char c1 = s1[i];
            char c2 = s2[i];
            boolean isNum1 = false;
            boolean isNum2 = false;
            if (c1 < 'A') {
                isNum1 = true;
            }
            if (c2 < 'A') {
                isNum2 = true;
            }
            if(isNum1) {
                if(!isNum2) {
                    for (int j = 0; j < 10; j++) {
                        if(j == Character.getNumericValue(c1)) continue;
                        prohibitAlphabets[c2-'A'][j] = true;
                    }
                }
                
            } else {
                if(i == 0) {
                    prohibitAlphabets[c1 - 'A'][0] = true;
                }
                if(!isNum2) {
                    for (int j = 0; j < 10; j++) {
                        if(prohibitAlphabets[c1 - 'A'][j]) prohibitAlphabets[c2-'A'][j] = true;
                        if(prohibitAlphabets[c2 - 'A'][j]) prohibitAlphabets[c1-'A'][j] = true;
                    }
                }
            }
 
            if(isNum2) {
                if(!isNum1) {
                    for (int j = 0; j < 10; j++) {
                        if(j == Character.getNumericValue(c2)) continue;
                        prohibitAlphabets[c1-'A'][j] = true;
                    }
                }
            } else {
                if(i == 0) {
                    prohibitAlphabets[c2 - 'A'][0] = true;
                }
            }
        }
        }
        long res = 1;
        boolean[] used = new boolean[26];
 
        for (int i = 0; i < N; i++) {
            long count = 0;
            char c1 = s1[i];
            char c2 = s2[i];
            for (int j = 0; j < 10; j++) {
                if (c1 < 'A' || c2 < 'A' || used[c1 - 'A'] || used[c2 - 'A']) {
                    count = 1;
                    break;
                }
                if(prohibitAlphabets[c1 - 'A'][j] || prohibitAlphabets[c2 - 'A'][j]) continue;
                count++;
            }
            if(c1 >= 'A') {
                used[c1-'A'] = true;
            }
            if(c2 >= 'A') {
                used[c2-'A'] = true;
            }
            res*=count;
            
        }
        
        pw.println(res);
    }

C問題

問題概要

・典型的DP

・ナップザック問題が少し複雑になった感じ

・2種類のチケットとチケットで買えるものがあって、価値の総和が最も高い場合にいくつになるかを返却する。

・2種類のチケットのうち、1種類のチケットは物を買う時に常に消費しなければならない制約がある

解き方

・必須チケットじゃなくて通常のチケットを優先して使えばよさそう

・部分点もある問題かぁ・・・・

・買えるもののインデックス(300以下)、必須チケットの使用枚数(300以下)、通常チケットの使用枚数(300以下)の値毎に

 最大の価値をメモすることでDP出来そう。

 でも、300*300*300=2700万要素の配列かぁ・・・・メモリ足りなそうだなぁ。

・うーーーーん。どうやって解くべきか。・・・・intのメモリ確保容量ってどれくらいだろう。

 4byteかぁ。ということは、100メガちょっと。ん?足りそうだぞ。

・MLE・・・・・30点ゲット

・やっぱりC問題はまだ解けないよなぁ。

・と思いつつもよくよく見直してlong型で配列を宣言していたのをint型に変更したらAC

    int X, Y, N;
    int[] mustTikets = null;
    int[] happiness = null;
    static int[][][] dp = null;
 
    void solve() throws Throwable {
        
        X = readInt();
        Y = readInt();
        N = readInt();
        mustTikets = new int[N];
        happiness = new int[N];
        for (int i = 0; i < N; i++) {
            mustTikets[i] = readInt();
            happiness[i] = readInt();
        }
        
        dp = new int[N][X+1][Y+1];
        pw.println(dfs(0,0,0));
    }
 
    int dfs(int i, int special, int normal) {
        if (i == N)
            return 0;
        if (dp[i][special][normal] != 0)
            return dp[i][special][normal];
        if (special >= X || mustTikets[i] + special + normal > X + Y) {
            return dp[i][special][normal] = dfs(i + 1, special, normal);
        } else {
            int last = Math.max(0, mustTikets[i] - (Y - normal) - 1);
            return dp[i][special][normal]= Math.max(dfs(i + 1, special, normal),
                    dfs(i + 1, special + 1 + last,
                            normal + (mustTikets[i] - last - 1))
                            + happiness[i]);
        }
    }

結果は59位で、2級に昇級出来ましたヽ(^o^)丿

時間があれば、D問題の部分点も取れそうだったのに残念

2014-07-28

CodeForces MemSQL

| 16:41

1完・・・・

A問題

概要

・固有名詞のリストがあらかじめ提示される。

・引数で「a..b..c」の様な文字列が与えられる。

・'.'は任意の一文字に置き換えることが出来る。

・引数がどの文字列に合致するかを調べて返却する。

解法

・あらかじめ提示されている文字列にmatch(String regex)を使用する

    void solve() throws Throwable {
        int N = readInt();
        String word = readString();
        String[] names = {
                "vaporeon", "jolteon", "flareon", "espeon", "umbreon", "leafeon", "glaceon", "sylveon"
        };

        for (String string : names) {
            if(string.matches(word)) {
                pw.println(string);
                return;
            }
        }
    }

B問題

概要

・N * Mサイズの格子が与えられる。

・任意の4点を指定することが出来る。

・[p1,p2],[p2,p3],[p3,p4]の3本の直線の長さの総和が最大になるような4点を求める。

解法

・任意の4点は、左上(0,0),右下(N,M)が中心になる。

 そのため、点の候補になりそうなものをあらかじめ列挙する。(ここの指定が甘くて落としました。)

 順列を使用するが、4Cnなので、nが20ぐらいまでなら余裕で計算できた。

・また、N,Mが0の時の処理は特例として処理するようにした。

    int[][] pos = new int[8][2];
    double max = 0;
    int[] maxPos = null;

    void solve() throws Throwable {
        
        int N = readInt();
        int M = readInt();
        
        if(N == 0) {
            pw.println(0 + " " + 1);
            pw.println(0 + " " + M);
            pw.println(0 + " " + 0);
            pw.println(0 + " " + (M - 1));
            return;
        } else if(M == 0) {
            pw.println(1 + " " + 0);
            pw.println(N + " " + 0);
            pw.println(0 + " " + 0);
            pw.println((N-1) + " " + 0);
            return;
        }

        pos[0] = new int[] {0,0};
        pos[1] = new int[] {N,M};
        pos[2] = new int[] {N - 1,M};
        pos[3] = new int[] {0,1};
        pos[4] = new int[] {1,0};
        pos[5] = new int[] {N,0};
        pos[6] = new int[] {N, M -1};
        pos[7] = new int[] {0, M};
`
        permutationAll(new int[] {0,1,2,3,4,5,6,7});
        pw.println(pos[maxPos[0]][0] + " " + pos[maxPos[0]][1]);
        pw.println(pos[maxPos[1]][0] + " " + pos[maxPos[1]][1]);
        pw.println(pos[maxPos[2]][0] + " " + pos[maxPos[2]][1]);
        pw.println(pos[maxPos[3]][0] + " " + pos[maxPos[3]][1]);
    }
    void permutationAll(int[] p) {
        permutation(p, 0, p.length - 1);
    }
    void permutation(int[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == 4) { 
            O++;
            double sum = 0;
            int p1 = elements[0];
            int p2 = elements[1];
            int p3 = elements[2];
            int p4 = elements[3];
            if(pos[p1][0] == pos[p2][0] && pos[p1][1] == pos[p2][1]) return;
            if(pos[p1][0] == pos[p3][0] && pos[p1][1] == pos[p3][1]) return;
            if(pos[p1][0] == pos[p4][0] && pos[p1][1] == pos[p4][1]) return;
            if(pos[p2][0] == pos[p3][0] && pos[p2][1] == pos[p3][1]) return;
            if(pos[p2][0] == pos[p4][0] && pos[p2][1] == pos[p4][1]) return;
            if(pos[p3][0] == pos[p4][0] && pos[p3][1] == pos[p4][1]) return;

            double seg1 = Math.sqrt(Math.pow(pos[p1][0] - pos[p2][0], 2) + Math.pow(pos[p1][1] - pos[p2][1], 2)); 
            double seg2 = Math.sqrt(Math.pow(pos[p2][0] - pos[p3][0], 2) + Math.pow(pos[p2][1] - pos[p3][1], 2)); 
            double seg3 = Math.sqrt(Math.pow(pos[p3][0] - pos[p4][0], 2) + Math.pow(pos[p3][1] - pos[p4][1], 2)); 
            sum = seg1 + seg2 + seg3;
//            System.out.println(sum + " " + p1 + " " + p2 + " " + p3 + " " + p4);

            if(max < sum) {
                max = sum;
                maxPos = Arrays.copyOf(elements, 4);
            }

        } else {

            for (int i = nowCnt; i <= totalCnt; i++) {
                int tmp = elements[nowCnt]; 
                elements[nowCnt] = elements[i]; 
                elements[i] = tmp;
                permutation(elements, nowCnt+1, totalCnt);
                tmp = elements[nowCnt]; 
                elements[nowCnt] = elements[i]; 
                elements[i] = tmp;
            }
        }
    }

この問題は結構時間を使ったので解きたかった。

C問題

概要

・1~NまでのトランプがMセットある。

・Mセットをごちゃ混ぜにして、N枚取得する。

・1枚トランプを引いて、また山に戻した時に、同一の数のトランプを引く確率を求める。

解法

・不明・・・・・

・コンビネーションを使うと計算量はすごい事になりそうだし、longの範囲で収まらない。

・他の人の解法だけ記しておく。

    void solve() throws Throwable {
        double N = readInt();
        double M = readInt();
        if(M == 1) {
            pw.println(1.0 / N);
            return;
        }
        pw.println(1 / N + (M-1) * (N-1) / N / (N * M - 1));
    }

Mが1の時は、トランプを混ぜないので、1/Nになるのは分かる。

それ以外の場合が分からない。

同一のカードが一枚しか入らない場合と、うーん。

D問題

概要

・タスクがN個ある。

・1個のタスクはA,B,Cを順番にこなす必要がある。

・A,B,Cそれぞれ一度に行えるタスクの個数とタスクにかかる時間が引数で与えられる。

・全てのタスクを終えるための最小の時間を答える。

解法

・動的計画法を使用する。

・タスクAは単純にフルで回す。(タスクAが終わった毎にタスクAを実行する。)

・タスクBのN個目が終わる最小の時間は、

 「タスクAのN個目が終わった時間」

 「タスクBの[N-タスクBを一度に処理できる個数]が終わった時間」

 のいずれかの後に終わる時間+タスクBにかかる時間となる。

・タスクCについてもタスクBと同様にタスクBとの比較で最小時間を計算する。

    int[] dp2 = new int[10001];
    int[] dp3 = new int[10001];
    int K = 0;
    int N1 = 0;
    int N2 = 0;
    int N3 = 0;
    int T1 = 0;
    int T2 = 0;
    int T3 = 0;

    void solve() throws Throwable {
        K = readInt();
        N1 = readInt();
        N2 = readInt();
        N3 = readInt();
        T1 = readInt();
        T2 = readInt();
        T3 = readInt();
        int before = 0;
        
        for (int i = N1; i < K + N1; i+=N1) {
            int nCnt = i / N1;
            int nTime = nCnt * T1;
            for (int j = before; j < i; j++) {
                int jCnt = (j - before) / N2 + 1;
                if(j - N2 >=0) {
                    dp2[j] = Math.max(dp2[j - N2] + T2, nTime + T2 * jCnt);
                } else {
                    dp2[j] = nTime + T2 * jCnt;
                }
            }
            before = i;
        }
        dp2[K] = dp2[K-1];
        before = 0;
        for (int i = 0; i < K; i++) {
            if(i -N3 >= 0) {
                dp3[i] = Math.max(dp2[i] + T3, dp3[i-N3] + T3);
            } else {
                dp3[i] = dp2[i] + T3;
            }
        }
        pw.println(dp3[K-1]);
    
    }

タスクAの処理にかかる時間を計算するところで、

タスクAのループ処理の終了条件をKにしているところで失敗しました。

ループの開始をタスクAで処理できる個数にしていたので、

K+N1まで計算しないとやりきらないことがあります。

結果としては1完ですが、

なぜかレートは上がりました・・・・・。

1488⇒1585

土曜か日曜の夜早め以外の時間帯は参加できなくなるので、

競プロはもうたまにだなー

2014-07-23

SRM628 Div2

| 20:58

1完

easy

概要

・チェス盤とビショップの駒が与えられる。

・ビショップの現在位置の座標と移動したい場所の座標が与えられる。

・移動出来ない場合は-1,移動できる場合は移動に掛る回数を返却する。

解答方法

・x軸の距離とy軸の距離が等しい場合、1回で移動できる。

・x軸の距離とy軸の距離の偶奇が等しくない場合、移動できない。

 等しい場合、2回で移動できる。

	public int howManyMoves(int r1, int c1, int r2, int c2)
	{
	    
	    int p1 = Math.abs(r1 - r2);
	    int p2 = Math.abs(c1 - c2);
	    
	    if(p1 == 0 && p2 == 0) return 0;
	    
	    if(p1 == p2) {
	        return 1;
	    } else if (p1 % 2 == p2 % 2) {
	        return 2;
	    } 
	    return -1;
        }

medium

概要

・(,),{,},[,],Xで構成される文字列が与えられる。

・各カッコの同期が取れているかを操作する。また、Xは任意の文字に置き換えることが出来る。

XMLファイルの様に入れ子構造は許容しないものとする。

解答方法

・各種カッコが連続しているものを除外する。

・Xをそれぞれ6種類の文字に置き換えて、上記の処理を回す。

    private boolean dfs(String s) {
        while(s.contains("[]") || s.contains("{}") || s.contains("()")) {
            s = s.replaceAll("\\(\\)", "");
            s = s.replaceAll("\\[\\]", "");
            s = s.replaceAll("\\{\\}", "");
        }
        
        if(s.length() == 0) {
            return true;
        } else {
            if(s.contains("X")) {
                return dfs(s.replaceFirst("X", "[")) ||
                        dfs(s.replaceFirst("X", "{")) ||
                        dfs(s.replaceFirst("X", "(")) ||
                        dfs(s.replaceFirst("X", "]")) ||
                        dfs(s.replaceFirst("X", "}")) ||
                        dfs(s.replaceFirst("X", ")")) ;
                
            }
        }
        
        return false;
    }
    
	public String ifPossible(String expression)
	{
	    boolean b = dfs(expression);
	    return  b ? "possible" : "impossible";
        }

実際には、easyの問題は幅優先探索を使用して、

何回で移動出来るか試してたので、実装にちょっと時間かかりましたorz

medium問題は、Xのうまい取扱い方法が分からなくて

実装ミスりました。Xが5回以内しか出現しないという緩めの制約だったので、

全通り試せばいいとは思ってたんですが・・・・

918⇒891

グレーに落ちました。

8月からは月一ぐらいしか参加できなそうなのになぁ・・・・

2014-07-20

CodeForces R257 Div2

| 19:00

1完

A問題

概要

 ・飴が欲しくて一列に並んでいる子供がいる。

 ・子供はそれぞれ飴の欲しい数が異なる。

 ・列の先頭の子にN個の飴をあげる

 ・満足すれば列から抜ける。満足しなければ最後尾に並びなおす。

 ・一番最後に飴を貰う子を答える。

解答方法

 ・ループ処理で先頭から順に飴をあげる。

 ・飴をあげるごとに最後に飴をあげた子供の番号を更新する。

 ・ループ内で一度も飴をあげなかった場合(既に子供が並んでいない)に最後に飴をあげた番号を返す。

    void solve() throws Throwable {
        int n = readInt();
        int m = readInt();
        int[] c = readIntArray();
        int index = 0;
        while(true) {
            boolean isC = false;
            int i = 0;
            for (; i < n ; i++) {
                if(c[i] <= 0) {
                    continue;
                }
                c[i] -= m;
                index = i;
                isC = true;
            }
            if(!isC) {
                pw.println(index + 1);
                return;
            }
        }
    }    

B問題

概要

 ・f(i) = f(i-1) + f(i+1)

 ・f(1) = x, f(2) = y

 ・x,y,Nが与えられるときに、Nの戻り値を答える。

解答方法

 ・数学ゲー?

 ・N%6の戻り値分のケースに分類できる模様。

 ・でもよくわからない。

C問題

概要

 ・N * M のマスが与えられる。

 ・縦方向、または横方向に全部でN回分割出来る。

 ・最小のマスの大きさが最大になるようにした場合の大きさを返却する。

解答方法

 ・N,M,Kが10^9なので、Nの分割回数を0~K、または0~N試すとTLEになる。

1586⇒1486

CodeForces R256 Div2

| 18:45

2完

A問題

概要

 ・複数の棚がある。

 ・棚にメダルとトロフィーを入れたい。

 ・一つの棚にはメダル10個までかトロフィー5個までのどちらかのみを入れる。

 ・それぞれの大会で獲得したメダルとトロフィーの数と棚の数が与えられる。

 ・全て格納出来るかどうかを答える。

解答方法

 ・メダルとトロフィーの総和をそれぞれ計算する。

 ・それぞれ格納できる数で割る。

 ・また、剰余が発生するかを確認し、剰余が発生する場合は棚の数をデクリメントする。

ただし、他の人のソースを見て気付いたけど、わざわざ剰余を計算するよりも、以下の様に書いた方がすっきりしてよい。

あらかじめ「割られる数」に割る数-1を足してやれば、余りが出た場合も切り上げで求めることが出来る。

  N -= (aS + 4) / 5;

    void solve() throws Throwable {
        int[] a = readIntArray();
        int[] b = readIntArray();
        int N = readInt();
        
        int aS = 0;
        for (int aN  : a) {
            aS += aN; 
        }
        
        int bS = 0;
        for (int i : b) {
            bS += i;
        }
        
        N -= aS / 5;
        if (aS % 5 != 0) N--;
        
        N -= bS / 10;
        if (bS % 10 !=0) N--;
        
        if(N >=0) {
            pw.println("YES");
        } else {
            pw.println("NO");
        }
    }

B問題

概要

 ・文字列Sを変形して文字列Tにすることが出来るかどうか。

 ・文字列Sの要素を削除するだけでTに出来る場合は、「automaton」

 ・文字列Sの要素を並び変えるだけでTに出来る場合は、「array」

 ・どちらも行う場合は、「both」

 ・どちらを行っても出来ない場合は、「need tree」

解答方法

 ・それぞれの文字列のアルファベットの出現回数をメモする。

 ・文字列Tの方が出願回数の多いアルファベットがある場合、「need tree」

 ・文字列Sの方が出現回数の多いアルファベットがある場合、「automaton」のフラグを立てる。

 ・文字列Sと文字列Tで最長共通部分文字列を取得し、最長共通部分文字列の長さが文字列Tと等しくない場合、「array」のフラグを立てる。

 ・上記の2点より、「automaton」、「array」、「both」を判別する。

    void solve() throws Throwable {
        String s = readLine();
        String t = readLine();
        
        int[] sA = new int[27];
        int[] tA = new int[27];
        for (char c : s.toCharArray()) {
            sA[c-'a']++;
        }
        for (char c : t.toCharArray()) {
            tA[c-'a']++;
        }
        
        boolean isAutoMaton = false;
        for (int i = 0; i < 27; i++) {
            if(sA[i] > tA[i]) {
                isAutoMaton = true;
            } else if (sA[i] < tA[i]) {
                pw.println("need tree");
                return;
            }
        }
        
        char[] sX = s.toCharArray();
        char[] tX = t.toCharArray();
            
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < t.length(); j++) {
                if(sX[i] == tX[j]) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else {
                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        
        boolean isArray = false;
        if(dp[s.length()][t.length()] != t.length()) {
            isArray = true;
        }
        
        if(isAutoMaton && isArray) {
            pw.println("both");
        } else if (isAutoMaton) {
            pw.println("automaton");
        } else if (isArray) {
            pw.println("array");
        }
    }    

C問題

概要

 ・複数のフェンスがある。

 ・フェンスの横幅は1M,縦幅はそれぞれ異なる。

 ・フェンスに色を塗りたい。一回で塗れるのは縦方向、または横方向のみ。横方向に塗る場合は、塗る高さにフェンスが連続してないといけない。

 ・全てのフェンスに色を塗る時の最小の回数を求める。

解答方法(他の人のソースを参考にしてます)

 ・動的計画法を使う。

 ・dp[N+1]に、N本目を横塗りした場合の最小の塗る回数をメモする。

  やり方としては、N本目までに出現しているフェンスから遡って順々に、

  最も高さの低いフェンスから、今回横で塗りたいフェンスの高さの差を求める。

  N-j本目の最小の塗る数 + (i - j - 1)(一本遡る毎に縦塗りをする)+ 求めた高さの差

  N本目からN-j本目まで塗る場合の最小の塗る数を求める。

 

    void solve() throws Throwable {
        int N = readInt();
        int[] a = new int[N + 2];
        for (int i = 0; i < N; i++) {
            a[i+1] = readInt();
        }
        
        int[] dp = new int[N + 2];
        Arrays.fill(dp, N);
        dp[0] = 0;
        
        for (int i = 1; i <= N + 1; i++) {
            int minH = Integer.MAX_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                minH = Math.min(minH,  a[j]);
                int p = Math.max(0, a[i] - minH);
                dp[i] = Math.min(dp[i], dp[j] + i-j-1 + p);
//                System.out.println(i + " " + j + " " + dp[i]);
            }
        }
        
        pw.println(dp[N+1]);
}

1501⇒1586

最高レート更新ヽ(^o^)丿