bpeldi2oerkd8の開発日誌

とあるひよっこエンジニアの成長の記録。

エイシング プログラミング コンテスト 2020 に参加しました (AtCoder)

エイシング2020
お久しぶりとなります。
エイシング プログラミング コンテスト 2020 に参加しました。
久しぶりのコンテストだったので、感覚を忘れていて、リハビリ感覚です。

ちなみに、前回の記事はこちらです。(だいぶ前となってしまいますが・・・)
developer-bpeldi2oerkd8.hatenablog.com

準備

ほとんどできていないです。
これから少しずつでも復帰できたらなと思います。

経過

前回からしばらく空いていたので、とにかく感覚を取り戻すのに精一杯でした。
A・B問題をさくっと解き、C問題に移りました。

C問題はぱっと見わからず、式変形を試みたりしましたが、
x^x+y^y+z^z+x*y+y*z+z*x >= 1となる関係から、
x=1, y=1と考えてもz=100くらいだと思ったので、全探索で行きました。
余裕をもってx, y, z <= 200で3重ループを回すと問題なく通りました。
(ここまで40分ほど)

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] count = new int[N+1];
		Arrays.fill(count, 0);
		for(int x=1; x<=200; x++) {
			for(int y=1; y<=200; y++) {
				for(int z=1; z<=200; z++) {
					int n = x*x+y*y+z*z+x*y+y*z+z*x;
					if(n <=N) {
						count[n]++;
					}
				}
			}
		}

		PrintWriter pw = new PrintWriter(System.out);
		for(int i=1; i<=N; i++) {
			pw.println(count[i]);
		}
		pw.flush();

	}

}

D問題は再帰と進数の変換を用いて実装しましたが、N=2*10^5と大きいので、
途中計算の記憶をMapで実装しました。
しかし、サンプルは通したのですが、ほとんどREとなってしまいました。
原因については、調べます。

import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	//java11

//	static int[] fn;
	static Map<Integer, Integer> fn;
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		String X = sc.next();

//		fn = new int[(int)Math.pow(2, N)];
//		fn = new int[10000000];
		fn = new HashMap<>();
//		Arrays.fill(fn, -1);

		PrintWriter pw = new PrintWriter(System.out);
		for(int i=0; i<N; i++) {
			StringBuilder sb = new StringBuilder(X);
			//bit反転
			if(X.charAt(i) == '0') {
				sb.setCharAt(i, '1');
			}else {
				sb.setCharAt(i, '0');
			}

			int Xi = Integer.parseInt(sb.toString(), 2);

			pw.println(fn(Xi));

		}

		pw.flush();

	}

	public static int fn(int n) {
		if(fn.get(n) != null) {
			return fn.get(n);
		}

		if(n == 0) {
//			fn[n] = 0;
			fn.put(n, 0);
			return fn.get(n);
		}

		if(popcount(n) == 0) {
			fn.put(n, fn(0) + 1);
		}else {
			fn.put(n, fn(n % popcount(n)) + 1);
		}
		return fn.get(n);
	}

	public static int popcount(int n) {
		return Integer.bitCount(n);
	}

}

結果

エイシング2020_result
久しぶりにしてはという感じですが、やはり問題を解かないとレベルは上がっていきませんね。
他のことでも忙しいのですが、なんとか時間を作って頑張りたいと思います。


というわけで、エイシング プログラミング コンテスト 2020の結果でした。
次回も参加したいと思います。