RUPC2016 Day1 F リレー / Relay
考察
基本的には公式解説にある通りの考え方で何となく理解しましたが,オイラーツアーを行う実装がイメージできなかったので,mayokoさんの解説記事のコードを参考にさせていただきました。セグメントツリーは蟻本写経しました。
公式解説よりうまく説明できないと思うので,メモ程度に書いていきます。
まず,求めたいのが木の直径を構成する端点 u,v なので,それらの端点をdouble sweepというアルゴリズムを使って求める。
double sweep
- 木から適当に頂点を決めてそこから最も距離が遠い頂点を v
- vから最も距離が遠い頂点を u
- v と u はその木の直径を構成する頂点となる。つまりv と u の距離がその木の直径となる。
その後 u,v を根としてそれぞれからオイラーツアーを行う。
(u,v)から付け替える辺 e を除いて到達できる最も遠い頂点を決め距離を求める。
オイラーツアーでやること
- depth[v] = 根から頂点vまでの距離
- first[v] = 根から深さ優先探索をして最初に頂点vに到達した時点のそれまでの頂点を訪れた回数
- last[v] = 根から深さ優先探索をして最後に頂点vに到達した時点のそれまでの頂点を訪れた回数
- 深さ優先探索をしつつ頂点を訪れるたびに回数をカウントする
- 初めて訪れた頂点でfirst[v]に訪れた回数を記録,depth[v]に根からの距離を記録
- その頂点から出ていき,もう訪れない時はlast[v]に訪れた回数を記録する
公式解説:
立命合宿 2016 - 立命館大学情報理工学部プロジェクト団体プログラミングコンテスト部門 RiPPro
参考にした記事等:
mayokoex.hatenablog.com
あとは公式解説内にあるリンク先とか参考にしました。
ソースコード
恐らく僕の実装があまり良くないらしくてスタックのサイズを指定しないとRuntime Errorになってしまいます。
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; public class Main implements Runnable{ int N,num,size; int[] depth,first,last,segment; ArrayList<Edge>[] graph; private class Edge{ int to,weight; public Edge(int to,int weight){ this.to = to; this.weight = weight; } } public void init(int n){ size = 1; while(size < n)size<<=1; segment = new int[2*size]; for(int i = 0;i < 2 * size - 1;i++)segment[i]=Integer.MIN_VALUE; } public void update(int k,int a){ k += size - 1; segment[k] = a; while(k > 0){ k = (k - 1) / 2; segment[k] = Math.max(segment[k * 2 + 1], segment[k * 2 + 2]); } } public int query(int a,int b,int k,int l,int r){ if(r <= a || b <= l)return Integer.MIN_VALUE; if(a <= l && r <= b)return segment[k]; int vl = query(a,b,k * 2 + 1,l,(l + r)/2); int vr = query(a,b,k * 2 + 2,(l + r)/2,r); return Math.max(vl, vr); } public int[] dfs(int prev,int now){ int[] ret = {now,0}; for(Edge edge : graph[now]){ if(edge.to != prev){ int[] tmp = dfs(now,edge.to); tmp[1]+=edge.weight; if(ret[1] < tmp[1])ret = tmp; } } return ret; } //木の直径の端点u,vを求める public int[] doubleSweep(){ int u = dfs(-1,0)[0]; int v = dfs(-1,u)[0]; return new int[]{u,v}; } public void eulerTour(int prev,int now,int dis){ depth[now] = dis; first[now] = num++; for(Edge edge : graph[now]){ if(edge.to != prev){ eulerTour(now,edge.to,dis+edge.weight); num++; } } last[now] = num; } @SuppressWarnings("unchecked") public void solve() { N = nextInt(); graph = new ArrayList[N]; for(int i = 0;i < N;i++)graph[i] = new ArrayList<Edge>(); for(int i = 0;i < N-1;i++){ int p = nextInt(); int w = nextInt(); graph[i+1].add(new Edge(p,w)); graph[p].add(new Edge(i+1,w)); } int[] tmp = doubleSweep(); int u = tmp[0]; int v = tmp[1]; int ans = 0; int M = 2 * N; depth = new int[M]; first = new int[M]; last = new int[M]; //u num = 0; eulerTour(-1,u,0); init(2*M); for(int i = 0;i < N;i++){ update(first[i],depth[i]); } for(int i = 0;i < N;i++){ for(Edge edge : graph[i]){ int to = edge.to; if(depth[edge.to] < depth[i])to = i; int vl = query(0,first[to],0,0,size); int vr = query(last[to],M-1,0,0,size); ans = Math.max(ans,Math.max(vl, vr)+edge.weight); } } Arrays.fill(depth, 0); Arrays.fill(first,0); Arrays.fill(last, 0); Arrays.fill(segment, Integer.MIN_VALUE); num = 0; //v eulerTour(-1,v,0); for(int i = 0;i < N;i++){ update(first[i],depth[i]); } for(int i = 0;i < N;i++){ for(Edge edge : graph[i]){ int to = edge.to; if(depth[edge.to] < depth[i])to = i; int vl = query(0,first[to],0,0,size); int vr = query(last[to],M-1,0,0,size); ans = Math.max(ans,Math.max(vl, vr)+edge.weight); } } out.println(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 Day1 E 28
考察
良い整数は各桁に,2または8しか現れないのでまでの正整数はそこまで多くない。
なので、考えられる良い整数はすべて生成しておき、を割り切ることが出来る良い整数だけを抜き出しておく。
抜き出した良い整数の積からNが構成できるかどうかをメモ化全探索する。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.NoSuchElementException; public class Main { long N; ArrayList<Long> all,sub; HashMap<Long,Integer>[] map; public void createGoodNumber(){ all = new ArrayList<Long>(); ArrayDeque<Long> q = new ArrayDeque<Long>(); q.add(2L); q.add(8L); while(q.size() > 0){ long L = q.poll(); all.add(L); if(L >= (long)1e17)continue; q.add(L * 10 + 2); q.add(L * 10 + 8); } Collections.sort(all); } public int dfs(int i,long n){ if(n == 1){ return 0; } if(map[i].containsKey(n)){ return map[i].get(n); } int ret = -1; for(int j = i;j < sub.size();j++){ if(n % sub.get(j) == 0){ int tmp = dfs(j,n / sub.get(j)); if(tmp+1 > 0){ map[i].put(n, tmp+1); return tmp+1; } } } map[i].put(n,ret); return ret; } @SuppressWarnings("unchecked") public void solve() { N = nextLong(); createGoodNumber(); sub = new ArrayList<Long>(); for(int i = 0;i < all.size();i++){ if(N % all.get(i) == 0)sub.add(all.get(i)); } if(N == 1){ out.println(-1); return; } map = new HashMap[sub.size()]; for(int i = 0;i < sub.size();i++){ map[i] = new HashMap<Long,Integer>(); } if(sub.size() == 0){ out.println(-1); }else{ out.println(dfs(0,N)); } } 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 Day1 D スキャナー / Scanner
考察
当初、貪欲に時間のかかる紙から選んで、早くスキャンが終わっているスキャナーに振り分けた。が、通らなかった。
3つ目のスキャナーのスキャン終了時間は、残り2つのスキャナーのスキャン終了時間が分かれば分かる。(この考察は解説見る前に気付いたが、ここからどうすればよいのか分からなかった。(メモ))
※Javaででギリギリぐらいだったので以下記事のようににした方が良い。
参考にさせていただいた解説記事:
pakapa104.hatenablog.com
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { int N; int[] T; boolean[][][] dp; public void solve() { N = nextInt(); T = new int[N]; int sum = 0; for(int i = 0;i < N;i++){ T[i] = nextInt(); sum += T[i]; } dp = new boolean[N + 1][2500 + 1][2500 + 1]; dp[0][0][0] = true; for(int i = 0;i < N;i++){ for(int j = 0;j < 2500 + 1;j++){ for(int k = 0;k < 2500 + 1;k++){ if(!dp[i][j][k])continue; if(j + T[i] < 2500)dp[i + 1][j + T[i]][k] = true; if(k + T[i] < 2500)dp[i + 1][j][k + T[i]] = true; dp[i + 1][j][k] = true; } } } int ans = Integer.MAX_VALUE; for(int i = 0;i < 2500 + 1;i++){ for(int j = 0;j < 2500 + 1;j++){ if(dp[N][i][j]){ ans = Math.min(ans, Math.max(sum - i - j,Math.max(i, j))); } } } 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 Day1 C 足し算掛け算 / AddMul
考察
出現するアルファベットの数を、1~9までの出来るだけ大きい数を括弧でくくれるようにカウントする。
を文字列Sの中に回出現するアルファベットの数とする。
もし,が1以上だったらをに加える、それ以外だったら何も加えない。
そして、を2~9まで見ていき、その中で以下の処理を行う
- が以上で, なら,ならをに加える。
- がで,なら,ならをansに加える。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.NoSuchElementException; public class Main { int N; String S; int[] a; @SuppressWarnings("unchecked") public void solve() { N = nextInt(); S = next(); a = new int[26]; for(int i = 0;i < N;i++){ if(S.charAt(i) >= 'a' && S.charAt(i) <= 'z') a[S.charAt(i)-'a']++; } ArrayList<Integer>[] list = new ArrayList[10]; for(int i = 0;i < 10;i++){ list[i] = new ArrayList<Integer>(); } for(int i = 0;i < 26;i++){ if(a[i] == 0)continue; for(int j = 9;j >= 1;j--){ if(a[i]%j==0){ list[j].add(i); break; } } } int ans = list[1].size() > 0 ? (list[1].size() - 1)* 2 + 1 : 0; for(int i = 2;i < 10;i++){ if(list[i].size() >= 2){ if(ans == 0)ans += (list[i].size() -1) * 2 + 1 + 4; else ans += (list[i].size() -1) * 2 + 4 + 1 + 1; }else if(list[i].size() == 1){ if(ans == 0)ans += 3; else ans += 4; } } 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 Day1 B ハミング距離 / Hamming Distance
考察
ハミング距離がである値の中で最大のものを求めなければならないので、を左から見ていき,'0'である文字を個'1'に変える。
もし、'0'である文字が個に満たない場合はを右から見ていき,先程'0'から'1'に変えていない文字なおかつ'1'である文字を'0'に変えていく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { int N,D; String X; public void solve() { N = nextInt(); X = next(); D = nextInt(); char[] ch = X.toCharArray(); boolean[] used = new boolean[N]; int change = 0; for(int i = 0;i < N;i++){ if(change >= D)break; if(ch[i] == '0'){ used[i] = true; change++; ch[i] = '1'; } } for(int i = N - 1;i >= 0;i--){ if(change >= D)break; if(!used[i] && ch[i] == '1'){ change++; ch[i] = '0'; } } out.println(String.valueOf(ch)); } 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 Day1 A 秤 / Steelyard
考察
吊らされたおもりと対称的におもりを吊っていく。
具体的にはに同じ重さのおもりを吊っていく。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.NoSuchElementException; public class Main { int L,N; int[] x,w; ArrayList<Integer>[] list; @SuppressWarnings("unchecked") public void solve() { L = nextInt(); N = nextInt(); x = new int[N]; w = new int[N]; list = new ArrayList[2 * L + 1]; for(int i = 0;i < 2 * L + 1;i++){ list[i] = new ArrayList<Integer>(); } for(int i = 0;i < N;i++){ x[i] = nextInt(); w[i] = nextInt(); list[-x[i] + L].add(w[i]); } out.println(N); for(int i = 0;i < 2 * L + 1;i++){ for(int weight : list[i]){ out.println((i-L) + " " + weight); } } } 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()); } }
AtCoderBeginnerContest 010 D 浮気予防
考察
当初、複数のを含む連結成分を探して,橋を見つけてそれを消していけば良いのかなぐらいに考えてたけど、そこから何も分からなかったので解説を見て最大フローを求める問題と分かった。
フローを扱う問題を解いたことなかったので蟻本や,以下記事を参考にしました。
参考にさせていただいた記事:
even-eko.hatenablog.com
公式の解説スライドがとても分かりやすいので、それを見れば大体どういうことをすれば良いのかなんとなく分かった。
- 個のに対して,始点を0(高橋君のID),終点をN(個目の頂点を追加)とするために個のそれぞれと終点Nとの間に辺を追加する
- 通常の辺と逆辺の分、つまり1つの友人関係に対して2つの辺を追加していく(問題の設定上無向グラフなので)
あとはFord-Fulkerson法と呼ばれる最大フローを求めるアルゴリズムを使ってやると求まる。らしい
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; public class Main { static final int INF = (int)1e9 + 7; int N,G,E; ArrayList<Edge>[] graph; boolean[] used; class Edge{ int to,cap,rev; public Edge(int to,int cap,int rev){ this.to = to; this.cap = cap; this.rev = rev; } } public void addEdge(int from,int to,int cap){ graph[from].add(new Edge(to,cap,graph[to].size())); graph[to].add(new Edge(from,0,graph[from].size()-1)); } public int dfs(int v,int t,int f){ if(v == t)return f; used[v] = true; for(int i = 0;i < graph[v].size();i++){ Edge e = graph[v].get(i); if(!used[e.to] && e.cap > 0){ int d = dfs(e.to,t,Math.min(f,e.cap)); if(d > 0){ e.cap -= d; graph[e.to].get(e.rev).cap += d; return d; } } } return 0; } public int maxFlow(int s,int t){ int flow = 0; used = new boolean[N+1]; for(;;){ Arrays.fill(used,false); int f = dfs(s,t,INF); if(f == 0)return flow; flow += f; } } @SuppressWarnings("unchecked") public void solve() { N = nextInt(); G = nextInt(); E = nextInt(); graph = new ArrayList[N + 1]; for(int i = 0;i < N + 1;i++){ graph[i] = new ArrayList<Edge>(); } for(int i = 0;i < G;i++){ int p = nextInt(); addEdge(p,N,1); } for(int i = 0;i < E;i++){ int a = nextInt(); int b = nextInt(); addEdge(a,b,1); addEdge(b,a,1); } out.println(maxFlow(0,N)); } 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()); } }