AtCoder振り返り:Panasonic Programming Contest 2020

競技プログラミング

初めてAtCoderBeginner以外のコンテストに挑戦してみました。
結果としては惨敗（ABのみの2完)、C問について理解が及んでおりませんでした。

改めて問題を振り返ります。
※E, Fは自分の実力ではまだ理解できない部分が多いので今後はD問までを中心に復習していきます。

A問

問題

atcoder.jp

32個の配列に対して、引数として渡されたN番目の要素を取得するという問題です。
初歩的な問題なので特に問題はないと思いますが、
引数N-1 = 取得したい要素であることを注意することくらいでしょうか。

回答コード

import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int idx = sc.nextInt();
		int[] datas = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		for(int i = 0; i < 32; i++) {
			if(i+1 == idx) {
				System.out.println(datas[i]);
			}
		}
	}
}

B問

atcoder.jp

問題

縦がH, 横がWの場合に、ビショップが移動できるマス数はいくつあるか？という問題です。
※ビショップは何回でも移動でき、盤面上にはビショップしか存在しない。

この問題を考えたとき、以前作成多五目並べゲームがふと頭をよぎって
要素 x y の ±1 を計算する再帰処理、、、とか考えたのですが無駄だと悟りました。

・単純に斜めに動けるならば、マス数 / 2 で求めることができます。※あまり切り上げ
しかし、注意しなくてはならないのがマス数が縦横いずれかが1マスのだった場合の例外です。
この場合斜め移動ができないためビショップは１マス（自身がいるマス）以外は移動できません。
こちらの例外が考慮できているかが回答のポイントだと思います。

回答コード

import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		long H = sc.nextLong();
		long W = sc.nextLong();

		if(H != 1 && W != 1) {
			System.out.println((H * W) / 2 + (H * W) % 2);
		} else {
			System.out.println(1);
		}
	}
}

C問

atcoder.jp

問題

√a + √b < √c であるか確認する問題です。
初めてみたときボーナス問題だ！Math.sqrtで簡単に割り出せる！と思っていました。

とはいえそんなことはありませんでした。
Math.sqrtでは誤差が生じる可能性があるためどうしても正確な計算が行えないことがあります。
後述の誤回答ソースコードでは20/24の正解でした。

Math.sqrt以外にニュートン法やBigdecimalでの計算など試しましたが結局時間内に解けませんでした。
a, b, cが大きい値の場合精度が十分でなくなってしまいますが、
前提としてすべて整数であるという条件があるため以下の計算で求められるそうです。

■計算式

sqrt(a) + sqrt(b) < sqrt(c)
= a + b + 2*sqrt(ab) < c
= 2*sqrt(ab) < c - a - b
= 4*ab < (c - a - b)^2


回答コード

■誤回答版

import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if(Math.sqrt(a) + Math.sqrt(b) < Math.sqrt(c)) {
			System.out.print("Yes");
		} else {
			System.out.println("No");
		}
	}

}

■正回答版

import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		long a = sc.nextLong();
		long b = sc.nextLong();
		long c = sc.nextLong();

		long num = c - a - b;
		//c < a + bならば絶対にNo
		if (num < 0)  { 
			System.out.print("No");
		} else {

			if(num * num > 4 * a * b) {
				System.out.print("Yes");
			} else {
				System.out.print("No");
			}
		}
	}
}

D問

問題

atcoder.jp

1桁から10桁までの文字列について、辞書順ですべての文字列の組み合わせを出力する処理です。
この問題は全ての文字列の組み合わせを出力するので、
DFS(depth-first search) と呼ばれる深さ優先探索が有効とのことです。
正直深さ優先探索アルゴリズムをしっかりと把握したわけではないので今回は写経ですが概ね動きは理解できました。

回答コード(写経)

import java.util.Scanner;


public class panas_004Main {

	static int N;

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		dfs("", 'a');
	}

	public static void dfs(String s, char mx) {
		if(s.length() == N) {
			System.out.println(s);
		} else {
			for(char c='a'; c <= mx; c++) {
				dfs(s + c, ((c == mx) ? (char)(mx + 1) : mx));
			}
		}
	}
}

参考

解説
https://img.atcoder.jp/panasonic2020/editorial.pdf