はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - 202<s>3</s>
問題文はこちら
特に深いことは考えずに、文字列を切り出して末尾に4を付けて出力しました。
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){
//Sの受け取り
String S = sc.next();
//末尾を4に変えて出力
out.println(S.substring(0,S.length()-1)+"4");
out.close();
}
}
B - Tetrahedral Number
問題文はこちら
これも特に何も考えずに3重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){
//Nの受け取り
int N = sc.nextInt();
//全列挙
for(int i=0;i<=N;i++){
for(int j=0;i+j<=N;j++){
for(int k=0;i+j+k<=N;k++){
out.println(i+" "+j+" "+k);
}
}
}
out.close();
}
}
C - Loong Tracking
問題文はこちら
ArrayDequeにランダムアクセスが無いので、代わりにリングバッファの要領で配列に座標を保持して解きました。
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、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//初期状態の設定
Point[] point = new Point[N];
for(int i=0;i<N;i++)
point[i] = new Point(i+1,0);
//先頭を表すint
int head = 0;
//クエリ処理
while(Q-->0){
//クエリ番号の受け取り
int t = sc.nextInt();
if(t==1){
//移動方向に合わせて調整
char C = sc.nextChar();
Point bef = point[head];
head = (head+N-1)%N;
point[head] = switch(C){
case 'R' -> new Point(bef.x+1,bef.y);
case 'L' -> new Point(bef.x-1,bef.y);
case 'U' -> new Point(bef.x,bef.y+1);
default -> new Point(bef.x,bef.y-1);
};
}
else{
//指定された座標を出力
int p = sc.nextInt();
Point sub = point[(head+p-1)%N];
out.println(sub.x+" "+sub.y);
}
}
out.close();
}
}
リングバッファ自体は書いたことがあったので割とサクッと解けました。
D - Loong and Takahashi
問題文はこちら
出力例1みたいに渦巻き状に埋めていけば必ず構築できるので、それで解きました。
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の受け取り
int N = sc.nextInt();
//適当にTの部分をマスクしておく
int[][] ans = new int[N][N];
ans[N>>1][N>>1] = N*N;
//渦巻き状に埋める
dfs(0,0,1,0,ans);
//出力
for(int i=0;i<N;i++){
out.print(ans[i][0]);
for(int j=1;j<N;j++){
out.print(" ");
if(ans[i][j]==N*N)
out.print("T");
else
out.print(ans[i][j]);
}
out.println();
}
out.close();
}
//遷移用
private static final int[] dx = {0,1,0,-1};
private static final int[] dy = {1,0,-1,0};
//渦巻き構築用
private static void dfs(int x,int y,int now,int d,int[][] ans){
ans[x][y] = now;
//次の座標
int nx = x+dx[d];
int ny = y+dy[d];
//有効な座標ならそこに遷移
if(MathFunction.rangeCheck(nx,0,ans.length)&&
MathFunction.rangeCheck(ny,0,ans.length)&&
ans[nx][ny]==0){
dfs(nx,ny,now+1,d,ans);
}
else{
//壁に当たったなら方向転換
d = (d+1)%4;
nx = x+dx[d];
ny = y+dy[d];
if(MathFunction.rangeCheck(nx,0,ans.length)&&
MathFunction.rangeCheck(ny,0,ans.length)&&
ans[nx][ny]==0){
dfs(nx,ny,now+1,d,ans);
}
}
}
}
最初テキトーにDFSしたせいで1ペナ出してしまった…。
E - Non-Decreasing Colorful Path
問題文はこちら
コンテスト後に書いたコードですが、Aが昇順になるような順番で探索をしていくことで答えが求められます。昇順に探索していくのにはダイクストラ法を用いました。
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、A、グラフの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
int[][] graph = sc.nextGraph(N,M);
//答え用配列
int[] ans = new int[N+1];
ans[1] = 1;
//ダイクストラ用
PriorityQueue<int[]> deq = new PriorityQueue<>((a,b)->{
if(A[a[0]-1]!=A[b[0]-1])
return Integer.compare(A[a[0]-1],A[b[0]-1]);
else
return Integer.compare(a[1],b[1]);
});
//ダイクストラ法
deq.add(new int[]{1,1});
while(deq.size()>0){
int[] now = deq.poll();
if(now[1]<ans[now[0]])
continue;
for(int next:graph[now[0]]){
if(A[now[0]-1]<A[next-1]){
if(ans[next]<ans[now[0]]+1){
ans[next] = ans[now[0]]+1;
deq.add(new int[]{next,ans[next]});
}
}
else if(A[now[0]-1]==A[next-1]){
if(ans[next]<ans[now[0]]){
ans[next] = ans[now[0]];
deq.add(new int[]{next,ans[next]});
}
}
}
}
//答えの出力
out.println(ans[N]);
out.close();
}
}
最初単に得点でダイクストラ法を適用してしまったがためにペナを出すという…悲しい…。
F - Hop Sugoroku
問題文はこちら
公式解説の通りです。
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){
//Nの受け取り
final int N = sc.nextInt();
//いろいろ設定
final int mod = 998244353;
final int M = (int)Math.sqrt(N);
//Aが小さい時用
final int[][] sum = new int[M+1][];
for(int i=0;i<=M;i++)
sum[i] = new int[i];
//DPテーブル
final int[] dp = new int[N];
dp[0] = 1;
//遷移
for(int i=0;i<N;i++){
final int A = sc.nextInt();
for(int j=1;j<=M;j++){
dp[i] += sum[j][i%j];
if(mod<=dp[i])
dp[i] -= mod;
}
if(A<=M){
int B = i%A;
sum[A][B] += dp[i];
if(mod<=sum[A][B])
sum[A][B] -= mod;
}
else{
for(int j=i+A;j<N;j+=A){
dp[j] += dp[i];
if(mod<=dp[j])
dp[j] -= mod;
}
}
}
//答えの数え上げ
int ans = 0;
for(int num:dp){
ans += num;
if(mod<=ans)
ans -= mod;
}
//出力
out.println(ans);
out.close();
}
}
いやぁ…一度頭に浮かんだんですが、計算量が削減できるイメージができなくて切り捨ててしまいました…。数弱さん…。
感想
A,B:易しい
C:ちょっと悩んだ
D:出力例にまんま解法が載っていてびっくりした
E:得点でダイクストラ法は無理かもって思いながら実装して提出する奇行をしてしまった()
F:手も足も出なかった…
って感じでした。
レートは上がったけど、もう少し…良い成績が取りたい…。