tookunn’s diary

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

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問題

問題

codeforces.com

考察

周期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問題

問題

codeforces.com

考察

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問題

問題

codeforces.com

考察

まず,適当に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();

	}
}

RUCP2016 Day3 B 周期数列 - Periodic Sequence -

RUPC2016

問題

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

考察

考えられる周期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

Codeforces


問題

codeforces.com

考察

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

問題

codeforces.com

考察

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

問題

codeforces.com

考察

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

Codeforces #388 Div2 A~C

Codeforces

A問題

codeforces.com

考察

Nは2または3だけで表すことが出来るので,2で出来るだけ表すようにして,Nが2で割り切れなかったら最後の2を3にすればよい。

ソースコード

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

public class A {
	int N;
	public void solve() {
		N = nextInt();
		out.println(N/2);
		for(int i = 0;i < N/2 - N%2;i++){
			if(i != 0)out.print(" ");
			out.print(2);
		}

		if(N%2==1)out.print(" 3");
		out.println();

	}

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

B問題

codeforces.com

考察

与えられた3点を使って平行四辺形を作ることができる残り1点の候補は3つだけ

与えられた3点をA,B,Cとし,求める残り1点をDとするとベクトルAB,ACと点Aの和を求めるとDの座標が分かる。

参考にさせて頂いた解説記事：
pekempey.hatenablog.com

ソースコード

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

public class B {
	private class V{
		int x,y;
		public V(int x,int y){
			this.x = x;
			this.y = y;
		}
	}
	public void solve() {
		V[] v = new V[3];
		for(int i = 0;i < 3;i++){
			v[i] = new V(nextInt(),nextInt());
		}

		HashSet<int[]> set = new HashSet<int[]>();

		for(int i = 0;i < 3;i++){
			int j = i + 1;
			int k = j + 1;
			j %= 3;
			k %= 3;

			int x = v[i].x + v[j].x - v[i].x + v[k].x - v[i].x;
			int y = v[i].y + v[j].y - v[i].y + v[k].y - v[i].y;

			set.add(new int[]{x,y});
		}
		out.println(set.size());
		for(int[] a : set){
			out.println(a[0] + " " + a[1]);
		}
	}

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

C問題

codeforces.com

考察

問題文通りにシュミレーションした

与えられた文字列Sを先頭から見ていき,もしその文字が投票権を持っていたら,今見ている文字と対となる文字の中で次に呼ばれる可能性がある文字の投票権を打ち消す。

ソースコード

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

public class C {
	int N;
	String s;
	public void solve() {
		N = nextInt();
		s = next();

		TreeSet<Integer> D = new TreeSet<Integer>();
		TreeSet<Integer> R = new TreeSet<Integer>();
		for(int i = 0;i < N;i++){
			if(s.charAt(i) == 'D'){
				D.add(i);
			}else{
				R.add(i);
			}
		}
		for(int i = 0;R.size() > 0 &&  D.size() > 0;i++,i%=N){
			if(s.charAt(i) == 'D'){
				if(!D.contains(i))continue;
				if(R.higher(i) != null){
					R.remove(R.higher(i));
				}else{
					R.remove(R.lower(i));
				}
			}else{
				if(!R.contains(i))continue;
				if(D.higher(i) != null){
					D.remove(D.higher(i));
				}else{
					D.remove(D.lower(i));
				}
			}
		}

		if(D.size() > 0){
			out.println("D");
		}else{
			out.println("R");
		}
	}

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

RUPC2016 Day3 A マイナンバー - My Number -

RUPC2016

問題

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

これは当時本番で解いたのでそこまで苦労しないで解けた感(実装は時間掛かった)

考察

?のところに0～9までの数字を当てはめて実際にそのマイナンバーでチェックディジットが一致するかどうかを見ていけば良い。

複数の数字でチェックディジットが一致した場合はMUTLIPLEを出力
1つだけの数字でチェックディジットが一致した場合はその数字を出力

ソースコード

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{
	String s;
	public void solve() {
		s = next();
		ArrayList<Integer> list = new ArrayList<Integer>();

		for(int i = 0;i < 10;i++){
			char[] ch = s.toCharArray();
			for(int j = 0;j < 12;j++)
				if(ch[j] == '?')
					ch[j] = (char)(i + '0');
			int digit = 0;
			for(int j = 11;j >= 1;j--){
				int Q = j >= 7 ? j - 5 : j + 1;
				digit += (ch[(11-j)]-'0') * Q;
			}
			digit %= 11;
			if(digit <= 1)digit = 0;
			else digit = 11 - digit;

			if(digit+'0' == ch[11])list.add(i);
		}

		if(list.size() > 1)out.println("MULTIPLE");
		else out.println(list.get(0));
	}

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

	}
}