はじめに
今回はEまでコンテスト中に解けたのでそれをそのまま載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Same
問題文はこちら
$A_1$と全要素を比較して判定しました。
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、A_1の受け取り
int N = sc.nextInt();
int A = sc.nextInt();
//A_2以降がA_1と等しいか調べる
while(--N>0){
int a = sc.nextInt();
//値が違うならNoを出力して終了
if(A!=a){
System.out.println("No");
return;
}
}
//ループを抜けた=全部等しいのでYes
out.println("Yes");
out.close();
}
}
$A$を事前にソートして$A_1=A_N$で判定する方が楽でしたね。
A改.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Aの受け取り(Aはソートする)
int N = sc.nextInt();
int[] A = new int[N];
Arrays.setAll(A,i->sc.nextInt());
Arrays.sort(A);
//先頭と末尾が等しいなら全部等しいのでYes
System.out.println(A[0]==A[N-1]?"Yes":"No");
}
}
B - 3-smooth Numbers
問題文はこちら
$2$、$3$で割れるだけ割って$1$になるかで判定しました。
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の受け取り
long N = sc.nextLong();
//2、3で割れるだけ割る
while(N%3==0)
N /= 3;
while(N%2==0)
N /= 2;
//1になったらYes、違うならNoを出力
out.println(N==1?"Yes":"No");
out.close();
}
}
まぁ易しめですね。
C - Error Correction
問題文はこちら
問題文の通りに実装しました。
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、T'の受け取り
int N = sc.nextInt();
String T = sc.next();
//答えを保持するList
ArrayList<Integer> list = new ArrayList<>();
//先頭から調べて行く
Loop:for(int i=1;i<=N;i++){
//Sの受け取り
String S = sc.next();
//文字列の長さの差が2以上なら条件を満たさないのでスルー
if(Math.abs(S.length()-T.length())>1){
continue;
}
//Sの方が長いならTを部分列として持っているか調べる
if(S.length()==T.length()+1){
int index = 0;
for(int j=0;j<T.length();j++){
while(index<S.length()&&S.charAt(index)!=T.charAt(j))
index++;
index++;
if(index>S.length()){
continue Loop;
}
}
list.add(i);
}
//Tの方が長いならSを部分列として持っているか調べる
else if(S.length()+1==T.length()){
int index = 0;
for(int j=0;j<S.length();j++){
while(index<T.length()&&S.charAt(j)!=T.charAt(index))
index++;
index++;
if(index>T.length()){
continue Loop;
}
}
list.add(i);
}
//長さが等しいなら不一致の数が1以下か調べる
else{
int count = 0;
for(int j=0;j<S.length();j++)
if(S.charAt(j)!=T.charAt(j))
count++;
if(count<2)
list.add(i);
}
}
//候補の数を出力
out.println(list.size());
//候補が存在するならそれを空白区切りで出力
if(list.size()>0){
out.print(list.get(0));
for(int i=1;i<list.size();i++)
out.print(" "+list.get(i));
out.println();
}
out.close();
}
}
ちょっとめんどくさかったですが特に苦戦はしませんでした。
D - Square Permutation
問題文はこちら
$N$の最大値から作れる平方数は$10^{13}$未満なので、$S$を並べ替えて作れる最大値を$K$として$i=1～\sqrt{K}$について、$i^2$が作れるかを判定することで解きました。
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の受け取り
int N = sc.nextInt();
char[] S = sc.nextCharArray();
//Sで作れる最大値を求めておく(M)
Arrays.sort(S);
String subS = Converter.reverse(new String(S));
long M = Long.parseLong(subS);
//各数字の個数を求める
int[] count = new int[10];
for(char c:S)
count[c-'0']++;
//作れる総数を求めるための変数
int ans = 0;
//√Mまで全探索
Loop:for(long x=0;x*x<=M;x++){
//x^2の各桁の数字をバケットに入れる
int[] sum = new int[10];
for(char c:Long.toString(x*x).toCharArray())
sum[c-'0']++;
//1～9の数が一致しているか調べる
for(int i=1;i<10;i++)
if(count[i]!=sum[i])
continue Loop;
//0の個数は超えてさえ無ければ良いので<=で判定
if(sum[0]<=count[0])
ans++;
}
//総数を出力
out.println(ans);
out.close();
}
}
割と早めに気づけたので良かったです。
E - Joint Two Strings
問題文はこちら
$S_i$について、先頭から何文字目まで作れるか、末尾から何文字目まで作れるかを求め、$j$文字以上作れる$S_i$の総数を$\mathrm{sum}[j]$として累積和を取り、$S_i$に対して、自分の後ろに連結すると$T$を作れる個数を$O(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 );
public static void main ( String[] args ) {
//N、Tの受け取り
int N = sc.nextInt();
String T = sc.next();
//count[i][j]:j文字目まで作れる個数(i=0なら先頭から、j=1なら末尾から)
int[][] count = new int[2][T.length()+1];
//len[i][j]:S_jが作れる長さ(i=0なら先頭から、j=1なら末尾から)
int[][] len = new int[2][N];
for(int i=0;i<N;i++){
//Sの受け取り
String S = sc.next();
//先頭から何文字目まで作れるか調べる
int index = 0;
for(char c:S.toCharArray())
if(index<T.length()&&T.charAt(index)==c)
index++;
//記録
count[0][index]++;
len[0][i] = index;
//Sを前後ひっくり返して、末尾から何文字作れるか調べる
S = Converter.reverse(S);
index = 0;
for(char c:S.toCharArray())
if(index<T.length()&&T.charAt(T.length()-index-1)==c)
index++;
//記録
count[1][index]++;
len[1][i] = index;
}
//累積和を取る
for(int i=T.length();i>0;i--){
count[0][i-1] += count[0][i];
count[1][i-1] += count[1][i];
}
//Tが作れる組み合わせの総数を求める
long ans = 0;
for(int i=0;i<N;i++){
ans += count[1][T.length()-len[0][i]];
}
//答えの出力
out.println(ans);
out.close();
}
}
実装に手間取ってしまいました…。悲しい…。
感想
A,B:易しい
C:ちょっと大変だけどまだ易しい方
D:そんなに悩まなかった
E:気づきは早かったけど実装に時間をかけてしまった…
って感じでした。
悪くはないけど…って感じの結果でした。もうちょっと速く解けるようになりたいです。