はじめに
今回はコンテスト中にDまで、コンテスト後にFまで解けたのでそれを載せようと思います。
では、見ていきましょう。
A - Seats
問題文はこちら
条件に合うものを愚直に探索しました。
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 N = sc.nextInt();
char[] S = sc.nextCharArray();
int ans = 0;
for(int i=2;i<N;i++)
if(S[i-2]=='#'&&S[i-1]=='.'&&S[i]=='#')
ans++;
out.println(ans);
out.close();
}
}
B - Traveling Takahashi Problem
問題文はこちら
シミュレーションで愚直に求めました。
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){
int N = sc.nextInt();
Point p = new Point(0,0);
double ans = 0;
while(N-->0){
Point x = sc.nextPoint();
ans += Math.hypot(p.x-x.x,p.y-x.y);
p = x;
}
out.println(ans+Math.hypot(p.x,p.y));
out.close();
}
}
C - Spiral Rotation
問題文はこちら
各マスが何回操作されているかを求めることで解を高速に構築することができます。
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){
int N = sc.nextInt();
char[][] A = sc.nextCharArray(N);
char[][] ans = new char[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(Math.min(Math.min(j,N-j-1),Math.min(i,N-i-1))%4==0){
ans[i][j] = A[N-j-1][i];
}
else if(Math.min(Math.min(j,N-j-1),Math.min(i,N-i-1))%4==1){
ans[i][j] = A[N-i-1][N-j-1];
}
else if(Math.min(Math.min(j,N-j-1),Math.min(i,N-i-1))%4==2){
ans[i][j] = A[j][N-i-1];
}
else{
ans[i][j] = A[i][j];
}
}
}
out.println(ans);
out.close();
}
}
D - ABA
問題文はこちら
$S_j$を考えると、$S_i=S_k(i<j<k)$を満たす$i$と$k$の組み合わせを考えればよいので、HashMapなどで管理することで解を高速に数え上げることができます。
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){
char[] S = sc.nextCharArray();
HashMap<Character,ArrayList<Integer>> map = new HashMap<>();
for(char c='A';c<='Z';c++)
map.put(c,new ArrayList<>());
for(int i=0;i<S.length;i++)
map.get(S[i]).add(i);
long ans = 0;
for(char c='A';c<='Z';c++){
ArrayList<Integer> list = map.get(c);
for(int i=0;i<S.length;i++){
int l = Searcher.underSearch(list,i);
int r = Searcher.overSearch(list,i);
if(l<0||r==list.size())
continue;
ans += (long)(l+1)*(list.size()-r);
}
}
out.println(ans);
out.close();
}
}
E - 3 Team Division
問題文はこちら
公式解説の通りです。
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 class Node{
int a,b,c;
public Node(int a,int b,int c){
this.a = a;
this.b = b;
this.c = c;
}
@Override
public int hashCode(){
return (a<<10)^(b<<5)^c;
}
@Override
public boolean equals(Object o){
if(o instanceof Node n){
return a==n.a&&b==n.b&&c==n.c;
}
return false;
}
}
public static void main(String[] args){
int N = sc.nextInt();
int[] A = new int[N];
int[] B = new int[N];
for(int i=0;i<N;i++){
A[i] = sc.nextInt();
B[i] = sc.nextInt();
}
int sum = (int)MathFunction.sum(B);
if(sum%3>0)
out.println(-1);
else{
HashMap<Node,Integer> dp = new HashMap<>();
dp.put(new Node(0,0,0),0);
for(int i=0;i<N;i++){
HashMap<Node,Integer> next = new HashMap<>();
for(Entry<Node,Integer> entry:dp.entrySet()){
int a = entry.getKey().a;
int b = entry.getKey().b;
int c = entry.getKey().c;
int now = entry.getValue();
if(a+B[i]<=sum/3)
next.merge(
new Node(a+B[i],b,c),
now+(A[i]==1?0:1),
Integer::min);
if(b+B[i]<=sum/3)
next.merge(
new Node(a,b+B[i],c),
now+(A[i]==2?0:1),
Integer::min);
if(c+B[i]<=sum/3)
next.merge(
new Node(a,b,c+B[i]),
now+(A[i]==3?0:1),
Integer::min);
}
dp = next;
}
out.println(dp.getOrDefault(new Node(sum/3,sum/3,sum/3),-1));
}
out.close();
}
}
気づけなかったなぁ…。
F - Road Blocked
問題文はこちら
公式解説の通りです。
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 M = sc.nextInt();
int Q = sc.nextInt();
int[][] path = sc.nextInt(M,3);
int[][] query = new int[Q][3];
HashSet<Integer> set = new HashSet<>();
int count = 0;
while(Q-->0){
int t = sc.nextInt();
if(t==1){
query[Q][0] = 1;
query[Q][1] = sc.nextInt()-1;
set.add(query[Q][1]);
}
else{
query[Q][0] = 2;
query[Q][1] = sc.nextInt();
query[Q][2] = sc.nextInt();
count++;
}
}
long[][] dist = new long[N+1][N+1];
long max = Long.MAX_VALUE>>1;
for(long[] temp:dist)
Arrays.fill(temp,max);
for(int i=1;i<=N;i++)
dist[i][i] = 0;
for(int i=0;i<M;i++)
if(!set.contains(i)){
dist[path[i][0]][path[i][1]] = path[i][2];
dist[path[i][1]][path[i][0]] = path[i][2];
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
for(int k=1;k<=N;k++)
dist[j][k] = Math.min(dist[j][k],dist[j][i]+dist[i][k]);
long[] ans = new long[count];
for(int[] q:query){
int t = q[0];
if(t==1){
int[] p = path[q[1]];
dist[p[0]][p[1]] = Math.min(dist[p[0]][p[1]],p[2]);
dist[p[1]][p[0]] = Math.min(dist[p[1]][p[0]],p[2]);
for(int i:new int[]{p[0],p[1]})
for(int j=1;j<=N;j++)
for(int k=1;k<=N;k++)
dist[j][k] = Math.min(dist[j][k],dist[j][i]+dist[i][k]);
}
else{
int x = q[1];
int y = q[2];
ans[--count] = dist[x][y]==max?-1:dist[x][y];
}
}
out.println(ans,"\n");
out.close();
}
}
ワーシャルフロイド法…ド忘れ…全然思いつきませんでした…。
感想
A,B:易しい
C:めんどくさい
D:気づけばサクッと解ける
E,F:難しい…
って感じでした。
むむむ…圧倒的実力不足…。