AtCoder Beginner Contest 098 B, C レビュー - ヤマカサのプログラミング勉強日記

B問題

制約が $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]);
//     }

    }
}

B問題

方針

コード

C問題

方針

と を求める。

と を求める。

最小値を求める。

コード

$a_i$ と $b_i$ を求める。

$c_i$ と $d_i$ を求める。