はじめに
今回は所用でコンテストに参加できなかったのでコンテスト後に解いたものを載せようと思います。
なお、僕のライブラリに関しては提出結果をご確認ください。
では、見ていきましょう。
A - Penalty Kick
問題文はこちら
ooxが永遠に繰り返されている文字列の先頭から$N$文字目までを切り出せば答えが求められるので、雑にooxを$N$回繰り返した文字列を構築し、substringメソッドで答えを求めました。
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の受け取り
int N = sc.nextInt();
//答えの出力
out.println("oox".repeat(N).substring(0,N));
out.close();
}
}
B - Farthest Point
問題文はこちら
制約が小さいので各点に対して一番遠い点を全探索しても十分間に合います。
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();
Point[] point = sc.nextPoint(N);
//各点に対する答えを求める
for(Point p:point){
//一番遠い点を求める(距離の二乗で管理)
int ans = -1;
int max = 0;
for(int i=0;i<N;i++){
int dist = (p.x-point[i].x)*(p.x-point[i].x)+(p.y-point[i].y)*(p.y-point[i].y);
if(max<dist){
max = dist;
ans = i;
}
}
//答えの出力
out.println(ans+1);
}
out.close();
}
}
C - Colorful Beans
問題文はこちら
各色に対する最小値を保持しておいて、その中での最大値が答えになります。
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の受け取り
int N = sc.nextInt();
//各色に対する最小値を記録
HashMap<Integer,Integer> map = new HashMap<>();
while(N-->0){
int A = sc.nextInt();
int C = sc.nextInt();
map.merge(C,A,Integer::min);
}
//答えの出力(何となくstream使ってみた)
int ans = map.values().stream().max(Integer::compare).get();
out.println(ans);
out.close();
}
}
D - Medicines on Grid
問題文はこちら
各薬の位置から移動するのに必要な距離を全部求めて、薬の位置を頂点として見ると、薬から薬へ直接移動できるところに辺を貼ることで始点からゴールへいくつかの辺を辿って到達できるか、という問題に変形できます。前計算が$O(HWN)$で、最後のBFSもO(N^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){
//H、W、A、N、各点、Eの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
char[][] A = sc.nextCharArray(H);
int N = sc.nextInt();
Point[] p = new Point[N];
int[] E = new int[N];
for(int i=0;i<N;i++){
p[i] = sc.nextPoint();
p[i].x--;
p[i].y--;
E[i] = sc.nextInt();
}
//始点と終点を探す
int sR = -1;
int sC = -1;
int gR = -1;
int gC = -1;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(A[i][j]=='S'){
sR = i;
sC = j;
}
if(A[i][j]=='T'){
gR = i;
gC = j;
}
}
}
//各薬の位置からの最短距離を元に、移動できる他の地点へ辺を貼る
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
int startPoint = -1;
for(int i=0;i<N;i++){
int[][] dist = bfs(p[i].x,p[i].y,A);
for(int j=0;j<N;j++)
if(i!=j&&dist[p[j].x][p[j].y]<=E[i])
list.get(i).add(j);
if(dist[gR][gC]<=E[i])
list.get(i).add(N);
if(p[i].x==sR&&p[i].y==sC)
startPoint = i;
}
//始点に薬が無ければそもそも移動不可
if(startPoint==-1)
out.println("No");
//始点・終点・薬間をBFSで
else{
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(startPoint);
boolean[] canMove = new boolean[N+1];
canMove[startPoint] = true;
while(deq.size()>0){
int now = deq.pollFirst();
for(int next:list.get(now)){
if(!canMove[next]){
canMove[next] = true;
deq.add(next);
}
}
}
//終点に到達できたか
out.println(canMove[N]?"Yes":"No");
}
out.close();
}
//遷移用
private static final int[] dx = {1,-1,0,0};
private static final int[] dy = {0,0,1,-1};
//BFS
private static int[][] bfs(int x,int y,char[][] map){
int[][] ans = new int[map.length][map[0].length];
for(int[] temp:ans)
Arrays.fill(temp,Integer.MAX_VALUE);
ans[x][y] = 0;
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(x);
deq.add(y);
while(deq.size()>0){
int nowX = deq.pollFirst();
int nowY = deq.pollFirst();
for(int i=0;i<4;i++){
int nextX = nowX+dx[i];
int nextY = nowY+dy[i];
if(
MathFunction.rangeCheck(nextX,0,map.length) &&
MathFunction.rangeCheck(nextY,0,map[0].length) &&
map[nextX][nextY]!='#' &&
ans[nowX][nowY]+1<ans[nextX][nextY]
){
ans[nextX][nextY] = ans[nowX][nowY]+1;
deq.add(nextX);
deq.add(nextY);
}
}
}
return ans;
}
}
E - Minimize Sum of Distances
問題文はこちら
以下、$f(x)$を「$x$を根としたときの答え」と表現します。
頂点$1$を根としたときの答えをDFSで求めながら、隣の頂点を根としたときから各頂点を根としたときへ遷移したときの答えの差を求めてあげることで、再度頂点1からDFSすることで全頂点を根としたときの答えが求まり、求めたい最小値が求まります。
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 long[] sub;
public static void main(String[] args){
//N、グラフ、Cの受け取り
int N = sc.nextInt();
int[][] graph = sc.nextGraph(N,N-1);
int[] C = new int[N+1];
for(int i=1;i<=N;i++)
C[i] = sc.nextInt();
//f(1)を求めながら増減を記録
long ans = 0;
sub = new long[N+1];
for(int p:graph[1]){
ans += dfs1(p,1,graph,C);
}
long sum = MathFunction.sum(C);
sub = ArrayFunction.reBuild(sub,num->sum-num*2);
//増減を元に全f(i)の答えを求め、最小値を求める
long min = ans;
for(int p:graph[1]){
min = Math.min(min,dfs2(p,1,graph,ans));
}
//答えの出力
out.println(min);
out.close();
}
//戻り値はbefを根としたときの部分木の答え
private static long dfs1(int now,int bef,int[][] graph,int[] C){
long sum = 0;
for(int next:graph[now])
if(next!=bef){
sum += dfs1(next,now,graph,C);
sub[now] += sub[next]; //移動先の情報を加える
}
sub[now] += C[now]; //自分の情報も加える
return sum+sub[now];
}
//差分を元にその部分木における最小値を返す
private static long dfs2(int now,int bef,int[][] graph,long sum){
long ans = sum+sub[now]; //f(now)
for(int next:graph[now])
if(next!=bef)
ans = Math.min(ans,dfs2(next,now,graph,sum+sub[now]));
return ans;
}
}
かなり汚い実装になってしまった…。全方位木DP履修しなきゃ…。
F - Oddly Similar
問題文はこちら
各$i$について、$A_{j,i}$が同じ同士の$j$を探して同じ項の個数の偶奇を反転させる、みたいな処理を考えると$O(MN^2)$になります。そのままだと実行時間がかなり厳しいですが、「同じ項の個数の偶奇を反転させる」はビット反転で考えることができて、自分と$A_j$が似ているときに$j$番目のビットが立っている、という風に管理することを考えればBitSetで処理できる、と判断することができます。すると、ワードサイズを$w$として$O(\frac{MN^2}{w})$に改善できるので、少々重いですがTLには間に合います。
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、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[][] A = sc.nextInt(N,M);
//自身と似ている数列を管理する用
BitSet[] bits = new BitSet[N];
for(int i=0;i<N;i++)
bits[i] = new BitSet(N);
//各項について処理
for(int i=0;i<M;i++){
//各値と、その値を持つ数列を記録
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
for(int j=0;j<N;j++){
if(!map.containsKey(A[j][i]))
map.put(A[j][i],new ArrayList<>());
map.get(A[j][i]).add(j);
}
//項が同じもののビットを立ててxorを取る
for(ArrayList<Integer> list:map.values()){
BitSet bit = new BitSet(N);
for(int b:list)
bit.set(b);
for(int b:list)
bits[b].xor(bit);
}
}
//組み合わせを数え上げ((i,j)と(j,i)を区別して数え上げるので2倍になってる)
int ans = 0;
for(int i=0;i<N;i++){
bits[i].clear(i); //自分自身のビットが立っている可能性があるのでclearしておく
ans += bits[i].cardinality();
}
//答えの出力
out.println(ans>>1);
out.close();
}
}
いやぁ、気付いたときはテンション上がりました(？)。
感想
A,B,C:易しい
D:実装が思ったより重い…
E:綺麗に実装できるようになりたいね…
F:思ったより速く気付けた
って感じでした。
解いた感触としては得意回だったかもしれなくて(まぁコンテスト中に解いたわけじゃないので何とも言えないですけど)、出れば良かったなぁという気持ちが…。