はじめに
今回はコンテスト中にEまで、コンテスト後にFが解けたのでそれを載せようと思います。
なお、僕のライブラリに関しては提出結果をご覧ください。
では見ていきましょう。
A - The bottom of the ninth
問題文はこちら
$A$の総和から$B$の総和を引いて$1$加えた値が答えになるのでそれを求めました。
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){
//A、Bの総和を求める
long A = MathFunction.sum(sc.nextInt(9));
long B = MathFunction.sum(sc.nextInt(8));
//差+1の出力
out.println(A-B+1);
out.close();
}
}
B - Spot the Difference
問題文はこちら
ちょうど$1$箇所のみ異なるので、異なる箇所を見つけたら出力するように実装しました。
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、A、Bの受け取り
int N = sc.nextInt();
char[][] A = sc.nextCharArray(N);
char[][] B = sc.nextCharArray(N);
//全探索
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(A[i][j]!=B[i][j]){
out.println((i+1)+" "+(j+1));
}
}
}
out.close();
}
}
C - Merge the balls
問題文はこちら
$N$回の操作で出現するボールは$N$個であり、単純に隣り合うボールの数字が一緒なら足し合わせて片方消す、という処理になるので削除は最大でも$N-1$回しか起きず、比較も最大でも$2N-3$回しか起きないことがわかるので、愚直にシミュレーションを行なうことで十分高速に答えを求められます。
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();
//シミュレーション
ArrayDeque<Integer> deq = new ArrayDeque<>();
while(N-->0){
//Aの受け取り
int A = sc.nextInt();
deq.add(A);
//操作を行なう
while(deq.size()>1){
int a1 = deq.pollLast();
int a2 = deq.pollLast();
if(a1==a2){
deq.add(a1+1);
}
else{
deq.add(a2);
deq.add(a1);
break;
}
}
}
//個数の出力
out.println(deq.size());
out.close();
}
}
D - Grid and Magnet
問題文はこちら
自由に行き来できるマスは事前に連結しておき、そのマスから移動できる、磁石によって束縛されてしまうマスを数え上げることで答えを求めることができます。
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);
private static final int[] dx = {1,-1,0,0};
private static final int[] dy = {0,0,1,-1};
public static void main(String[] args){
//H、W、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
final char[][] S = sc.nextCharArray(H);
//自由に行き来できるマスの連結と、
//そのマスから行ける磁石で束縛されるマスの記録
final UnionFind uf = new UnionFind(H*W);
HashMap<Integer,ArrayList<Integer>> memo = new HashMap<>();
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
memo.put(i*W+j,new ArrayList<>());
if(S[i][j]!='#'&&check(i,j,S)){
for(int k=0;k<4;k++){
int nx = i+dx[k];
int ny = j+dy[k];
if(MathFunction.rangeCheck(nx,0,H) &&
MathFunction.rangeCheck(ny,0,W)
){
if(check(nx,ny,S))
uf.unite(i*W+j,nx*W+ny);
memo.get(i*W+j).add(nx*W+ny);
}
}
}
memo.get(i*W+j).add(i*W+j);
}
}
//各連結成分ごとに集計
HashMap<Integer,TreeSet<Integer>> map = new HashMap<>();
for(int i=0;i<H*W;i++){
if(!map.containsKey(uf.root(i)))
map.put(uf.root(i),new TreeSet<>());
map.get(uf.root(i)).addAll(memo.get(i));
}
int ans = 0;
for(TreeSet<Integer> set:map.values())
ans = Math.max(ans,set.size());
//最大値の出力
out.println(ans);
out.close();
}
//磁石によって束縛されるマスか判定するメソッド
private static boolean check(int x,int y,char[][] S){
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(MathFunction.rangeCheck(nx,0,S.length) &&
MathFunction.rangeCheck(ny,0,S[0].length) &&
S[nx][ny]=='#'
){
return false;
}
}
return true;
}
}
実装下手くそ過ぎてペナ出しまくって地獄と化しました…。
E - Jump Distance Sum
問題文はこちら
斜めへの移動しかできないので、$xy$平面を$45$度回転させた座標系で考えれば答えは行き来できる座標間のマンハッタン距離の総和に帰着できます。
$x$座標、$y$座標の差の総和は累積和の要領で求めることができ、行き来できるかどうかは元の座標$(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){
//Nの受け取り
int N = sc.nextInt();
//座標の総和の偶奇で分けて管理
ArrayList<Point> odd = new ArrayList<>();
ArrayList<Point> even = new ArrayList<>();
for(int i=0;i<N;i++){
int X = sc.nextInt();
int Y = sc.nextInt();
if((X+Y)%2==0)
even.add(new Point(X,Y));
else
odd.add(new Point(X,Y));
}
//座標変換
for(Point p:even){
int x = (p.y+p.x)/2;
int y = (p.y-p.x)/2;
p.x = x;
p.y = y;
}
for(Point p:odd){
int x = (p.y+p.x-1)/2;
int y = (p.y-p.x-1)/2;
p.x = x;
p.y = y;
}
//マンハッタン距離の総和を求める
long ans = 0;
long bef;
long sum;
Collections.sort(even,(a,b)->Integer.compare(a.x,b.x));
bef = 0;
sum = 0;
for(int i=0;i<even.size();i++){
sum += (even.get(i).x-bef)*i;
ans += sum;
bef = even.get(i).x;
}
Collections.sort(even,(a,b)->Integer.compare(a.y,b.y));
bef = 0;
sum = 0;
for(int i=0;i<even.size();i++){
sum += (even.get(i).y-bef)*i;
ans += sum;
bef = even.get(i).y;
}
Collections.sort(odd,(a,b)->Integer.compare(a.x,b.x));
bef = 0;
sum = 0;
for(int i=0;i<odd.size();i++){
sum += (odd.get(i).x-bef)*i;
ans += sum;
bef = odd.get(i).x;
}
Collections.sort(odd,(a,b)->Integer.compare(a.y,b.y));
bef = 0;
sum = 0;
for(int i=0;i<odd.size();i++){
sum += (odd.get(i).y-bef)*i;
ans += sum;
bef = odd.get(i).y;
}
//答えの出力
out.println(ans);
out.close();
}
}
これも解法自体はすぐ気付いたんですが、実装下手過ぎて…うぅ…。
F - Double Sum
問題文はこちら
ソート済みの$A$を$B$とすると、
$$\sum_{i=1}^N \sum_{j=i+1}^N \max(A_j-A_i,0)
= \frac{1}{2} \left( \sum_{i=1}^N \sum_{j=i+1}^N(B_j-B_i) +
\sum_{i=1}^N \sum_{j=i+1}^N(A_j-A_i) \right)$$
に変形できるので、これを求めました。
これは、$(B_j-B_i)+(A_j-A_i)$が以下のような性質を持つことに由来します。
$$(B_j-B_i)+(A_j-A_i)=
\begin{cases}
2(A_j-A_i) & \max(A_j-A_i,0) \gt 0 \\
0 & \max(A_j-A_i,0) = 0
\end{cases}
$$
F.java
import java.util.Scanner;
import java.util.Arrays;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Aの受け取り
int N = sc.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++)
A[i] = sc.nextInt();
//ソート済み配列の構築
int[] sortedA = A.clone();
Arrays.sort(sortedA);
//上記の式の値を求める
long ans = 0;
long sum = 0;
for(int i=0;i<N;i++){
ans += sum-(long)sortedA[N-i-1]*i;
sum += sortedA[N-i-1];
}
sum = 0;
for(int i=0;i<N;i++){
ans += sum-(long)A[N-i-1]*i;
sum += A[N-i-1];
}
//答えの出力
System.out.println(ans>>1);
}
}
これは気付けないな…。
感想
A,B,C:易しい
D:かなり手こずった…
E:実装下手くそ過ぎた…
F:難しい…><
って感じでした。
レート駄々下がり…悲しすぎる…。