tookunn’s diary

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

Codeforces #349 Div2 A~C

codeforces.com
全体的に問題文の量が比較的多くて辛かった...。誤読も多かったし。

A

考察

・まず、半径をr,円周率(3.14...)をpiとすると1秒間に増加する量はr * r * pi * eとなり、v(1秒間に減少する量)より多ければ、容器の中の水は減ることがないので、この時点でNOだとわかる。
・あとは、1秒間に減少する量 - 1秒間に増加する量は必ず1以上となるので、初期状態から入っている量が何秒後に空になるかを求めればよい。

ソースコード

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

public class A {
	int d,h,v,e;
	public void solve() {
		d = nextInt();
		h = nextInt();
		v = nextInt();
		e = nextInt();

		double r = d * 1.0 / 2;
		double pi = Math.PI;

		if(v <= r * r * pi * e){
			out.println("NO");
			return;
		}

		double V = v - r * r * pi * e;
		double ans = h * r * r * pi / V;

		out.println("YES");
		out.println(String.format("%.9f",ans));
	}

	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

考察

・最小の辺を追加して、三角形を作れるようにしよう。とのことなので、入力で与えれる辺の長さの1番短い辺と2番目に短い辺を繋げて、それの辺をまた一つの辺として追加する。その操作を辺の数が2つになるまで続ける。
・2番目の短い辺 - 1番短い辺 + 1が追加すべき、最小の辺となる。

ソースコード

public class B {
	int N;
	int[] l;
	public void solve() {
		N = nextInt();
		l = new int[N];
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for(int i = 0;i < N;i++){
			l[i] = nextInt();
			pq.add(l[i]);
		}

		while(pq.size() > 2){
			int a = pq.poll();
			int b = pq.poll();
			pq.add(a + b);
		}

		int a = pq.poll();
		int b = pq.poll();

		out.println(b - a + 1);
	}

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

C

考察

・とりあえず、「root」となる文字列を定めて、あとは2,3文字ずつ接尾辞を定めていく。
・dfs(n,pre) = 前の接尾辞のハッシュがpreでn番目の文字までを見た時にその接尾辞の取り方があっているかどうか。

・出力は重複がない、アルファベット順に出力するので,TreeSetを使う。
参考:
kmjp.hatenablog.jp
ei1333.hateblo.jp

ソースコード

public class C {
	String S;
	int N;
	boolean[][] dp;
	int[] pre;
	TreeSet<String> suffixes;

	public int toNum(String s) {
		int num = 0;
		for (int i = 0; i < s.length(); i++) {
			if (i != 0)
				num *= 26;
			num += s.charAt(i) - 'a' + 1;
		}
		return num;
	}
	public boolean dfs(int n,int pre) {
		if(n == N)return true;
		if(dp[n][pre])return true;
		boolean ret = false;
		for(int i = 2;i <= 3;i++){
			if(n + i <= N){
				String suffix = S.substring(n, n + i);
				int h = toNum(suffix);
				if(pre == h)continue;
				boolean f = dfs(n + i,h);
				ret |= f;
				if(f){
					suffixes.add(suffix);
				}
			}
		}
		return dp[n][pre] = ret;
	}

	public void solve() {
		S = next();
		N = S.length();
		suffixes = new TreeSet<String>();
		dp = new boolean[N + 1][27 * 27 * 27 + 100];
		pre = new int[N + 1];
		Arrays.fill(pre,-1);
		for (int i = 5; i <= N - 2; i++) {
			dfs(i,0);
		}
		out.println(suffixes.size());
		for (String suffix : suffixes) {
			out.println(suffix);
		}
	}

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