山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 101 の感想

AtCoder Beginner Contest 100

結果はB問題まで解くことができました。

f:id:yamakasa3:20180624004919p:plain

コンテスト開始後7分以降は何の成果もあげられませんでした。

A - Eating Symbols Easy

文字列を見て計算するだけの問題です。

B - Digit Sums

 N を文字列として扱い、一文字ずつ取り出すことで各桁の和を計算することができます。

割と良く見る問題ですね。

C: Minimization

正解できなかった問題です。解説を見ても良く分かりませんでした。

最初考えた方法(2回目の提出)

問題を見たときに与えられた配列を使わずに N K だけで回答が出せると思ったんですが、残念ながら不正解でした。結果的に公式の解説と似たような考えでした。

自分で不正解となる例も見つけることができたんですが、別の方法を考えることにしました。

不正解となったコードです。

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        int []A = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        scan.close();
        if(K == N) {
            System.out.println(1);
        }else {
            if(K == 2) {
                System.out.println(N - 1);
            }else {
                if(N % (K - 1) == 0) {
                    System.out.println(N / (K - 1));
                }else {
                    System.out.println(N / (K - 1) + 1);
                }
            }
        }
    }
}
最初とは異なる方法

配列のかで 1 が存在する要素番号を元に考える方法。

最初に操作を行う部分は1を含む連続した K 個の配列です。どのような選びかたがあるかというのを配列の要素番号を無視して考えます。そうすると、 K 組の1を含む連続した配列が考えられます。

操作は必ず 1 を含んで行う必要があるので、 K - 1 個の配列が 1 になります。

ここで、 A_p = 1 を満たす p を考えます。

 0 \leq i \lt K を満たす i に対して、

 r = p - K + i + 1

 l = p + i

 r = r + K - 1 r N - 1 以上になるまで繰り返されるカウントと l = l - K + 1 0 以下になるまでに繰り返されるカウントを足し合わせたものを i の中で最小となるものが答えです。

日本語でokっすな。

コンテスト終了後に正解となったコード

import java.util.Scanner;

public class ProblemC1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        int p = 0;
        for(int i = 0; i < N; i++) {
            int a = scan.nextInt();
            if(a == 1) {
                p = i;
            }
        }
        scan.close();
        if(N == K) {
            System.out.println(1);
            System.exit(0);
        }

        int r = 0;
        int l = 0;
        int min = N;
        int m = K - 1;
        for(int i = 0; i < K; i++) {
            int cnt = 1;
            l = p - m + i;
            r = p + i;
            if(l > 0) {
                while(l > 0) {
                    l = l - m;
                    cnt ++;
                }
            }
            if(r < N - 1) {
                while(r < N - 1) {
                    r = r + m;
                    cnt ++;
                }
            }
            if(min > cnt) {
                min = cnt;
            }
        }
        System.out.println(min);

    }
}

感想

勉強不足かまたは実力通りの結果だと思います。

yukicoderを重点的に進めようと思います。それとAOJもやらないとな。

AtCoderはテストケースが一部しか公開されていないので、僕みたいな初心者には学習が難しいと思います。競技をやる意味では申し分ないですが、学習となるとyukicoderやAOJが良いと思いました。yukicoderは出題者の解説がない問題もありますが、解答者による解説が充実しているので、よくお世話になっています。

僕はプログラム問題を解くのは好きですが、競技は向いてないと思いました。時間制限があるなか解けないとイライラしてしまいます。