読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

参加記録:AtCoder Beginner Contest 027

[参加記録] AtCoder Beginner Contest 027

URL

コンテストURL

abc027.contest.atcoder.jp

解説スライド

www.slideshare.net

結果

  • A, B, C問題の300点
    • D問題は部分点を狙いに行ったが取れず...orz
    • ABC的には難し目だったらしく59位。C問題が解けてよかった。

プログラム

A問題
  • 長方形の三辺の長さl1, l2, l3が与えられるので,残りの一辺の長さを求めよ。
  • 答え
    • l1, l2, l3のうち二辺の長さは同じなので,余っている一辺の長さが残りの一辺の長さに等しい。
    public void calc() {
        int l1 = in.nextInt();
        int l2 = in.nextInt();
        int l3 = in.nextInt();

        int ans = -1;
        
        if (l1 == l2) {
            ans = l3;
        }
        else if (l1 == l3) {
            ans = l2;
        }
        else if (l2 == l3) {
            ans = l1;
        }

        out.println(ans);
        out.close();
    }
B問題
  • 島の数Nと,各島の住人の数Aiが与えられる。
    • 各島の間には橋を架けることができ,橋を渡って島の住人を自由に移動させることができる。
    • 全ての島の住人の数を等しくしたいとき,架ける必要のある橋の最小の数を求めよ。
  • 答え
    • 最終的に各島に住むことになる住人の数Xは,全住人の数 ÷ 全島の数
    • 島を左から順に見ていき,前の島と橋を架ける必要があれば橋を架ける
    • 橋を架ける必要があるのは,現在の住人の数がXに等しくないとき
    • ただし,橋により繋がっている島々で,住人の平均がXに等しくなれば,それらの島々から更に橋を架ける必要はない
    public void calc() {
        int N = in.nextInt();         // 島の数
        int[] a = new int[N];        // 島iに住む住人の数
        double davg = 0.0;        // 最終的に各島に住むことになる人の数
        
        for (int i = 0; i < N; i++) {
            a[i] = in.nextInt();
            davg += a[i];
        }

        // 全住民の数を島の数で割った値が最終的な各島の住人の数
        davg /= N;
        
        // 最終的な住人の数が整数でなければ-1を出力して終了
        if (davg - (int)davg != 0.0) {
            out.println(-1);
        }
        else {
            int bridge = 0;            // 橋の数
            int sumPerson = 0;    // 島を左から見ていったときの,現在の住人の合計数
            int island = 0;            // 現在まで見てきた島の数
            
            // 島を左から順に見ていく
            for (int i = 0; i < N; i++) {
                // 住人と島の数を増やす
                sumPerson += a[i];
                island++;

                // 橋を架け始める最初の島だった場合
                if (island == 1) {
                    // 住人が初めから最終目的値と等しければ,橋は架けない
                    if (sumPerson == davg) {
                        sumPerson = 0;
                        island = 0;
                    }
                    // 次の島に進む
                    continue;
                }
                
                // 前の島との間に橋を架ける
                bridge++;

                // ここまで橋を架けてきた島々の住人の数を島の数で割る
                double personPerIsland = sumPerson / (double)island;

                // 最終目的値に等しければ,住人と島の数をリセットして次の島へ進む
                // 島の数をリセットすることで,次の島との間に橋は架からない
                if (personPerIsland == davg) {
                    sumPerson = 0;
                    island = 0;
                }
            }
            out.println(bridge);
        }        
        out.close();
    }
C問題
  • 正の数Nが与えられ,変数xを1に初期化する。
    • 高橋君と青木君は,それぞれ交互にxをx * 2もしくはx * 2 + 1に置き換えていく。
    • xがNよりも大きくなったとき,最後に操作を行った方が負けとなる。
    • それぞれが最善を尽くしたとき,どちらが勝つか求めよ。
  • 答え
    • 詳細は解説スライド参照だが,それぞれの戦略(x * 2にするかx * 2 + 1にするか)がNの深さによって変わってくる。
    • 自分の解いた方法は,Nの深さによって,高橋君が勝つことになる組み合わせの数が決定することを使用した。
    • 高橋君が勝つことになる組み合わせの数は以下のように決まる。(凄くわかりにくいけど。。。)
Nの深さ(ここではその深さでの最小の数) 1 2 4 8 16 32
高橋君が勝つことになる組み合わせの数 0 2 2 6 10 22
計算式(1行目の数 - 1つ前の勝つ組み合わせの数) X 2 - 0 4 - 2 8 - 2 16 - 6 32 - 10
高橋君が勝つのは小さい数からか大きい数からか
高橋くんが勝つ数の範囲 X 2~3 4~5 10~15 16~25 42~63
    public void calc() {
        BigDecimal N = new BigDecimal(in.next());

        boolean order = true;
        String ans;
        
        BigDecimal cur = new BigDecimal("1");
        BigDecimal two = new BigDecimal("2");
        BigDecimal takahashi = new BigDecimal("0");
        BigDecimal next;
                
        // curを2倍にしていって,Nの深さを求める
        while (true) {
            next = cur.multiply(two);
            
            if (next.compareTo(N) > 0) {
                break;
            }
            cur = next;
            takahashi = cur.subtract(takahashi);
            order = !order;
        }

        // Nの深さの偶奇により高橋君が勝つ数の範囲が小さい方からか否か決まる
        if (order) {
            // この場合高橋君が勝つのはN ~ N+takahashi-1
            if (cur.add(takahashi).compareTo(N) > 0) {
                ans = "Takahashi";
            }
            else {
                ans = "Aoki";            
            }            
        }
        else {
            // この場合高橋君が勝つのはN*2-takahashi ~ N*2-1
            if (next.subtract(takahashi).compareTo(N) <= 0) {
                ans = "Takahashi";            
            }
            else {
                ans = "Aoki";
            }                        
        }

        out.println(ans);
        out.close();
    }
D問題
  • 座標の原点にロボットが置かれており,ロボットには命令列Sが与えられる
    • 命令列は先頭から順に末尾まで実行され,M, +, -の3つの命令が含まれる
    • 命令がMのとき,ロボットは座標軸を正か負の方向に進むことができる
    • 命令が+(-)のとき,幸福度が現在の座標の位置だけ増える(減る)
    • 幸福度の初期値が0, 最後の命令を終えた時点でロボットは座標軸の原点に居なければならないとき,幸福度の最大値を求めよ
  • 答え
    • 再帰で色々条件を付けて枝刈りをしたもののTLE。
    • 解答を見ると,命令がMのとき,自分より右側の命令にある+と-の数がわかれば,幸福度の変化量が予測できるとのこと
    • これを利用し,幸福度が最大にな&&最終的に原点に戻るような行動の組み合わせを求める
    • 詳細は解答参照。プログラムにすると以下のようになった
    public void calc() {
        // 命令列
        char[] s = in.next().toCharArray();
        // 命令Mの数
        int numOfM = 0;        
        
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'M') {
                numOfM++;
            }
        }
        
        // 各Mで正の方向に進んだときの幸福度の増減値
        int[] A = new int[numOfM];
        // 現在見ている位置より右側にある'+'の数
        int numOfPlus = 0;
        // 現在見ている位置より右側にある'-'の数
        int numOfMinus = 0;
        // 現在見ているM(右から見ていく)
        int target = numOfM - 1;

        // 命令列を右から見ていく
        for (int i = s.length - 1; i >= 0; i--) {
            if (s[i] == 'M') {
                // 命令がMなら,自分より右側にある+の数から-の数を引いたものをAに入れる
                A[target] = numOfPlus - numOfMinus;
                target--;
            }
            else if (s[i] == '+') {
                numOfPlus++;
            }
            else if (s[i] == '-') {
                numOfMinus++;
            }
        }
        
        // Aをソート
        Arrays.sort(A);

        // 幸福度
        int kofuku = 0;

        // ソートしたAの前半分を負の方向に進む方に充てる
        for (int i = 0; i < A.length / 2; i++) {
            kofuku -= A[i];
        }
        // ソートしたAの後半分を正の方向に進む方に充てる
        for (int i = A.length / 2; i < A.length; i++) {
            kofuku += A[i];
        }
        
        out.println(kofuku);
        out.close();
    }