はじめに
今回はFまで解けたのでそれを載せようと思います。
では見ていきましょう。
A - Attack
問題文はこちら
$\lceil \frac{A}{B} \rceil$が答えですね。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//A、Bの受け取り
long A = sc.nextLong();
long B = sc.nextLong();
//切りあげ
out.println((A+B-1)/B);
out.close();
}
}
A問題で、intで扱えない問題に遭遇した記憶が無かったのでびっくりしました。
B - Find snuke
問題文はこちら
愚直に探しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//H、W、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
char[][] S = sc.nextCharArray(H);
//答えを入れるようの配列
int[][] ans = new int[5][2];
String snuke = "snuke";
Search:for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
//右
if(j<W-4){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i][j+k];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i+1,j+2};
ans[2] = new int[]{i+1,j+3};
ans[3] = new int[]{i+1,j+4};
ans[4] = new int[]{i+1,j+5};
break Search;
}
}
//下
if(i<H-4){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i+k][j];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i+2,j+1};
ans[2] = new int[]{i+3,j+1};
ans[3] = new int[]{i+4,j+1};
ans[4] = new int[]{i+5,j+1};
break Search;
}
}
//右下
if(i<H-4&&j<W-4){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i+k][j+k];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i+2,j+2};
ans[2] = new int[]{i+3,j+3};
ans[3] = new int[]{i+4,j+4};
ans[4] = new int[]{i+5,j+5};
break Search;
}
}
//左
if(3<j){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i][j-k];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i+1,j};
ans[2] = new int[]{i+1,j-1};
ans[3] = new int[]{i+1,j-2};
ans[4] = new int[]{i+1,j-3};
break Search;
}
}
//上
if(3<i){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i-k][j];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i,j+1};
ans[2] = new int[]{i-1,j+1};
ans[3] = new int[]{i-2,j+1};
ans[4] = new int[]{i-3,j+1};
break Search;
}
}
//左上
if(3<i&&3<j){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i-k][j-k];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i,j};
ans[2] = new int[]{i-1,j-1};
ans[3] = new int[]{i-2,j-2};
ans[4] = new int[]{i-3,j-3};
break Search;
}
}
//左下
if(i<H-4&&3<j){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i+k][j-k];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i+2,j};
ans[2] = new int[]{i+3,j-1};
ans[3] = new int[]{i+4,j-2};
ans[4] = new int[]{i+5,j-3};
break Search;
}
}
//右上
if(3<i&&j<W-4){
boolean isSnuke = true;
for(int k=0;k<5;k++)
isSnuke &= snuke.charAt(k)==S[i-k][j+k];
if(isSnuke){
ans[0] = new int[]{i+1,j+1};
ans[1] = new int[]{i,j+2};
ans[2] = new int[]{i-1,j+3};
ans[3] = new int[]{i-2,j+4};
ans[4] = new int[]{i-3,j+5};
break Search;
}
}
}
}
//全探索で見つかったものを出力
out.println(ans);
out.close();
}
}
8方向全部書くのを忘れてペナルティを頂いてしまいました…。
C - Almost Equal
問題文はこちら
全探索しました。
C++のnext_permutationに相当するものがないのでそれっぽいメソッド作って実装しました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、Sの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
String[] S = sc.next(N);
//順列の準備
int[] perm = new int[N];
Arrays.setAll(perm,i->i);
//良い並べ替えが存在するか
boolean canSort = false;
//全探索
do{
boolean allGood = true;
for(int i=1;i<N;i++){
int count = 0;
for(int j=0;j<M;j++)
if(S[perm[i]].charAt(j)!=S[perm[i-1]].charAt(j))
count++;
allGood &= count<2;
}
canSort |= allGood;
}while(nextP(perm));
//見つかった？
out.println(canSort?"Yes":"No");
out.close();
}
//next_permutation相当のメソッド
private static boolean nextP(int[] array){
int index = -1;
for(int i=1;i<array.length;i++){
if(array[i-1]<array[i])
index = i-1;
}
if(index==-1)
return false;
int[] arr = new int[array.length-index];
System.arraycopy(array,index,arr,0,arr.length);
ArrayFunction.sort(arr);
int index2 = Searcher.overSearch(arr,array[index]);
array[index] = arr[index2];
int index3 = index+1;
for(int i=0;i<arr.length;i++){
if(i==index2)
continue;
array[index3++] = arr[i];
}
return true;
}
}
ミスってないか不安でしたが通って良かったです。
D - Impartial Gift
問題文はこちら
$A$、$B$共にソートして大きい方から見て答えを探しました。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、D、A、Bの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long D = sc.nextLong();
long[] A = sc.nextLong(N);
long[] B = sc.nextLong(M);
//ソート
ArrayFunction.sort(A);
ArrayFunction.sort(B);
//後ろから見ていく
int indexA = N-1;
int indexB = M-1;
while(0<=indexA&&0<=indexB&&Math.abs(A[indexA]-B[indexB])>D){
if(A[indexA]>B[indexB])
indexA--;
else
indexB--;
}
//解があったらそれを、無ければ-1
out.println(0<=indexA&&0<=indexB?A[indexA]+B[indexB]:-1);
out.close();
}
}
これは比較的速く解けました。
E - Isolation
問題文はこちら
直接結ばれている頂点のみを保持していれば良いので、ArrayList<TreeSet<Integer>>で保持してシミュレーションしました。
E.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//直接結ばれている頂点を管理する用
ArrayList<TreeSet<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new TreeSet<>());
//現状の答え
int ans = N;
while(Q-->0){
int q = sc.nextInt();
//クエリ1
if(q==1){
//u、vの受け取り
int u = sc.nextInt();
int v = sc.nextInt();
//答えから引く
if(list.get(u).size()==0)
ans--;
list.get(u).add(v);
if(list.get(v).size()==0)
ans--;
list.get(v).add(u);
}
//クエリ2
else{
//vの受け取り
int v = sc.nextInt();
//各辺を取り除く
for(int p:list.get(v)){
list.get(p).remove(v);
if(list.get(p).size()==0)
ans++;
}
//辺が元々あったら答えに加算する
if(list.get(v).size()>0)
ans++;
list.get(v).clear();
}
//現状の答えを出力
out.println(ans);
}
out.close();
}
}
Eにしては簡単…？
F - Merge Set
問題文はこちら
数字と集合それぞれを頂点としてみて、集合とその集合に含まれている要素に対して辺を貼ってDijkstra法で答えを求めました。
F.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//隣接リストの構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=M;i++)
list.add(new ArrayList<>());
for(int i=0;i<N;i++){
int A = sc.nextInt();
ArrayList<Integer> temp = new ArrayList<>();
while(A-->0)
temp.add(sc.nextInt());
for(int num:temp)
list.get(num).add(i+M+1);
list.add(temp);
}
//Dijkstra
PriorityQueue<Pair<Integer,Integer>> queue = new PriorityQueue<>(
(p1,p2)->Integer.compare(p1.getValue(),p2.getValue()));
queue.add(new Pair<>(1,0));
int[] costs = new int[N+M+2];
Arrays.fill(costs,Integer.MAX_VALUE);
costs[1] = 0;
while(queue.size()>0){
Pair<Integer,Integer> pair = queue.poll();
int now = pair.getKey();
int cost = pair.getValue();
if(now==M){
//途中で答えが見つかれば出力して終了
System.out.println(cost-1);
return;
}
for(int nextP:list.get(now)){
int nextC = cost;
if(nextP>M)
nextC++;
if(costs[nextP]>nextC){
costs[nextP] = nextC;
queue.add(new Pair<>(nextP,nextC));
}
}
}
//答えが見つからなかったのなら1->Mは不可
out.println(-1);
out.close();
}
}
思っていたよりもサクッと解けました。
感想
A:易しい
B:結構沼った…
C:ちょっと重いなと思ったけど比較的簡単
D,E:比較的易しい
F:最初UnionFindとかを考えたおかげでグラフ問題だと早めに気づけた
って感じでした。
普段もFまで解ければ苦労しないんですけどね…維持できるよう頑張ります。