はじめに
今回はコンテスト中にDまで、コンテスト後にFまで解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Long Loong
問題文はこちら
oはrepeatメソッドで繰り返せるので、それを使って解きました。
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){
//Xの受け取り
int X = sc.nextInt();
//答えを構築して出力
out.println("L"+"o".repeat(X)+"ng");
out.close();
}
}
B - CTZ
問題文はこちら
JavaにはInteger::numberOfTrailingZerosでそのまま答えが求められるのでこれを使いました。
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の受け取り
int N = sc.nextInt();
//答えの出力
out.println(Integer.numberOfTrailingZeros(N));
out.close();
}
}
C - Even Digits
問題文はこちら
答えは5進数表記表記した数字を10進数として2倍した値と一致するので、一度5進数の文字列に変換した後に10進数として数値に変換して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の受け取り(0-indexedにするため-1)
long N = sc.nextLong()-1;
//5進数変換して10進数と解釈
long value = Long.parseLong(Long.toString(N,5));
//2倍して出力
System.out.println(value<<1);
out.close();
}
}
D - Pyramid
問題文はこちら
ちょっとごちゃごちゃ書いてしまいましたが、片側から見たときに山半分を作れる最大値を記録していき、それを元に尺取で解きました。
山の幅が奇数でなんかやりにくかったので、偶数番目と奇数番目で分けて解きました。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//後ろから見て構築できる最大の山半分を求める
int[] backFollow = new int[N];
int l = N-1;
for(int r=N-1;r>=0;r--){
while(0<=l&&r-l<A[l])
l--;
backFollow[r] = r-l;
}
//前からも
int[] frontFollow = new int[N];
int r = 0;
for(l=0;l<N;l++){
while(r<N&&r-l<A[r])
r++;
frontFollow[l] = r-l;
}
//偶奇で分けて答えを求める
int ans = 1;
r = 0;
for(l=0;l<N;l+=2){
while(r<N&&(r-l)/2<backFollow[r]&&(r-l)/2<=frontFollow[l])
r += 2;
ans = Math.max(ans,(r-l+1)/2);
}
r = 1;
for(l=1;l<N;l+=2){
while(r<N&&(r-l)/2<backFollow[r]&&(r-l)/2<=frontFollow[l])
r += 2;
ans = Math.max(ans,(r-l+1)/2);
}
out.println(ans);
out.close();
}
}
E - Digit Sum Divisible
問題文はこちら
公式解説の通りです。
E.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
public static void main(String[] args){
final Scanner sc = new Scanner(System.in);
//Nの受け取り
final String N = sc.next();
//桁数を別変数に
final int len = N.length();
long ans = 0;
//高速化のために配列使い回し
long[][] dp1 = new long[len*9+1][len*9];
long[][] dp2 = new long[len*9+1][len*9];
long[][] next1 = new long[len*9+1][len*9];
long[][] next2 = new long[len*9+1][len*9];
//遷移
for(int s=1;s<=len*9;s++){
for(final long[] temp:dp1)
Arrays.fill(temp,0);
for(final long[] temp:dp2)
Arrays.fill(temp,0);
dp2[0][0] = 1;
for(char c:N.toCharArray()){
for(final long[] temp:next1)
Arrays.fill(temp,0);
for(final long[] temp:next2)
Arrays.fill(temp,0);
final int nextValue = c-'0';
for(int j=0;j<=len*9;j++){
for(int k=0;k<len*9;k++){
final long val1 = dp1[j][k];
final long val2 = dp2[j][k];
if(val1>0){
final int max1 = Math.min(len*9-j+1,10);
for(int i=0;i<max1;i++)
next1[i+j][(k*10+i)%s] += val1;
}
if(val2>0){
final int max2 = Math.min(len*9-j+1,nextValue);
for(int i=0;i<max2;i++)
next1[i+j][(k*10+i)%s] += val2;
}
}
}
for(int i=0;i+c-'0'<=len*9;i++){
for(int j=0;j<len*9;j++){
next2[i+nextValue][(j*10+nextValue)%s] += dp2[i][j];
}
}
long[][] temp = dp1;
dp1 = next1;
next1 = temp;
temp = dp2;
dp2 = next2;
next2 = temp;
}
ans += dp1[s][0]+dp2[s][0];
}
//数え上げた答えを出力
System.out.println(ans);
}
}
む～ん…桁DPなんだろうなくらいにしか思えず、それ以上の進展が無かった…。
F - Rotation Puzzle
問題文はこちら
ほとんど公式解説の通りですが、高速化がそこまで行なわれていませんので、実行時間が結構ギリギリです。
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){
//H、W、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int[][] S = sc.nextInt(H,W);
//状態を保持するクラス
class Node{
int[][] map;
int hash;
BigInteger bigHash;
Node(int[][] m){
map = m;
hash = 0;
bigHash = BigInteger.ZERO;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
hash = hash*(H*W+1)+map[i][j];
bigHash = bigHash.shiftLeft(7).or(BigInteger.valueOf(map[i][j]));
}
}
}
@Override
public int hashCode(){
return hash;
}
@Override
public boolean equals(Object o){
if(o instanceof Node n){
return bigHash.equals(n.bigHash);
}
return false;
}
}
//作りたい最終形を構築しておく
int[][] origin = new int[H][W];
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
origin[i][j] = i*W+j+1;
//最終形から逆算
HashMap<Node,Integer> map = new HashMap<>();
map.put(new Node(origin),0);
ArrayDeque<Node> deq = new ArrayDeque<>();
deq.add(new Node(origin));
for(int s=1;s<=10;s++){
ArrayDeque<Node> next = new ArrayDeque<>();
while(deq.size()>0){
Node now = deq.pollFirst();
int[][] next1 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next1[i][j] = now.map[H-i-2][W-j-2];
for(int i=0;i<H;i++)
next1[i][W-1] = now.map[i][W-1];
for(int i=0;i<W;i++)
next1[H-1][i] = now.map[H-1][i];
if(map.putIfAbsent(new Node(next1),s)==null)
next.add(new Node(next1));
int[][] next2 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next2[i][j+1] = now.map[H-i-2][W-j-1];
for(int i=0;i<H;i++)
next2[i][0] = now.map[i][0];
for(int i=0;i<W;i++)
next2[H-1][i] = now.map[H-1][i];
if(map.putIfAbsent(new Node(next2),s)==null)
next.add(new Node(next2));
int[][] next3 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next3[i+1][j] = now.map[H-i-1][W-j-2];
for(int i=0;i<H;i++)
next3[i][W-1] = now.map[i][W-1];
for(int i=0;i<W;i++)
next3[0][i] = now.map[0][i];
if(map.putIfAbsent(new Node(next3),s)==null)
next.add(new Node(next3));
int[][] next4 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next4[i+1][j+1] = now.map[H-i-1][W-j-1];
for(int i=0;i<H;i++)
next4[i][0] = now.map[i][0];
for(int i=0;i<W;i++)
next4[0][i] = now.map[0][i];
if(map.putIfAbsent(new Node(next4),s)==null)
next.add(new Node(next4));
}
deq = next;
}
//今の状態からも遷移
deq = new ArrayDeque<>();
HashMap<Node,Integer> map2 = new HashMap<>();
map2.put(new Node(S),0);
deq.add(new Node(S));
for(int s=1;s<=10;s++){
ArrayDeque<Node> next = new ArrayDeque<>();
while(deq.size()>0){
Node now = deq.pollFirst();
int[][] next1 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next1[i][j] = now.map[H-i-2][W-j-2];
for(int i=0;i<H;i++)
next1[i][W-1] = now.map[i][W-1];
for(int i=0;i<W;i++)
next1[H-1][i] = now.map[H-1][i];
if(map2.putIfAbsent(new Node(next1),s)==null)
next.add(new Node(next1));
int[][] next2 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next2[i][j+1] = now.map[H-i-2][W-j-1];
for(int i=0;i<H;i++)
next2[i][0] = now.map[i][0];
for(int i=0;i<W;i++)
next2[H-1][i] = now.map[H-1][i];
if(map2.putIfAbsent(new Node(next2),s)==null)
next.add(new Node(next2));
int[][] next3 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next3[i+1][j] = now.map[H-i-1][W-j-2];
for(int i=0;i<H;i++)
next3[i][W-1] = now.map[i][W-1];
for(int i=0;i<W;i++)
next3[0][i] = now.map[0][i];
if(map2.putIfAbsent(new Node(next3),s)==null)
next.add(new Node(next3));
int[][] next4 = new int[H][W];
for(int i=0;i<H-1;i++)
for(int j=0;j<W-1;j++)
next4[i+1][j+1] = now.map[H-i-1][W-j-1];
for(int i=0;i<H;i++)
next4[i][0] = now.map[i][0];
for(int i=0;i<W;i++)
next4[0][i] = now.map[0][i];
if(map2.putIfAbsent(new Node(next4),s)==null)
next.add(new Node(next4));
}
deq = next;
}
//半分全列挙が出来ているので答えをもとめｒ
int min = 21;
for(Entry<Node,Integer> entry:map.entrySet())
min = Math.min(map2.getOrDefault(entry.getKey(),21)+entry.getValue(),min);
out.println(min<21?min:-1);
out.close();
}
}
気づけないなぁ…。
感想
A,B,C:これらはライブラリでどうとでもなったので良かった
D:かなり手こずった…
E:遷移ミスって地獄
F:何も見えてこなかった…
って感じでした。
う～ん…ダメダメ過ぎる…。