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

新人SEの学習記録

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

参加記録:AtCoder Regular Contest 041,AtCoder Beginner Contest 026

AtCoder 参加記録 プログラミングコンテスト

[参加記録] AtCoder Regular Contest 041

コンテストURL

Welcome to AtCoder Regular Contest 041 - AtCoder Regular Contest 041 | AtCoder

結果

  • A, B問題の200点
    • Cはもう少しだった…orz

プログラム

B問題
  • N x Mマスの盤面があり,各マスにはa_ij匹のアメーバがいた。
    • その後各マスのアメーバは分裂して上下左右のマスに1匹ずつ別れ,現在の各マスにはb_ij匹のアメーバが存在する
    • 現在の配置b_ijが与えられたとき,元の配置a_ijを求めよ

マスの左上から走査し,上下左右の隣マスのうち一番少ない数が元の配置のアメーバの数になる。

    public void calc() {
        int N = in.nextInt();
        int M = in.nextInt();
        char[][] input = new char[N][M];
        int[][] b = new int[N][M];
        int[][] ans = new int[N][M];

        for (int i = 0; i < N; i++) {
            input[i] = in.next().toCharArray();
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                b[i][j] = Character.getNumericValue(input[i][j]); 
            }
        }
        
        for (int i = 1; i < N - 1; i++) {
            for (int j = 1; j < M - 1; j++) {
                ans[i][j] = Math.min(b[i - 1][j], Math.min(b[i + 1][j], 
                        Math.min(b[i][j - 1], b[i][j + 1])));
                if (b[i - 1][j] != 0) b[i - 1][j] -= ans[i][j];
                if (b[i + 1][j] != 0) b[i + 1][j] -= ans[i][j];
                if (b[i][j - 1] != 0) b[i][j - 1] -= ans[i][j];
                if (b[i][j + 1] != 0) b[i][j + 1] -= ans[i][j];
                
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                out.print(ans[i][j]);
            }
            out.println();
        }
        out.close();
    }

[参加記録] AtCoder Beginner Contest 026

コンテストURL

Welcome to AtCoder Beginner Contest 026 - AtCoder Beginner Contest 026 | AtCoder

結果

  • 久々の全問完答!

プログラム

C問題
  • 会社にはN人の従業員がおり,それぞれ番号が1〜Nで与えられている。
    • 社員番号1の社長以外には,それぞれ一人の直属の上司Biを持つ。
    • 直属の部下がいない社員の給料は1で,それ以外の社員の給料はmin(直属の部下の給料)+max(直属の部下の給料)+1である。
    • 社長の給料を求めよ。

自分を上司とする社員を再帰で走査していって,
部下のいない(自分を上司とする社員のいない)社員の給料を1に設定してからその上司の給料を順に計算していく。
提出したプログラムは無駄にPersonクラスとかを作っていて読みにくかったので少し修正。
(まだごちゃごちゃしてるけど…)

    int N;
    int[] B;
    int[] Sal;
    List<List<Integer>> bukaLists;

    void saiki(int cur) {
        for (int i = 1; i < N; i++) {
            if (B[i] == cur) {
                saiki(i);
                bukaLists.get(cur).add(i);
            }
        }

        Sal[cur] = calcSalary(bukaLists.get(cur));
    }

    int calcSalary(List<Integer> bl) {
        if (bl.size() == 0) {
            return 1;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (Integer buka : bl) {
            int sal = Sal[buka];
            if (min > sal) {
                min = sal;
            }
            if (max < sal) {
                max = sal;
            }
        }

        return min + max + 1;
    }

    public void calc() {
        N = in.nextInt();
        B = new int[N];
        bukaLists = new ArrayList<List<Integer>>();
        Sal = new int[N];

        bukaLists.add(new ArrayList<Integer>());

        for (int i = 1; i < N; i++) {
            B[i] = in.nextInt() - 1;
            bukaLists.add(new ArrayList<Integer>());
        }

        saiki(0);

        out.println(Sal[0]);
        out.close();
    }
D問題
  • A, B, Cの値が与えられた時,f(t) = At * Bsin(Ctπ) = 100となるtを求める。

sinの文字が見えた時点で諦めかけていたが,二分探索でなんとかなるんじゃね?とやってみたら行けた。
探索範囲が大分適当だったが,実際にはt >= 200ならf(t)は100以上になる
(Bの最大値が100なので,Bsin(Ctπ)は最小でも-100になり,Aが最小の1でもt=200なら200-100で100になる)ので,
0〜200の間を走査すれば良いらしい。

    double EPS = 0.000001;
    int A, B, C;

    double f(double t) {
        return A * t + B * Math.sin(C * Math.PI * t);
    }
    
    public void calc() {
        A = in.nextInt();
        B = in.nextInt();
        C = in.nextInt();

        double a = 0.0, b = 200.0, m = 0.0;

        do {
            m = (a + b) / 2.0;
            if (f(m) > 100) {
                b = m;
            }
            else {
                a = m;
            }
        } while (!(Math.abs(f(m) - 100.0) < EPS));
        
        out.println(m);
        out.close();
    }