yukicoder No514 宝探し3
考察
- 座標と座標のマンハッタン距離はである。(とする)
- そこで、座標と座標のマンハッタン距離を考える。(y座標を求めるためにx座標を0に固定する)
- すると、となり、と出来る。これでは求まった。
- あとはとなり、座標が求まった。(なので)
ソースコード
import sys def query(p): print(p[0],p[1]) sys.stdout.flush() ret = int(input()) if ret == 0: sys.exit(0) return ret a=query((0,0)) b=query(((a,0))) query((a-b//2,b//2))
Codeforces #397 Div1+Div2 D Artsem and Saunders
考察
多分これは,与えられた2つの式
から、式を変形して考察を進めれば良いのかな?
@tookunn_1213 この単射ではないっていうのはh(a) = h(b)の場合,h(a) = h(b) = Aとして、g(h(a)) = a,g(h(b)) = bで,g(A) = a,bはaかbどちらかに一意に定まっていないということか
— tookunn (@tookunn_1213) 2017年2月16日
@tookunn_1213 h(g(x))とh(g(y))は同一の値になることが分かって、g(h(g(x))) = g(h(g(y)))でなきゃいけないからg(x) = g(y)であるということかな(説明が下手)
— tookunn (@tookunn_1213) 2017年2月16日
@tookunn_1213 メモhttps://t.co/phi9xhu1uZ
— tookunn (@tookunn_1213) 2017年2月16日
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashMap; import java.util.NoSuchElementException; public class D { int N; int[] g; ArrayList<Integer> h; HashMap<Integer,Integer> map; public void solve() { N = nextInt(); g = new int[N]; h = new ArrayList<Integer>(); map = new HashMap<Integer,Integer>(); for(int i = 0;i < N;i++){ int f = nextInt()-1; /* * fの値ごとにまとめて適当に値を割り当てる * 今回はmap.size()を割り当てる * hには重複なしのfの値を挿入 */ if(!map.containsKey(f)){ map.put(f, map.size()); h.add(f); } //fの値をkeyにして適当に割り当てた値をg[i]に g[i] = map.get(f); } for(int i = 0;i < map.size();i++){ //g(h(x)) = x if(g[h.get(i)] != i){ out.println(-1); return; } } out.println(map.size()); for(int i = 0;i < N;i++){ if(i != 0)out.print(" "); out.print(g[i]+1); } out.println(); for(int i = 0;i < map.size();i++){ if(i != 0)out.print(" "); out.print(h.get(i)+1); } out.println(); } public static void main(String[] args) { out.flush(); new D().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()); } }
SRM 708 Div2 Hard
考察
うーん。これ思いつく発想ってどうやるんだろ。
「X[i]を決めた時のiより左、右に分けた時の左側、右側それぞれの文字列が左右対称であることを思いつく」 ことかなぁ
@tookunn_1213
— ばたこ (@btk15049) 2017年2月9日
dp[i][j]:=S[0...i]とR[0...j]の共通部分文字列の個数
の間違いでした
失礼しました
@tookunn_1213 文字列S[i-1] = 文字列R[j-1]の時,dp[i][j] += dp[i-1][j-1]するのは,S[i-1] = R[j-1]からS[i-1]のR[j-1]のペアを回文に含める場合とそうでない場合があるからというのもなんとなく分かった
— tookunn (@tookunn_1213) 2017年2月10日
@tookunn_1213 学校にいるので、帰宅後用メモ pic.twitter.com/aLsmMULoUJ
— tookunn (@tookunn_1213) 2017年2月10日
ソースコード
public class PalindromicSubseq2 { static final int MOD = (int)1e9 + 7; public int solve(String s){ char[] S = s.toCharArray(); char[] R = new StringBuilder(s).reverse().toString().toCharArray(); int N = S.length; long[][] dp = new long[N+1][N+1]; for(int i = 0;i < N+1;i++){ dp[i][0] = 1; dp[0][i] = 1; } for(int i = 1;i < N + 1;i++){ for(int j = 1;j < N + 1;j++){ dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + MOD) % MOD; dp[i][j] %= MOD; if(S[i-1] == R[j-1]){ dp[i][j] += dp[i-1][j-1] % MOD; dp[i][j] %= MOD; } } } long ans = 0; for(int i = 1;i < N + 1;i++){ ans ^= (dp[i-1][N-i] * i % MOD); } return (int)ans; } }
AtCoderBeginnerContest 054 D
考察
- 薬品を買うか買わないかの2通り,その選択をN回行う 通り
- 通りの買い方の中から,比がになる薬品の買い方を見ていく。そして、その買い方の中で最小の予算を求める
- 番目の薬品までを見た時,タイプの総量が,タイプの総量がの時の最小の予算
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { static final int INF = (int)1e9 + 7; int N,Ma,Mb; int[] A,B,C; public void solve() { N = nextInt(); Ma = nextInt(); Mb = nextInt(); A = new int[N]; B = new int[N]; C = new int[N]; for(int i = 0;i < N;i++){ A[i] = nextInt(); B[i] = nextInt(); C[i] = nextInt(); } int[][][] dp = new int[N+1][444][444]; for(int i = 0;i < N + 1;i++){ for(int j = 0;j < 444;j++){ for(int k = 0;k < 444;k++){ dp[i][j][k] = INF; } } } dp[0][0][0] = 0; for(int i = 0;i < N;i++){ for(int j = 0;j < 444 - A[i];j++){ for(int k = 0;k < 444 - B[i];k++){ int a = j + A[i]; int b = k + B[i]; dp[i+1][j][k] = Math.min(dp[i+1][j][k], dp[i][j][k]); dp[i+1][a][b] = Math.min(dp[i+1][a][b],dp[i][j][k]+C[i]); } } } int ans = INF; int max = Math.max(Ma,Mb); for(int i = 1;i * max < 444;i++){ ans = Math.min(ans,dp[N][i*Ma][i*Mb]); } if(ans == INF){ out.println(-1); }else{ 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()); } }
最大流 蟻本読んだメモ
最大流問題
- 始点Sから終点Tまで各辺の容量を超えることなく流すことが出来る最大の流量を求める。
定義
- 有向グラフ,頂点の集合,辺の集合
- 始点,終点
- 各辺
- 容量
- 実際に流れる流量
条件
- 各辺はを満たす
- を含まない頂点に対して,へ入ってくる流量とから出ていく流量が等しい。つまり、
実際に最大流を求めるイメージ(Ford-Fulkerson法)
- 辺の容量(最大でも流せる流量)
- 辺に実際に流れている流量
1. 初期状態
2.パス s - 1 - 2 - t に5流す
3.パス s - 1 - 3 - t に5流す
4. パス s - 2 - 1 - 3 - tに1流す(逆辺を通る)
残余グラフ
グラフの各辺に対して逆辺を追加したグラフ、
そのグラフ上のである, である逆辺のみからなるグラフを残余グラフという。
残余グラフでは辺の容量の定義は以下の通りになる
- 辺の容量
- 逆辺の容量
残余グラフ上のパス(sからtまでの辺,逆辺を通る経路)を増加路(増加パス)という
先程のイメージ図3を残余グラフとして表すと下図のようになる
(この図場合、の逆辺も表示しているが、取り除く場合もあるらしい)
- なら流量をあと増やせる
- なら流量をあと減らせる
実装(Java)
蟻本の写経です
import java.util.ArrayList; import java.util.Arrays; static final int INF = (int)1e9 + 7; ArrayList<Edge>[] G; 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){ G[from].add(new Edge(to,cap,G[to].size())); G[to].add(new Edge(from,0,G[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 < G[v].size();i++){ Edge e = G[v].get(i); if(!used[e.to] && e.cap > 0){ int d = dfs(e.to,t,Math.min(f, G[v].get(i).cap)); if(d > 0){ e.cap -= d; G[e.to].get(e.rev).cap += d; return d; } } } return 0; } public int max_flow(int s,int t){ int flow = 0; for(;;){ Arrays.fill(used, false); int f = dfs(s,t,INF); if(f == 0)return flow; flow += f; } }
RUCP2016 Day3 D Complex Oracle - Complex Oracle -
問題
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=D
考察にめちゃくちゃ時間を奪われたので,もっと考察する時間を短縮させたい。
考察
は,
全体で番目の値より大きい値の数が分かれば,番目の値がこの数列の中で何番目に大きいのかが分かる。
それをN回繰り返せば元の数列が分かる。
解説:
http://www.slideshare.net/hcpc_hokudai/2016d-60984811
他の解説記事:
pekempeyさん
pekempey.hatenablog.com
kenkooooさん
セグメント木を使う方法があったっぽいけど,全く思いつかなかった...。セグメント木を使う問題に慣れて無さ過ぎた...
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; public class Main implements Runnable{ int N; int[] ans; long[] left,right; public long query(int l,int r){ if(l == 1){ if(left[r] == -1){ out.println("? " + l + " " + r); out.flush(); return left[r] = nextLong(); }else{ return left[r]; } }else{ if(right[l] == -1){ out.println("? " + l + " " + r); out.flush(); return right[l] = nextLong(); }else{ return right[l]; } } } public void solve() { N = nextInt(); ans = new int[N]; left = new long[N+1]; right = new long[N+1]; Arrays.fill(left, -1); Arrays.fill(right, -1); for(int i = 1;i <= N;i++){ int L = 0; int R = 0; if(i - 1 >= 1){ L = (int)(query(1,i) - query(1,i-1)); } if(i + 1 <= N){ R = (int)(query(i,N) - query(i+1,N)); R = (N - (i + 1) + 1) - R; } ans[i-1] = N - L - R; } out.print("!"); for(int i = 0;i < N;i++){ out.print(" " + ans[i]); } out.println(); } 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(); } }
Codeforces #395 Div2 A~C
A問題
考察
周期Nと周期Mが重なる数をカウントする
Editorialを見ると,Z / lcm(N,M)が解になるらしい。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class A { int N,M,Z; int[] a; public void solve() { N = nextInt(); M = nextInt(); Z = nextInt(); a = new int[Z + 1]; for(int i = N;i <= Z;i+=N){ a[i] |= 1; } for(int i = M;i <= Z;i+=M){ a[i] |= 2; } int ans = 0; for(int i = 0;i <= Z;i++){ if(a[i] == 3){ ans++; } } out.println(ans); } public static void main(String[] args) { out.flush(); new A().solve(); out.close(); } }
B問題
考察
i回目のstep時、i番目より前のペアはもう値が交換されることはない。
数列aのi番目とN+1-i番目のペアはiを2で割った余りが1の場合、値を入れ替える
計算量はO(N)
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class B { int N; int[] a; public void solve() { N = nextInt(); a = new int[N]; for(int i = 0;i < N;i++){ a[i] = nextInt(); } for(int i = 0;i < N / 2;i++){ if(i % 2 == 0){ int tmp = a[i]; a[i] = a[N-1-i]; a[N-1-i] = tmp; } } for(int i = 0;i < N;i++){ if(i != 0)out.print(" "); out.print(a[i]); } out.println(); } public static void main(String[] args) { out.flush(); new B().solve(); out.close(); } }
C問題
考察
まず,適当にrootを決めてそこからBFSをしてrootと色が違う頂点に達したらその頂点を覚えておく。
その覚えた頂点が取り除く頂点の候補である。
そして、その頂点を取り除いた時に、残った複数の部分木がそれぞれ単一色の木になるかをBFSで調べていく。
正直TLEになるかと思ったけど800msぐらいで通った。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.NoSuchElementException; public class C { int N; int[] c; ArrayList<Integer>[] graph; boolean[] use; public int root(int v) { for (int u : graph[v]) { if (use[u]) continue; use[u] = true; return root(u); } return v; } @SuppressWarnings("unchecked") public void solve() { N = nextInt(); graph = new ArrayList[N]; for (int i = 0; i < N; i++) { graph[i] = new ArrayList<Integer>(); } for (int i = 0; i < N - 1; i++) { int u = nextInt() - 1; int v = nextInt() - 1; graph[u].add(v); graph[v].add(u); } c = new int[N]; for (int i = 0; i < N; i++) { c[i] = nextInt(); } use = new boolean[N]; use[0] = true; int root = root(0); ArrayList<Integer> takeNode = new ArrayList<Integer>(); ArrayDeque<Integer> q = new ArrayDeque<Integer>(); boolean[] used = new boolean[N]; q.add(root); while (q.size() > 0) { int p = q.poll(); if (used[p]) continue; used[p] = true; for (int u : graph[p]) { if (c[u] != c[p]) { takeNode.add(u); } else { q.add(u); } } } takeNode.add(root); for (int i : takeNode) { ArrayDeque<Integer> qq = new ArrayDeque<Integer>(); boolean[] visited = new boolean[N]; boolean flag = true; for (int j : graph[i]) { qq.add(j); visited[j] = true; } visited[i] = true; out : while (qq.size() > 0) { int p = qq.poll(); for (int k : graph[p]) { if (visited[k]) continue; visited[k] = true; if (c[k] != c[p]) { flag = false; break out; } else { qq.add(k); } } } if (flag) { out.println("YES"); out.println(i + 1); return; } } out.println("NO"); } public static void main(String[] args) { out.flush(); new C().solve(); out.close(); } }