tookunn’s diary

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

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