新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:ABC #071

[学習記録] ABC #071

引き続きAtCoder Beginner Contestの過去問を解いてます。

コンテストURL

abc071.contest.atcoder.jp

結果

今回もA〜Dまで解説を見ずに解けた!
ABCをやるより頑張ってARCに挑んだ方が良いか…?

A問題

問題

数直線上の位置a, b, xが与えられる。
xからaとbのどちらが近いか求め,"A"か"B"で出力せよ。

解答

絶対値を使って三項演算子で"A"か"B"を入れた。

    public void calc() {
        int x = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();

        String ans = (Math.abs(a - x) < Math.abs(b - x))? "A" : "B"; 
        
        out.println(ans);
        out.close();
    }

B問題

問題

英小文字からなる文字列Sが与えられる。
Sに現れない英小文字について,アルファベット順で小さいものを求めよ。ただし,Sに全ての英小文字が現れる場合は"None"を出力せよ。

解答

各小文字についてフラグを管理する方法もあると思うが(そっちの方がわかりやすかった気がする),
配列をソートしてごちゃごちゃやってしまった。

    public void calc() {
        String S = in.next();
        char[] carray = S.toCharArray();
        Arrays.sort(carray);
        String alphabet = "abcdefghijklmnopqrstuvwxyz";
        int index = 0;
        String ans = "None";
        
        for (char c : alphabet.toCharArray()) {
            if (index >= carray.length || carray[index] != c) {
                ans = c + "";
                break;
            }
            while (index < carray.length && carray[index] == c) {
                index++;
            }
        }

        out.println(ans);
        out.close();
    }

C問題

問題

N個の棒について,長さAiが与えられる。
これらの棒から異なる4本を選び,長方形を作る時,最大の面積になる長方形の面積を求めよ。

解答

Mapに棒の長さとその長さの棒の本数を入れてソート。
棒を長い順に見ていって,2本以上あればそれを使う,という感じで作った。
もっとも長い棒が4本ある場合,縦も横も同じ長さの棒を使えることを最初失念していてエラーになった。
また,Aiが10^9以下と大きいので,面積を求めるときはBigDecimalなりを使わないとダメ。

    public void calc() {
        int N = in.nextInt();
        int[] A = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < N; i++) {
            map.put(A[i], map.getOrDefault(A[i], 0) + 1);
        }
        
        Object[] mapkey = map.keySet().toArray();
        Arrays.sort(mapkey);

        int w = 0;
        int h = 0;
        
        for (int i = mapkey.length - 1; i >= 0; i--) {
            int key = (int)mapkey[i];
            int num = map.get(key);
            if (num >= 4 && w == 0) {
                w = key;
                h = key;
                break;
            }
            else if (num >= 2 && w == 0) {
                w = key;
            }
            else if (num >= 2 && w != 0) {
                h = key;
                break;
            }
        }        
        
        BigDecimal width = new BigDecimal(String.valueOf(w));
        BigDecimal height = new BigDecimal(String.valueOf(h));
        BigDecimal ans = width.multiply(height).stripTrailingZeros();
        
        out.println(ans.toPlainString());
        out.close();
    }

D問題

問題

2×Nのマス目があり,このマス目にN個のドミノを敷き詰める。
ドミノは1×2の大きさで,マス目に縦または横に配置できる。
ドミノの敷き詰め方は文字列S1, S2で与えられ,それぞれ異なる英字で以下のように示される。

xaa
xbb

このとき,左端にはドミノが縦に,その次にはドミノが横になって上下に配置されていることを示す。
これらのドミノを3色で塗り,接しているドミノは異なる色で塗り分けるようにするとき,塗り方が何通りあるかをmod 1000000007で求めよ。

解答

複雑で投げ出しそうになったが,左端からドミノを見ていくと,縦にドミノを1つ置くか,横にドミノを上下2つで並べるかの2通りしかない。
左から順に見ていき,塗り分けられるパターンが何通りあるかを掛けていけば良い。
一番左端が縦ドミノの場合は3通り,横ドミノの場合は6通りの塗り分け方が存在する。
その次からは,左隣りのドミノが縦か横かと,自分自身が縦か横かの4パターンで塗り分け方が何通りあるか異なる。

  • 縦 -> 縦:2通り
  • 縦 -> 横:2通り
  • 横 -> 縦:1通り
  • 横 -> 横:3通り

これらの値を,左端のドミノから掛け算していけばOK。
なお,答えはmod 1000000007で求める必要があるので,掛け算の度にmodを求めておく。
その際,Javaのintだと一時的にintの最大値を越えてしまう可能性があるのでlongにしておくこと。

    public void calc() {
        int N = in.nextInt();
        char[] S1 = in.next().toCharArray();
        char[] S2 = in.next().toCharArray();
        final int MOD = 1000000007;

        long ans = 0;
        // 左横のドミノが縦向きならtrueをとる
        boolean portrait = false;
        
        // S1について1文字ずつ見ていく
        for (int i = 0; i < S1.length; i++) {
            char c = S1[i];

            // ドミノが縦向きなら
            if (c == S2[i]) {
                if (i == 0) {
                    // 左端のドミノが縦向きなら最初の塗り方は3通り
                    ans = 3;
                }
                else {
                    if (portrait) {
                        // 縦 -> 縦なら*2通りする
                        ans = ((ans % MOD) * 2) % MOD;
                    }
                    else {
                        // 横 -> 縦なら1通りしかないので何もしない
                    }
                }
                // 前のドミノを縦向きにする
                portrait = true;
            }
            // ドミノが横向きなら
            else {
                if (i == 0) {
                    // 左端のドミノが横向きなら最初の塗り方は6通り
                    ans = 6;
                }               
                else {
                    if (portrait) {
                        // 縦 -> 横なら*2通りする
                        ans = ((ans % MOD) * 2) % MOD;
                    }
                    else {
                        // 横 -> 横なら*3通りする
                        ans = ((ans % MOD) * 3) % MOD;                        
                    }
                }
                // 前のドミノを横向きに設定して1つ多く進む
                portrait = false;
                i++;
            }
        }