Java初心者の競技プログラミング日記

Dvorak配列でjavaを書いてます

トップ > atcoder > AtCoder Beginner Contest 088

AtCoder Beginner Contest 088

atcoder

A - Infinite Coins

import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int a = sc.nextInt();
		if (n%500 <= a) {System.out.println("Yes");}
		else {System.out.println("No");}
	}
}


n円を500で割った余りを求める。これをx円とする。x円分（x個）1円玉を持っていれば支払うことができるので、1円玉の所持数をxと比較して、支払えるならYes、支払えないならNo。


B - Card Game for Two

import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int alice = 0;
		int bob = 0;
		Integer[] ar = new Integer[n];
		for (int i=0; i<n; i++) {
			ar[i] = sc.nextInt();
		}
		Arrays.sort(ar,Comparator.reverseOrder());
		for (int i=0; i<n; i++) {
			int a = ar[i];
			if (i%2==0) {alice += a;}
			else {bob += a;}
		}
		System.out.println(Math.abs(alice-bob));
	}
}


カードを降順にソートして、Aliceから先に交互に取っていって、二人の合計の差の絶対値をとれば終わり。


C - Takahashi's Information

import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[][] ar = new int[3][3];
		int[][] ar2 = new int[3][3];
		int max = -1;
		for (int i=0; i<3; i++) {
			for (int j=0; j<3; j++) {
				ar[i][j] = sc.nextInt();
				ar2[i][j] = ar[i][j];
				max = Math.max(max,ar[i][j]);
			}
		}
		
		
		boolean F = false;
		for (int i=0; i<=max; i++) {
			for (int j=0; j<=max; j++) {
				for (int k=0; k<=max; k++) {
					
					for (int x=0; x<3; x++) {
						for (int y=0; y<3; y++) {
							if (x==0) {ar[x][y] -= i;}
							else if (x==1) {ar[x][y] -= j;}
							else if (x==2) {ar[x][y] -= k;}
						}
					}
					
					int count = 0;
					for (int x=0; x<3; x++) {
						if (ar[0][x]==ar[1][x] && ar[1][x]==ar[2][x]) {
							count++;
						}
					}
					if (count==3) {F = true; break;}
					
					for (int x=0; x<3; x++) {
						for (int y=0; y<3; y++) {
							ar[x][y] = ar2[x][y];
						}
					}
					
				}
				if (F==true) {break;}
			}
			if (F==true) {break;}
		}
		System.out.println(F==true?"Yes":"No");
	}
}


いま振り返っても、自分でもおぞましく思うくらいに回りくどい解き方をしている。

a1・a2・a3の値での全探索がベースになっている。探索の範囲は、0～グリッド内の最大値。

forループの一番深いところには3つのfor文があるが、このうち一つ目のfor文では、a1・a2・a3の値をグリッドから引くという処理をしている。例えば、入力例1で、a1=0、a2=1、a3=0として、それぞれグリッドから引くと、
1 0 1
1 0 1
1 0 1
となる。要は、a1・a2・a3を引いたとき、縦に三種類の数字が並んでいるこのような状態になれば、高橋君の情報は正しいということになる。今回僕が書いたのは、このようなa1・a2・a3の値を全探索で調べるプログラムになる。

二つ目のfor文では、数字が上記のように並んでいるかどうかを判定している。三列とも同じ数字であれば、ループから抜けて出力。

三つ目のfor文では、グリッドから引く処理をすると、グリッド内部の値が変わってしまうので、次のループに備えて別の配列に確保しておいた初期値に戻しているのだが、ここは上手いことやれば省略できたのではないかと思う。とくに今回は二次元配列が3*3と小さいし。


D - Grid Repainting

問題を見て、深さ優先探索あるいは幅優先探索を使えば解けるだろうなあ、というところまでは分かったが、肝心の実装方法を何一つ理解していなかったため、解答するのはあきらめた。


まとめ

C問題が一発でACできたのはよかったのだが、もう少し早く数字の並びの規則性に気づきたかった。ふだん、競技プログラミング以外では数学にまったく触れない生活を送っているので、今後は高校数学を少しずつ学び直したいと思っている。D問題に関してはどうしようもない。僕が習得しているアルゴリズムが少なすぎるのが問題なのだ。二分探索はもちろん、今回の二つの探索、グラフ、動的計画法、何一つ分からない。そろそろ本格的に書籍など買って、体系的に競プロアルゴリズムを学ぶ必要があることを、今回のコンテストを終えてから痛切に感じた。