Codeforces #389 Div2 A~C

@tookunn_1213 pic.twitter.com/SHGWcrMwJV

— tookunn (@tookunn_1213) 2017年1月6日

問題

codeforces.com

考察

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

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