AtCoder Beginner Contest 134 E-Sequence Decomposing

E - Sequence Decomposing

解法:

二次元配列を作ります。そしてDPのように更新ならずの追加していきます。

イメージ図

入力:2

[2]

入力:1

[2]

[1]

入力:4

[2,4]

[1]

入力:5

[2,4,5]

[1]

入力:3

[2,4,5]

[1,3]

これを馬鹿正直に実装するとこうなります。

public static void main(String[] args) {
       FScanner sc = new FScanner();
    long N = sc.nextLong();
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for (long i = 0; i < N; i++) {
        int num = sc.nextInt();
        boolean flg = false;
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j).get(list.get(j).size() - 1) < num) {
                flg = true;
                list.get(j).add(num);
                break;
            }
        }
        if (!flg) {
            List<Integer> ary = new ArrayList<Integer>();
            ary.add(num);
            list.add(ary);
        }
    }
    System.out.println(list.size());
}

しかしこの回答はTLEします。

実はこの解法、結局は各配列の最大値を見ているだけなので、一次元配列で良いことに気が付きます

一次元に落とすとこうなります。最大値を更新しているだけですね

public static void main(String[] args) {
    FScanner sc = new FScanner();
    long N = sc.nextLong();
    List<Integer> list = new ArrayList<Integer>();
    for (long i = 0; i < N; i++) {
        int num = sc.nextInt();
        boolean flg = false;
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) < num) {
                flg = true;
                list.set(j, num);
                break;
            }
        }
        if (!flg) {
            list.add(num);
        }
    }
    System.out.println(list.size());
}

しかしこの回答もTLEします。ということは・・・

のんきに配列を回しているのが問題ということになります。

そこで二分探索を使います。(正確にはc++のstd::lower_boundをjavaの二分探索を使って実装します。

注意としては二分探索はソートしてないと使えません。また重複キーを検知しないのでComparatorをいじる必要があります。

ここを参考(丸パクリ)しました。

qiita.com

最終的なコードは以下になります

public static void main(String[] args) {
    FScanner sc = new FScanner();
    long N = sc.nextLong();
    List<Integer> list = new ArrayList<Integer>();
    int[] n = new int[(int) N];
    for (int i = 0; i < N; i++) {
        n[i] = sc.nextInt();
    }
    for (long i = 0; i < N; i++) {
        int num = n[(int) i];
        int j = LowerBoundCollection(list, num);
        if (list.size() == 0) {
            list.add(num);
            continue;
        }
        if (list.size() < j || j > 0) {
            list.set(j - 1, num);
        } else {
            list.add(0, num);
        }
    }
    System.out.println(list.size());
}
 
public static int LowerBoundCollection(List<Integer> ary, int target) {
    int result = Collections.binarySearch(ary, target, new LowerBoundComparator<>());
    int insertionPoint = (result >= 0) ? result : ~result;
    return insertionPoint;
}
 
public static class LowerBoundComparator<T extends Comparable<? super T>>
        implements Comparator<T> {
    public int compare(T x, T y) {
        return (x.compareTo(y) >= 0) ? 1 : -1;
    }
}

AtCoder Beginner Contest 134受験記

AtCoder Beginner Contest 134

A - Dodecagon

そ の ま ま

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int r = sc.nextInt();
    System.out.println((int) Math.pow(r, 2) * 3);
}

B - Golden Apple

監視できる範囲が 2D + 1 だから N / (2D + 1) であまりがあれば切り上げ

絵をかいたら分かった

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int N = sc.nextInt();
    int D = sc.nextInt();
    int amari = N % (1 + 2 * D);
    int syou = N / (1 + 2 * D);
    if (amari != 0) {
        syou++;
    }
    System.out.println(syou);
}

C - Exception Handling

ソートして値が最大値と一致したら最大値以下の最大値を出力

最大値と一致しないなら最大値を出力

例:3 5 1 5 => 1 3 5 5

対象:5 => ソート済み配列最大値の5と一致するので最大値以下の最大値 すなわち 1 3 ⑤ 5の⑤を出力

対象:最大値以外 => 最大値である5を出力

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int N = sc.nextInt();
    int[] ary = new int[N];
    int[] sorted = new int[N];
    for (int i = 0; i < N; i++) {
        ary[i] = sc.nextInt();
        sorted[i] = ary[i];
    }
    Arrays.sort(sorted);
    for (int i = 0; i < N; i++) {
        if (sorted[N - 1] == ary[i]) {
            System.out.println(sorted[N - 2]);
        } else {
            System.out.println(sorted[N - 1]);
        }
    }
}

D - Preparing Boxes

貪欲法で後ろから見ていく

すると2で割ったあまりであるため以下のように一意の値に決めることができる

aのi番目が0の時 かつ 各合計の2で割ったあまりが0の時 => 0

aのi番目が1の時 かつ 各合計の2で割ったあまりが0の時 => 1

aのi番目が0の時 かつ 各合計の2で割ったあまりが1の時 => 1

aのi番目が1の時 かつ 各合計の2で割ったあまりが1の時 => 0

なんかサンプルケースの出力に騙されたり問題読み間違えたりして時間食った

-1になるケースは存在しない

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int N = sc.nextInt();
    int[] ary = new int[N];
    for (int i = 0; i < N; i++) {
        ary[i] = sc.nextInt();
    }
    int[] collect = new int[N];
    for (int i = N - 1; i >= 0; i--) {
        if (N / (i + 1) == 1) {
            collect[i] = ary[i];
        } else {
            int sum = 0;
            int syou = N / (i + 1);
            int f = (i + 1) * syou;
            while (syou > 0) {
                sum += collect[f - 1];
                f -= (i + 1);
                syou -= 1;
            }
            sum = sum % 2;
            if (ary[i] == sum) {
                collect[i] = 0;
            } else {
                collect[i] = 1;
            }
        }
    }
    int kosu = 0;
    for (int i = 0; i < N; i++) {
        if (collect[i] == 1) {
            kosu++;
        }
    }
    System.out.println(kosu);
    boolean fFlg = false;
    for (int i = 0; i < N; i++) {
        if (collect[i] == 1) {
            if (fFlg) {
                System.out.print(" ");
            }
            fFlg = true;
            System.out.print(i + 1);
        }
    }
}

E - Sequence Decomposing

実装は簡単だけどTLEでした

計算量の工夫が必要ですね...

レート更新

レート更新早くなった?? 茶色までが遠いです!!!!!!!! パフォ緑でてるのにね

f:id:repenguin:20190720235108p:plain

f:id:repenguin:20190720235150p:plain

AtCoder Beginner Contest 133受験記

AtCoder Beginner Contest 133受験しました

C問題まで解けました。D問題はT・L・E!!

A - T or T

計算して最小値を出すだけ

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int N = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    int train = N * A;
    int taxi = B;
    System.out.println(Math.min(train, taxi));
}

B - Good Distance

これも全通り計算するだけ

ルートが整数か判定するのに一瞬戸惑ったが intにキャストして比較すればOKだった

public static void main(String[] args) {
    FScanner sc = new FScanner();
    int N = sc.nextInt();
    int D = sc.nextInt();
    int[][] ary = new int[N][D];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < D; j++) {
            ary[i][j] = sc.nextInt();
        }
    }
    int ret = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            long sum = 0;
            for (int k = 0; k < D; k++) {
                sum += Math.pow(ary[i][k] - ary[j][k], 2);
            }
            double root = Math.sqrt(sum);
            if (root == (int) root) {
                ret++;
            }
        }
    }
    System.out.println(ret);
}

C - Remainder Minimization 2019

2019のあまりという時点でいくつか場合わけができる

①L <= 2019 * x <= Rの場合 (xは整数)

LR間に2019の倍数が含む場合2019の倍数を使用することであまりは必ず0になる

②①以外の場合(R<2019 OR 2019の倍数をLR間に含まない)

全探索 下のコードは②を場合分けしてる

public static void main(String[] args) {
    FScanner sc = new FScanner();
    long L = sc.nextLong();
    long R = sc.nextLong();
    if (R < 2019) {
        long min = (L * R) % 2019;
        for (long i = L; i < R; i++) {
            for (long j = i + 1; j <= R; j++) {
                long cal = (i * j) % 2019;
                min = Math.min(min, cal);
            }
        }
        System.out.println(min);
        return;
    } else {
        int q = 1;
        boolean contain = false;
        while (q * 2019 <= R) {
            if (L <= q * 2019 && R >= 2019 * q) {
                contain = true;
                break;
            }
            q++;
        }
        if (contain) {
            System.out.println(0);
            return;
        } else {
            long min = (L * R) % 2019;
            for (long i = L; i < R; i++) {
                for (long j = i + 1; j <= R; j++) {
                    long cal = (i * j) % 2019;
                    min = Math.min(min, cal);
                }
            }
            System.out.println(min);
            return;
        }
    }
}

D - Rain Flows into Dams

TLE + WA

山1を決めてやることで後ろの山がすべて決まる。

そのため貪欲法で全探索すれば解けると判断

しかしTLE タイムアップで終了

レート更新

f:id:repenguin:20190707231542p:plain

AtCoder Beginner Contest 132受験記

AtCoder Beginner Contest 132

A - Fifty-Fifty

なんかA問題にくだらない時間を取られ、挙句の果てには謎のWAを出してしましました。悲しいです。

最終的にはこの汚いコードでF

ソートしてif文書いてやるのが一番早かったですね

FScanner sc = new FScanner();
        String S = sc.next();
        List<String> list = new ArrayList<String>();
        for (int i = 0; i < S.length(); i++) {
            String s = String.valueOf(S.charAt(i));
            list.add(s);
        }
        boolean flg = false;
        for (int i = 0; i < list.size(); i++) {
            String str = list.get(i);
            int cnt = 0;
            for (int j = 0; j < list.size(); j++) {
                if (str.equals(list.get(j))) {
                    cnt++;
                }
            }
            if (cnt == 2) {
                flg = true;
            } else {
                flg = false;
                break;
            }
        }
 
        if (flg) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

B - Ordinary Number

for文回して条件のif文を書くだけ

FScanner sc = new FScanner();
        int n = sc.nextInt();
        int[] ary = new int[n];
        for (int i = 0; i < n; i++) {
            ary[i] = sc.nextInt();
        }
        int cnt = 0;
        for (int i = 0; i < n - 2; i++) {
            int p1 = ary[i];
            int p2 = ary[i + 1];
            int p3 = ary[i + 2];
            if ((p1 < p2 && p2 < p3) || (p3 < p2 && p2 < p1)) {
                cnt++;
            }
        }
        System.out.println(cnt);

C - Divide the Problems

ソートして半分に割って境界値間の数を数えるだけ

9 1 4 4 6 7 => 1 4 4 6 7 9 => 1 4 4 | 6 7 9

境界値 4,6の間は5,6が存在する。※以上という条件に注意

よって答えは 6 - 4 = 2で求まる

FScanner sc = new FScanner();
        long N = sc.nextLong();
        long[] ary = new long[(int) N];
        for (long i = 0; i < N; i++) {
            ary[(int) i] = sc.nextLong();
        }
        if (N % 2 == 1) {
            System.out.println(0);
            return;
        }
        Arrays.sort(ary);
        long end = ary.length / 2;
        long start = end - 1;
        System.out.println(ary[(int) end] - ary[(int) start]);

D - Blue and Red Balls

とけませんでした。

コンビネーションは以下のURLを参考にテンプレートを作っておくのがよろし

drken1215.hatenablog.com

忘れがちだと思ったのは最後にかけた後1000000007で割ったあまりを出すこと

そうしないと大半のケースがWAとなる

コンビネーションの問題ちょっと勉強したほうがよさそうですねー

レート更新

茶色が遠い...

f:id:repenguin:20190630213420p:plain

atCoder 過去問演習 2019/6/29

AtCoder Beginner Contest 061

B - Counting Roads

普通に都市の配列を作って足せばいいだけ

道が一本ならグラフ理論みたいに書いてもいいが今回は道が複数あるので通用しない

C - Big Array

LinkedListにしてたらTLEしました

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long K = sc.nextLong();
        List<BigAry> list = new ArrayList<BigAry>();
        for (long i = 0; i < N; i++) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            BigAry ary = new BigAry(a, b);
            list.add(ary);
        }
        list.sort((a, b) -> (int) a.value - (int) b.value);
        long sum = 0;
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i).num;
            if (sum >= K) {
                System.out.println(list.get(i).value);
                return;
            }
        }
    }

    public static class BigAry {
        private long value;
        private long num;

        public BigAry(long value, long num) {
            this.value = value;
            this.num = num;
        }
    }

atCoder 過去問演習 2019/6/28

AtCoder Beginner Contest 054

C - One-stroke Path

無向グラフの一筆書き問題ですね

グラフ問題は避けては通れません。

以下のサイトを完コピして実装しました。

https://tx-driver.hatenablog.com/entry/2019/01/08/233242

AtCoder Beginner Contest 055

特になし

AtCoder Beginner Contest 056

特になし

AtCoder Beginner Contest 057

C - Digits in Multiplication

以前約数の個数を数えるときに使用していたアルゴリズムを使用するとTLEした。

回答としてはループの条件を工夫する

安直に考えるとAを1からNまで繰り返し割ってみる必要があるが上限はNの平方根になることに気付けるかどうか

っていうかNの平方根が上限とは気づいてたんだけどねぇ

AtCoder Beginner Contest 058

C - 怪文書 / Dubious Document

ばか正直にHashMap使って数えてごにょごにょしてREで通らない馬鹿をしていました。

解法としてはDPみたいに N * 26 の配列を作成しそこにアルファベットの出現回数をカウントしていく。

最後にAから順番に各アルファベットの個数の最小値を求めその回数分だけ出力する。

以上!!閉廷!!

HashMapで書いてたらえらい行数行ってたのにDPもどきを使ったら超簡潔に書けました。っていうかデータをきれいにフォーマットしてたのが愚かだった。

積集合を作って次のMapと比較してできたきれいなMapのみを出力するみたいなね...

 

static String alphabet = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" };


public static void main(String args) {

 Scanner sc = new Scanner(System.in);

 int n = sc.nextInt();

 int av = new int[n][alphabet.length];

 for (int i = 0; i < n; i++) {

  String str = sc.next();

  for (int j = 0; j < str.length(); j++) {

   String str2 = String.valueOf(str.charAt(j));

   av[i][search(str2)] += 1;

  }

 }

 for (int j = 0; j < av[0].length; j++) {

  int min = av[0][j];

  for (int i = 1; i < n; i++) {

   if (min > av[i][j]) {

    min = av[i][j];

   }

  }

  for (int i = 0; i < min; i++) {

   System.out.print(alphabet[j]);

  }

 }

}
public static int search(String str) {

 for (int i = 0; i < alphabet.length; i++) {

  if (alphabet[i].equals(str)) { return i; }

  }

 return -1;

}

AtCoder Beginner Contest 059

C - Sequence

奇数番目が正の時と偶数番目が正の時の二パターンを試すのが肝なんですねー

あとは貪欲法なので条件を満たしている間は余計な事をしない

例えば平均とってそろえようとしたりね

 

AtCoder Beginner Contest 060

B - Choose Integers

C - Sentou

とにかく書いて規則性を発見することが大事!!

 

 

 

 

 

atCoder 過去問演習 2019/6/25

AtCoder Beginner Contest 047

悩んだところ

C問題

解説を見てなるほどと思った。

①石の色によって区間が分かれる。

BBWWWB =>BB WWW B

区間の数は3

②右端か左端に石を置くことによって何ができるかというと区間を減らすことができる

ex) 右端にWを置く

 BB WWW B  => BB WWW B W => BB WWWWW

区間の数は2

区間の数を1にすることができればすべて同じ色ということになる。

BBBBBBB

区間の数は1

④したがって(最初の区間の数 - 1)回、区間の数を減らす必要がある。これが最小の手数となる。

問題をシミュレーションして解こうとすると破滅するパターンの問題だった。

 

AtCoder Beginner Contest 048

悩んだところ

B問題 

long型を受けるときは sc.nextLong()で受けましょう!!

倍数の個数を数えるときは

始点 % X = 0 の時は1加算しましょう

 

C - Boxes and Candies

int型使用しているときは桁オーバーに注意しましょう!!

貪欲法を使うらしい。知らずに使っていたが...

 https://www.itmedia.co.jp/enterprise/articles/1009/04/news002_3.html

 

AtCoder Beginner Contest 049

C - 白昼夢 / Daydream

MLE メモリオーバ

なんて初めて見ました。

substrとstring中で宣言しまくってたのがいけなかったんですかねー

AtCoder Beginner Contest 050

C - Lining Up

考え方はあってたが4ケースが通らずACにならない。

ほかの人の回答を見たところ

2のN乗にMath.powを使わずfor文の中でやっていた。さらに二乗するたびに10の9乗+7であまりを出していた。

for (int i = 0; i < N / 2; i++) {

 ret *= 2;

 ret %= 1000000007;

}

不思議に思ったので私も同じようにしてみた。

すると通った。どうやら2のN乗の値がlong型を超えていたようだ

覚えておこう

AtCoder Beginner Contest 051

B - Sum of Three Integers

nの三乗だと計算量がオーバーするので他の方法を考える必要あり

DPで解いてみたがなぜか二ケースだけ通らない...

S=X+Y+Zなので変形させると

Z = S-X-Yとなり計算量をNの二乗まで落とせる

X,YをKまで総当たりしてZを計算。Zが0<=Z<=Kとなるようなケースを計測すると求まる。DPなんていらんかったんや