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

問題

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

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

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

考え方

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

ハミング距離 - Wikipedia

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

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

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

となります。

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

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

「problem」の先頭の番号による操作回数の最小値を表す配列を とします。調べる範囲は下になります。

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

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

「good」の方は、先頭番号のハミング距離を求めた配列を用意します。この配列をとします。

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

よって、

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

コード

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]);
        }
    }
}