はじめに

今回はコンテスト中にDまで、コンテスト後にFが解けたのでそれを載せようと思います。

なお、僕のライブラリはGitHubよりご確認ください。
では、見ていきましょう。

A - Insert

問題文はこちら

挿入位置手前までを受け取って出力し、挿入したい値を出力、あとは残りの配列を受け取って出力しました。

A.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//N、K、Xの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();
		int X = sc.nextInt();

  		//先頭K個と末尾N-K個を別々に受け取る
		int[] fA = sc.nextInt(K);
		int[] lA = sc.nextInt(N-K);

  		//先頭K個、X、末尾N-K個の順に出力する
		out.print(fA);
		out.print(" "+X+" ");
		out.println(lA);

		out.close();
	}
}

B - Intersection of Cuboids

問題文はこちら

共通部分がある場合、$x$の範囲、$y$の範囲、$z$の範囲全てで共通部分があるので、それを判定しました。

B.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//入力の受け取り
		int[] cube1 = sc.nextInt(6);
		int[] cube2 = sc.nextInt(6);

  		//全成分の区間に共通部分があるか調べる
		if(
			(MathFunction.rangeCheck(cube2[0],cube1[0],cube1[3])||MathFunction.rangeCheck(cube1[0],cube2[0],cube2[3]))&&
			(MathFunction.rangeCheck(cube2[1],cube1[1],cube1[4])||MathFunction.rangeCheck(cube1[1],cube2[1],cube2[4]))&&
			(MathFunction.rangeCheck(cube2[2],cube1[2],cube1[5])||MathFunction.rangeCheck(cube1[2],cube2[2],cube2[5]))
		){
			out.println("Yes");
		}
		else{
			out.println("No");
		}

		out.close();
	}
}

C - Make Them Narrow

問題文はこちら

最大、最小にしか興味がないので順序は関係無いです。なので、事前に$A$をソートし、$\min(A_{i+N-K-1}-A_i)$を求めれば良いです。

C.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//N、K、Aの受け取り
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] A = sc.nextInt(N);

  		//ソート
		Arrays.sort(A);

  		//最小値を求める
		int min = Integer.MAX_VALUE;
		for(int i=0;i<=K;i++){
			min = Math.min(min,A[i+N-K-1]-A[i]);
		}

  		//答えの出力
		out.println(min);

		out.close();
	}
}

D - Go Stone Puzzle

問題文はこちら

通り数がそんなに多くないので、BFSを用いて取り得る全通りへの最小操作回数を求め、解を求めました。

D.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//N、S、Tの受け取り(空きマスの代わりとして?を追加)
		int N = sc.nextInt();
		String S = sc.next()+"??";
		String T = sc.next()+"??";

  		//BFS
		HashMap<String,Integer> map = new HashMap<>();
		map.put(S,0);
		ArrayDeque<String> deq = new ArrayDeque<>();
		deq.add(S);
		int nowC = 0;
		while(deq.size()>0){
			nowC++;
			ArrayDeque<String> next = new ArrayDeque<>();
			for(String now:deq){
				int index = 0;
				while(now.charAt(index)!='?')
					index++;
				for(int i=0;i<now.length()-1;i++){
					if(now.charAt(i)=='?'||i+1==index)
						continue;
					String nS;
					if(i<index)
						nS = now.substring(0,i)+"??"+now.substring(i+2,index)+now.substring(i,i+2)+now.substring(index+2);
					else
						nS = now.substring(0,index)+now.substring(i,i+2)+now.substring(index+2,i)+"??"+now.substring(i+2);
					if(!map.containsKey(nS)){
						map.put(nS,nowC);
						next.add(nS);
					}
				}
			}
			deq = next;
		}

  		//答えの出力
		out.println(map.getOrDefault(T,-1));

		out.close();
	}
}

F - x = a^b

問題文はこちら

$b$を固定して$a$の個数を数えたとき、$b$は高々60程度までしか考えなくてよく、かつ$b$が素数である場合のみ考えれば良いです。例えば、$b=6$のとき、$a=13$が解の一つであった場合、$b=2$のときの$a=13^3$、$b=3$のときの$a=13^2$と重複してしまいます。これは$b$が合成数のときの$a$全てにおいて同様のことが言え、探索しても問題はないですが無駄なので今回は省きます。さて、$2 \lt b$のときを考えてみると、入力例$2$からもわかる通り、そんなに通り数は多くないです。なので、$2 \lt b$においてはHashSet<Long>を用いて愚直に列挙しても十分高速です(実装では$b=2$で表現できないもののみを列挙しています)。あとは$b=2$のときのあり得る$a$は$1$以上$\lfloor \sqrt{N} \rfloor$以下なので、HashSet<Long>の要素数に$\lfloor \sqrt{N} \rfloor$を加算してあげれば目的の解が得られます。

F.java

final class Main{
	private static final boolean autoFlush = false;
	private static final SimpleScanner sc = new SimpleScanner(System.in);
	private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);

	public static void main(String[] args){

		//60以下の素数を予め求める
		final int[] p = MathFunction.primes(60);

  		//平方数は省きたいので事前に求めておく
		final BitSet isSquare = new BitSet(1_000_002);
		for(int i=2;i<=1000;i++)
			isSquare.set(i*i);

   		//Nの受け取り
		final long N = sc.nextLong();

  		//2<bで全列挙
		HashSet<Long> set = new HashSet<>();
		for(int i=p.length-1;i>0;i--){
			long t;
			for(int j=2;(t=pow(j,p[i]))<=N;j=isSquare.nextClearBit(j+1))
				set.add(t);
		}

  		//b=2におけるaの通り数を求める
		long ans = (long)Math.sqrt(N);
		if(N<ans*ans)
			ans--;

   		//答えの出力
		out.println(ans+set.size());

		out.close();
	}

 	//オーバーフローとpowの誤差が怖いので、ザックリlongの範囲に収まるように処理
	private static long pow(final long a,final long b){
		if(Long.MAX_VALUE<=Math.pow(a,b))
			return Long.MAX_VALUE;
		return MathFunction.pow(a,b);
	}
}

コンテスト中に間に合わなかった…キツい…。

感想

A:易しい
B:ちょっと実装に迷った
C:誤読してちょっと時間食った…
D:易しめ
F:キツい
って感じでした。

いやぁ…めちゃくちゃ苦手セットでした…あまりにも下手くそ…。