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

Dvorak配列でjavaを書いてます

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位)。今後はアルゴリズムの復習をしつつ、以前買った競プロ本も進めていければなと思っている。