ビット全探索

ビット全探索とは、二進数とビットを用いて、ある集合の部分集合を全列挙（全探索）するアルゴリズムのこと。

public class Blog {
	public static void main(String[] args) {
		//集合
		String[] ar = {"a","b","c"};
		
		//要素数
		int n = 3;
		
		//以下メイン処理
		for (int i=0; i<(Math.pow(2,n)); i++) {
			String s = "-";
			for (int j=0; j<n; j++) {
				if ((1&i>>j) == 1) {s += ar[j];}
			}
			System.out.println(s);
		}
		
		/*出力
		
		-
		-a
		-b
		-ab
		-c
		-ac
		-bc
		-abc
		
		*/
	}
}

上から順に見ていく。まず、外側のforの条件式について。

for (int i=0; i<(1<<n); i++) {};

「1<<n」の部分は、集合（ここではa,b,c）の部分集合（a,ac,abcなど）が何種類あるか、つまりこれから全探索することになる部分集合の個数を表している。「1<<n」の意味は「1をnだけ左にビットシフトする」であり、要は「2のn乗」である。よって、「1<<n」の部分は「Math.pow(2,n)」と書いてもよい。今回は集合の要素数が3個なので、その部分集合の数は（空集合を含めて）2^3=8となり、外側のループは8回まわる。

次に、内側のループのif文について。

if ((1 & i>>j) == 1) {};

この条件の意味は、「二進数iをjだけ右にビットシフトしたときの、iの1桁目と1とでビット論理積をとって、演算結果が1であるなら処理を実行する」というものである。ビット論理積は、二つのビットを比較して、両方とも1であれば1、それ以外は0を返す演算のこと。

外側のループを回していくと、iの値は

・000　-(空集合)
・001　-a
・010　-b
・011　-ab
・100　-c
・101　-ac
・110　-bc
・111　-abc

と変化する。右側は出力された部分集合である。ここでは便宜上、桁数を合わせるために0を先頭に付け足している。

iの値をよく見てみると、1桁目が配列の0番目、2桁目が配列の1番目、3桁目が配列の2番目の要素に対応していることが分かる。

より視覚的に分かりやすくするため、iの値を逆にしてみると……

・000　___
・100　a__
・010　_b_
・110　ab_
・001　__c
・101　a_c
・011　_bc
・111　abc

とこんなふうに、iの値のビットの立っている部分（1の部分）が、そのまま部分集合となっているのが分かる。

以上をまとめると、ビット全探索とは、まず集合に含まれる部分集合の数だけ二進数を0から順にピックアップし、その二進数の各桁のビットが立っているかどうかを条件式で判断し、立っている桁に対応する要素を（ピックアップした二進数の）部分集合とするアルゴリズム……ということになると思う。

ビット全探索で解くことのできる問題として、以下をあげておく。

例題1：C: たくさんの数式 / Many Formulas - AtCoder Beginner Contest 045 | AtCoder
解説1：この問題では、n桁の数字が与えられ、数字と数字のあいだに最大でn-1個の"+"を入れることができ、その入れかたのパターンを、今回紹介したbit全探索で列挙することができる。

例題2：#239883 No.617 Nafmo、買い出しに行く - yukicoder
解説2：いわゆるナップサック問題。本来はビット全探索では時間がかかりすぎるのだが、この問題では価値の概念がなく重さだけで選ぶのに加え、商品の数が最大でも20と小さいので、ビット全探索で解くことができる。

例題3：C - Train Ticket
解説3：例題1が解ければこれも解けると思う。ただしこちらは要素の数が3個（組み合わせは2^3で8通り）と少ないので、解説ページにもあるようにビット全探索を使わなくても解ける。

ビット全探索のほかにも、再帰関数を用いて同様に全列挙することも可能らしい。いずれは記事にしたい。

迷路探索メソッド

迷路を探索するメソッド。
幅優先探索が分からなかったので、Listを使ってそれっぽく作ってみた。
以下のような問題で利用できる。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder
D: Grid Repainting - AtCoder Beginner Contest 088 | AtCoder

【最短歩数を返すメソッド】

static int SearchRoute (int sx, int sy, int gx, int gy, String[][] ar) {
	Deque<Point> p = new ArrayDeque<>();
	p.add(new Point(sx,sy));
	int moves = 0;
	ar[sx][sy] = "0";
	int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	int s,i,j;
	while (true) {
		s = p.size();
		for (int k=0; k<s; k++) {
			i = p.getFirst().x;
			j = p.removeFirst().y;
			for (int a=0; a<4; a++) {
				if (i+dx[a]<0 || ar.length-1<i+dx[a] || j+dy[a]<0 || ar[0].length-1<j+dy[a]) {
					continue;
				}
				if (ar[i+dx[a]][j+dy[a]].equals(".")==false) {continue;}
				ar[i+dx[a]][j+dy[a]] = String.valueOf(moves+1);
				p.addLast(new Point(i+dx[a],j+dy[a]));
			}
		}
		moves++;
		if (s == 0) {break;}
	}
	if (ar[gx][gy].equals(".")) {return -1;}
	return Integer.parseInt(ar[gx][gy]);
}

スタート地点（sx,sy）、ゴール地点（gx,gy）と、"."と"#"から構成された二次元配列の迷路を引数として与えてあげることで、最短歩数が戻り値として返される。ゴール地点にたどりつけないような迷路の場合は-1が返される。

スタート地点とゴール地点の距離を求めたい場合は、戻り値に1足せばOK。

【最短ルートを描くメソッド】

static void PrintRoute (int sx, int sy, int gx, int gy, String[][] ar) {
	Deque<Integer> x = new ArrayDeque<>();
	Deque<Integer> y = new ArrayDeque<>();
	x.addFirst(sx);
	y.addFirst(sy);
	int moves = 0;
	ar[sx][sy] = "0";
	while (true) {
		int s = x.size();
		for (int k=0; k<s; k++) {
			int i = x.removeFirst();
			int j = y.removeFirst();
			if (i>0 && ar[i-1][j].equals(".")) {
				ar[i-1][j] = String.valueOf(moves+1);
				x.addLast(i-1);
				y.addLast(j);
			}
			if (i<ar.length-1 && ar[i+1][j].equals(".")) {
				ar[i+1][j] = String.valueOf(moves+1);
				x.addLast(i+1);
				y.addLast(j);
			}
			if (j>0 && ar[i][j-1].equals(".")) {
				ar[i][j-1] = String.valueOf(moves+1);
				x.addLast(i);
				y.addLast(j-1);
			}
			if (j<ar[0].length-1 && ar[i][j+1].equals(".")) {
				ar[i][j+1] = String.valueOf(moves+1);
				x.addLast(i);
				y.addLast(j+1);
			}
		}
		moves++;
		if (s == 0) {break;}
	}
	if (ar[gx][gy].equals(".")) {System.out.println("error");}
	else {
		int i = gx;
		int j = gy;
		int num = Integer.parseInt(ar[gx][gy])-1;
		while (true) {
			String s = String.valueOf(num);
				if (i>0 && ar[i-1][j].equals(s)) {
					if (Integer.parseInt(ar[i-1][j]) == num) {
						ar[i-1][j] = "$";
						i--;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
				if (i<ar.length-1 && ar[i+1][j].equals(s)) {
					if (Integer.parseInt(ar[i+1][j]) == num) {
						ar[i+1][j] = "$";
						i++;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
				if (j>0 && ar[i][j-1].equals(s)) {
					if (Integer.parseInt(ar[i][j-1]) == num) {
						ar[i][j-1] = "$";
						j--;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
				if (j<ar[0].length-1 && ar[i][j+1].equals(s)) {
					if (Integer.parseInt(ar[i][j+1]) == num) {
						ar[i][j+1] = "$";
						j++;
						num--;
					}
				}
			if (i==sx && j==sy) {break;}
		}
		ar[gx][gy] = "G";
		ar[sx][sy] = "S";
		for (int a=0; a<ar.length; a++) {
			for (int b=0; b<ar[0].length; b++) {
				if (ar[a][b].matches("[#$GS]")==false) {
					System.out.print(".");
				}
				else {
					System.out.print(ar[a][b]);
				}
			}
			System.out.println();
		}
	}
}

使用例（数字は上から、迷路のサイズ（縦横）、スタート座標、ゴール座標）

AtCoder Beginner Contest 088

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問題に関してはどうしようもない。僕が習得しているアルゴリズムが少なすぎるのが問題なのだ。二分探索はもちろん、今回の二つの探索、グラフ、動的計画法、何一つ分からない。そろそろ本格的に書籍など買って、体系的に競プロアルゴリズムを学ぶ必要があることを、今回のコンテストを終えてから痛切に感じた。

基数変換メソッド

n進数snをm進数に変換するメソッド。
使用できる基数（n,m）は2以上36以下。

static String BaseConversion (String sn, int n, int m) {
	String sm = Long.toString(Long.parseLong(sn,n),m);
	return sm;
}

使用例

//10進数5を2進数に
System.out.println(BaseConversion("5",10,2)); //output = 101

//5進数1234を10進数に
System.out.println(BaseConversion("1234",5,10)); //output = 194

//36進数aiueoを10進数に
System.out.println(BaseConversion("aiueo",36,10)); //output = 17675376

汎用性を重視するため、引数も戻り値もString型にしてみた。
Longを使っているのは桁あふれ防止のため。変換後の値がint型の範囲を超えないなら、intでも大丈夫だと思う。

Javaで基数変換（10進数からn進数、n進数から10進数）

yukicoderの[No.499 7進数変換]を解いていて、10進数で与えられる数値を7進数に変換する必要があったので、自分は数値を7で割りながらその余りを求めていく方法で解いた。以下がその僕の回答だ。
#236582 No.499 7進数変換 - yukicoder

しかし調べていくと、はるかに簡単な求め方があったようなのでそれを紹介する。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//【10進数→n進数】
		
		//10進数30を16進数に変換
		String s_16 = Integer.toString(30,16);
		
		//10進数100を7進数に変換
		int i_7 = Integer.parseInt(Integer.toString(100,7));
		
		//出力
		System.out.println(s_16); //output = 1e
		System.out.println(i_7); //output = 202
		
		
		
		//【n進数→10進数】
		
		//16進数1eを10進数に変換
		int i1 = Integer.parseInt("1e",16);
		
		//7進数202を10進数に変換
		int i2 = Integer.parseInt("202",7);
		
		//出力
		System.out.println(i1); //output = 30
		System.out.println(i2); //output = 100
		
		
		
		//【n進数→m進数】
		int n = 2;
		int m = 8;
		String s = Integer.toString(Integer.parseInt("1110",n),m);
		
		//出力
		System.out.println(s); //output = 16
		


		//【基数の下限と上限】
		System.out.println(Character.MIN_RADIX); //output = 2
		System.out.println(Character.MAX_RADIX); //output = 36
	}
}

・String sn = Integer.toString(i,n);
　→「10進数（i）」を「n進数（sn）」に変換する

・int i = Integer.parseInt("sn",n);
　→「n進数（sn）」を「10進数（i）」に変換する

・String sm = Integer.toString(Integer.parseInt("sn",n),m);
　→「n進数（sn）」を「m進数（sm）」に変換する

・String sm = Long.toString(Long.parseLong("sn",n),m);
　→変換後の値がint型の範囲を超える場合はこっち

これを使うさいの注意点について。

①基数が11以上の進数に変換する場合、戻り値にアルファベットが含まれるので、必ずString型で受け取るようにする。

②基数が10以下の進数に変換する場合は、int型でも受け取ることができる。ただし、Integer.toString()は文字列を返すので、Integer.parseInt()を使ってint型に変換してから受け取る。また、基数が大きいものから小さいものに変換すると、もとの値よりも桁数が増えるので、値によってはLong.parseLong()を使ってlong型で受け取ったほうがいいと思われる。例えば、10進数1000000000を4進数に変換すると323212230220000となり、int型では桁あふれを起こしてしまうので、long型で受け取る。

③基数に設定できるのはCharacter.MIN_RADIXからCharacter.MAX_RADIXまで、2～36となっている。

④10進数から2、8、16進数への変換については、それぞれ専用のメソッドが用意されているようなので、そちらを使ったほうが速いかもしれない。
・String bin = Integer.toBinaryString(i);　10進数i → 2進数bin
・String oct = Integer.toOctalString(i);　10進数i→8進数oct
・String hex = Integer.toHexString(i);　10進数i→16進数hex

記事を書くにあたって、こちらの回答と記事を参考にさせていただきました。
#164033 No.499 7進数変換 - yukicoder
Javaで進数変換を行う方法 - Qiita

yukicoder No.508 超ゆとり教育

解説にもある通り、与えられる面積の最高値（10^12）であっても、円周率を3として計算してみると、大体570000くらいになる。よって、たとえ1を出力しようが999を出力しようが、誤差は1000000以内に抑えられてしまう。

1～1000001までの正整数を出力しておけば、どのテストケースに対してもACできる、と思う。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		System.out.println(3);
	}
}

Javaの型変換について

Javaのデータ型は、基本型（プリミティブ型）や参照型、クラス型などさまざまに分類され、型変換のさいには山ほどの規則と注意点があるということなのだが、ここではとりあえず、それぞれの型同士の相互変換が成り立つか、成り立つとすればどのような方法で変換すればいいか、それをまとめておきたいと思ったので、この記事を書くことにした。

今回は、Javaプログラミングでよく使う以下のデータ型
・String
・char
・int
・long
・double
これらの相互変換をまとめてみたい。

【String型】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//これらの文字列をそれぞれのデータ型に変換する
		String s_int = "100";
		String s_long = "999999999999999";
		String s_double = "3.14";
		String s_char1 = "abcde";
		String s_char2 = "a";
		
		
		//int型,long型,double型へは、それぞれに対応したメソッドを使えば変換できる
		int i = Integer.parseInt(s_int);
		long L = Long.parseLong(s_long);
		double d = Double.parseDouble(s_double);
		
		
		//char型には1バイトしか入らないので、Stringを分解してchar型配列に入れる
		char[] c1 = s_char1.toCharArray();
		
		//Stringが1バイトの場合は、charAt()を使う
		char c2 = s_char2.charAt(0);
	}
}

【char型】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//これらの文字をそれぞれのデータ型に変換する
		char c_int = 'I';
		char c_long = 'L';
		char c_double = 'D';
		char c_String = 'S';
		
		
		//int型,long型,double型
		//int以外は多分使わないと思うが一応……
		int i = (int)(c_int); //output = 73
		long L = (long)(c_long); //output = 76
		double d = (double)(c_double); //output = 68.0;
		
		
		//String型
		String s1 = String.valueOf(c_String); //output = S
		
		//String型に直接char型を足し合わせることもできる
		String s2 = "abc";
		s2 += c_String; //output = abcS
	}
}

【int型】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//これらの値をそれぞれのデータ型に変換する
		int i_long = 10000;
		int i_double = 100;
		int i_char = 65;
		int i_String = 1234567890;
		
		
		//long型,double型
		//何もしなくても勝手に変換される……？
		long L = i_long;
		double d = i_double;
		
		
		//char型
		//intの値が、char型で扱える範囲の数値であることが条件。
		char c = (char)(i_char); //output = A
		
		
		//String型
		String s = String.valueOf(i_String);
	}
}

【long型】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//これらの値をそれぞれのデータ型に変換する
		long L_int = 10000;
		long L_double = 100;
		long L_char = 65;
		long L_String = 999999999999999L;
		
		
		//int型,double型
		//long型からint型に変換すると桁あふれを起こす可能性があるので、
		//基本的にはしないほうがいいと思われる。
		int i = (int)(L_int);
		double d = L_double;
		
		
		//char型
		//long型の値が、char型で扱える範囲の数値であることが条件。
		//多分一生使わないと思う。
		char c = (char)(L_char); //output = A
		
		
		//String型
		String s = String.valueOf(L_String);
	}
}

【double型】

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//これらの値をそれぞれのデータ型に変換する
		double d_int = 1.5;
		double d_long = 100.555;
		double d_char = 65.0;
		double d_String = 0.999999999999999;
		
		
		//int型,double型
		//小数点以下が消失し、誤差が発生してしまうので、
		//基本的にはしないほうが無難だと思われる。
		//逆にそのことを利用して、小数点以下を切り捨てるのに使うことができる。
		int i = (int)(d_int); //output = 1
		long L = (int)(d_long); //output = 100
		
		
		//char型
		//double型の値が、char型で扱える範囲の数値であることが条件。
		//多分一生使わないと思う。
		char c = (char)(d_char); //output = A
		
		
		//String型
		String s = String.valueOf(d_String); //output = 0.999999999999999
	}
}