はじめに
今回はコンテスト中にEまで、コンテスト後にFが解けたのでそれを載せようと思います。
なお、僕のライブラリはGitHubよりご確認ください。
では、見ていきましょう。
A - Shout Everyday
問題文はこちら
$B$を基準に$A$、$C$を調整後$B<A<C$かを判定することで求めました。
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){
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
if(C<B)
C += 24;
if(A<B)
A += 24;
out.println(MathFunction.rangeCheckClose(A,B,C)?"No":"Yes");
out.close();
}
}
B - Cut .0
問題文はこちら
末尾の0を愚直に取り除いた後、末尾が.ならついでにそれも取り除いて出力することで解きました。
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){
String X = sc.next();
while(X.charAt(X.length()-1)=='0')
X = X.substring(0,X.length()-1);
if(X.charAt(X.length()-1)=='.')
X = X.substring(0,X.length()-1);
out.println(X);
out.close();
}
}
C - Enumerate Sequences
問題文はこちら
愚直に調べても制約上そこまで計算量が大きくならないので再帰関数を使って求めました。
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);
private static final ArrayList<int[]> answer = new ArrayList<>();
public static void main(String[] args){
int N = sc.nextInt();
int K = sc.nextInt();
int[] R = sc.nextInt(N);
dfs(0,0,K,R,new int[N]);
for(int[] ans:answer)
out.println(ans);
out.close();
}
private static void dfs(int now,int sum,int K,int[] R,int[] ans){
if(now==R.length){
if(sum%K==0)
answer.add(ans.clone());
return;
}
for(int i=1;i<=R[now];i++){
ans[now] = i;
dfs(now+1,sum+i,K,R,ans);
}
}
}
D - Pedometer
問題文はこちら
事前に休憩所1からの距離を$M$で割った余りを求めておき、それをHashMap内で個数を管理し、開始点をずらしながら$M$の倍数になる個数を数え上げました。
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){
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
HashMap<Long,Integer> map = new HashMap<>();
map.put(0L,1);
long now = 0;
for(int i=0;i<N-1;i++){
now += A[i];
map.merge(now%M,1,Integer::sum);
}
long ans = 0;
long sum = 0;
for(int i=0;i<N;i++){
map.merge(sum%M,-1,Integer::sum);
ans += map.get(sum%M);
sum += A[i];
now += A[i==0?N-1:i-1];
map.merge(now%M,1,Integer::sum);
}
out.println(ans);
out.close();
}
}
実装が汚い…もっと良い書き方があるかも…。
E - Permute K times
問題文はこちら
移動の仕方は固定なので、ダブリングを用いることで$2^i(0 \le i)$回移動したときの移動先を事前に求められ、あとは$K$に合わせて遷移すれば良いです。
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){
int N = sc.nextInt();
long K = sc.nextLong();
int[] X = sc.nextInt(N);
int[] A = sc.nextInt(N);
int[][] dp = new int[61][N];
dp[0] = X.clone();
for(int i=1;i<61;i++){
int[] nextX = new int[N];
for(int j=0;j<N;j++)
nextX[j] = dp[i][j] = X[X[j]-1];
X = nextX;
}
int index = 0;
while(K>0){
if((K&1)>0){
int[] nextA = new int[N];
for(int i=0;i<N;i++)
nextA[i] = A[dp[index][i]-1];
A = nextA;
}
K >>= 1;
index++;
}
out.println(A);
out.close();
}
}
F - Rearrange Query
問題文はこちら
並び順はどうだってよく、各値の存在判定さえできれば良いので、Zobrist Hashを用いることで確率的に高速に判定することができます。
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){
int N = sc.nextInt();
int Q = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(N);
long[] hashA = new long[N+1];
for(int i=1;i<=N;i++)
hashA[i] = hashA[i-1]+hash(A[i-1]);
long[] hashB = new long[N+1];
for(int i=1;i<=N;i++)
hashB[i] = hashB[i-1]+hash(B[i-1]);
while(Q-->0){
int l = sc.nextInt();
int r = sc.nextInt();
int L = sc.nextInt();
int R = sc.nextInt();
out.println((hashA[r]-hashA[l-1])==(hashB[R]-hashB[L-1])?"Yes":"No");
}
out.close();
}
private static HashMap<Integer,Long> memo = new HashMap<>();
private static long hash(int num){
if(memo.containsKey(num))
return memo.get(num);
memo.put(num,new Random().nextLong());
return memo.get(num);
}
}
時間内に解けなかった…。
感想
A,B,C:易しい
D:めちゃくちゃサンプル合わなくて時間かかった…
E:易しめ？
F:思いつきはしたけど、さすがに間に合わない…
って感じでした。
うぅ…レート駄々下がりで悲しい…。