はじめに
今回はコンテスト中にFまで解けたのでそれをそのまま載せようと思います。
なお、僕のライブラリはGitHubのものをご確認下さい。
では、見ていきましょう。
A - Piling Up
問題文はこちら
答えは$\lfloor\frac{R+100}{100}\rfloor\times100-R$で求まるのでこれを実装しました。
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){
//Rの受け取り
int R = sc.nextInt();
//上記の式の実装
out.println((R+100)/100*100-R);
out.close();
}
}
B - Japanese Cursed Doll
問題文はこちら
制約上愚直にシミュレーションして探索しても十分高速に求まるのでそれを実装しました。
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){
//N、T、P、Lの受け取り
int N = sc.nextInt();
int T = sc.nextInt();
int P = sc.nextInt();
int[] L = sc.nextInt(N);
//愚直に1日ずつ増やしてシミュレーション
int ans = 0;
do{
int count = 0;
for(int l:L)
if(l+ans>=T)
count++;
if(count>=P){
out.println(ans);
break;
}
ans++;
}while(true);
out.close();
}
}
C - Avoid K Palindrome 2
問題文はこちら
制約が十分小さいので順列全探索で全組み合わせの文字を構築しながら条件を満たしているか判定して解きました。
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、Sの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
char[] S = sc.nextCharArray();
//順列全探索
Arrays.sort(S);
int ans = 0;
Loop:do{
for(int i=0;i<=N-K;i++){
boolean check = true;
for(int j=0;j<K;j++)
check &= S[i+j]==S[i+K-j-1];
if(check)
continue Loop;
}
ans++;
}while(ArrayUtil.nextPermutation(S));
//答えの出力
out.println(ans);
out.close();
}
}
D - Palindromic Number
問題文はこちら
何桁かは高速に求められるので事前に求めておき、回文数は上位半分だけで全体が求まるのでそれを元に目的の値を構築しました。
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の受け取り
long N = sc.nextLong();
//先に簡単に求まるものは求める
if(N<=10){
System.out.println(N-1);
return;
}
//桁を調べる
long sum = 0;
int len = 0;
while(sum<N)
sum += count(++len);
sum -= count(len);
//偶数桁か奇数桁かで場合分けして求める
if(len%2==0){
long num = N-sum+MathFunction.pow(10,len/2-1)-1;
String S = ""+num;
out.println(S+Converter.reverse(S));
}
else{
long num = (N-sum-1)/10+MathFunction.pow(10,len/2-1);
long r = (N-sum-1)%10;
String S = ""+num;
out.println(S+r+Converter.reverse(S));
}
out.close();
}
//指定された桁数の回文数の個数を返すメソッドメソッド
private static long count(int len){
if(len==0)
return 1;
if(len%2==0)
return MathFunction.pow(10,len/2)-MathFunction.pow(10,len/2-1);
return count(len-1)*10;
}
}
E - Sinking Land
問題文はこちら
現時点で海に面しているマスを予めPriorityQueueで管理することで1年ずつシミュレーションしながら解を求めました。
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);
private static final int[] dx = {1,-1,0,0};
private static final int[] dy = {0,0,1,-1};
public static void main(String[] args){
//H、W、Y、Aの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int Y = sc.nextInt();
int[][] A = sc.nextInt(H,W);
//海に面しているマスを記録
PriorityQueue<Point> queue = new PriorityQueue<>((a,b)->Integer.compare(A[a.x][a.y],A[b.x][b.y]));
boolean[][] checked = new boolean[H][W];
for(int i=0;i<H;i++){
checked[i][0] = true;
checked[i][W-1] = true;
queue.add(new Point(i,0));
if(W>1)
queue.add(new Point(i,W-1));
}
for(int i=1;i<W-1;i++){
checked[0][i] = true;
checked[H-1][i] = true;
queue.add(new Point(0,i));
if(H>1)
queue.add(new Point(H-1,i));
}
//1年ずつシミュレーション
int ans = H*W;
for(int y=1;y<=Y;y++){
while(queue.size()>0){
Point p = queue.poll();
if(A[p.x][p.y]<=y){
ans--;
for(int i=0;i<4;i++){
int nx = p.x+dx[i];
int ny = p.y+dy[i];
if(MathFunction.rangeCheck(nx,0,H)&&MathFunction.rangeCheck(ny,0,W))
if(!checked[nx][ny]){
checked[nx][ny] = true;
queue.add(new Point(nx,ny));
}
}
}
else{
queue.add(p);
break;
}
}
out.println(ans);
}
out.close();
}
}
F - Palindromic Expression
問題文はこちら
数字に関しては$N$の約数のみチェックすればよく、反転したものが$N$を自身で割ったものの約数になっているもののみについて探索をすれば良いので、そんなに多く再帰することは無いと思い、そのまま実装してみました。
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);
//答えを記録する用のArrayList
private static final ArrayList<Long> ans = new ArrayList<>();
public static void main(String[] args){
//Nの受け取り
long N = sc.nextLong();
//解が構築できたらそれぞれの数字を*で連結して出力
if(dfs(N)){
StringBuilder answer = new StringBuilder();
long sub = 1;
for(int i=0;i<ans.size()-1;i++){
sub *= ans.get(i);
sub *= Long.parseLong(Converter.reverse(""+ans.get(i)));
answer.append(ans.get(i));
answer.append("*");
}
if(sub*ans.get(ans.size()-1)<N){
answer.append(ans.get(ans.size()-1));
answer.append("*");
}
for(int i=ans.size()-1;i>=0;i--){
answer.append(Converter.reverse(""+ans.get(i)));
if(i>0)
answer.append("*");
}
out.println(answer);
}
else
out.println(-1);
out.close();
}
//再帰探索用
public static boolean dfs(long N){
//自身がSの中心になり得るか調べる
String S = ""+N;
if(check(N)&&isGood(S)){
ans.add(N);
return true;
}
else{
//自身と反転したものでNが割り切れるときのみ再帰的に探索
for(long n=2;n*n<=N;n++){
long rn = Long.parseLong(Converter.reverse(""+n));
if(N%(n*rn)==0&&check(n)&&check(rn)){
ans.add(n);
if(dfs(N/n/rn))
return true;
ans.remove(ans.size()-1);
}
}
}
return false;
}
//回文か調べるメソッド
public static boolean isGood(String S){
int l = 0;
int r = S.length();
while(l<r)
if(S.charAt(l++)!=S.charAt(--r))
return false;
return true;
}
//0が含まれていないか調べるめそっど
public static boolean check(long n){
while(n>1){
if(n%10==0)
return false;
n /= 10;
}
return true;
}
}
予想が当たって良かったです。
感想
A,B,C:易しい
D:ちょっと時間かかっちゃった…
E:Eにしては易しめ？
F:メモ化再帰しても良かったな…
って感じでした。
初カンストパフォで嬉しくなっております。