Codeforces #371 Div2 A~C - tookunn’s diary

A

問題

考察

・区間[l1,r1],区間[l2,r2]を数直線上で考えて、[l1,r1]と[l2,r2]の位置関係でそれぞれ場合分けして,
[l1,r1]と[l2,r2]間でかさなっている区間の長さ + 1が解になる。
・kが重なっている区間内に存在する場合は長さから-1した値が解になる。

・他の人の提出を見て気付いたけれど、実は場合分けをせずにできることができる。
・min(r1,r2) - max(l1,l2) + 1が重なっている区間の長さになるになるのだけど,
min(r1,r2) < max(l1,l2)の場合は区間が重なってないので0になる。

ソースコード

場合分け

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	long l1,r1,l2,r2,k;
	public void solve(){
		l1 = nextLong();
		r1 = nextLong();
		l2 = nextLong();
		r2 = nextLong();
		k = nextLong();
		int a = 0;
		if(r1 < l2 || r2 < l1 || r2 < l1 || r1 < l2){
			out.println(0);
		}
		else if(l1 <= l2 && r1 <= r2){
			
			if(l2 <= k && k <= r1)a=1;
			out.println(r1 - l2 + 1 - a);
		}else if(l2 <= l1 && r2 <= r1){
			
			if(l1 <= k && k <= r2)a=1;
			out.println(r2 - l1 + 1 - a);
		}else if(l2 <= l1 && r1 <= r2){
		
			if(l1 <= k && k <= r1)a=1;
			out.println(r1 - l1 + 1 - a);
		}else if(l1 <= l2 && r2 <= r1){
			
			if(l2 <= k && k <= r2)a=1;
			out.println(r2 - l2 + 1 - a);
		}
	}
 
	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());
	}
}

min,maxを取る

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	long l1,r1,l2,r2,k;
	public void solve(){
		l1 = nextLong();
		r1 = nextLong();
		l2 = nextLong();
		r2 = nextLong();
		k = nextLong();
		
		long maxL = Math.max(l1,l2);
		long minR = Math.min(r1,r2);
		
		if(maxL > minR){
			out.println(0);
		}else{
			
			int a = 0;
			if(maxL <= k && k <= minR)a=1;
			out.println(minR - maxL + 1 - a);
			
		}
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

B

問題

codeforces.com

考察

・配列 $a$ の値すべてが $x$ という値をそれぞれの要素に最大一回使って表せる値は $max(a),min(a),min(a) + (max(a) - min(a)) / 2$ の三種類しかない。
・これは $max(a)+x$ にしてしまうと他の配列 $a$ 内の $max(a)$ 以下の値は $x$ を一回使っても $max(a) + x$ にならないため。また $min(a) - x$ も同じこと。
・そして、やることは $a$ の値を $max(a),min(a),(max(a) - min(a)) / 2$ それぞれの値に出来るかどうかを試していけばよい。

・実はこれも他にもっと良い方法があって、 $a$ 内の要素の値の種類が2以下の場合は一方のどちらかの値に合わせれば良いのでYES,
4以上の時は $x$ をどんな値にしてもすべて同じ値にすることは出来ないのでNO,3の場合で,最小の値 = x,二番目に小さい値 = y,最大の値 = z,としたときに,
y * 2 = x + yになる場合はすべて同じ値にすることが出来る。

ソースコード

愚直解

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	int N;
	long[] a;
	
	public void solve(){
		N = nextInt();
		a = new long[N];
		for(int i = 0;i < N;i++){
			a[i] = nextLong();
		}
		Arrays.sort(a);
		boolean flag = true;
		for(int i = 0;i < N;i++){
			if(a[i] == a[N - 1])break;
			if(a[N - 1] - a[i] != a[N - 1] - a[0])flag = false;
		}
		
		if(flag){
			out.println("YES");
			return;
		}
		
		flag = true;
		for(int i = 0;i < N - 1;i++){
			if(a[i] == a[0])continue;
			if(a[i] - a[0] != a[N -1] - a[0])flag = false;
		}
		
		if(flag){
			out.println("YES");
		}
		
		flag = true;
		long mid = (a[N - 1] - a[0]) / 2 + a[0];
		long pre = mid - a[0];
		for(int i = 0;i < N;i++){
			if(a[i] == mid)continue;
			long diff = 0;
			if(a[i] > mid){
				diff = a[i] - mid;
			}else{
				diff = mid - a[i];
			}
			if(diff != pre){
				flag = false;
				break;
			}
		}
		if(flag){
			out.println("YES");
		}else{
			out.println("NO");
		}
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
}

値の種類をカウント

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	int N;
	TreeSet<Integer> a;
	
	public void solve(){
		N = nextInt();
		a = new TreeSet<Integer>();
		for(int i = 0;i < N;i++){
			a.add(nextInt());
		}
		boolean ok;
		if(a.size() <= 2){
			ok = true;
		}else if(a.size() > 3){
			ok = false;
		}else{
			int x = a.pollFirst();
			int y = a.pollFirst();
			int z = a.pollFirst();
			
			if(y * 2 == x + z){
				ok = true;
			}else{
				ok = false;
			}
		}
		
		if(ok){
			out.println("YES");
		}else{
			out.println("NO");
		}
		
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
}

C

問題

codeforces.com

考察

・ $a$ を数値化(ハッシュ化？)して管理して,インクリメント,デクリメントしていく。
・ $s$ として0101,101等の値が渡されるが,上桁の連続した0は無視しても良い。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	int T;
	char[] c;
	long[] a;
	String[] s;
	int[] hashTable;
	public int hash(String x){
		int i = 1;
		int j = x.length() - 1;
		int h = 0;
		while(j >= 0){
			h += ((x.charAt(j) - '0')&1) * i;
			i <<= 1;
			j--;
		}
		return h;
	}
	
	public void solve(){
		T = nextInt();
		c = new char[T];
		a = new long[T];
		s = new String[T];
		hashTable = new int[1 << 20];
		for(int i = 0;i < T;i++){
			c[i] = next().charAt(0);
			if(c[i] == '+'){
				a[i] = nextLong();
			}else if(c[i] == '-'){
				a[i] = nextLong();
			}else{
				s[i] = next();
			}
		}
		
		for(int i = 0;i < T;i++){
			if(c[i] == '+'){
				int j = 1;
				int x = 0;
				while(a[i] > 0){
					x += (int)(((a[i] % 10)&1)*j);
					j <<= 1;
					a[i] /= 10;
				}
				hashTable[x]++;
				
			}else if(c[i] == '-'){
				int j = 1;
				int x = 0;
				while(a[i] > 0){
					x += (int)(((a[i] % 10)&1)*j);
					j <<= 1;
					a[i] /= 10;
				}
				hashTable[x]--;
			}else{
				out.println(hashTable[hash(s[i])]);
			}
		}
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
}

A,Bは無駄に実装がめんどくさい方法しか思いつかなかった&&時間を結構かけてしまったし、Cは普通に解けなかったしで残念...。