AtCoder ABC 127 A&B&C&D

近いうちにE&Fを解きに戻ってくる。

2019/05/27
　Bのコード修正

A - Ferris Wheel

    private void solveA() {
        int a = nextInt();
        int b = nextInt();

        if (a <= 5) {
            out.println(0);
        } else if (a <= 12) {
            out.println(b / 2);
        } else {
            out.println(b);
        }
    }

B - Algae

$x_{2001}=r \times x_{2000}−D$
$x_{2002}=r \times x_{2001}−D$
・
・
$x_{i+1}=r \times x_i−D$

    private void solveB() {
        int r = nextInt();
        int d = nextInt();
        int x2000 = nextInt();

        int pre = x2000;
        for (int i = 1; i <= 10; i++) {
            pre = r * pre - d;
            out.println(pre);
        }

    }

C - Prison

入力例１

4 2
1 3
2 4

1番目のゲートは1,2,3のキーで開く
2番目のゲートは2,3,4のキーで開く
- 両方のゲートを開けられるのは2,3のキー
すべてのゲートで使われているキーを探せばよい

	Key:1	Key:2	Key:3	Key:4
Gate:1	O	O	O
Gate:2		O	O	O
すべてを開ける鍵		↑	↑

数字に置き換えてみた。

	Key:1	Key:2	Key:3	Key:4
Gate:1	1	1	1
Gate:2		1	1	1
合計	1	2	2	1

合計=ゲートの数になるキーがすべての扉を開けられる。
こういうある範囲からある範囲までを足すみたいな処理は、、、いもす法が早い。

ということでいつもの参考サイトリストを貼っておく

参考サイト(いもす法および累積和)

        int n = nextInt();
        int m = nextInt();

        //各ゲートで何番のキーが必要かのmemo用
        int[] wk = new int[n];

        for (int i = 0; i < m; i++) {
            int l = nextInt() - 1;
            int r = nextInt() - 1;
            wk[l] += 1;
            if (r + 1 < n) {
                wk[r + 1] -= 1;
            }
        }

        //
        for (int i = 1; i < n; i++) {
            wk[i] += wk[i - 1];
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (wk[i] == m) {
                cnt++;
            }
        }

        out.println(cnt);

D - Integer Cards

カードを書き換える順番に指定はないので
- 取り込んだカードの小さいものを大きいもので書き換えていくのがよさそう

A（取り込んだカード達）を並べる（ここでは昇順）
B（枚数）,C（整数）をC順に並べる（ここでは降順）
Aの小さいものから順に、[B,C]と比較する
最大B枚まで、CがAより大きいかどうかを比較して、Cの方が大きいならAを書き換える
1. 3-4を繰り返す

3の箇所について、コード上は以下の処理をしているけど、これは「B,Cは降順に並べているので一度Cで書き換えた個所は、それ以降書き換えられることはない（書き換えた時のCより大きいCは出現しない）」ため
こうしないと余計な処理をしていて時間が足りなくなる

 //同じところを書き換える（比較する）意味はないのでstartをずらしていく
        int start = 0;

コード全体

    private void solveD() {
        int n = nextInt();
        int m = nextInt();
        long[] a = LongStream.range(0, n).map(i -> nextLong()).toArray();

        //小さい順に並べ替え
        Arrays.sort(a);

        int[][] bc = IntStream.range(0, m).collect(() -> new int[m][2],
                (t, i) -> {
                    t[i][0] = nextInt();
                    t[i][1] = nextInt();
                },
                (t, u) -> {
                    Stream.concat(Arrays.stream(t), Arrays.stream(u));
                });

        //Cが大きい順に並べ替え
        Arrays.sort(bc, (x, y) -> -Integer.compare(x[1], y[1]));
        //同じところを書き換える（比較する）意味はないのでstartをずらしていく
        int start = 0;
        for (int j = 0; j < m; j++) {
            int max = Integer.min((start + bc[j][0]), n);
            for (int k = start; k < max; k++) {
                if (bc[j][1] > a[k]) {
                    //a[i]の方が小さいのは書き換え
                    a[k] = bc[j][1];
                    //次のstartをずらす準備
                    start = k + 1;
                } else {
                    //既にソート済みなので、a[i]の方が大きいならこれ以上比較する必要なし
                    break;
                }
            }

        }
        //合計
        long res = Arrays.stream(a).sum();

        out.println(res);
    }

ABC - 127 - A&B&C

AtCoder ABC 127 A&B&C&D

A - Ferris Wheel

B - Algae

C - Prison

D - Integer Cards