新人SEの学習記録

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

参加記録:AtCoder Beginner Contest 028

[参加記録] AtCoder Beginner Contest 028

URL

コンテストURL

abc028.contest.atcoder.jp

結果

  • 久々の完答400点
    • 30分ほどで終わったがD問題でWAしまくったため順位は低い...orz

プログラム

A問題
  • テストの点数が与えられるので,点数によって"Good"などの文字列を出力せよ。

if文使うだけなので省略。

B問題
  • 与えられた文字列中に含まれる'A'〜'F'の個数を出力せよ。

C++だとcount関数があるらしいが,Javaだと1文字1文字数えるか,replaceして文字列の長さを変えるなどするしかない?

count(s.begin(), s.end(), 'A')

なおScalaだとcount関数があった。
引数はChar => Boolean型で,Intを返す。

scala> val str = "ABBCCCDDDD"
str: String = ABBCCCDDDD

scala> str.count(c => c == 'A')
res0: Int = 1

scala> str.count(c => c == 'B')
res1: Int = 2

scala> str.count(c => c == 'C')
res2: Int = 3

scala> str.count(c => c == 'D')
res3: Int = 4
C問題
  • 異なる5つの数A, B, C, D, Eが与えられ,そのうち3つの数の合計値の中で3番目に大きい数を求めよ。

全ての組み合わせで足し算してソート。

    public void calc() {
        int[] num = new int[5];
        int[] result = new int[5 * 4 * 3];
        
        for (int i = 0; i < num.length; i++) {
            num[i] = in.nextInt();
        }
        
        int cur = 0;

        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 4; j++) {
                for (int k = j + 1; k < 5; k++) {
                    result[cur] = num[i] + num[j] + num[k];
                    cur++;
                }
            }
        }
        
        Arrays.sort(result);

        out.println(result[60 - 3]);
        out.close();
    }

…と思ったら問題文の条件"A < B < C < D < E"を見逃していた。。。
この条件下で3番目に大きい数はA + D + EかB + C + Eなのでこれらのmaxを取るだけで良いらしい。

    public void calc() {
        int A = in.nextInt();
        int B = in.nextInt();
        int C = in.nextInt();
        int D = in.nextInt();
        int E = in.nextInt();
        
        out.println(Math.max(A + D + E, B + C + E));
        out.close();
    }
D問題
  • 整数N, Kが与えられるので,1~Nの値をとる乱数を3回生成したとき,3つの値の中央値がKになる確率を求めよ。

中央値がKになる組み合わせは

  • (1~K-1), K, (K+1~N)の組み合わせ(順序入れ替えで6通り)
  • (1~K-1), K, Kの組み合わせ(順序入れ替えで3通り)
  • K, K, (K+1~N)の組み合わせ(順序入れ替えで3通り)
  • K, K, Kの組み合わせ(1通りのみ)

なので,これの和をN^3で割ればOK。

ちなみにWAの原因は以下だった。。

  • Nは最大10^6なのでN^3をintとかに入れるとオーバーフロー
  • println関数だと値が小さくなると勝手に指数表現になる(2.699878E-9など)
    public void calc() {
        int N = in.nextInt();
        int K = in.nextInt();
        
        double comb = (K - 1.0) * (N - K) * 6 + (K - 1) * 3 + (N - K) * 3 + 1;
        
        System.out.printf("%.10f\n", comb / N / N / N);
        out.close();
    }