Greedyアルゴリズム編

別途説明記事書いてましたけど

mankozooyork.hatenablog.com

A - Sorted Arrays

atcoder.jp

全く実装は思いつかなかったです...
単純に 1 - 2 - 3 - 2 - 1と数字がきたなら[1,2,3], [2,1]と左から数字が上がっていっているのか、下がっていっているのか見ていくやりかた.
これはググったらでてきた方のC++コードを勝手にjavaにしてるだけです.
while部分で <=や>=があるのは、例えば2,3,2,3,3といった数字が来た際に[2,3],[2,3],[3]となってしまうことを防ぐためです.

        int ans = 0;
        for(int i=0; i<n; i++) {
            while(i+1 < n && a[i] == a[i+1]) i++;
            if(i+1 < n && a[i] < a[i+1]) {
                while(i+1 < n && a[i] <= a[i+1]) i++;
            } else if(i+1 < n && a[i] > a[i+1]) {
                while(i+1 < n && a[i] >= a[i+1]) i++;
            }
            ans++;
        }
        System.out.println(ans);

A - Airport Bus

atcoder.jp

なんとなーくイケそうな雰囲気したけど撃沈でした
Kの差分まで許容するGreedyなグループ分けをしないとACになりませんでした

あとは今回はnも10⁶だったのでfor文にi++が必要ないバージョンでした（とゆうかつけたら答え間違う）

Arrays.sort(t);
int bus = 0;
for(int i=0; i<n;) {
    int start = i;
    while(i < n && t[i] - t[start] <= k && i - start < c) i++;
    bus++;
}
System.out.println(bus);

C - Sequence

atcoder.jp

まずそれぞれの与えられた和の解が+-+-とかになってないといけない＆＆それぞれの値の和は0にはなってはいけない状況下で、
最も数字を変えずにできる回数はいくつですかという問題ですが押さえておくべきポイントは３つ

1. 数字の符号を入れ替えたいときはその数字の絶対値+1でできること
   e.g. 数字が-1だった場合: Math.abs(-1)+1とすれば1に入れ替わる。この問題であれば左記の解が操作回数となる.
2. +-+-...、-+-+...と並ぶ以外のパターンはないので、それに気づいてそれぞれに対しての解を求めること
3. 二重ループしないやり方だと1.をするしかない。最近のGreedy系の回答であるforとwhileの掛け合わせしたらTLEだった

下記は+-+-の場合、あとは反対版をやってMath.min()するだけ。

        //+-+-
        for(int i=0; i<n; i++) {
            tmp1 += a[i];
            if(i % 2 == 0) {
                if(tmp1 <= 0) {
                    num1 += Math.abs(tmp1) + 1;
                    tmp1 += Math.abs(tmp1) + 1;
                }
            } else {
                if(tmp1 >= 0) {
                    num1 += Math.abs(tmp1) + 1;
                    tmp1 -= Math.abs(tmp1) + 1;
                }
            }
        }

C - Together

atcoder.jp

これは解けそうな気がしたがTLEくらってBuket Sortしたら99999とかきたときにindex out of rangeになって悶々としてたら
set->mapのfrequencyとかする必要全くなしで、単にmapで数え上げるだけでよいそこまでgreedy感もない問題でした
ポイントはただ単に全ての可能性を考えた配列を作って、そこにHashMapでキーに対する登場回数を数え上げて最大値をとってくるだけ...
下記さえできれば何も問題ない。

        Map<Integer,Integer> m = new HashMap<>();
        for(int i: na) {
            if(m.containsKey(i)) {
                m.put(i, m.get(i)+1);
            } else {
                m.put(i, 1);
            }
        }

B - Magic 2

単純にA<B<CとなるまでにB、Cを何回２倍すれば左記条件式を満たすか？という発想がでてこれば一瞬で解けるはずだけどでてきませんでした。。
意味不明な全探索をしていて解けず。下記ができれば十分です.

        int cnt = 0;
        while(a >= b) {
            b *= 2;
            cnt++;
        }

        while(b >= c) {
            c *= 2;
            cnt++;
        }

        if(k >= cnt) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }