2017-08-15

SRM719 Div2 Hard

SRM

問題

TopCoder Statistics - Problem Statement

考察

根ノードから任意のノードまでのパスのXORの計算を行う。

xor[V] = 根ノードから任意のノードVまでのXOR

そうすると任意のノードVから他の任意のノードUまでのパスのXORの計算結果は
xor[V] ^ xor[U]になる。これはXORの性質を考えると分かる。
A xor B = X
A xor C = Y
X xor Y = B xor C

詳しくはkmjpさんの解説記事で
kmjp.hatenablog.jp

ソースコード

下のコードでやっていることは

ノード0から任意のノードvまでのXORを求めとく。
制約からノード数<=1000なので、パスの始点ノードsと終点ノードtを全探索してxor[s]^xor[t]をSetに挿入。
0<=w[i]<=1023なのでXORの計算結果は高々1024通りしかない。
あとはSetから重複を許して値を二つ選んでXORの最大値を求める。

import java.util.HashSet;
import java.util.Set;
public class TwoDogsOnATree{

        public int maximalXorSum(int[] parent,int[] w){

            int N = parent.length + 1;
            int[] xor = new int[N];

            for(int i = 1;i < N;i++){
                int v = i;

                while(v > 0){
                    xor[i] ^= w[v-1];
                    v = parent[v-1];
                }
            }
            Set<Integer> xorSet = new HashSet<>();
            for(int i = 0;i < N;i++){
                for(int j = 0;j < N;j++){
                    xorSet.add(xor[i]^xor[j]);
                }
            }

            int ans = 0;
            for(int a : xorSet){
                for(int b : xorSet){
                    ans = Math.max(ans,a^b);
                }
            }
            return ans;
        }
    }

2017-08-01

AtCoder Regular Contest 079 D Decrease (Contestant ver.)

ARC

問題

arc079.contest.atcoder.jp

考察

・公式解説
Editorial - AtCoder Regular Contest 079 | AtCoder

公式解説見ながらソースコード中に考えたこと書きました。

実験して解法につながる性質とか規則性見つけるの難しい。
こういう問題に出くわしたらどうするのが良いのだろう

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	long K;
	int N;

	public void solve() {
		K = nextLong();
		N = 50;

		long[] a = new long[N];

		//解説の通り、[0,1,2,3,4,5,6...,N-1]にする
		for(int i = 0;i < 50;i++){
			a[i] = i;
		}

		/*
		 * 1番目,2番目,3番目,4番目,5番目,...N番目,1番目,2番目,3番目,..みたいな感じ
		 * で1～N番目の要素を順番にそれぞれに対して操作を合計K回行う
		 */

		long x = K / N;//xはそれぞれの要素に必ず操作する回数
		long y = K % N;//先頭からy番目まで追加で操作を行う

		for(int i = 0;i < N;i++){

			a[i] += N * x;//x回N増やす
			a[i] -= (N-1)* x;//他の要素の数×一つの要素に対して必ず操作する回数
			a[i] -= y;//全ての要素の中で追加で操作する回数

			if(i < y){
				a[i] += N+1;//今見ている要素に対して追加で操作を行うとき
			}
		}

		out.println(N);
		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 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());
	}
}

2017-05-06

yukicoder No514 宝探し３

yukicoder

問題

http://yukicoder.me/problems/no/514

考察

座標 $(0,0)$ と座標 $(AX,AY)$ のマンハッタン距離は $AX+AY$ である。（ $AX+AY=A$ とする）

そこで、座標 $(AX+AY,0)$ と座標 $(AX,AY)$ のマンハッタン距離 $AX+AY-AX+AY=B$ を考える。（y座標を求めるためにx座標を0に固定する）

すると、 $B=AY+AY=2*AY$ となり、 $AY=B/2$ と出来る。これで $AY$ は求まった。

あとは $A-AY=AX$ となり、座標 $(AX,AY)$ が求まった。( $A=AX+AY$ なので)

ソースコード

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

2017-02-16

Codeforces #397 Div1+Div2 D Artsem and Saunders

Codeforces

問題

codeforces.com

考察

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

$g(h(x)) = x \{x \in m\}$

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

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

@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日

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

2017-02-12

SRM 708 Div2 Hard

SRM

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14536

考察

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

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

@tookunn_1213
dp[i][j]:=S[0...i]とR[0...j]の共通部分文字列の個数
の間違いでした
失礼しました
— ばたこ (@btk15049) 2017年2月9日

@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;
	}
}

2017-02-12

AtCoderBeginnerContest 054 D

ABC

問題

abc054.contest.atcoder.jp

考察

薬品を買うか買わないかの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());
	}
}

2017-02-07

最大流　蟻本読んだメモ

メモ

参考にした資料：

蟻本第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) =$ 実際に流れる流量

条件

各辺 $e$ は $0 \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;
	}
}

tookunn’s diary

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

SRM719 Div2 Hard

問題

考察

ソースコード

AtCoder Regular Contest 079 D Decrease (Contestant ver.)

問題

考察

ソースコード

yukicoder No514 宝探し３

問題

考察

ソースコード

Codeforces #397 Div1+Div2 D Artsem and Saunders

問題

考察

ソースコード

SRM 708 Div2 Hard

問題

考察

ソースコード

AtCoderBeginnerContest 054 D

問題

考察

ソースコード

最大流　蟻本読んだメモ

参考にした資料：

最大流問題

定義

条件

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

1. 初期状態

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

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

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

残余グラフ

実装(Java)