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

Dvorak配列でjavaを書いてます

yukicoder No.688 E869120 and Constructing Array 2

方針

・0と1の順番は関係ないので、リストに1を適当個詰めたあと、0を適当個詰めて、出力する
・ここでは便宜上、1を「2を作るための数」と定義し、0を「組み合わせを増やすための数」と定義する。
・合計が2になるには、1が少なくとも2個は必要。
 →k=0のときは、0か1をひとつだけ出力すればよい。


1のみで数列を構成した場合

合計が2となる選びかたは……

・11 → 選び方は1通り
・111 → 3通り
・1111 → 6通り
・11111 → 10通り

1のみで配列を構成した場合、合計が2となるような選びかたは、「(1の数)C2」のコンビネーションで求まる。


0のみで数列を構成した場合

数列の部分集合(すべての選びかたの合計)は……

・0 → 選び方は2通り
・00 → 4通り
・000 → 8通り
・0000 → 16通り

0のみで配列を構成した場合、その部分集合の数は「2^(0の数)」で求まる。


1と0から数列を構成する

・1の個数とその選び方 2(1), 3(3), 4(6), 5(10), 6(15)......
・0の個数とその選び方 0(1), 1(2), 2(4), 3(8), 4(16), 5(32)......

たとえば、K=96のとき、1が4個(6通り)、0が4個(16通り)からなる数列を作ることで、題意を満たす数列となります。

K=10のときは1を5個並べればよいですし、K=2のときは1を2個と0を1個並べればよいです。


実装する

まず、k=0の場合は1もしくは0を出力して終わらせます。

次に、数列を1のみから構成した場合の選び方(Key)とその個数(Value)をmapに入れます。
・11 map.put(1,2)
・111 map.put(3,3)
・1111 map.put(6,4)
・11111 map.put(10,5)
・1*30 map.put(435,30) 最大値

もし指定されたkがこのmapのKeyに含まれているなら、そのValueぶんだけ1をリストに追加し、それを出力します。

さて問題は、指定されたkがmapのKeyに含まれていない場合です(2560など)

この場合は、kが(mapのKeyに含まれている数)*(2^n)の形になればよいわけですから、kを手当たり次第にmapのKeyで割っていきます(k/key = dとします)。このdが2^nの形になっているかどうかを確かめ、もしなっているなら、1をvalue回、0をn回リストに追加し、それを出力します。

追記:この方法だと配列の長さが30を超えてしまいそうなので、公式解説にある通り、0と1の個数を全探索するのがよいと思います。


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

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		Map<Integer,Integer> map = new HashMap<>();
		for (int i=2; i<=30; i++) {
			map.put(i*(i-1)/2, i);
		}
		
		Set<Long> set = new HashSet<>();
		for (int i=1; i<=28; i++) {
			set.add((long)Math.pow(2,i));
		}
		
		
		List<Integer> ans = new ArrayList<>();

		long n = sc.nextLong();
		
		if (n == 0) out.println(1);
		if (map.containsKey((int)n)) {
			for (int i=0; i<map.get((int)n); i++) {
				ans.add(1);
			}
			printList(ans);
		}
		else {
			for (Map.Entry<Integer,Integer> e: map.entrySet()) {
				int k = e.getKey();
				long d = n/k;
				if (set.contains(d)) {
					
					for (int i=0; i<map.get(k); i++) {
						ans.add(1);
					}
					while (d%2 == 0) {
						d /= 2;
						ans.add(0);
					}
					printList(ans);
					
					break;
				}
			}
		}
	}

	static void printList(List<Integer> list) {
		for (int i=0; i<list.size(); i++) {
			out.print((i==0?"":" ")+list.get(i));
		}
	}
}

AtCoder Beginner Contest 097

A - Colorful Transceivers

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), d=sc.nextInt();
		int difAB = (int)Math.abs(a-b);
		int difBC = (int)Math.abs(b-c);
		int difAC = (int)Math.abs(a-c);
		if (difAB<=d && difBC<=d) {
			out.println("Yes");
		}
		else if (difAC <= d) out.println("Yes");
		else out.println("No");
	}
}

むっ、A問題にしては少し難しくないですか。僕だけですか。
AさんとCさんが通話する方法には2パターンある。

・Bさんを間に挟んでいる場合(Math.abs(a-b)とMath.abs(b-c)、両方がd以下ならば通話可能)
・AさんとCさんが隣り合っている場合(Math.abs(a-c)がd以下であれば通話可能)

よって、この2パターンを試してみて、どちらかで通話可能ならYes、どちらの方法でも通話できないならNoを出力する。


B - Exponential

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int x = sc.nextInt();
		TreeSet<Integer> set = new TreeSet<>();
		set.add(1);
		for (int i=2; i<=33; i++) {
			for (int j=2; j<=100; j++) {
				if (Math.pow(i,j) > x) break;
				set.add((int)Math.pow(i,j));
			}
		}
		
		int ans = 1;
		for (Integer n: set) {
			if (n > x) break;
			ans = n;
		}
		out.println(ans);
	}
}

僕はこの問題で致命傷(3WA)を負いました。原因は、問題文を読み違えていたから。
対象となる数列を、

・1,4,9,16,25,36......

のような、(i*i)の形で表せるもの限定だと思い込んでいた。
問題文とサンプルをよく読めば、

・1,4,8,9,16,25,27,32,36......

であることが分かる。2^3や、2^5といった数字も入ってくる。

ACできたプログラムでは、「2^2,2^3,2^4......2^n」「3^2,3^3,3^4......3^n」「33^2(最大の値)」というような、x以下のべき乗数を片っ端からsetに詰め込んでいる。


C - K-th Substring

部分点解答→満点解答という順に提出したので、まずは部分点解答を。

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		int k = sc.nextInt();
		int n = s.length();
		
		TreeSet<String> set = new TreeSet<>();
		
		for (int i=1; i<=n; i++) {
			for (int j=0; j<n-i+1; j++) {
				set.add(s.substring(j,j+i));
			}
		}
		
		int i = 1;
		for (String str: set) {
			if (i == k) {
				out.println(str); break;
			}
			i++;
		}
	}
}

部分点解答は、「長さnまでの、考えられうるすべてのsubstringを列挙し、TreeSetに詰め込み、先頭からk番目を出力する」というものになっている。

TLEして当然の全探索解答だが、意識的に部分点解答を作れたという点で成長が見られると思う。

では次に、満点解答を。


import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		int k = sc.nextInt();
		int n = s.length();
		
		TreeSet<Character> set = new TreeSet<>();
		for (int i=0; i<n; i++) {
			set.add(s.charAt(i));
		}
		
		List<Character> list = new ArrayList<>();
		int x=0;
		for (Character c: set) {
			if (x >= Math.min(set.size(),k)) break;
			list.add(c);
			x++;
		}
		
		TreeSet<String> ans = new TreeSet<>();
		for (int i=0; i<list.size(); i++) {
			char c = list.get(i);
			for (int j=0; j<n; j++) {
				if (s.charAt(j)==c) {
					
					for (int l=0; l<Math.min(k,n-j); l++) {
						ans.add(s.substring(j,j+l+1));
					}
					
				}
			}
		}
		
		
		int i = 1;
		for (String str: ans) {
			if (i == k) {
				out.println(str); break;
			}
			i++;
		}
	}
}

流れとしては、

・sを1文字ずつ探索し、TreeSet1に入れる
・TreeSet1の先頭から Math.min(5,s.length()) 個取り出し、リストに入れる
・リストに入っている文字一つ一つにつき、sを再び1文字ずつ探索する。
 ・リストの文字に行き当たったら、そこから Math.min(5,伸ばせるだけ) 伸ばしつつ、TreeSet2に格納していく。
 ・仮にsがabcdefgだとすると、リストの文字が bのときは、[b,bc,bcd,bcde,bcdef] がTreeSet2に入ることになる。
・TreeSet2の、先頭からk番目を出力して終了。

というもの。ようは、辞書順の小さいものを優先して探索して、計算量を減らそうと試みている。

追記:2つめのfor文のあとに「if(ans.size() >= k) break;」を入れれば、さらに計算量を減らせそう。
理由:辞書順で一番小さい文字(aとします)についてすべて探索し終えた段階で、substringがk個以上あったなら、その中からk番目に小さいsubstringを出力すればよく、もはやそれよりも辞書順で大きい文字(b,c,d......)を探索する必要はないからです。


しかし、解答となるsubstringが5文字以下であることを考えると、sの各文字について後方に5文字ぶんだけ探索し、setに入れることを繰り返せば、計算量25000で済み、TLEしないのでは……?

ということで、以下に、その方針に従って改良したプログラムをのせます。


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

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		int k = sc.nextInt();
		int n = s.length();

		TreeSet<String> ans = new TreeSet<>();
		for (int i=0; i<n; i++) {
			for (int j=0; j<Math.min(k,n-i); j++) {
				ans.add(s.substring(i,i+j+1));
			}
		}

		int i = 1;
		for (String str: ans) {
			if (i == k) {
				out.println(str); break;
			}
			i++;
		}
	}
}

うーん、これだけで済んでしまうのか。計算量だけでいえば一つ前の解答のほうが優れているんだろうけど、競プロならこっちを書くべきだろう。計算量の計算をとっさにできるようにしたい。

追記:あっ……部分点解答のnを5にするだけで満点解答になるじゃないか……


D - Equals

またこんど


まとめ

問題文をよく読むこと。それだけで今回の順位も50位は縮められた。C問題については、自力で部分点解答から満点解答まで持っていくことができ、素直に嬉しかった。昨日の記事では悲惨な結果に終わりそうなどと書いたが、終わってみると可もなく不可もなくという内容だった(202位)。今後はアルゴリズムの復習をしつつ、以前買った競プロ本も進めていければなと思っている。

n以下のすべての素数をリストで返すメソッド

エラトステネスのふるいを用いて、n以下のすべての素数をリストアップするメソッド。

ふるい終わったあとの配列が穴だらけになって不便なので、単にそれをリストに詰め込んだだけです。

static List<Integer> primeList(int n) {
	List<Integer> list = new ArrayList<>();
	boolean[] prime = new boolean[n+1];
	Arrays.fill(prime,true);
	prime[0]=false; prime[1]=false;
	for (int i=2; i<Math.sqrt(n); i++) {
		if (!prime[i]) continue;
		for (int j=2; i*j<=n; j++) {
			prime[i*j] = false;
		}
	}
	for (int i=0; i<prime.length; i++) {
		if (prime[i]) list.add(i);
	}
	return list;
}

<参考にしたページ>
Javaで素数を求めるプログラムを実装 - にわとりプログラマーの備忘録

AtCoder Beginner Contest 096

※今回は不参加で、問題はすべてコンテスト終了後に解きました。

A - Day of Takahashi

out.println(a<=b?a:a-1);


B - Maximum Sum

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), k=sc.nextInt();
		int total = a+b+c;
		int max = max(a,b,c);
		int pow = (int)Math.pow(2,k);
		out.println((total-max)+max*pow);
	}
	
	static int max(int... ar) {
		Arrays.sort(ar);
		return ar[ar.length-1];
	}
}

一番大きい数字を2倍していけばいいのではと考え、素直に実装した。


C - Grid Repainting 2

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int[] dx = {0,1,0,-1};
	static int[] dy = {-1,0,1,0};
 
	public static void main(String[] args) {
		int h=sc.nextInt(), w=sc.nextInt();
		char[][] map = new char[h+2][w+2];
		for (int i=1; i<h+1; i++) {
			String s = sc.next();
			for (int j=0; j<w; j++) {
				map[i][j+1] = s.charAt(j);
			}
		}
 
		boolean isAchievable = true;
		loop: for (int i=1; i<h+1; i++) {
			for (int j=1; j<w+1; j++) {
				if (map[i][j]=='#') {
					boolean isBlack = false;
					for (int k=0; k<4; k++) {
						if (map[i+dy[k]][j+dx[k]]=='#') isBlack = true;
					}
					if (!isBlack) {
						isAchievable = false;
						break loop;
					}
				}
			}
		}
 
		out.println(isAchievable?"Yes":"No");
	}
}

正直に告白すると、今回の問題は4問ともすべて解説を見てから解いている。
それでこの問題だが、すべての黒マスについて「上下左右のマスのうち、少なくとも一つが黒マス」という形になっていれば、達成できる。逆に、「上下左右すべてが白マス」という黒マスがあれば、達成できないということになる。
よって、すべての黒マスについて、上下左右のマスを調べればよい。


D - Five, Five Everywhere

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		List<Integer> list = primeList(55555);
		for (int i=0; i<n; i++) {
			out.print((i==0?"":" ")+list.get(i));
		}
	}
	
	static List<Integer> primeList(int n) {
		List<Integer> list = new ArrayList<>();
		boolean[] prime = new boolean[n+1];
		Arrays.fill(prime,true);
		prime[0]=false; prime[1]=false;
		for (int i=2; i<Math.sqrt(n); i++) {
			if (!prime[i]) continue;
			for (int j=2; i*j<=n; j++) {
				prime[i*j] = false;
			}
		}
		for (int i=0; i<prime.length; i++) {
			if (prime[i] && i%5==1) list.add(i); 
		}
		return list;
	}
}

メソッド「primeList」では、「n以下かつ、5で割って1余る素数」のリストを返すようにしている。
まずメインメソッドでprimeListを引数55555で動作させ、戻り値をlistに格納する。そしてその中から、小さい順にn個を出力して解答の数列としている。

このメソッドの作成にあたって、以下のページを参考にしました。
Javaで素数を求めるプログラムを実装 - にわとりプログラマーの備忘録


まとめ

とりあえず、競プロを休止していた期間に行われたコンテストについては、これですべて解き終わった。今日開催されるABC097は1か月ぶりのコンテストということになるけれど、悲惨な結果に終わるような気がしてならない。
それと、今回使った「n以下の素数をリストとして返すメソッド」というのは便利そうなので、作って記事にしようと思った。

AtCoder Beginner Contest 095

※今回は不参加で、問題はすべてコンテスト終了後に解きました。

A - Something on It

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String s = sc.next();
		int price = 700;
		for (int i=0; i<3; i++) {
			if (s.charAt(i)=='o') price += 100;
		}
		out.println(price);
	}
}

B - Bitter Alchemy

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n=sc.nextInt(), x=sc.nextInt();
		int min = Integer.MAX_VALUE;
		for (int i=0; i<n; i++) {
			int temp = sc.nextInt();
			min = Math.min(min,temp);
			x -= temp;
		}
		out.println(n+(x/min));
	}
}

入力で与えられたn種類のドーナツについては、すべて作れることが保障されているので、まずはそれを作る。残った粉で、一番粉消費が少ないドーナツを作れるだけ作る。


C - Half and Half

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt(), x=sc.nextInt(), y=sc.nextInt();
		int total = 0;
		if (a+b > 2*c) { //ABピザを買う必要あり
			total += 2*c*(Math.min(x,y));
			if (x > y) {
				total += (x-y)*a;
			}
			else if (x < y) {
				total += (y-x)*b;
			}
			int total2 = 2*c*(Math.max(x,y));
			out.println(Math.min(total,total2));
		}
		else {
			total = a*x + b*y;
			out.println(total);
		}
	}
}

まず、(a+b > 2*c)の条件式によって、ABピザを作る必要があるかどうか判断する。作らない場合は簡単。
ABピザを作る場合だが、「最低限の数だけABピザを作り、残りをAピザもしくはBピザで補う場合」と、「余ることが前提でABピザを作り、AピザとBピザは1枚も作らない場合」に分けられる。前者はmin(x,y)個、後者はmax(x,y)個ということだ。
それぞれ実際に作ってみて、金額が少ないほうを出力する。


D - Static Sushi

部分点の解のほうは理解できそうだったけれど、とりあえず先送り


まとめ

とくになし

可変長引数を用いた、最大値・最小値を求めるメソッド

可変長引数なるものがあることを(たった今)知りました。面白い書き方だったので、すぐにメモすることに。

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

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		out.println(max(1,8,5,10,9));
		out.println(min(9,5,7,1));
	}

	public static int max(int... ar) {
		Arrays.sort(ar);
		return ar[ar.length-1];
	}
	public static int min(int... ar) {
		Arrays.sort(ar);
		return ar[0];
	}
}

とこのように書けば、一つの型につき何個でも引数をとれるようなメソッドを作れる。


可変長引数には以下のような制約がある。
・一つのメソッドに一つだけ
・最後の引数でのみ使用できる


とここまで書いて、便利な機能だと感心したものの、競プロではあまり使い道はないかもしれない。3、4個の数字から最大値を求めるためにわざわざメソッドなど作っていては解答が遅くなるし、10個の数字から最大値を……となれば、配列を使えばよいからだ。

AtCoder Beginner Contest 094

※今回は不参加で、問題はすべてコンテスト終了後に解きました。

A - Cats and Dogs

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int a=sc.nextInt(), b=sc.nextInt(), x=sc.nextInt();
		
		if (x < a) out.println("NO");
		else {
			out.println(x-a<=b?"YES":"NO");
		}
	}
}

猫の最小値はa匹なので、それ未満の数の猫を指定された場合は条件分岐で弾く。
それ以上を指定された場合は、b匹のなかにx-a匹の猫がいることを証明する、つまりx-aがb以下であればよいので、それを条件式で処理して終わり。


B - Toll Gates

import static java.lang.System.*;
import java.util.*;
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n=sc.nextInt(), m=sc.nextInt(), x=sc.nextInt();
		int[] ar = new int[n+1];
		for (int i=0; i<m; i++) {
			int temp = sc.nextInt();
			ar[temp]++;
		}
		
		int costL=0, costR=0;
		for (int i=x; i>=0; i--) costL += ar[i];
		for (int i=x; i<=n; i++) costR += ar[i];
		
		out.println(Math.min(costL,costR));
	}
}

配列を用意して、初期地点から左端(0)に向かうときのコストと、右端(n-1)に向かうときのコストを比較して、少ないほうを出力する。


C - Many Medians

import static java.lang.System.*;
import java.util.*;
 
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];
		int[] ar2 = new int[n];
		for (int i=0; i<n; i++) {
			ar[i] = sc.nextInt();
			ar2[i] = ar[i];
		}
		Arrays.sort(ar);
		
		int medianA = ar[n/2-1];
		int medianB = ar[n/2];
		for (int i=0; i<n; i++) {
			if (ar2[i] <= medianA) out.println(medianB);
			else out.println(medianA);
		}
	}
}

答えとなる値は2通りしかないな、というのはすぐに分かりました。

与えられる要素数は偶数なので、配列をソートし、左側の中央値(本来なら2値の平均をとりますが、暫定的に)と右側の中央値をまず求める。
次に、ソートする前の配列を回していって、値が左側の中央値以下ならば右側の中央値を、右側の中央値以下ならば左側の中央値を出力する。


D - Binomial Coefficients

import static java.lang.System.*;
import java.util.*;
 
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];
		for (int i=0; i<n; i++) {
			ar[i] = sc.nextInt();
		}
		Arrays.sort(ar);
		
		int max = ar[n-1];
		double target = max/2.0;
		double minDif = Integer.MAX_VALUE;
		int ans = 0;
		for (int i=0; i<n-1; i++) {
			double tempDif = Math.abs(ar[i]-target);
			if (tempDif < minDif) {
				ans = ar[i];
				minDif = tempDif;
			}
		}
		
		out.println(max+" "+ans);
	}
}

出力例1を見て、「最大値」と「最大値/2にいちばん近い値」を順に出力すればいいのでは、と思い、そのように書いたところACしました。
その後解説を読みましたが、何が何やら分からないので、やっぱり数学の知識をつけないといけないのだなと改めて思いました。


まとめ

とくになし