AtCoder Beginner Contest 156振り返り

昨日AtCoder2回目の参加をしました。

結果として3完ですが、4問目以降のアルゴリズムが分からなくて取れませんでした。次回は４問目も解けるように今回の振り返りをしていこうと思います。

なおAtCoderさんは毎回試験終了後に解説を展開してくださるのでその内容もチェック要です。

AtCoder：ABC解説

https://img.atcoder.jp/abc156/editorial.pdf

第1問
第2問
第3問
第4問
第5問
第6問
所感

第1問

第1問はレーティングの計算ですが、これは結構簡単ですね。（当たり前ですが）

atcoder.jp

問題文

AtCoderにおけるレーティグ算出の問題でした。

個人的なポイントは

・表示レーティングは、内部レーティングから $100 \times (10 - K)$ 引いた数

・その会員のコンテスト参加回数が $10$ 以上のときは内部レーティングに等しい。

・高橋君のコンテスト参加回数が $N$ で表示レーティングが $R$ であるとき、高橋君の内部レーティングを求める。

自分の回答

ちょっとだけ分岐処理が入る程度で、ほとんど難しい内容はありませんでした。

最終的には以下のコードで正解となりました。

import java.util.Scanner;
public class Main {
public static void main(String args){
Scanner sc = new Scanner(System.in);
String s = sc.next();
String ss = sc.next();
int N = Integer.parseInt(s);
int R = Integer.parseInt(ss);
if (N > 10) N = 10;
System.out.println(R + (100*(10-N)));
}
}

17行目の処理ですが、誤って+ではなく "-"にしていたため、2回不正解になってしまいました。解くのに10分かかってしまったので、ここらへんは安定して取れるようにしておきたいですね。

また、解説を見るとif分岐は利用せずにmin処理で10以上は10固定にしていますね。こういったやり方ならもっと簡単に実装できますね。

第2問

atcoder.jp

第2問は特定の数字(N)をK進法で表記した場合何桁になるか？という問題です。

これはむかーし昔に解いた経験があるのでこちらは5分で実装できましたね。

import java.util.Scanner;
public class Main {
public static void main(String args){
Scanner sc = new Scanner(System.in);
String s = sc.next();
String ss = sc.next();
int N = Integer.parseInt(s);
int R = Integer.parseInt(ss);
int cont = 0;
while(N > 0) {
N = N / R;
cont ++;
}
System.out.println(cont);
}
}

import java.util.Scanner;


public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		String ss = sc.next();


        int N = Integer.parseInt(s);
        int R = Integer.parseInt(ss);

        int cont = 0;
        while(N > 0) {
        	N = N / R;
        	cont ++;
        }
        System.out.println(cont);
	}
}

単純に、特定の数字(N) をKで除算した回数を計上して行って最終的に割り切れなくなる＝0となった場合終了する処理であれば桁数が簡単に計上できました。

解説も確認しましたが、自分の実装とほぼ同じなのでこのアルゴリズムは間違いではないみたいです。一発で行けた時はドーパミンドバドバ出ました。（初心者レベルなので自慢にはならないですが。。。）

第3問

atcoder.jp

ここからやや難しくなってきます。

この問題は各座標Xiから特定の地点Pに移動する場合の、体力の消費量(P-Xi)^2 の総和が一番小さいものを求めるというものです。

Xi(MIN)の座標にいる人からXi(Max)まで順にP地点までの距離を計算すれば解くことができます。

私はMIN/MAXを求めるためにXi地点の座標の方をソートしました。回答は以下のとおりです。

import java.util.Scanner;
public class Main {
public static void main(String args){
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.next()); //N人
int xs = new int[N];
for(int i = 0; i < N; i++) {
xs[i] = Integer.parseInt(sc.next());
}
quick_sort(xs, 0, xs.length-1);
int sum = 0;
int current = 0;
boolean flg = true;
for(int i = xs[0]; i <= xs[N-1]; i++) {
for(int j = 0; j < N; j++) {
int pos = (xs[j]-i) * (xs[j]-i);
current += pos;
}
if (current < sum || flg) {
sum = current;
flg = false;
}
current = 0;
}
System.out.println(sum);
}
static void quick_sort(int[] d, int left, int right) {
if (left>=right) {
return;
}
int p = d[(left+right)/2];
int l = left, r = right, tmp;
while(l<=r) {
while(d[l] < p) { l++; }
while(d[r] > p) { r--; }
if (l<=r) {
tmp = d[l]; d[l] = d[r]; d[r] = tmp;
l++; r--;
}
}
quick_sort(d, left, r); // ピボットより左側をクイックソート
quick_sort(d, l, right); // ピボットより右側をクイックソート
}
}

import java.util.Scanner;


public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

        int N = Integer.parseInt(sc.next());	//N人
        int[] xs = new int[N];
        for(int i = 0; i < N; i++) {

        	xs[i] = Integer.parseInt(sc.next());
        }
        quick_sort(xs, 0, xs.length-1);

        int sum = 0;
        int current = 0;
        boolean flg = true;
        for(int i = xs[0]; i <= xs[N-1]; i++) {
        	for(int j = 0; j < N; j++) {
        		int pos = (xs[j]-i) * (xs[j]-i);
        		current += pos;
        	}
        	if (current < sum || flg) {
        		sum = current;
        		flg = false;
        	}
        	current = 0;
        }
        System.out.println(sum);
	}


	static void quick_sort(int[] d, int left, int right) {
        if (left>=right) {
            return;
        }
        int p = d[(left+right)/2];
        int l = left, r = right, tmp;
        while(l<=r) {
            while(d[l] < p) { l++; }
            while(d[r] > p) { r--; }
            if (l<=r) {
                tmp = d[l]; d[l] = d[r]; d[r] = tmp;
                l++; r--;
            }
        }
        quick_sort(d, left, r);  // ピボットより左側をクイックソート
        quick_sort(d, l, right); // ピボットより右側をクイックソート
    }
}

解説の方では、C++などでMIN/MAXが利用できるのでソートは利用していないようですね。うーんMIN/MAXなど気軽に特定できる処理は覚えておかないと、と思います。

ここまでで40分経過しました。

残り60分もあったのですが、私はここで力尽きています。。。

第4問

atcoder.jp

この問題は解くことができませんでしたが、単純に組み合わせアルゴリズム(nCrの計算）であることはわかりました。

nCrの計算なので、例えば10本の花から3本の花を取得する組み合わせの場合、

（10 × 9 × 8）　÷　(1 × 2 × 3) = 120通りと求めることができます。

今回はこの数字を積み上げれば良い。というところまでは理解できました。ただ単純なforループではTLEになるだろうから難しいと思ったため、再帰関数で実行するが一般的とのことです。

でもnが10^9が最大なので単純にループすうが一兆超えてTLEになるんじゃないか、、、など考えつつPGMで実装して時間切れになってしまいました。。。

解説を見ると、

"まず「a, b 本の花からなる花束は作ることができない」という制約を無視して問題を解いてみます。このとき答えは 2 n − 1 になります。"

マジかよ。。。超簡単じゃん。。。組み合わせは2n - 1計算した後に、除外すべき２組を計算すればよいので超簡単でした。やはり数学など基礎を分かっていないととダメですね。精進します。

第5問

atcoder.jp

ここから先は見る時間がなかったので、予習的な感じで見ていきます。

n個の部屋が存在し、各部屋に１人ずつ存在します。

その後k回数の部屋移動が発生した場合、部屋人数の組み合わせが何通りあるか答えるといものです。

第4問の発展版のような内容でしょうか。正直ぱっと見でよく分かっていません。

解説を見てみると

f:id:lawrence-twin:20200223123340p:plain

ごめんなさい、わかりません。。。

部屋iにいる人数をciとした場合上記の式になるそうです。

他にもあるのですが、適切な計算処理であればO(1)で済むそうです。自分にはまだちょっとこの辺りの領域は早いですね。。。

今後ディープラーニングや機械学習を学ぶなら外せない領域だと思いますが。。。

第6問

atcoder.jp

この辺りは自分にはまだ早い領域だと思います。まず問題がわからない。。。

解説されている方の記事も参照したのですが、やはりわからない。

凄いなぁ。。。と思いますがいつか自分もこの領域に行きたい。

harady.hatenadiary.com

所感

3完までは（まだ2回ですが）取れているので4完できるを次回の目標として頑張ります。そのためにはアルゴリズムの基礎（組み合わせ、再帰、全探索など）を抑えておかないとですね。

また競技プログラミング用にC++に切り替えようかと思っています。やりたいことが盛り沢山ですが中々難しいですが一つずつ着手していこうと思います。