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

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

AtCoder Beginner Contest 098 B, C レビュー

B問題

B - Cut and Count

制約が  N \leq 100 なので、効率の悪いコードを書いても大丈夫そうです。

方針

全パターン調べます。 配列  X を作るときに文字の重複を無くして作成します。この配列を  Y と比較することで答えを得ます。

コード

import java.util.ArrayList;
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        String S = scan.next();
        scan.close();
        String []a = S.split("");
        //Arrays.sort(a);
        ArrayList<String> list1 = new ArrayList<String>();
        //list1.add(a[0]);
        int max = 0;
        int cnt = 0;
        for(int i = 0; i < N; i++) {
            check(list1, a[i]);
            cnt = 0;
            for(int j = 0; j < list1.size(); j++) {
                String t = list1.get(j);
                for(int l = i + 1; l < N; l++) {
                    if(t.equals(a[l])) {
                        cnt ++;
                        if(max < cnt) {
                            max = cnt;
                        }
                        break;
                    }
                }
            }
            //System.out.println(i + " listsize " + list1.size() + " max " + max);
        }
        //System.out.println("listsize" + list1.size());
        System.out.println(max);
    }
    public static void check(ArrayList<String> list, String a) {
        for(int i = 0; i < list.size(); i++) {
            if(a.equals(list.get(i))) {
                return;
            }
        }
        list.add(a);
    }
}

C問題

C - Attention

リーダの方を向くというのが良く分かりませんでしたが、同じ方向に向くというのではないということです。 二重ループがあるとタイムアウトしそうな問題でしょうか。

方針

文字列のEとWの数を計算結果を利用して解答を導く。

 i 番目の東側と西側にEとWが何個あるか計算する(i番目は無視する)。

 i 番目の要素に対して次の集合  D_i を考えます。

 D_i = (S_i, a_i, b_i, c_i, d_i)

ここで、

 a_i :  i 番目の東側にあるEの数。

 b_i :  i 番目の東側にあるWの数。

 c_i :  i 番目の西側にあるEの数。

 d_i :  i 番目の西側にあるWの数。

とします。また、SのEの数を e、Wの数を  w とします。

ここで、 e + w = N を満たします。

 a_i b_i を求める。

  •  S_0 = E のとき  a_0 = e - 1  b_0 = w

  •  S_0 = W のとき  a_0 = e  b_0 = w - 1

 S_i = E のとき  b_i = w

 a_{i - 1} = 0 ならば  a_{i} = 0

 a_{i - 1}  \neq 0 ならば、

 a_i = a_{i - 1} - 1

 S_i = W のとき  a_i = w

 b_{i - 1} = 0 ならば  b_{i} = 0

 b_{i - 1}  \neq 0 ならば、

 b_i = b_{i - 1} - 1

となります。

つまり、 a_i , b_i i - 1 番目の要素に依存するということです。

したがって、二重ループになることはありません。

 c_i d_i を求める。

これも  a_i b_i と同様にして求めることができます。

最小値を求める。

 i 番目がリーダーであるとした場合、リーダーの方を向いていない数  k は、

 k =a_i + d_i

となります。また、リーダーの向いてる方向に依存しません。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        String S = scan.next();
        scan.close();
        String []a = S.split("");
        int cntrW[] = new int[N];
        int cntrE[] = new int[N];
        int cntlW[] = new int[N];
        int cntlE[] = new int[N];
        int cntW = 0;
        int cntE = 0;
        cntlW[0] = 0;
        cntlE[0] = 0;
        cntrW[N - 1] = 0;
        cntrE[N - 1] = 0;
        for(int i = 0; i < N; i++) {
            if(a[i].equals("W")) {
                cntW ++;
            }
        }
        cntE = N - cntW;
        if(cntW == 0) {
            System.out.println(0);
            System.exit(0);
        }else if(cntE == 0) {
            System.out.println(0);
            System.exit(0);
        }
        if(a[0].equals("W")) {
            cntrW[0] = cntW - 1;
            cntrE[0] = cntE;
        }else {
            cntrW[0] = cntW;
            cntrE[0] = cntE - 1;
        }

        for(int i = 1; i < N - 1; i++) {
            if(a[i].equals("W")) {
                if(cntrW[i - 1] == 0) {
                    cntrW[i] = 0;
                }else {
                    cntrW[i] = cntrW[i - 1] - 1;
                }
                cntrE[i] = cntrE[i - 1];
            }else if(a[i].equals("E")){
                if(cntrE[i - 1] == 0) {
                    cntrE[i] = 0;
                }else {
                    cntrE[i] = cntrE[i - 1] - 1;
                }
                cntrW[i] = cntrW[i - 1];
            }
        }

        if(a[N - 1].equals("W")){
            cntlW[N - 1] = cntW - 1;
            cntlE[N - 1] = cntE;
        }else {
            cntlW[N - 1] = cntW;
            cntlE[N - 1] = cntE - 1;
        }
        for(int i = N - 2; i >= 1; i--) {
            if(a[i].equals("W")) {
                if(cntlW[i + 1] == 0) {
                    cntlW[i] = 0;
                }else {
                    cntlW[i] = cntlW[i + 1] - 1;
                }
                cntlE[i] = cntlE[i + 1];
            }else if(a[i].equals("E")){
                if(cntlE[i + 1] == 0) {
                    cntlE[i] = 0;
                }else {
                    cntlE[i] = cntlE[i + 1] - 1;
                }
                cntlW[i] = cntlW[i + 1];
            }
        }
        //int []k = new int[N];
        int min = 10000000;
        int k = 0;
        for(int i = 0; i < N; i++) {
            if(a[i].equals("W")) {
                k = cntrE[i] + cntlW[i];
            }else {   // E と等しい
                k = cntrE[i] + cntlW[i];
            }
            if(k <= min) {
                min = k;
            }

        }
//     for(int i = 0; i < N; i++) {
//         int sum = cntrW[i] + cntrE[i] + cntlW[i] + cntlE[i] + 1;
//         if(sum != N) {
//             System.out.println("error");
//         }
//     }
        System.out.println(min);

//     System.out.println(cntW + " " + cntE);
//     for(int i = 0; i < N; i++) {
//         System.out.print(i + " left: E " + cntlE[i] + " / W " + cntlW[i]);
//         System.out.println(" right: E " + cntrE[i] + " / W " + cntrW[i]);
//     }

    }
}