tookunn’s diary

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

AtCoderBeginnerContest 054 D

考察

  • 薬品を買うか買わないかの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 -

問題

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

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 -

問題

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

	}
}

RUCP2016 Day3 B 周期数列 - Periodic Sequence -

考察

考えられる周期tをそれぞれ試していくだけ

N = ktから,tはNを割り切る数なのでそこまで多くない

ソースコード

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

public class Main implements Runnable{
	int N;
	int[] S;
	public void solve() {
		N = nextInt();
		S = new int[N];
		for(int i = 0;i < N;i++){
			S[i] = nextInt();
		}

		ArrayList<Integer> ts = new ArrayList<Integer>();
		for(int i = 1;i <= N;i++){
			if(N%i==0){
				ts.add(i);
			}
		}
		int ans = 0;
		for(int t : ts){

			int k = N / t;
			boolean flag = false;
			for(int i = 0;i < t;i++){
				for(int j = 0;j < k;j++){
					if(S[j * t + i]==S[i])continue;
					flag = true;
					break;
				}
				if(flag)break;
			}

			if(!flag){
				ans = Math.max(ans, k);
			}
		}

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

	}
}

Codeforces #389 Div2 A~C


考察

rとdを導出する式を見つけ出すのに結構時間掛かってしまった

r = ceil(K/(2M))
d = ceil( (K-2M(r-1))/2)
RかLかは偶奇を見ればよい

ソースコード

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

public class A {
	int N,M,K;
	public void solve() {
		N = nextInt();
		M = nextInt();
		K = nextInt();


		int r = (int)Math.ceil(((double)K/(2*M)));
		int d = (int)Math.ceil((K-((double)r-1)*2*M)/2);
		char s = K%2==1 ? 'L' : 'R';
		out.println(r + " " + d + " " + s);
	}

	public static void main(String[] args) {
		out.flush();
		new A().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を同時に一文字ずつ見ていき,その文字の対応を保持していく。

alpha[a] == b && alpha[b] == aの場合は既にaとbの対応が出来ているのでスルー

alpha[a] == -1 && alpha[b] == -1の場合はまだa,b両方に何も対応が出来ていないので,aとbを対応付ける

それ以外の場合は-1

その後はalphaを順に見ていき対応する文字を出力していく。

ソースコード

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 B {
	String s,t;
	int[] alpha;
	public void solve() {
		s = next();
		t = next();
		alpha = new int[26];
		Arrays.fill(alpha,-1);
		for(int i = 0;i < s.length();i++){

			int a = s.charAt(i) - 'a';
			int b = t.charAt(i) - 'a';
			if(alpha[a] == b && alpha[b] == a){
				continue;
			}else if(alpha[a] == -1 && alpha[b] == -1){
				alpha[b] = a;
				alpha[a] = b;
			}else{
				out.println(-1);
				return;
			}
		}
		ArrayList<int[]> ans = new ArrayList<int[]>();
		for(int i = 0;i < 26;i++){
			if(i == alpha[i])continue;
			if(alpha[i] == -1)continue;
			if(i == alpha[alpha[i]]){
				ans.add(new int[]{i,alpha[i]});
				alpha[alpha[i]] = -1;
				alpha[i] = -1;
			}
		}

		out.println(ans.size());
		for(int[] i : ans){
			char a = (char)(i[0]+'a');
			char b = (char)(i[1]+'a');
			out.println(a + " " + b);
		}
	}

	public static void main(String[] args) {
		out.flush();
		new B().solve();
		out.close();
	}
}

考察

これはEditorial見たけどいまいちよく分からない。
codeforces.com

とりあえず,進んだ方向と逆方向に進むことがわかったら,その度にカウントするみたいな感じっぽい。

与えられた文字列Sを先頭から1文字ずつ見ていき,文字の対応を保持する。

見ている文字S[i]の対となる文字がiより前に出現していたらその文字同士を対応付けて,その他の保持している対応をリセットする。

ソースコード

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

public class C {
	int N;
	char[] ch;
	boolean[] used;
	public void solve() {
		N = nextInt();
		ch = next().toCharArray();
		used = new boolean[4];
		int ans = 1;
		for(int i = 0;i < N;i++){
			if(ch[i]=='L'){
				if(used[1]){
					ans++;
					Arrays.fill(used,false);
				}
				used[0] = true;
			}else if(ch[i]=='R'){
				if(used[0]){
					ans++;
					Arrays.fill(used,false);
				}
				used[1] = true;
			}else if(ch[i]=='U'){
				if(used[3]){
					ans++;
					Arrays.fill(used,false);
				}
				used[2] = true;
			}else if(ch[i]=='D'){
				if(used[2]){
					ans++;
					Arrays.fill(used,false);
				}
				used[3] = true;
			}
		}
		out.println(ans);
	}

	public static void main(String[] args) {
		out.flush();
		new C().solve();
		out.close();
	}
}