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

Dvorak配列でjavaを書いてます

AtCoder Beginners Selection

AtCoder Beginners Selectionの問題を解いてみました。全十問。

AtCoder Beginners Selection - AtCoder Beginners Selection | AtCoder


PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		String s = sc.next();
		out.println((a+b+c)+" "+s);
	}
}

特になし。


ABC086A - Product

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		out.println(a*b%2==0?"Even":"Odd");
	}
}

三項演算子を使った。


ABC081A - Placing Marbles

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		int num = 0;
		for (int i=0; i<s.length(); i++) {
			if (s.charAt(i)=='1') num++;
		}
		out.println(num);
	}
}

sを先頭から1文字ずつ調べて、1であればカウントを増やす。


ABC081B - Shift only

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int[] ar = new int[n];
		boolean F = false;
		for (int i=0; i<n; i++) {
			ar[i] = sc.nextInt();
			if (ar[i]%2==1) {F = true;}
		}
		
		if (F == true) {out.println(0);}
		else {
			int min = Integer.MAX_VALUE;
			for (int i=0; i<n; i++) {
				int times = 0;
				while (ar[i]%2==0) {
					ar[i] /= 2;
					times++;
				}
				min = Math.min(min,times);
			}
			out.println(min);
		}
	}
}

奇数が1つでも含まれていれば0回なので、まずは奇数が含まれているかどうかを判定した。そのあと、実際にすべての値を2で割ってみて、割れた回数のうち一番少ないものが答え。


ABC087B - Coins

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int x = sc.nextInt();
		
		int num = 0;
		for (int i=0; i<=a; i++) {
			for (int j=0; j<=b; j++) {
				for (int k=0; k<=c; k++) {
					if (500*i+100*j+50*k == x) num++;
				}
			}
		}
		out.println(num);
	}
}

素直に三重ループを使った。


ABC083B - Some Sums

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		long total = 0;
		
		for (int i=1; i<=n; i++) {
			String s = String.valueOf(i);
			int sum = 0;
			for (int j=0; j<s.length(); j++) {
				sum += Character.getNumericValue(s.charAt(j));
			}
			if (sum<=b && a<=sum) total += i;
		}
		
		out.println(total);
	}
}

たとえば1000の位の数字を求めるには1000で割ってやればよいのだが、めんどくさいので文字列に変換してから各桁の数字を足し合わせる方針をとった。


ABC088B - Card Game for Two

import java.util.*;
import static java.lang.System.*;

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

Integer型を使ったのは、降順ソートが使えるから。Int型配列に入れて昇順にソートしてもいいのだが、それをすると配列の最後の要素の添字を奇数と偶数で場合分けする必要が生じてしまう。


ABC085B - Kagami Mochi

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		Set<Integer> set = new HashSet<>();
		for (int i=0; i<n; i++) set.add(sc.nextInt());
		out.println(set.size());
	}
}

問題文を読むと、求めたいのは「大きさの重複がないようにモチを選んだときの総数」であることが分かるので、モチをSetに片っ端からぶち込んでいき、Setの要素数を出力すればよい。


ABC085C - Otoshidama

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		int total = sc.nextInt();
		
		int a = -1;
		int b = -1;
		int c = -1;
		for (int i=0; i<=total/10000; i++) {
			for (int j=0; j<=(total-10000*i)/5000; j++) {
				int k = n - (i+j);
				if (10000*i+5000*j+1000*k == total) {
					a=i; b=j; c=k;
					break;
				}
			}
		}
		
		out.println(a+" "+b+" "+c);
	}
}

すっと書けてすっと通ったので、自分の成長ぶりに自分でも驚いた(以前に一度解いていることもあるだろうけど)。上で解いた「ABC087B - Coins」に比べてnの値が大きいので、愚直にループを回していてはおそらく正解できない。そこで、i(一万円の枚数)は必ず「お年玉/10000」以下であることを利用し、ループの回数を減らす。jも同様。千円の枚数については、一万円と五千円の枚数が定まれば「n-(一万円の枚数+五千円の枚数)」で一意に定まるので、ループを回す必要はない。このようにして二重のループを回し、値が見つかったらbreakして出力する。


ABC049C - 白昼夢 / Daydream

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		s = s.replaceAll("eraser","");
		s = s.replaceAll("erase","");
		s = s.replaceAll("dreamer","");
		s = s.replaceAll("dream","");
		out.println(s.equals("")?"YES":"NO");
	}
}

以前解いたときに読んだ解説には、文字列を逆さまにして判定……といったことが書かれていたような気がするのだが、ひょっとしてそんなことしなくても正規表現で処理できるのではないかと思い、やってみたところWAを生やした。原因は、「eraser,erase」より先に「dreamer,dream」を置換していたせい。そうしてしまうと、たとえば「dreamerase」という文字列、これはYES(可能な)と出力すべき文字列なのだが、dreamerを最初に空文字列に置換してしまうと、「ase」が残り、うまく処理できない。こうなってしまうことを避けるために、まずは「erase,eraser」を置換し、次に「dreamer,dream」を置換する。最後に残ったのが空文字列であれば(すべてが上記の4単語から構成されているなら)YES、そうでなければNOを出力して終わり。


ABC086C - Traveling

import java.util.*;
import static java.lang.System.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		
		int t,x,y,dis;
		String ans = "Yes";
		for (int i=0; i<n; i++) {
			t = sc.nextInt();
			x = sc.nextInt();
			y = sc.nextInt();
			dis = x+y;
			if (dis > t) {
				ans = "No";
				break;
			}
			else if (dis < t) {
				if ((t-dis)%2 == 1) {
					ans = "No";
					break;
				}
			}
		}
		
		out.println(ans);
	}
}

時刻0に(0,0)にいるとして、予定を処理していく。たとえば入力例1には3,1,2とあるが、これは時刻3までに(1,2)へ行けますか、ということになる。まず、(0,0)と(1,2)のマンハッタン距離を求める。3である。時刻と距離が等しいとき、必ずたどり着ける。時刻より距離が大きいとき、決してたどり着けない。問題は時刻より距離が小さい場合である。言い換えるなら、時間に余裕がある場合。その場にとどまって時間を潰すことはできないので、必然的に、目的の座標とその隣の座標のあいだを、時間がなくなるまで往復し続けることになる。このとき、余った時間(時刻-距離)が偶数の場合は、時刻ちょうどに座標にたどり着ける。逆に奇数の場合はたどり着けない。といった感じで、条件分岐を実装してやれば解ける。実際には、x+yとtの偶奇を調べるだけで解けるようなのだが、解答中はそこまで思いつかなかった。なお、現在座標をいちいち変えながらシミュレーションする必要はない……と思ったが、たとえばn=2,(3,0,3),(4,0,0)のときはどうだろう。時刻3のとき(0,3)にはたどり着けるが、時刻4、つまりその1時刻後に(0,0)に戻ることはできない。これをACしたコードで読み込むとYESとなってしまう……うーん、よく分からないので深く考えないでおこう。


感想

どれもクセのない問題ばかりで、たしかに初心者にはうってつけの問題集かもしれない。僕としては、二次元配列を処理する問題(画像処理とか迷路とか)が好きなので、そういう問題も欲しかったな~とは思った。