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となってしまう……うーん、よく分からないので深く考えないでおこう。

感想

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

マップを値でソートする方法

マップを値でソートする方法については以前記事にしたのだけれども、

マップを値でソートするメソッド - Java初心者の競技プログラミング日記

あまりに冗長すぎるのでもっと短く書ける方法を探した。見つかった。

//昇順
map = map.entrySet().stream()
.sorted(Entry.<String,Integer>comparingByValue())
.collect(Collectors.toMap(Entry::getKey,Entry::getValue,(e1, e2)->e1,LinkedHashMap::new));

//降順
map = map.entrySet().stream()
.sorted(Entry.<String,Integer>comparingByValue().reversed())
.collect(Collectors.toMap(Entry::getKey,Entry::getValue,(e1, e2)->e1,LinkedHashMap::new));

java.util.Map.Entry と java.util.stream.Collectors をインポートしてある。

以下のサイトを参考にしました
How to Sort Map by values in Java 8 using Lambdas and Stream - Example Tutorial | Java67

自作クラスの入ったリスト・配列をソートする方法

まずはリスト。

class Point {
	int x;
	int y;
	char color;
	Point(int a, int b, char c) {
		this.x = a;
		this.y = b;
		this.color = c;
	}
	int getX() {
		return this.x;
	}
	int getY() {
		return this.y;
	}
	char getColor() {
		return this.color;
	}
}

クラスPointが入っているリストlistを、それぞれのメンバ変数についてソートしてみる。

//xで昇順ソート
list.sort(Comparator.comparing(Point::getX));

//yで降順ソート
list.sort(Comparator.comparing(Point::getY).reversed());

//colorで昇順ソート
list.sort(Comparator.comparing(Point::getColor));

//xで昇順ソート、xが同じ場合はyで降順ソート、yも同じ場合はcolorで昇順ソート
list.sort(Comparator.comparing(Point::getX)
		.thenComparing(Point::getY).reversed()
		.thenComparing(Point::getColor));

メンバ変数xでソートする場合、xを取得するメソッドがクラス側に必要。

thenComparingで同じ値だった場合のソート条件を追加できる。

また、import static java.util.Comparator.* とインポートすることでComparatorの部分を省略できる。

次に配列。

class Person {
	String name;
	int age;
	Person(String s, int n) {
		this.name = s;
		this.age = n;
	}
	String getName() {
		return this.name;
	}
	int getAge() {
		return this.age;
	}
}

クラスPersonが入っている配列arを、それぞれのメンバ変数についてソートしてみる。

//nameで昇順ソート
Arrays.sort(ar,Comparator.comparing(Person::getName));

//ageで降順ソート
Arrays.sort(ar,Comparator.comparing(Person::getAge).reversed());

追記。以前、文字列の長さでソートする問題があったことを思い出したので、それもやってみる。

List<String> list = new ArrayList<>() と宣言した単純なString型のリストであれば、

・list.sort(Comparator.comparingInt(String::length));

とすることで、文字列の長さが短い順でソートできる。

では、上記のようなPerson型のオブジェクトが入っているリストを、nameの長さでソートする方法は？

少し調べてみたが分からない。Person::getName.length など色々試してみたがダメ。

解決策としては、nameの長さを変数nameLengthに入れておいて、

・list.sort(Comparator.comparing(Person::nameLength));

とすればいいと思う。

以下のサイトを参考にしました
Javaで自作クラスをソートする3通りの方法【Java8】 - 俺とプログラミング
(o1, o2) -> o1 - o2 なんて呪文はもうやめて！ - Java8でのComparatorの使い方 - Qiita

AtCoder Beginner Contest 091

A - Two Coins

A+B>=C ? "Yes":"No"

B - Two Colors Card Game

import java.util.*;
import static java.lang.System.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		HashMap<String,Integer> map = new HashMap<>();
		int n = sc.nextInt();
		String s;
		for (int i=0; i<n; i++) {
			s = sc.next();
			map.put(s,map.getOrDefault(s,0));
			map.put(s,map.get(s)+1);
		}
		int m = sc.nextInt();
		for (int i=0; i<m; i++) {
			s = sc.next();
			map.put(s,map.getOrDefault(s,0));
			map.put(s,map.get(s)-1);
		}
		int max = 0;
		for (Map.Entry<String,Integer> e : map.entrySet()) {
			max = Math.max(max,e.getValue());
		}
		out.println(max);
	}
}

最初のn回のループでは、文字列とその出現回数をマップに記録する。
次のm回のループでは、受け取った文字列がマップに含まれているなら出現回数から1引く。
このようにして入力を受け取ったあとの、マップ内の値の最大値が答え。最大値が0未満なら0。

C - 2D Plane 2N Points

今回もC問題はACできなかった。解説を読んでみる。

1．x座標、y座標、色。この3つのメンバ変数を持つクラスを作成する
2．ArrayListに、上記の3つのメンバ変数を持ったすべての赤座標オブジェクトと青座標オブジェクトを入れる
3．listをx座標でソートする
4．0～list.size() までループを回して、先頭の座標から見ていく
4-1．座標が赤ならsetに追加
4-2．座標が青なら、取得した青座標よりもy座標が小さい赤座標をsetの中から探す。そのうち、もっともy座標が大きいものを削除。
5．リストの末尾まで処理したあと、N-list.size() をしたものが答え。

解法を見てなるほどと思ったが、listに入っているオブジェクトをメンバ変数の大小でソートする方法が分からない。特殊なソートのやり方が全然分かっていないので勉強しないとダメ。Comparatorとか。

D - Two Sequences

問題を見ていない

まとめ

特殊なソートについては早急に学ぶ必要があると感じた。マップを値でソートするやり方についてもかなり怪しいので、それも見直す必要がある。

No.351 市松スライドパズル

逆シミュレーションする。

求めたいのは「最終的に左上のマスが何色であったか」なので、「最終盤面の左上のマスは、最初の盤面のどの位置から運ばれてきたか」を考える。

最終盤面の左上のマスの座標をx=0,y=0とおく。操作を後ろから順に行っていって、Rの番号が現在のxと一致していたらxから1引く。xがもし負の値になったら（盤面の左端からはみ出てしまったら）、Wを足す（盤面の右端におく）。同様に、Cの番号が現在のyと一致していたらyから1引く。負の値ならHを足す。

Rの番号がxと一致しない、あるいはCの番号がyと一致しない場合は何もしない。

全ての操作を処理し終えたときの（x,y）が「最初の盤面における、最終盤面の左上のマスの位置」である。このマスが、n回の操作のすえに最終的に左上まで運ばれてくるということになる。つまり、最初の盤面におけるマス（x,y）が何色かを考えればよい。これは、x+yが偶数なら白、x+yが奇数なら黒になる。

import java.util.*;
import static java.lang.System.*;
 
public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int H = sc.nextInt();
		int W = sc.nextInt();
		int n = sc.nextInt();
		Operation[] op = new Operation[n];
		for (int i=0; i<n; i++) {op[i] = new Operation(sc.next().charAt(0),sc.nextInt());}
		
		int x = 0, y = 0;
		for (int i=n-1; i>=0; i--) {
			if (op[i].RC=='R' && op[i].num==y) {
				x--;
				x += x<0?W:0;
			}
			else if (op[i].RC=='C' && op[i].num==x) {
				y--;
				y += y<0?H:0;
			}
		}
		
		out.println((x+y)%2==0?"white":"black");
	}
}

class Operation {
	char RC;
	int num;
	Operation (char c, int n) {
		this.RC = c;
		this.num = n;
	}
}

二分探索

二分探索は、ソートされた配列の中から、特定の要素を高速で見つけ出すアルゴリズムである。

線形探索（先頭から末尾まで順番に判定していく）とは桁違いの速さで、具体的には、要素数1000000のとき線形探索では1000000回の判定が必要なのに対して、二分探索ではたった20回で済む。

この20回という回数はどこから来ているのかというと、要素数を2^nで表したときのnから。判定回数は整数値なので、要素数が100なら2^7=128（7回）、要素数が1000000なら2^20=1048576（20回）となる。

まずはシンプルな二分探索を実装してみる。

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

public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[] ar = {45,20,10,30,5,50,15,25,35,40};
		Arrays.sort(ar); //ソートする
		
		//ソートされた配列を表示
		for (int e:ar) {out.print(e+" ");} out.println();
		
		//ここから二部探索
		//L,Rを宣言
		int L = 0;
		int R = ar.length; //Rの初期値は要素数
		int target = 30;
		
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] == target) {
				out.println(target+"は"+(M+1)+"番目です");
				break;
			}
			else if (ar[M] > target) {R = M;}
			else if (ar[M] < target) {L = M+1;}
		}
	}
}

出力

次に、「target以下・target以上、target未満・targetより大きい要素はそれぞれ配列中に何個あるか」を調べる二分探索を書いてみたい。なぜこれを書く気になったかというと、以下の問題を解いたから。

C - Snuke Festival

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

public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[] ar = {45,20,10,30,5,50,15,25,35,40};
		Arrays.sort(ar);
		for (int e:ar) {out.print(e+" ");} out.println();
		
		
		//以下
		int target = 30;
		int L = 0;
		int R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] > target) {R = M;}
			else if (ar[M] <= target) {L = M+1;} //以下・以上を調べるときはこちらに等号をつける
		}
		out.println("30以下の値は"+L+"個あります");
		
		
		//以上
		target = 30;
		target--; //target以上を調べる場合は、targetから1引いたものを使う
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] > target) {R = M;}
			else if (ar[M] <= target) {L = M+1;}
		}
		out.println("30以上の値は"+(ar.length-L)+"個あります");
		
		
		
		
		
		//未満
		target = 30;
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] >= target) {R = M;} //未満・より大きいを調べるときはこちらに等号をつける
			else if (ar[M] < target) {L = M+1;}
		}
		out.println("30未満の値は"+L+"個あります");
		
		
		//より大きい
		target = 30;
		target++; //targetより大きい値の個数を調べるときは、targetに1足したものを使う
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] >= target) {R = M;} //未満・より大きいを調べるときはこちらに等号をつける
			else if (ar[M] < target) {L = M+1;}
		}
		out.println("30より大きい値は"+(ar.length-L)+"個あります");
		
		
	}
}

出力

追記：Arrays.binarySearchというメソッドを見つけた。Arrays.binarySearch(ar,n)とすることで、配列ar内にあるnの位置を戻り値として返してくれる。機能が限られているのであまり使い道はないかもしれない。ざっと調べてみたところ、配列内に同じ値がある場合はどれが検索されるか不定とあったので、重複のない配列でのみ用いるのがよさそう。

再帰関数入門・迷路探索編

再帰関数を用いて迷路を探索し、スタートからゴールにたどりつけるかどうかを判定する。

使用するのは以下の問題。

A - 深さ優先探索

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

public class Blog {
	static Scanner sc = new Scanner(System.in);
	
	static int H=sc.nextInt(),W=sc.nextInt();
	static char[][] map = new char[H][W];
	static boolean[][] memo = new boolean[H][W];
	static int sy,sx;
	static int gy,gx;
	
	public static void main(String[] args) {
		
		for (int i=0; i<H; i++) {
			String s = sc.next();
			map[i] = s.toCharArray();
			for (int j=0; j<s.length(); j++) {
				if (s.charAt(j)=='s') {sy = i; sx = j;}
				else if (s.charAt(j)=='g') {gy = i; gx = j;}
			}
		}
		rec(sy,sx);
		System.out.println(memo[gy][gx]?"Yes":"No");
		
		//ここから探索結果表示
		for (int i=0; i<H; i++) {
			for (int j=0; j<W; j++) {
				out.print(memo[i][j]==true?"o":"x");
			}
			out.println();
		}
		//ここまで
	}

	static void rec(int y, int x) {
		if (y<0 || x<0 || H<=y || W<=x) {return;}
		if (map[y][x]=='#' || memo[y][x]) {return;}
		memo[y][x] = true;
		rec(y,x+1);
		rec(y,x-1);
		rec(y+1,x);
		rec(y-1,x);
	}
	
}

入力例4

まず、メインメソッドからスタート地点を引数にして再帰関数を起動する。

その後は、引数の座標に対して、

迷路の範囲外の場合　→　何もしない
壁の場合、あるいは座標が訪問済みの場合　→　何もしない
それ以外　→　訪問済みかどうかを記録する配列memoにtrueを代入、上下左右に分岐

という流れで処理していく。

処理が一通り終わったら（スタート地点から到達することができる全ての座標を探索したら）、ゴールが訪問済みになっているかどうかを調べて、訪問済みならYes（到達可能）、未訪問ならNo（スタート地点からは到達不可能）を出力する。

迷路探索のアルゴリズムでは、以前、幅優先探索のものを紹介した。

迷路探索メソッド - Java初心者の競技プログラミング日記

深さ優先と幅優先、どちらを使えばいいかは問題による。調べてみたところ、最短歩数を求めるような問題では、深さ優先探索は使えないらしい。また、ゴール地点がスタート地点から近ければ近いほど、幅優先探索のほうが有利になるらしい。

結局のところどちらを使えばいいのか……おそらく、単純にゴールに到達可能かどうかを調べるだけなら、深さ優先探索でいいと思う。コードも短くて済むし。高度なことをやる場合、たとえばyukicoderのコレ（No.424 立体迷路 - yukicoder）や、コレ（No.157 2つの空洞 - yukicoder）のような問題を解くときに、幅優先探索を使うのだと思う。