はじめに
今回はEまでコンテスト中に解けたのでそれをそのまま載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Leyland Number
問題文はこちら
for文で愚直に求めました。
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 ) {
//A、Bの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
//A^B
long ansA = 1;
for(int i=0;i<B;i++)
ansA *= A;
//B^A
long ansB = 1;
for(int i=0;i<A;i++)
ansB *= B;
//和を出力
out.println(ansA+ansB);
out.close();
}
}
まぁ難しくはないですね。
B - Longest Palindrome
問題文はこちら
始点と終点を二重for文で探索して求めました。
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 ) {
//Sの受け取り
String S = sc.next();
//最長の記録用
int ans = 1;
//始点
for(int l=0;l<S.length();l++)
//終点
for(int r=l+1;r<=S.length();r++)
//回文ならこの文字列の長さで最大値を更新
if(isPalindrome(S.substring(l,r)))
ans = Math.max(r-l,ans);
//最大値の出力
out.println(ans);
out.close();
}
//回文判定メソッド
private static boolean isPalindrome(String S){
return S.equals(new StringBuilder(S).reverse().toString());
}
}
最初始点は先頭固定なのかと勘違いして1ペナ出しました…悲しい…。
C - Slot Strategy 2 (Easy)
問題文はこちら
揃える数字と押す順番の順列全探索によって最小値を求めました。
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 ) {
//M、Sの受け取り
int M = sc.nextInt();
String[] S = sc.next(3);
//3つ繋げた文字列として扱った方が楽なのでrepeat(3)をしておく
for(int i=0;i<3;i++)
S[i] = S[i].repeat(3);
//最小値記録用
int ans = Integer.MAX_VALUE;
//揃える数字を全探索
for(int i=0;i<10;i++){
//順列全探索用配列
int[] map = new int[3];
Arrays.setAll(map,j->j);
//順列全探索
do{
//各Siの揃える数字のインデックスを探す
int t = -1;
for(int j=0;j<3;j++){
int next = S[map[j]].indexOf(""+i,t+1);
//もし見つからなかったら揃えられないのでtを大きめにしてforを抜ける
if(next==-1){
t = Integer.MAX_VALUE;
break;
}
t = next;
}
//この条件での最小値で答えを更新
ans = Math.min(ans,t);
}while(ArrayFunction.nextPermutation(map));
}
//一つも揃えられなかったら-1、一つでも揃えられたらansを出力
out.println(ans==Integer.MAX_VALUE?-1:ans);
out.close();
}
}
repeatメソッド使ったこと無かったので使ってみようかなと思って使いました。
D - Relative Position
問題文はこちら
人1から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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//隣接リストの構築(相対的な位置も持っておく)
ArrayList<ArrayList<int[]>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0){
int A = sc.nextInt();
int B = sc.nextInt();
int X = sc.nextInt();
int Y = sc.nextInt();
list.get(A).add(new int[]{B,X,Y});
list.get(B).add(new int[]{A,-X,-Y});
}
//各人の座標を管理する配列
long[][] point = new long[N+1][2];
//位置が求まったかどうか管理するboolean配列
boolean[] checked = new boolean[N+1];
checked[1] = true; //人1は位置が求まったとしておく
//BFS
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(1);
while(deq.size()>0){
int now = deq.pollFirst();
for(int[] next:list.get(now)){
if(checked[next[0]])
continue;
point[next[0]][0] = point[now][0]+next[1];
point[next[0]][1] = point[now][1]+next[2];
checked[next[0]] = true;
deq.add(next[0]);
}
}
//各人に対して、座標が確定してるならそれを、確定してないならundecidableを出力
for(int i=1;i<=N;i++)
out.println(checked[i]?point[i][0]+" "+point[i][1]:"undecidable");
out.close();
}
}
人1を探索済みにするのを忘れて2ペナも出してしまいました…詰めが甘過ぎる…。
E - Somen Nagashi
問題文はこちら
いつのそうめんが来るときまでに復帰できるかをArrayDequeにaddすることで記録しておき、そのそうめんが来るときにPriorityQueueに戻してあげることで答えを求めました。
E.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、M、T、W、Sの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] T = new int[M];
int[] W = new int[M];
int[] S = new int[M];
for(int i=0;i<M;i++){
T[i] = sc.nextInt();
W[i] = sc.nextInt();
S[i] = sc.nextInt();
}
//復活のタイミングを管理するList
ArrayList<ArrayDeque<Integer>> list = new ArrayList<>();
for(int i=0;i<=M;i++)
list.add(new ArrayDeque<>());
//今列にいる人を管理するPriorityQueue
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i=0;i<N;i++)
queue.add(i);
//各人の得たそうめんを管理する配列
long[] ans = new long[N];
//各そうめんに対して処理する
for(int i=0;i<M;i++){
//復帰する人がいればqueueに戻す
while(list.get(i).size()>0)
queue.add(list.get(i).poll());
//列に誰もいないならこのそうめんはスルー
if(queue.size()==0)
continue;
//一番先頭の人がこのそうめんを得る
int num = queue.poll();
ans[num] += W[i];
//どのそうめんまでには復帰するかを二分探索してその位置のDequeに追加
int index = Searcher.upSearch(T,T[i]+S[i]);
list.get(index).add(num);
}
//各人が得たそうめんの総量を改行区切りで出力
out.println(ans,"\n");
out.close();
}
}
これは割とすぐ解けた方かも。
感想
A,B,C,D:易しめ
E:Eにしては結構易しめ？
って感じでした。Eまでなら解けるって人にとっては速解き回って感じかも。
ペナが積もり積もって悲しい結果に…。