はじめに
今回はコンテスト中にEまで、コンテスト後にFが解けたのでそれを載せようと思います。
なお、僕のライブラリはGitHubよりご確認ください。
では、見ていきましょう。
A - Election 2
問題文はこちら
高橋氏と青木氏に残りの票を加算してみて大小が変わらないかを見て判定しました。
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();
int T = sc.nextInt();
int A = sc.nextInt();
out.println(
Integer.compare((N-T-A)+T,A)==Integer.compare(T,(N-T-A)+A)?
"Yes":"No");
out.close();
}
}
B - Vertical Writing
問題文はこちら
とりあえず*で埋めた行を構築し、余分な*をsubstringメソッドで取り除くことで答えを構築しました。
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();
String[] S = sc.next(N);
int len = 0;
for(String s:S)
len = Math.max(len,s.length());
for(int i=0;i<len;i++){
StringBuilder ans = new StringBuilder();
for(int j=N-1;j>=0;j--){
if(S[j].length()<=i)
ans.append('*');
else
ans.append(S[j].charAt(i));
}
int index = N;
while(ans.charAt(index-1)=='*')
index--;
out.println(ans.substring(0,index));
}
out.close();
}
}
余分な*を除くのを忘れててペナを…。
C - Balls and Bag Query
問題文はこちら
HashMapで番号とその個数を管理することで本問題を解きました。
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 Q = sc.nextInt();
HashMap<Integer,Integer> map = new HashMap<>();
while(Q-->0){
int q = sc.nextInt();
if(q==1){
int x = sc.nextInt();
map.merge(x,1,Integer::sum);
}
if(q==2){
int x = sc.nextInt();
map.merge(x,-1,(a,b)->a+b==0?null:a+b);
}
if(q==3){
out.println(map.size());
}
}
out.close();
}
}
D - Cuboid Sum Query
問題文はこちら
包除原理を利用して三次元累積和を構築し、クエリ辺り$O(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){
int N = sc.nextInt();
int[][][] A = new int[N][][];
for(int i=0;i<N;i++)
A[i] = sc.nextInt(N,N);
long[][][] sum = new long[N+1][N+1][N+1];
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
for(int k=1;k<=N;k++){
sum[i][j][k] = sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]
-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]
+sum[i-1][j-1][k-1]+A[i-1][j-1][k-1];
}
}
}
int Q = sc.nextInt();
while(Q-->0){
int Lx = sc.nextInt();
int Rx = sc.nextInt();
int Ly = sc.nextInt();
int Ry = sc.nextInt();
int Lz = sc.nextInt();
int Rz = sc.nextInt();
long ans = sum[Rx][Ry][Rz]-sum[Lx-1][Ry][Rz]-sum[Rx][Ly-1][Rz]-sum[Rx][Ry][Lz-1]
+sum[Lx-1][Ly-1][Rz]+sum[Lx-1][Ry][Lz-1]+sum[Rx][Ly-1][Lz-1]
-sum[Lx-1][Ly-1][Lz-1];
out.println(ans);
}
out.close();
}
}
E - Manhattan Multifocal Ellipse
問題文はこちら
マンハッタン距離は$x$座標の距離と$y$座標の距離を独立に考えることができるので、考え得る$x$座標、$y$座標におけるマンハッタン距離の総和を求めておくことで解を高速に数え上げることができます。
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();
int D = sc.nextInt();
Point[] p = sc.nextPoint(N);
int minX = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;
for(Point point:p){
minX = Math.min(minX,point.x);
maxX = Math.max(maxX,point.x);
minY = Math.min(minY,point.y);
maxY = Math.max(maxY,point.y);
}
int subX = D-minX;
maxX += subX+D;
int subY = D-minY;
maxY += subY+D;
for(Point point:p){
point.x += subX;
point.y += subY;
}
long[] dist = new long[maxY+1];
long now = 0;
int count = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(Point point:p){
now += point.x+point.y;
if(point.y==0)
count++;
else
queue.add(point.y);
}
for(int i=0;i<=maxY;i++){
dist[i] = now;
now += 2*count-N;
while(queue.size()>0&&queue.peek()==i+1){
count++;
queue.poll();
}
}
Arrays.sort(dist);
count = 0;
for(Point point:p){
if(point.x==0)
count++;
else
queue.add(point.x);
}
now = 0;
long ans = 0;
for(int i=0;i<=maxX;i++){
long val = D-now;
ans += Searcher.overSearch(dist,val);
now += 2*count-N;
while(queue.size()>0&&queue.peek()==i+1){
count++;
queue.poll();
}
}
out.println(ans);
out.close();
}
}
F - Maximum Composition
問題文はこちら
詳しくは公式解説をお読み下さい。
F.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int[][] func = new int[N][2];
for(int i=0;i<N;i++){
func[i][0] = sc.nextInt();
func[i][1] = sc.nextInt();
}
Arrays.sort(func,Main::linearFunctionComparator);
long[] dp = new long[K+1];
dp[0] = 1;
for(int[] f:func)
for(int i=K;0<i;i--)
dp[i] = Math.max(dp[i],dp[i-1]*f[0]+f[1]);
System.out.println(dp[K]);
}
private static int linearFunctionComparator(int[] f1,int[] f2){
int value1 = 1;
value1 = f2[0]*value1+f2[1];
value1 = f1[0]*value1+f1[1];
int value2 = 1;
value2 = f1[0]*value2+f1[1];
value2 = f2[0]*value2+f2[1];
return Integer.compare(value1,value2);
}
}
これは思いつけなかったな…
感想
A:易しい
B:ちょっとめんどくさい…
C:易しい
D:三次元累積和慣れない…
E:計算量不安だったけどどうにか間に合った
F:方針が立てられなかった…
って感じでした。
う～ん…もう少し正確かつ速く解きたい…。