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()); } }
AtCoderBeginnerContest 021 D 多重ループ
考察
という性質から,内の複数のの間で重複した値が許されるということが分かる。
これは結局,までの範囲の数値から個の数値を重複を許し,取り出すことと同じ。
例えば,までの範囲の数値から個の数値を重複を許し,取り出すことを考えると
という風な整数の組を取り出すことができ,整数の組中の数値を昇順ソートするととなり問題文の条件()を満たす。
のように重複する値が入っていてもになり,これも条件を満たすことになる。
以上の事と整数の組の個数と解が等しいというところから重複組み合わせを求めれば解が求まることが分かる。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { static final int MOD = (int)1e9 + 7; int N,K; public long modPow(long x,long y){ if(y == 0){ return 1; } else if(y == 1){ return x; } else if(y % 2 == 0){ long z = modPow(x,y / 2); return z * z % MOD; }else{ return (modPow(x,y - 1) * x) % MOD; } } public long nCk(int n,int k) { long a = 1; for(int i = 0;i < k;i++) { a *= (n - i); a %= MOD; } long b = 1; for(int i = k;i >= 2;i--){ b *= i; b %= MOD; } return (a * modPow(b,MOD - 2) % MOD) % MOD; } public void solve() { N = nextInt(); K = nextInt(); out.println(nCk(N + K - 1,K)); } 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()); } }
第3回 ドワンゴからの挑戦状 予選 B ニコニコレベル
考察
文字列を左から順に見ていき,'2','5','?'の時で場合分けして状態を遷移する。
2の場合
- i番目の文字が2である状態からi+1番目の文字が5である状態に遷移する
5の場合
- i番目の文字が5である状態からi+1番目の文字が2である状態に遷移する
- しかし,ニコニコ文字列は252525..のように2から始まる文字列なので,i-1番目の文字が2である必要がある
?の場合
- 2,5の場合で行う遷移を両方行えばよい
= 番目の文字がであり,番目の文字まで見た時の連続した最長のニコニコ文字列の長さ
書いてる途中で気付いたけど,じゃなくてで良さそうな気がする(2,5の2通りしか考慮しないため)
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { String T; char[] ch; int N; int[][] dp; public void solve() { T = next(); ch = T.toCharArray(); N = T.length(); dp = new int[N+1][10]; //dp[i番目][i番目の文字] for(int i = 0;i < N;i++){ if(ch[i] == '?'){ if(dp[i][5]%2==1)dp[i + 1][2] = Math.max(dp[i+1][2],dp[i][5]+1); dp[i + 1][5] = Math.max(dp[i+1][5],dp[i][2]+1); }else if(ch[i] == '2'){ dp[i + 1][5] = Math.max(dp[i+1][5],dp[i][2]+1); }else if(ch[i] == '5'){ if(dp[i][5]%2==1)dp[i + 1][2] = Math.max(dp[i+1][2],dp[i][5]+1); } } int ans = 0; for(int i = 0;i < N+1;i++){ for(int j = 0;j < 10;j++){ ans = Math.max(ans,dp[i][j]); } } out.println(ans/2 * 2); } 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()); } }