新人SEの学習記録

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

学習記録:ABC #072

[学習記録] ABC #072

今日から時間のある日はAtCoderのBeginner Contestの過去問題をやってみることにしました。
まずはABC #072から。

コンテストURL

abc072.contest.atcoder.jp

結果

A〜Dまで解説を見ずに解けた!

A問題

問題

砂時計に入っている砂の重さX[g]と,時間t[秒]が与えられる。
1秒間に1g砂が落ちるとして,t秒後に何gの砂が砂時計の上側に残っているか求めよ。

解答

Xよりtが大きければ0を返すように,三項演算子を使ってみた。

    public void calc() {
        int X = in.nextInt();
        int t = in.nextInt();
        
        int ans = (X - t > 0)? X - t: 0;
        
        out.println(ans);
        out.close();
    }

B問題

問題

文字列sが与えられる。
前から数えて奇数文字目だけ抜き出して作った文字列を求めよ。

解答

char型の配列にして,indexが(0オリジンなので)偶数の文字だけ出力した。

    public void calc() {
        String s = in.next();
        char[] carray = s.toCharArray();
        
        for (int i = 0; i < carray.length; i = i + 2) {
            out.print(carray[i]);
        }
        out.println();
        out.close();
    }

C問題

問題

長さNと整数列a1...aNが与えられる。
各aiについて1を足す or 1を引く or 何もしないの3つの操作からどれか一つを選んで行う。
上手く操作を行い,ある整数Xの個数を最大化したとき,この個数を求めよ。

解答

結局,各aiに1を足した時と1を引いた時と何もしなかったときで,他のaiには影響がないので,
全てのaiに+1, -1, +-0したときの個数を計算して一番大きい値を出せば良い。

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

        for (int i = 0; i < N; i++) {
            a[i] = in.nextInt();
        }

        // 整数XをKeyにし,その個数をValueとするMap
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < N; i++) {
            // 各aiについて何もしない, +1, -1したときの個数を入れていく
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
            map.put(a[i] + 1, map.getOrDefault(a[i] + 1, 0) + 1);
            map.put(a[i] - 1, map.getOrDefault(a[i] - 1, 0) + 1);
        }

        int ans = 0;
        
        for (Map.Entry<Integer, Integer> e: map.entrySet()) {
            // 一番大きいValue = 個数を求める
            ans = Math.max(e.getValue(), ans);
        }
        
        out.println(ans);
        out.close();
    }

D問題

問題

N個の整数からなる順列p1, ... pNが与えられる。
隣り合う二つの数を選んでスワップし,全てのpiに対して,i != piとなるようにしたい。
必要なスワップ操作の最小回数を求めよ。

解答

左端から見ていって,pi == iとなる数があったら,その右隣と入れ替えればOK。
最初は一番右端がpi == iとなっているときに入れ替えるのを忘れていた。

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

        for (int i = 1; i <= N; i++) {
            p[i] = in.nextInt();
        }

        int ans = 0;
        
        // 右隣と入れ替える(配列の長さを越えないように注意)
        for (int i = 1; i < N; i++) {
            if (p[i] == i) {
                int tmp = p[i];
                p[i] = p[i+1];
                p[i+1] = tmp;
                ans++;
            }
        }
        
        // 一番右端の数字を入れ替える場合
        if (p[N] == N) {
            ans++;
        }
        
        out.println(ans);
        out.close();
    }