読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

Codeforces #397 Div1+Div2 D Artsem and Saunders

Codeforces

考察

多分これは,与えられた2つの式

  • g(h(x)) = x \{x \in m\}
  • h(g(x)) = f(x) \{x \in n\}

から、式を変形して考察を進めれば良いのかな?





参考:
pekempey.hatenablog.com




ソースコード

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

SRM

考察

うーん。これ思いつく発想ってどうやるんだろ。

「X[i]を決めた時のiより左、右に分けた時の左側、右側それぞれの文字列が左右対称であることを思いつく」 ことかなぁ

ソースコード

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

ABC

考察

  • 薬品を買うか買わないかの2通り,その選択をN回行う 2^N通り
  • 2^N通りの買い方の中から,比がMa:Mbになる薬品の買い方を見ていく。そして、その買い方の中で最小の予算を求める
  • dp[i][j][k] :=i番目の薬品までを見た時,タイプAの総量がj,タイプBの総量がkの時の最小の予算

ソースコード

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());
	}
}

最大流 蟻本読んだメモ

メモ

参考にした資料:

蟻本第2版 P188~P191
ネットワークフロー入門 http://hos.ac/slides/20150319_flow.pdf


最大流問題

  • 始点Sから終点Tまで各辺の容量を超えることなく流すことが出来る最大の流量を求める。

定義

  • G = 有向グラフ,V =頂点の集合,E = 辺の集合
  • s = 始点,t = 終点
  • e = 各辺(e \in E)
  • c(e) = 容量
  • f(e) = 実際に流れる流量

条件

  • 各辺e0 \le f(e) \le c(e)を満たす
  • s,tを含まない頂点v (v \in V\setminus\{s,t\})に対して,vへ入ってくる流量とvから出ていく流量が等しい。つまり、\sum_{e = *v}^{}f(e) = \sum_{e = v*}^{}f(e)

実際に最大流を求めるイメージ(Ford-Fulkerson法)

  •  C =  辺の容量(最大でも流せる流量)
  •  F =  辺に実際に流れている流量
1. 初期状態

f:id:tookunn:20170207185511p:plain

2.パス s - 1 - 2 - t に5流す

f:id:tookunn:20170207190100p:plain

3.パス s - 1 - 3 - t に5流す

f:id:tookunn:20170207190233p:plain

4. パス s - 2 - 1 - 3 - tに1流す(逆辺を通る)

f:id:tookunn:20170207190520p:plain

残余グラフ

グラフGの各辺eに対して逆辺rev(e)を追加したグラフ、

そのグラフ上のf(e) \lt c(e)であるe, f(rev(e)) \gt 0である逆辺rev(e)のみからなるグラフを残余グラフという。

残余グラフでは辺の容量の定義は以下の通りになる

  • 辺の容量u_f(e) = c(e) - f(e)
  • 逆辺の容量u_f(rev(e)) = f(e)

残余グラフ上のs-tパス(sからtまでf(e) \lt c(e),f(rev(e)) \gt 0の辺,逆辺を通る経路)を増加路(増加パス)という

先程のイメージ図3を残余グラフとして表すと下図のようになる
(この図場合、u_f(rev(e)) = 0の逆辺も表示しているが、取り除く場合もあるらしい)

f:id:tookunn:20170207215904p:plain

  • u_f(e) \lt c(e)なら流量をあとu_f(e)増やせる
  • u_f(rev(e)) \gt 0なら流量をあとu_f(rev(e))減らせる

実装(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 -

RUPC2016

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=D

考察にめちゃくちゃ時間を奪われたので,もっと考察する時間を短縮させたい。

考察

  •  L = query(1,r) - query(1,r-1)は区間[1,r-1]に含まれているr番目の値より大きい値の数
  •  R = query(l,N) - query(l+1,N)は区間[l+1,N]に含まれているl番目の値より小さい値の数

 区間[l+1,N]に含まれているl番目の値より大きい値の数 R'は,
 R' = 区間[l+1,N]の長さ - R

全体でl番目の値より大きい値の数 = L + R'

全体でl番目の値より大きい値の数が分かれば,l番目の値がこの数列の中で何番目に大きいのかが分かる。
それをN回繰り返せば元の数列が分かる。

解説:
http://www.slideshare.net/hcpc_hokudai/2016d-60984811

他の解説記事:

pekempeyさん
pekempey.hatenablog.com

kenkooooさん

kenkoooo.hatenablog.com

kenkoooo.hatenablog.com

kenkoooo.hatenablog.com

セグメント木を使う方法があったっぽいけど,全く思いつかなかった...。セグメント木を使う問題に慣れて無さ過ぎた...

ソースコード

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

Codeforces

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();
	}
}

RUCP2016 Day3 C 成長する点 - Growing Point -

RUPC2016

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=C

割と問題文通りにやるだけなのだけど、幾何っぽいというのもあって方針は合ってるが実装のバグが取れないのが辛かった

考察

一番最初に拠点0と最も近い餌との間に直線を追加、そこから下記の手順をM-1回繰り返していく

  1. 追加した直線と粘菌網に含まれていない餌の中で一番近い餌を選ぶ(この餌をX)
  2. その餌Xと粘菌網に含まれている中で一番近い餌を選ぶ(この餌をY)
  3. 餌Xと餌Yとの間に直線を追加し、その直線の長さを解に加える。1に戻る。

公式解説:
http://www.slideshare.net/hcpc_hokudai/2016day3c

ソースコード

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main implements Runnable{
	int N,M,X,Y;
	int[] px,py;
	double[] min;
	boolean[] used;
	public void solve() {
		N = nextInt();
		M = nextInt();
		X = nextInt();
		Y = nextInt();
		px = new int[N+1];
		py = new int[N+1];
		px[0] = X;
		py[0] = Y;
		for(int i = 1;i <= N;i++){
			px[i] = nextInt();
			py[i] = nextInt();
		}

		double ans = 0.0;
		used = new boolean[N+1];
		min = new double[N+1];

		int minInd1 = 1;
		for(int i = 1;i <= N;i++){
			double dis = Point2D.distance(px[0], py[0], px[i], py[i]);
			min[i] = dis;
			if(dis < min[minInd1]){
				minInd1 = i;
			}
		}

		Line2D.Double line = new Line2D.Double(px[0],py[0],px[minInd1],py[minInd1]);
		used[minInd1] = true;
		used[0] = true;
		ans += min[minInd1];

		for(int i = 0;i < M-1;i++){

			for(int j = 0;j <= N;j++){
				if(used[j])continue;
				min[j] = Math.min(min[j],line.ptSegDist(px[j], py[j]));
			}

			int minInd2 = -1;
			for(int j = 0;j <= N;j++){
				if(used[j])continue;
				if(minInd2 == -1)minInd2 = j;
				else if(min[j] < min[minInd2]){
					minInd2 = j;
				}
			}

			double minDis3 = Double.MAX_VALUE;
			int minInd3 = -1;
			for(int j = 0;j <= N;j++){
				if(used[j]){
					double dis = Point2D.distance(px[minInd2], py[minInd2], px[j], py[j]);
					if(dis  < minDis3){
						minDis3 = dis;
						minInd3 = j;
					}
				}
			}
			ans += minDis3;
			used[minInd2] = true;
			line.setLine(px[minInd2], py[minInd2], px[minInd3], py[minInd3]);
		}

		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();

	}
}