Codeforces 370 Div2 A~C
A
考察
・とが同じことに気付く。
・が分かっているので,をからの順で問題文の式通りに求めていく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class A { int N; int[] a; public void solve() { N = nextInt(); a = new int[N]; for(int i = 0;i < N;i++){ a[i] = nextInt(); } int[] b = new int[N]; int[] sum = new int[2]; for(int i = N - 1;i >= 0;i--){ b[i] = a[i] + sum[i&1] - sum[(i&1)^1]; sum[(i&1)^1] += b[i]; } for(int i = 0;i < N;i++){ if(i != 0)out.print(" "); out.print(b[i]); } out.println(); } public static void main(String[] args) { out.flush(); new A().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
B
考察
・Uの数 = Dの数,Rの数 = Lの数,が等しくなければ最終的に元の位置は戻らない。
・つまり、sで与えられた文字列の長さ(移動回数)が奇数ならば絶対に元の位置には戻らない。
・が余った移動回数になるので,それを使ってRの数 = Lの数にできるように調整する。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class B { String s; int[] cnt; public void solve() { s = next(); if(s.length() % 2 == 1){ out.println("-1"); return; } cnt = new int[300]; for(int i = 0;i < s.length();i++){ cnt[s.charAt(i)]++; } int updown = Math.min(cnt['U'],cnt['D']); int leftright = Math.min(cnt['L'],cnt['R']); cnt['U'] -= updown; cnt['D'] -= updown; cnt['L'] -= leftright; cnt['R'] -= leftright; int min1 = Math.max(cnt['U'],cnt['D']); int min2 = Math.max(cnt['L'], cnt['R']); int min3 = Math.min(min1, min2); int ans = min3; ans += (min1 - min3) / 2; ans += (min2 - min3) / 2; out.println(ans); } public static void main(String[] args) { out.flush(); new B().solve(); out.close(); } }
考察
・からに辺を縮小するということなので、逆にからに伸長するようにしたらうまくいった。
・辺が小さい順にa,b,cとし,するとaはb + c - 1まで伸長できるのでそれをxになるまでやっていく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; import java.util.*; public class Main { int x,y; public void solve() { x = nextInt(); y = nextInt(); PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); int ans = 0; pq.add(y); pq.add(y); pq.add(y); while(pq.size() > 2){ int a = pq.poll(); int b = pq.poll(); int c = pq.poll(); if(a == x){ out.println(ans); break; } a = Math.min(x,b + c - 1); pq.add(a); pq.add(b); pq.add(c); ans++; } } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } }