はじめに
今回はコンテスト中に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:キツい
って感じでした。
いやぁ…めちゃくちゃ苦手セットでした…あまりにも下手くそ…。