山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.150 "良問"(良問とは言っていない

問題

https://yukicoder.me/problems/no/150

文字列の問題です。文字列の問題はなんか苦手意識があります。

必要な操作回数が 0 となるケースを見つけるのは簡単なので、操作を必要とするケースは考える必要があります。

考え方

必要な操作回数はハミング距離で与えられます。

ハミング距離 - Wikipedia

与えられた文字列の長さを lとします。

 l = |S|

このとき、「good」の先頭の番号 aは、

 1 \leq a \leq l - 10

を満たす必要があり、「problem」の先頭の番号 b

 a + 4 \leq b \leq l - 6

となります。

「good」を固定して、「problem」を移動させて操作回数を求めるのは効率が悪いので、別の方法を考えます。

ここで、「problem」の文字列の後ろから操作回数の最小値を求めることを考えます。

「problem」の先頭の番号による操作回数の最小値を表す配列を \rm {cost}_2 [ b ] とします。調べる範囲は下になります。

 4 \leq b \leq l - 6

文字列の後ろから最小値を求めるので、この配列の値は単調増加になります。

なぜ単調増加になるかというと、 b = l - 7 から b = 4調べるときに、操作回数の最小値が減少することはあっても増加することはないからです。つまりこの配列の \rm {cost}_2 [ b ]の値の意味は、操作する文字列の先頭番号が b 以降の部分文字列のなかで、ハミング距離の最小値を表しています。

「good」の方は、先頭番号 aのハミング距離を求めた配列を用意します。この配列を \rm{cost}_1 [ a ] とします。

この配列は先頭番号が aのハミング距離なので、単調増加でも単調減少でもありません。

よって、

 \rm{cost}_1 [ i ]  +  \rm {cost}_2 [ i  + 4 ]

の最小値が答えとなります。

コード

import java.util.Scanner;

public class Exec0150 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        int []ans = new int[T];
        char []c1 = {'g', 'o', 'o', 'd'};
        char []c2 = {'p', 'r', 'o', 'b', 'l', 'e', 'm'};

        for(int i = 0; i < T; i++) {
            String s = scan.next();
            int index1 = s.indexOf("good");
            int index2 = s.indexOf("problem");
            if(index1 != -1 && index1 < index2) {
                ans[i] = 0;
            }else {
                int []cost1 = new int[s.length()];
                int []cost2 = new int[s.length()];
                int min = 7;
                //System.out.println(s.length());
                for(int j = s.length() - 7; j >= 4; j--) {
                    int cnt2 = 0;
                    for(int k = 0; k <= 6; k++) {
                        char t1 = s.charAt(j + k);
                        if(t1 != c2[k]) {
                            cnt2++;
                        }
                    }
                    if(min > cnt2) {
                        min = cnt2;
                    }
                    //System.out.println(min);
                    cost2[j] = min;
                }
                for(int j = 0; j < s.length() - 10; j++) {
                    int cnt1 = 0;
                    for(int k = 0; k < 4; k++) {
                        char t1 = s.charAt(j + k);
                        if(t1 != c1[k]) {
                            cnt1++;
                        }
                    }
                    cost1[j] = cnt1;
                }
                int cost = 11;
                for(int j = 0; j < s.length() - 10; j++) {
                    int t = cost1[j] + cost2[j + 4];
                    if(t < cost) {
                        cost = t;
                    }

                }
                ans[i] = cost;
            }
        }
        scan.close();
        for(int i = 0; i < T; i++) {
            System.out.println(ans[i]);
        }
    }
}