Codeforces #388 Div2 A~C
Codeforces Round #388 (Div. 2)
— tookunn (@tookunn_1213) 2017年1月6日
B問題,二次元座標上に平行四辺形を作る問題で,三点が与えられて残りの一つの点の候補を上げていく問題だったけど全然分からなかった。
C問題,submitデバッグしたら通った感じ#tookunnVirtual pic.twitter.com/669qgq7q9M
A問題
考察
Nは2または3だけで表すことが出来るので,2で出来るだけ表すようにして,Nが2で割り切れなかったら最後の2を3にすればよい。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class A { int N; public void solve() { N = nextInt(); out.println(N/2); for(int i = 0;i < N/2 - N%2;i++){ if(i != 0)out.print(" "); out.print(2); } if(N%2==1)out.print(" 3"); 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問題
考察
与えられた3点を使って平行四辺形を作ることができる残り1点の候補は3つだけ
与えられた3点をA,B,Cとし,求める残り1点をDとするとベクトルAB,ACと点Aの和を求めるとDの座標が分かる。
参考にさせて頂いた解説記事:
pekempey.hatenablog.com
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.HashSet; import java.util.NoSuchElementException; public class B { private class V{ int x,y; public V(int x,int y){ this.x = x; this.y = y; } } public void solve() { V[] v = new V[3]; for(int i = 0;i < 3;i++){ v[i] = new V(nextInt(),nextInt()); } HashSet<int[]> set = new HashSet<int[]>(); for(int i = 0;i < 3;i++){ int j = i + 1; int k = j + 1; j %= 3; k %= 3; int x = v[i].x + v[j].x - v[i].x + v[k].x - v[i].x; int y = v[i].y + v[j].y - v[i].y + v[k].y - v[i].y; set.add(new int[]{x,y}); } out.println(set.size()); for(int[] a : set){ out.println(a[0] + " " + a[1]); } } public static void main(String[] args) { out.flush(); new B().solve(); out.close(); } }
C問題
考察
問題文通りにシュミレーションした
与えられた文字列Sを先頭から見ていき,もしその文字が投票権を持っていたら,今見ている文字と対となる文字の中で次に呼ばれる可能性がある文字の投票権を打ち消す。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; import java.util.TreeSet; public class C { int N; String s; public void solve() { N = nextInt(); s = next(); TreeSet<Integer> D = new TreeSet<Integer>(); TreeSet<Integer> R = new TreeSet<Integer>(); for(int i = 0;i < N;i++){ if(s.charAt(i) == 'D'){ D.add(i); }else{ R.add(i); } } for(int i = 0;R.size() > 0 && D.size() > 0;i++,i%=N){ if(s.charAt(i) == 'D'){ if(!D.contains(i))continue; if(R.higher(i) != null){ R.remove(R.higher(i)); }else{ R.remove(R.lower(i)); } }else{ if(!R.contains(i))continue; if(D.higher(i) != null){ D.remove(D.higher(i)); }else{ D.remove(D.lower(i)); } } } if(D.size() > 0){ out.println("D"); }else{ out.println("R"); } } public static void main(String[] args) { out.flush(); new C().solve(); out.close(); } }
RUPC2016 Day3 A マイナンバー - My Number -
問題
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=A
これは当時本番で解いたのでそこまで苦労しないで解けた感(実装は時間掛かった)
考察
?のところに0~9までの数字を当てはめて実際にそのマイナンバーでチェックディジットが一致するかどうかを見ていけば良い。
複数の数字でチェックディジットが一致した場合はMUTLIPLEを出力
1つだけの数字でチェックディジットが一致した場合はその数字を出力
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.NoSuchElementException; public class Main implements Runnable{ String s; public void solve() { s = next(); ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0;i < 10;i++){ char[] ch = s.toCharArray(); for(int j = 0;j < 12;j++) if(ch[j] == '?') ch[j] = (char)(i + '0'); int digit = 0; for(int j = 11;j >= 1;j--){ int Q = j >= 7 ? j - 5 : j + 1; digit += (ch[(11-j)]-'0') * Q; } digit %= 11; if(digit <= 1)digit = 0; else digit = 11 - digit; if(digit+'0' == ch[11])list.add(i); } if(list.size() > 1)out.println("MULTIPLE"); else out.println(list.get(0)); } public static void main(String[] args) { new Thread(null,new Main(),"",32 * 1024 * 1024).start(); } /* 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()); } @Override public void run() { out.flush(); new Main().solve(); out.close(); } }
RUPC2016 Day2 G Max Pig Noodle
問題
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=G
誤読というか,交換人と交換しなくていいパターンあるの読み取れなくて苦戦したが,自力で解けたので良かった。
考察
当初,N人の交換人との交換をどの順番に行っていくかを考えていたけど,順番を決めていくと計算量がどう考えても間に合わなそうだったので考え直した。
そこで,順番を考えずにi番目の交換人と「交換する(方法1,方法2)」「しない」をやっていき,N番目の交換人との操作まで終わって最終的に「うまか棒の数」と「ふがしの数」が0未満の数になっていなければその状態はあり得ると考えられるので,その状態での「ブタメソの数」と今までの「ブタメソの数」の最大値とのmaxを取る。
これをそれぞれの状態をメモ化しながら全パターン試していく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main implements Runnable{ int N,X,Y; int[] a,b,c,d; int[][][] dp; public int dfs(int n,int x,int y){ if(n >= N){ if(x < 300 || y < 300)return -1; return 0; } if(dp[n][x][y] != Integer.MIN_VALUE){ return dp[n][x][y]; } int ret = -1; { int tmp = dfs(n + 1,x - a[n],y + b[n]); if(tmp != -1){ ret = Math.max(ret,tmp); } } { int tmp = dfs(n + 1,x,y - c[n]); if(tmp != -1){ ret = Math.max(ret,tmp + d[n]); } } { int tmp = dfs(n + 1,x,y); if(tmp != -1){ ret = Math.max(ret,tmp); } } return dp[n][x][y] = ret; } public void solve() { N = nextInt(); X = nextInt(); Y = nextInt(); a = new int[N]; b = new int[N]; c = new int[N]; d = new int[N]; for(int i = 0;i < N;i++){ a[i] = nextInt(); b[i] = nextInt(); c[i] = nextInt(); d[i] = nextInt(); } dp = new int[N][901][901]; for(int i = 0;i < N;i++){ for(int j = 0;j < 901;j++){ for(int k = 0;k < 901;k++){ dp[i][j][k] = Integer.MIN_VALUE; } } } int ans = dfs(0,X + 300,Y + 300); out.println(ans == -1 ? 0 : ans); } public static void main(String[] args) { new Thread(null,new Main(),"",32 * 1024 * 1024).start(); } /* 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()); } @Override public void run() { out.flush(); new Main().solve(); out.close(); } }
RUPC2016 Day2 D Courage Test
考察
まず,頂点uと頂点vから同じ回数しか移動できないので,Nが奇数の場合はNoになる。
次は,頂点uと頂点vそれぞれから各頂点の最短距離を記憶しておく。ダイクストラで求めても良いが,辺のコストは1なので普通にQueueを使った方が早い。
ここで,頂点u と頂点vそれぞれから最短距離がN/2の頂点を覚えておく。(実は最短距離がN/2になる頂点数は少ない)
頂点uまたは頂点vどちらかの頂点から最短距離がN/2の頂点が存在しない場合はNoとなる。
そして,(頂点uから最短距離がN/2の頂点)×(頂点vから最短距離がN/2の頂点)の組み合わせを全部試して,それぞれの最短距離の経路が被らないものがあればYesとなる。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.NoSuchElementException; public class Main{ static final int INF = (int)1e9 + 7; int N,u,v; ArrayList<Integer>[] G; int[] prev1,prev2; public void dijkstra(int s,int[] dis,int[] prev){ Arrays.fill(prev, -1); Arrays.fill(dis, INF); dis[s] = 1; ArrayDeque<int[]> q = new ArrayDeque<int[]>(); q.add(new int[]{s,1}); while(q.size() > 0){ int[] p = q.poll(); if(dis[p[0]] < p[1])continue; for(int n : G[p[0]]){ if(dis[p[0]]+1 <= N/2 && dis[n] > dis[p[0]]+1){ dis[n] = dis[p[0]]+1; q.add(new int[]{n,p[1]+1}); prev[n] = p[0]; } } } } public ArrayList<Integer> getPath(int t,int[] prev){ ArrayList<Integer> path = new ArrayList<Integer>(); for(;t != -1;t = prev[t])path.add(t); Collections.reverse(path); return path; } @SuppressWarnings("unchecked") public void solve() { N = nextInt(); u = nextInt()-1; v = nextInt()-1; G = new ArrayList[N]; for(int i = 0;i < N;i++)G[i] = new ArrayList<Integer>(); for(int i = 0;i < N-1;i++){ int a = nextInt()-1; int b = nextInt()-1; G[a].add(b); G[b].add(a); } if(N % 2 == 1){ out.println("No"); return; } int[] dis1 = new int[N],dis2 = new int[N]; prev1 = new int[N]; prev2 = new int[N]; dijkstra(u,dis1,prev1); dijkstra(v,dis2,prev2); ArrayList<Integer> du = new ArrayList<Integer>(),dv = new ArrayList<Integer>(); for(int i = 0;i < N;i++){ if(dis1[i] == N/2)du.add(i); if(dis2[i] == N/2)dv.add(i); } if(du.size() == 0 || dv.size() == 0){ out.println("No"); return; } boolean[] used = new boolean[N]; for(int i = 0;i < du.size();i++){ for(int j = 0;j < dv.size();j++){ Arrays.fill(used, false); for(int n : getPath(du.get(i),prev1)){ used[n] = true; } boolean flag = true; for(int n : getPath(dv.get(j),prev2)){ if(used[n]){ flag = false; break; } } if(flag){ out.println("Yes"); return; } } } out.println("No"); } public static void main(String[] args) { out.flush(); new Main().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()); } }
RUPC2016 Day2 C ABNN is 17 years old forever
問題
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=C
当時は結構苦戦してたけど,今やるとUnionFindの練習ぐらいに感じる...
考察
村の合併をUnionFindで表現して,合併するごとにrankを増加させていき,最終的にrankが1の時は村とし,それ以外だったら町とする。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; public class Main{ int N,M; int[] union,rank; boolean[] used; public boolean same(int x,int y){ return find(x) == find(y); } public int find(int x){ if(union[x] == x)return x; return union[x] = find(union[x]); } public void unite(int x,int y){ x = find(x); y = find(y); if(x == y)return; if(x < y){ union[y] = x; rank[x] += rank[y]; }else{ union[x] = y; rank[y] += rank[x]; } } public void solve() { N = nextInt(); M = nextInt(); union = new int[N]; rank = new int[N]; used = new boolean[N]; for(int i = 0;i < N;i++)union[i] = i; Arrays.fill(rank, 1); for(int i = 0;i < M;i++){ int a = nextInt()-1; int b = nextInt()-1; unite(a,b); } int big = 0; int small = 0; for(int i = 0;i < N;i++){ int root = find(i); if(used[root])continue; used[root] = true; if(rank[root] == 1)small++; else big++; } out.println(Math.abs(big-small)); } public static void main(String[] args) { out.flush(); new Main().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()); } }
RUPC2016 Day2 B SEARIGHT LIVE FES
考察
外側の角の部分から上,横,下に分けて考える。
外側の人がa番目に存在する
内側の人がb番目に存在する
以上を前提とすると
- 外側の人が上(W-1番目まで)に存在する場合,a == bで判定
- 外側の人が横(W+1番目からW+H-2番目まで)に存在する場合,a-2 == bで判定
- 外側の人が下(W+H-2+1番目からW*2+H-2番目まで)に存在する場合,a-4 == bで判定
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main{ int W,H,N,a,b; public void solve() { W = nextInt(); H = nextInt(); N = nextInt(); int ans = 0; a = 1; b = 1; for(int i = 0;i < N;i++){ int p = nextInt(); if(p==0)a++; else b++; if(a <= W-1){ if(a == b)ans++; }else if(a == W){ continue; }else if(W + 1 <= a && a <= W + H - 2){ if(a - 2 == b)ans++; }else if(a == W + H - 2 + 1){ continue; }else if(a >= W + H){ if(a - 4 == b)ans++; } } out.println(ans); } public static void main(String[] args) { out.flush(); new Main().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()); } }
RUPC2016 Day2 A Gossip
考察
が答え。
つまり最初に情報を持っているアイドルの間隔を2で割った値の最大値が解だが,アイドル1とアイドルNがそれぞれ情報持っているアイドルの中で一番間隔が近いアイドルとの間隔も先程の解の候補に含める。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main{ int N,M; int[] a; public void solve() { N = nextInt(); M = nextInt(); a = new int[M]; for(int i = 0;i < M;i++)a[i] = nextInt(); int ans = 0; for(int i = 0;i <= M;i++){ if(i == 0)ans = Math.max(ans, a[i]-1); else if(i==M)ans = Math.max(ans,N-a[i-1]); else ans = Math.max(ans, (a[i]-a[i-1])/2); } out.println(ans); } public static void main(String[] args) { out.flush(); new Main().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()); } }