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

Dvorak配列でjavaを書いてます

Javaで使える数学系メソッドまとめ

//最大公約数・最小公倍数(セットで使う)
static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
static int lcm (int a, int b) {return a*b/gcd(a,b);}


//素数判定
static boolean IsPrime (int n) {
	if (n<=2 || n%2==0) {return false;}
	double d = Math.sqrt(n);
	for (int i=3; i<=d; i+=2) if(n%i==0){return false;}
	return true;
}


//階乗
static long factorial (int i) {
	if (i==1) {return 1;}
	else {return i*factorial(i-1);}
}


//進数変換
static String toNbase (String sm, int m, int n) {
	return Long.toString(Long.parseLong(sm,m),n);
}

yukicoder No.652 E869120 and TimeZone

A問題に引き続いて時刻の問題。

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 h = sc.nextInt();
		int m = sc.nextInt();
		String s = sc.next();
		
		//日本の時刻(分)
		int japan = h*60+m;
		
		//X国の時刻を求める
		//余計な部分を取り除く
		double dif = Double.parseDouble(s.replaceAll("[UTC+]",""));
		
		//日本時間の9を引いてやることによって、
		//X国の現在時刻が日本とどれだけずれているかが求まる。
		dif = (dif*60)-(9.0*60);
		
		//X国の時刻(分)
		int x = japan+(int)dif;
		
		//以下、これを時と分の表記に直す
		x %= 1440;
		if (x<0) {
			x += 1440;
		}
		int H = x/60;
		int M = x%60;
		
		//直せたので、あとは出力するだけ
		String ans = "";
		if (H < 10) {ans += "0";}
		ans += H + ":";
		if (M < 10) {ans += "0";}
		ans += M;
		out.println(ans);
	}
}


追記:リジャッジでWAになってたので修正。
・(dif-9.0)*60 → (dif*60)-(9.0*60)

yukicoder No.651 E869120 and Driving

はじめてyukicoderコンテストに出場しました。結果はABC完答、DE放棄。


時速100kmでakm移動したときにかかる時間は。a/100時間。小数の問題があるのと、どちらにせよこのあと現在時刻にかかった時間を足して計算しなければならないので、分に直す。


目的地に移動するのにかかる時間は60*a/100分。これに現在時刻午前10時(600分)を足して、時:分の表記に直す。

import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a = sc.nextInt();
		a = 60*a/100;
		int time = 600+a;
		int h = time/60;
		int m = time%60;
		if (m<10) {System.out.println(h+":0"+m);}
		else {System.out.println(h+":"+m);}
	}
}


aの最大値は1000、つまりかかる時間は最大でも10時間なので、到着は22時となり、24時間表記のうちに収まる。よって、1440で割って余りを求める例の処理はこの問題では必要ない。また、時刻(h)の値も常に2桁なので、1桁の場合に0を付け加えてやる例の処理もない。分(m)のほうには必要。

「絶対・相対誤差10^(-n)以下であれば正答とみなされる」の意味

yukicoderで以下の問題を解いていて、一つ疑問に思ったので記事にすることにした。
No.379 五円硬貨 - yukicoder



問題文には「相対誤差または絶対誤差が10^(-12)以下であれば正答と見なされる」と書いてある。

このとき、解答では小数点以下何桁まで出力するべきなのか。

10^(-12)は「0.000000000001」と表される。絶対誤差あるいは相対誤差がこの値よりも小さければよい、ということなのだが、そもそも絶対誤差と相対誤差が分からない。そこで少し調べてみた。


・絶対誤差は単純に二つの値の差。

・相対誤差は絶対誤差を理論値で割ったもの。


例えば、100と出力しなければならない問題に、101と出力したときの絶対誤差と相対誤差はどれだけかというと

絶対誤差:101-100=1
相対誤差:(101-100)/100=0.01

となる。ここで注意すべきなのが、絶対誤差は二つの値と単位を同じくするので比較できるが(101kgと100kgの絶対誤差は1kg)、相対誤差は見ての通り比率なので単純に比較はできないということだ。

とりあえず、相対誤差はなんだか面倒くさそうなので、絶対誤差で考えることにする。

10^(-12)は「0.000000000001」だ。小数点以下の桁数は12桁。絶対誤差をこれ以下に抑えるためには、13桁まで出力してやればいいはず。

BigDecimalを使ってdivide(bd,13,RoundingMode.HALF_UP)と計算し、小数点14桁目を切り上げて小数点以下13桁まで出力した。すると無事にAC。

ここで注目したいのが、サンプル2の出力。「335030261.51740766171」となっている。小数点以下は11桁。あれッ、これでは通らないのではないのか。だがよくよく考えてみると、問題文では「絶対誤差あるいは相対誤差」となっているのだから、つまり、この出力の絶対誤差は10^(-12)以上ではあるが、相対誤差が10^(-12)以下となっているため正答、ということなのだろう。このあと自分でも小数点以下の桁数を10桁まで少なくして提出してみたところ、やはり通った。ちなみに9桁まで減らすと通らない。

と、ここまで長々と書いてきたが、結論としては

・「絶対・相対誤差10^(-n)以下」と指定された場合は「小数点以下n+1桁目」まで出力すればよい

ということになる。

ローマ数字をアラビア数字に変換するメソッド

ローマ数字からアラビア数字に変換するメソッドと、アラビア数字からローマ数字に変換するメソッド。

static int RomanToArabic (String s) {
	String[] a = {"IV","IX","XL","XC","CD","CM"};
	String[] b = {"IIII","VIIII","XXXX","LXXXX","CCCC","DCCCC"};
	for (int j=0; j<6; j++) {
		s = s.replaceAll(a[j],b[j]);
	}
	int n = 0;
	int[] number = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
	String[] roma = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
	for (int i=0; i<s.length(); i++) {
		for (int j=0; j<13; j++) {
			if (s.substring(i,i+1).equals(roma[j])) {n += number[j];}
		}
	}
	if (n > 3999) {return -1;}
	else {return n;}
}


static String ArabicToRoman (int n) {
	if (n<0 || 3999<n) {return "error";}
	int[] number = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
	String[] roma = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
	StringBuilder ans = new StringBuilder();
	for (int i=0; i<13; i++) {
		int ii = n/number[i];
		for (int j=0; j<ii; j++) {
			ans.append(roma[i]);
		}
		n = n%number[i];
	}
	return ans.toString();
}


ローマ数字からアラビア数字に変換するメソッド(RomanToArabic)については、引数の例外処理をしていないので、ローマ数字の規則から外れた文字列(XXXXXXXXXX)を渡しても、正しく変換されてしまう(100)ので注意が必要。

メソッドの中にこんなに配列を入れたら、メモリ消費量が上がってしまうような気がするが、もし気になるなら、配列をstaticにしてメソッドの外へ出してやることで、メモリ消費量も多少抑えられるのではないかと思う。

以下、このメソッドの使用例。
#237637 No.518 ローマ数字の和 - yukicoder

追記:やはり配列をメソッドの外に出さないと、メモリ消費量ではなく実行速度がかなり落ちるようなので、TLEを気にするなら配列を外に出すべきだ。配列を使わずif文だけで記述すれば実行速度も多少上がるのだろうが、書くのがめんどくさいのでやらない。

yukicoder No.457 (^^*)

左カッコ一つ一つに対して、文字列の最後まで探索し、その間に現れる左向きと右向きの数を数え上げる。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		
		//左向きの個数と右向きの個数をカウントする変数
		int L = 0;
		int R = 0;
		
		//一時的な文字列としてStringBuilderを利用する
		StringBuilder l = new StringBuilder();
		StringBuilder r = new StringBuilder();
		
		//すべての左カッコについて調べる
		for (int i=0; i<s.length(); i++) {
			//左カッコを検出
			if (s.charAt(i)=='(') {
				//左カッコならば、文字列の末尾まで探索
				for (int j=i+1; j<s.length(); j++) {
					char c = s.charAt(j);
					//*の場合と^の場合とで、それぞれ左向きと右向きとを作っていく
					if (c=='*') {
						if (r.length()==0) {r.append("*");}
						if (l.length()==2) {l.append("*");}
					}
					else if (c=='^') {
						if (r.length()==1 || r.length()==2) {r.append("^");}
						if (l.length()==0 || l.length()==1) {l.append("^");}
					}
					//右カッコが現れたとき、左向きor右向きが完成していればカウント。
					else if (c==')') {
						if (r.length()==3) {R++;}
						if (l.length()==3) {L++;}
					}
				}
				//一つの左カッコを調べ終わったら、左向きと右向きをリセット。
				r.setLength(0);
				l.setLength(0);
			}
		}
		
		System.out.println(L+" "+R);
	}
}


サンプル5を例にして説明する。

・(*^^)*(^^*)

左カッコは2個あるので、それぞれの左カッコについて文字列の末尾まで調べる。

1番目の左カッコを調べるときの流れを下に書いてみる。左向きがソースコード中の"l"、右向きがソースコード中の"r"に対応する。


・*  左向き0:右向き0[*]
・*^  左向き0[^]:右向き0[*^]
・*^^  左向き0[^^]:右向き0[*^^]
・*^^)  左向き0[^^]:右向き1[*^^] 

完成しているときに右カッコが現れたので右向き+1。以降、*や^が現れても、右向きのに付け足す必要はない(カッコ以外は何回でも使えるため)。

・*^^)*  左向き0[^^*]:右向き1[*^^]
・*^^)*(  変化なし いまは1番目の左カッコについて調べているので、左カッコが出てきても無視。
・*^^)*(^  変化なし
・*^^)*(^^  変化なし
・*^^)*(^^*)  左向き1[^^*]:右向き2[*^^] <処理終了>


というふうにして、1番目の左カッコについて調べた結果、左向き1、右向き2という結果が得られた。この処理を同様に2番目の左カッコに対しても行ってやると、左向き1となる。よって、左向き2、右向き2という出力が得られる。


この解法の時間計算量は、Nを文字列の長さとしたとき、おそらくO(N*logN)だと思われる。動的計画法を使えばO(N)で解けるらしい。

マップを値でソートするメソッド

マップを値でソートするメソッド。上のメソッドは、マップを渡すと、値でソートされたマップが戻り値として返されるメソッド。下のメソッドは、ソートしたマップを出力するだけの戻り値なしのメソッド。

static Map<String,Integer> MapValueSort (Map<String,Integer> map, int n) {
	List<Integer> list = new ArrayList<>(map.values());
	List<String> list2 = new ArrayList<>();
	Map<String,Integer> map2 = new LinkedHashMap<>();
	if (n==0) {Collections.sort(list);}
	else if (n==1) {Collections.sort(list,Comparator.reverseOrder());}
	for (int i=0; i<list.size(); i++) {
		for (Map.Entry<String,Integer> entry : map.entrySet()) {
			if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) {
				map2.put(entry.getKey(),entry.getValue());
				list2.add(entry.getKey());
				break;
			}
		}
	}
	return map2;
}


static void MapValueSortPrint (Map<String,Integer> map, int n) {
	List<Integer> list = new ArrayList<>(map.values());
	List<String> list2 = new ArrayList<>();
	if (n==0) {Collections.sort(list);}
	else if (n==1) {Collections.sort(list,Comparator.reverseOrder());}
	for (int i=0; i<list.size(); i++) {
		for (Map.Entry<String,Integer> entry : map.entrySet()) {
			if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) {
				System.out.println(entry.getKey()+" "+entry.getValue());
				list2.add(entry.getKey());
				break;
			}
		}
	}
}


アルゴリズムは以下の記事のものとまったく同じ。
yukicoder No.628 Tagの勢い - Java初心者の競技プログラミング日記


メモリ消費量がすごそうだが、とりあえず動いてくれてすぐ使えるものを、というスタンスで作った。引数にはソートするマップ(LinkedHashMapを想定、TreeMapでも多分動く)と、0か1の数字を指定する。0なら昇順、1なら降順にソートされる。


以下は使用例である。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		Map<String,Integer> map = new LinkedHashMap<>();
		map.put("a",5);
		map.put("c",1);
		map.put("e",4);
		map.put("d",3);
		map.put("b",2);
		


		//値で昇順ソート
		map = MapValueSort(map,0);
		
		System.out.println("<value ascending sort>");
		MapPrint(map);
		System.out.println();
		
		
		
		//値で降順ソート
		map = MapValueSort(map,1);
		
		System.out.println("<value descending sort>");
		MapPrint(map);
		System.out.println();
	}
	
	static Map<String,Integer> MapValueSort (Map<String,Integer> map, int n) {
		List<Integer> list = new ArrayList<>(map.values());
		List<String> list2 = new ArrayList<>();
		Map<String,Integer> map2 = new LinkedHashMap<>();
		if (n==0) {Collections.sort(list);}
		else if (n==1) {Collections.sort(list,Comparator.reverseOrder());}
		for (int i=0; i<list.size(); i++) {
			for (Map.Entry<String,Integer> entry : map.entrySet()) {
				if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) {
					map2.put(entry.getKey(),entry.getValue());
					list2.add(entry.getKey());
					break;
				}
			}
		}
		return map2;
	}
	
	//マップを全列挙するメソッド
	static void MapPrint (Map<String,Integer> map) {
		map.forEach((key,value)->System.out.println(key+":"+value));
	}
}



/*出力

<value ascending sort>
c:1
b:2
d:3
e:4
a:5

<value descending sort>
a:5
e:4
d:3
b:2
c:1

*/


もし値が同じキーが複数あった場合は、元の並び順が保障される。つまり、

a:2
b:5
c:2
d:1
e:2

要素がこのような順番で格納されているLinkedHashMapを、このメソッドを使って降順にソートすると、

b:5
a:2
c:2
e:2
d:1

とソートされる。ソート前もソート後も、値が2であったa,c,eの順番は変化していない。


これを利用することで、「値で降順ソート、もし値が同じキーがあるならそれらのキーを昇順ソート」としたい場合は、コンストラクタ無しのTreeMap<>()をこのメソッドで降順ソートしてやればよく、あるいは「値で昇順ソート、もし値が同じキーがあるならそれらのキーを降順ソート」としたい場合も、TreeMap<>(Comparator.reverseOrder())をこのメソッドで昇順ソートしてやることで実現できる。


この記事ではずっと値でソートすることについて述べてきたが、もし値でなくキーでソートしたい場合は、最初からTreemapを使うか、あるいはLinkedHashMapなどからTreemapに要素を移し替えてあげることでソートできる。