はじめに
今回はコンテスト中にFまで解けたのでそれを載せようと思います。
なお、僕のライブラリはGitHubからご確認ください。
では、見ていきましょう。
A - 369
問題文はこちら
$A$と$B$が等しいなら$A=B=x$の$1$通りしか存在せず、$\min(A,B)<x<\max(A,B)$かつ$x$から$A$、$B$それぞれへの距離が等しいような$x$を作れるなら$3$通り、それ以外は$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 A = sc.nextInt();
int B = sc.nextInt();
int x = A+B>>1;
if(A==B)
out.println(1);
else if(x-Math.min(A,B)==Math.max(A,B)-x)
out.println(3);
else
out.println(2);
out.close();
}
}
B - Piano 3
問題文はこちら
$A_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){
int N = sc.nextInt();
int L = -1;
int R = -1;
int ans = 0;
while(N-->0){
int A = sc.nextInt();
char S = sc.nextChar();
if(S=='L'){
if(0<L)
ans += Math.abs(A-L);
L = A;
}
else{
if(0<R)
ans += Math.abs(A-R);
R = A;
}
}
out.println(ans);
out.close();
}
}
C - Count Arithmetic Subarrays
問題文はこちら
始点$l$を固定したとき、等差数列を為す区間が$r$までと考えた時、$l+1$から$r$までも等差数列であることは変わらないので、尺取り法を用いて解を数え上げました。
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();
int[] A = sc.nextInt(N);
int r = 0;
long ans = 0;
for(int l=0;l<N;l++){
r = Math.max(r,l+2);
while(r<N&&A[r]-A[r-1]==A[l+1]-A[l])
r++;
ans += Math.max(0,r-l-2);
}
ans += N;
ans += N-1;
out.println(ans);
out.close();
}
}
D - Bonus EXP
問題文はこちら
現時点で奇数回倒した時に得られる最大経験値、偶数回倒した時に得られる最大経験値を保持しておくことで、動的計画法の要領で最適解を求めることができます。
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();
long odd = Integer.MIN_VALUE;
long even = 0;
while(N-->0){
int A = sc.nextInt();
long nextOdd = even+A;
long nextEven = odd+A*2;
odd = Math.max(odd,nextOdd);
even = Math.max(even,nextEven);
}
out.println(Math.max(odd,even));
out.close();
}
}
E - Sightseeing Tour
問題文はこちら
事前に全頂点から全頂点への最短距離をダイクストラ法を用いて求めておくことで、始点からある橋への片方の頂点への距離、他方の頂点から別の橋の片方の頂点への距離、のように距離を数え上げること考えられる通り方に対する距離をクエリあたり$O(K_i)$で求めることができ、クエリあたり$O(2^{K_i}K_i!)$通り考える必要があるので全体で$O(Q\max(K)2^{\max(K)}\max(K)!)$時間で解くことができます。
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 M = sc.nextInt();
ArrayList<ArrayList<int[]>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
int[][] path = new int[M][3];
for(int i=0;i<M;i++){
int U = sc.nextInt();
int V = sc.nextInt();
int T = sc.nextInt();
path[i][0] = U;
path[i][1] = V;
path[i][2] = T;
list.get(U).add(new int[]{V,T});
list.get(V).add(new int[]{U,T});
}
PriorityQueue<long[]> queue = new PriorityQueue<>((a,b)->Long.compare(a[1],b[1]));
long[][] cost = new long[N+1][N+1];
for(int i=1;i<=N;i++){
Arrays.fill(cost[i],Long.MAX_VALUE);
cost[i][i] = 0;
queue.add(new long[]{i,0});
while(queue.size()>0){
long[] node = queue.poll();
int n = (int)node[0];
long c = node[1];
if(cost[i][n]<c)
continue;
cost[i][n] = c;
for(int[] p:list.get(n)){
int nn = p[0];
long nc = c+p[1];
if(nc<cost[i][nn]){
cost[i][nn] = nc;
queue.add(new long[]{nn,nc});
}
}
}
}
int Q = sc.nextInt();
while(Q-->0){
int K = sc.nextInt();
int[] B = sc.nextInt(K);
long sum = 0;
for(int i:B)
sum += path[i-1][2];
boolean[] passed = new boolean[K];
out.println(dfs(1,passed,B,path,cost)+sum);
}
out.close();
}
}
F - Gather Coins
問題文はこちら
各列に対してセグメントツリーを用いて最大値と拾ったコインの座標を記録しておくことで解を求め、あとはコインを通るように適当に経路を構築することで解が求まります。
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 H = sc.nextInt();
int W = sc.nextInt();
int N = sc.nextInt();
TreeMap<Integer,ArrayList<Integer>> map = new TreeMap<>();
while(N-->0){
int R = sc.nextInt();
int C = sc.nextInt();
if(!map.containsKey(R))
map.put(R,new ArrayList<>());
map.get(R).add(C);
}
Node[] node = new Node[W+1];
SegmentTree<Integer> segT = new SegmentTree<>(W,0,true){
public Integer function(Integer a,Integer b){
return Math.max(a,b);
}
};
while(map.size()>0){
Entry<Integer,ArrayList<Integer>> entry = map.pollLastEntry();
int h = entry.getKey();
ArrayList<Integer> list = entry.getValue();
Collections.sort(list,Comparator.reverseOrder());
for(int w:list){
int max = segT.query(w,W);
if(segT.get(w)<=max){
int l = w;
int r = W+1;
while(r-l>1){
int mid = l+r>>1;
if(segT.query(mid,W)==max)
l = mid;
else
r = mid;
}
Node n = new Node(new Point(h,w));
n.next = node[l];
node[w] = n;
segT.update(w,max+1);
}
}
}
int max = segT.answer();
StringBuilder ans = new StringBuilder();
int x = 1;
int y = 1;
int index = 0;
while(segT.get(index)<max)
index++;
Node n = node[index];
while(n!=null){
while(x<n.p.x){
x++;
ans.append('D');
}
while(y<n.p.y){
y++;
ans.append('R');
}
n = n.next;
}
while(x<H){
x++;
ans.append('D');
}
while(y<W){
y++;
ans.append('R');
}
out.println(max);
out.println(ans.toString());
out.close();
}
}
感想
A,B:易しい
C:ちょっと実装に時間がかかってしまった…
D:DPらしい問題
E:発想に凄い時間がかかってしまった
F:公式解説のLIS解法、たしかにすぎる…
って感じでした。
む～ん…割と調子良い気がしたんですけどねぇ…これでもレート下がっちゃうのか…。