tookunn’s diary

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

Codeforces #371 Div2 A~C

Codeforces

A

問題

codeforces.com

考察

・区間[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は普通に解けなかったしで残念...。

SRM 699 Div2 Hard

SRM

問題文

TopCoder Statistics - Problem Statement

考察

・ i \ne jであり、(0 \le i,j \lt M)の時,b[i]からb[j]に辿ることが出来るということはb[i]とa[j]の最小公倍数になる整数の頂点を通るということ。
・最小公倍数はN以下である。

ソースコード

import java.util.*;
public class FromToDivisibleDiv2{
	final int INF = (int)1e9 + 7;
	int M;
	int[] d;
	private class P{
		int first,second;
		public P(int first,int second){
			this.first = first;
			this.second = second;
		}
	}
	public int gcd(int x,int y){
		return y == 0 ? x : gcd(y,x%y);
	}
	public long lcm(int x,int y){
		return (long)x * y / gcd(x,y);
	}
	public int shortest(int N,int S,int T,int[] a,int[] b){
		M = a.length;
		d = new int[M];
		Arrays.fill(d,INF);
		Queue<P> q = new ArrayDeque<P>();
		for(int i = 0;i < M;i++){
			if(S % a[i] == 0){
				q.add(new P(i,1));
				d[i] = 1;
			}
		}
		int ret = -1;
		while(q.size() > 0){
			P p = q.poll();
			if(T % b[p.first] == 0){
				ret = p.second;
				break;
			}
			for(int i = 0;i < M;i++){
				if(d[i] == INF && lcm(b[p.first],a[i]) <= N){
					d[i] = Math.min(d[i],d[p.first] + 1);
					q.add(new P(i,d[i]));
				}
			}
		}
		return ret;
	}
}

本番では解けなかったけど、Hardにしては実装とか考察はそこまで難しくないのかな

CODE FESTIVAL 2016 予選A D

CODE FESTIVAL

問題

code-festival-2016-quala.contest.atcoder.jp

考察

まず問題文にある式がどういうものかを考えてみる。
(左上の整数) + (右下の整数) = (右上の整数) + (左下の整数)を(i,j) + (i + 1,j + 1) = (i,j + 1) + (i + 1,j) と考える。
そしてこの式を変形すると,
(i,j) - (i,j + 1) = (i + 1,j) - (i + 1,j + 1)または
(i,j) - (i + 1,j) = (i,j + 1) - (i + 1,j + 1)となる。
この変形した式が表すのは,列jと列j + 1間の値の差は行iと行i + 1で同じであるということで,これは行と列を逆にしても同じことが言える。

となると
(i,j)-(i,j+1)=(i+1,j)-(i+1,j+1)=(i + 2,j)-(i + 2,j + 1)...
という風にすべての行において(i,j) = (i,j + 1)が成り立ち, 列jにある値と列j + 1にある値の差は必ず一意になることが分かる。
これも行と列を入れ替えても同じことが成り立つ。

また(i,j)の値と(i,j + 2)の値の差もすべての行において等しいことが分かり、
これは(i,j) - (i,j + 1) = (i + 1,j) - (i + 1,j + 1) = (i + 2,j) - (i + 2,j + 1)...から列jと他のすべての列との差がすべての行において等しいということが分かる。

ある列kを基準にし,列kを0と考え,列kと他の列(0 \le i \lt C)との差をx_iとする。
また行についても同じように考えることが出来て,ある行kと他の行(0 \le i \lt R)との差をy_iとする。

以上のことを含めるとb_{i,j}は行iであり,列jに存在する値とし、
b_{i,j} = x_j + y_iを求めることが出来る。

x_0x_1x_2
y_0b_{0,0}b_{0,1}b_{0,2}
y_1b_{1,0}b_{1,1}b_{1,2}
y_2b_{2,0}b_{2,1}b_{2,2}
そして,このx_j(0 \le j \lt C)とy_i(0 \le i \lt R)を頂点にして，与えられたa_i(0 \le i \lt N)を頂点x_{r_i}と頂点y_{c_i}間をつなぐ辺としてグラフにして考える。

適当な頂点から始めて辺を辿っていき,x_j + y_i = a_kとなることを目指し各頂点を通り,x_j,y_iを求めていきます。
この辺を辿っていく操作は各連結成分ごとに行います。

最終的にb_{i,j} = x_j + y_iとなっているか矛盾しているかを判定することができます。
ここで,問題の制約上各マスの値は非負整数となっているので、必ず各マスの値が0以上の値になっていなければなりません。
もし、x_j + y_i \lt 0の組み合わせが存在する場合は0以上の値に収まっていないマスが存在するので、解は「No」になります。

例)問題ページのサンプル4

x_0x_1x_2
y_00 10
y_1
y_210 20
f:id:tookunn:20160926213246j:plain
まず,上記で示したように入力で与えられたN個の辺を重みa_i(0 \le i \lt N)にして,頂点x_{r_i}と頂点y_{c_i}に張る。
それから,適当な頂点を選びます。今回の例ではy_0を選んでいます。y_0から辿っていき,それぞれx_i(0 \le i \lt C),y_i(0 \le i \lt R)を求めていきます。
今回の最初に辿る先としてはx_0とx_2があります。
式a_i = x_{c_j} + y_{r_i}から,辺の重みはつながっている二つの頂点の重みの合計と同値になっていなければならないので,頂点の一方でも重みが分かっていれば,
y_{r_i} = a_i - x_{c_j}みたいに式を変形して求めることが出来ます。
以上からx_0 = 0,x_2 = 10となります。
そして,y_2 = 10となり,すべての辺についてa_i = x_{c_j} + y_{r_i}が成り立つので、Yesとなります。

例)問題ページのサンプル2

x_0x_1x_2
y_001020
y_13040

f:id:tookunn:20160926213218j:plain
今回も適当な頂点として、y_0を選び,y_0 = 0とします。
そして,最初に辿る頂点はx_0,x_1,x_2になり,x_0 = 0,x_1 = 10,x_2 = 20となります。
ここで、最後に辿るy_1が問題になります。
x_0からy_1に辿るとy_1 = 30になりますが,そうなってしまうとy_1 + x_2 = 50になってしまい,y_1,x_2間の辺の重みと異なってしまうので,
今回はNoという結果になります。

公式解説
http://code-festival-2016-quala.contest.atcoder.jp/data/other/code-festival-2016-quala/editorial.pdf

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.*;
 
public class Main {
	int R,C,N;
	int[] r,c,a;
	long[][] b;
	boolean[][] used;
	ArrayList<Edge>[][] graph;
	
	private class Edge{
		int t,w;
		public Edge(int t,int w){
			this.t = t;
			this.w = w;
		}
	}
	
	private class P{
		int type,pos;
		long weight;
		public P(int type,int pos,long weight){
			this.type = type;
			this.pos = pos;
			this.weight = weight;
		}
	}
	
	public void solve() {
		R = nextInt();
		C = nextInt();
		N = nextInt();
		
		r = new int[N];
		c = new int[N];
		a = new int[N];
		
		used = new boolean[2][];
		used[0] = new boolean[R];
		used[1] = new boolean[C];
		
		b = new long[2][];
		b[0] = new long[R];
		b[1] = new long[C];
		
		graph = new ArrayList[2][];
		graph[0] = new ArrayList[R];
		graph[1] = new ArrayList[C];
		
		for(int i = 0;i < R;i++){
			graph[0][i] = new ArrayList<Edge>();
		}
		
		for(int i = 0;i < C;i++){
			graph[1][i] = new ArrayList<Edge>();
		}
		
		for(int i = 0;i < N;i++){
			r[i] = nextInt() - 1;
			c[i] = nextInt() - 1;
			a[i] = nextInt();
			
			graph[0][r[i]].add(new Edge(c[i],a[i]));
			graph[1][c[i]].add(new Edge(r[i],a[i]));
		}
		long[] min = new long[2];
		for(int i = 0;i < N;i++){
			if(used[0][r[i]])continue;
			Queue<P> q = new ArrayDeque<P>();
			//type,pos,weight
			min[0] = Long.MAX_VALUE;
		    min[1] = Long.MAX_VALUE;
			q.add(new P(0,r[i],0));
			while(q.size() > 0){
				P p = q.poll();
				if(used[p.type][p.pos])continue;
				used[p.type][p.pos] = true;
				min[p.type&1] = Math.min(min[p.type&1],p.weight);
				b[p.type][p.pos] = p.weight;
				for(Edge e : graph[p.type][p.pos]){
					q.add(new P(((p.type + 1)&1),e.t,e.w - p.weight));
				}
			}
			
			if(min[0] + min[1] < 0){
				out.println("No");
				return;
			}
		}
		for(int i = 0;i < N;i++){
			if(a[i] == b[0][r[i]] + b[1][c[i]])continue;
			out.println("No");
			return;
		}
		
		out.println("Yes");
	}
 
	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());
	}
}

考察とか結構自分の頭の中を整理するために書いたようなものなので,他の人は分かりづらいものになったかもしれませんが,
少しでも何かの気付きの手助けになればと思い,記事にして残しておきます。
間違い,指摘等あれば遠慮なくどうぞ

Codeforces #372 Div2 A~C

Codeforces

A

問題

codeforces.com

考察

t_i(0 \le i \lt n-1)を順に見ていき,カウントしていく。
t_iとt_{i+1}の差がcより大きければカウントをリセットする。

ソースコード

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

public class Main {
	int N,c;
	int[] t;
	public void solve() {
		N = nextInt();
		c = nextInt();
		t = new int[N];
		for(int i = 0;i < N;i++){
			t[i] = nextInt();
		}
		int cnt = 1;
		for(int i = 0;i < N - 1;i++){
			if(t[i + 1] - t[i] > c){
				cnt = 1;
			}else{
				cnt++;
			}
		}

		out.println(cnt);

	}

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

B

問題

codeforces.com

考察

・与えられた文字列Sの中で26文字の部分文字列を見つけ、A～Zの文字をそれぞれ1回ずつ使っているかを調べればよい。

・その部分文字列内の「？」の個数 = A～Zの中で使っていない文字の数であれば「？」をA～Zに置き換えて目的の文字列を作ることができる。

・もし目的の文字列が作れる場合、置き換えていない「？」はすべて適当な文字に当てはめればよい。

ソースコード

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

public class Main {

	char[] c;
	int N;

	public void solve() {
		c = next().toCharArray();
		N = c.length;
		int[] a;
		for(int i = 0;i < N - 25;i++){
			a = new int[26];
			int q = 0;

			for(int j = 0;j < 26;j++){
				if(c[i + j] == '?')q++;
				else a[c[i + j] - 'A']++;
			}

			for(int j = 0;j < 26;j++){
				if(a[j] == 0){
					q--;
				}
			}
			if(q == 0){
				for(int j = 0;j < 26;j++){

					if(c[i + j] == '?'){
						for(int k = 0;k < 26;k++){
							if(a[k] == 0){
								a[k] = 1;
								c[i + j] = (char)('A' + k);
								break;
							}
						}
					}
				}

				for(int j = 0;j < N;j++){
					if(c[j] == '?'){
						c[j] = 'A';
					}

					out.print(c[j]);
				}
				out.println();
				return;
			}
		}

		out.println(-1);
	}

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

C

問題

codeforces.com

考察

・解説見てもさっぱりだったので、とりあえずnを小さい値にして検証してみた。
X=2,K=1
X=3,K=1 (+1)
X=4,K=1 (+1)
X=2,K=2 (√)
X=4,K=2 (+2)
(略)
X=34,K=2 (+2)
X=36,K=2 (+2)
X=6,K=3 (√)
X=9,K=3 (+3)
(略)
X=141,K=3 (+3)
X=144,K=3 (+3)
X=12,K=4 (√)
X=16,K=4 (+4)
(続)

・以上のように検証していったらi(i + 1)がレベルi + 1に到達した時のXの値になることを発見できる。

・つまりi(i + 1)*i(i + 1)がレベルi時のルートを取る前の値になる。

・(i(i + 1) * i(i + 1) - i(i - 1)) / iが求めるべき値になる。

・しかしこのまま計算してしまうと10^18以上の値になってしまい、制約に反する。なので、i(i + 1) * i(i + 1) / i - i(i - 1)/iに変形するとiで割れることが分かって、i(i + 1) * (i + 1) - (i - 1)になって求めることができる。

・そして、iを1からNまでを舐めていき求めた値を出力する。

これ検証しても気付くの結構キツイと思う

Editorial:
codeforces.com

ソースコード

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

public class C {
	int N;
	public void solve() {
		N = nextInt();
		for(long k = 1;k <= N;k++){

			if(k == 1){
				out.println(2);
			}else{
				out.println(((k * (k + 1)) * ((k + 1)) - ((k - 1))));
			}
		}
	}

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

AtCoderBeginnerContest 044 D

ABC

問題

abc044.contest.atcoder.jp

考察

解説見てAC。

・bを探索したいが,全探索をしてしまうと最大b \le n+1になってO(10^{11})となり、間に合わない。

・ここでb > sqrt(n)の場合にnをb進数で表現すると2桁以下になることに気付くと2 \le b \le sqrt(n)とsqrt(n) \lt b \le nの範囲に分けてbを探索できることに気付ける。

・nをb進数で表現するとなぜ2桁以下になるのかはb > sqrt(n)であるのでn / bが上位桁になり,n mod bが下位桁になることから分かる。これが直観で分かりづらい方はnやbに具体的な値をいれて検証しましょう。（僕はこれで納得しました。実験大事！！）

・b \gt sqrt(n)の時nをb進数で表現した上位桁をp,下位桁をqとすると
n = pb + q
p + q = s
n - s = pb - p + q - q
n - s = p(b - 1)
b = (n - s) / p + 1
以上の式から
pが決まればbが決まりそうなので,pを探索する。

・2 \le b \le sqrt(n)の時はO(sqrt(n))なのでbを全探索をしても十分間に合う。

公式解説：
http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
public class Main {
	long N,S;
 
	public long f(long b,long n){
		if(n < b)return n;
		return f(b,n / b) + (n % b);
	}
 
	public void solve() {
		N = nextLong();
		S = nextLong();
 
		if(N == S){
			out.println(N + 1);
			return;
		}
 
		long ans = Long.MAX_VALUE;
		for(int i = 2;(long)i * i <= N;i++){
			long res = f(i,N);
			if(res == S){
				out.println(i);
				return;
			}
		}
 
		for(int i = 1;(long)i * i <= N - S;i++){
			long B = (N - S) / i + 1;
			if(f(B,N) == S){
				ans = Math.min(ans,B);
			}
		}
		out.println(ans == Long.MAX_VALUE ? -1 : ans);
	}
 
	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());
	}
}

競技プログラミングTODO#1

TODO

なんか競技プログラミングでやりたいことを明確に文字に起こした方がモチベが上がるかもという試みです。
TODOが達成出来たり,他のやるべきことが出来たらまた書くかもしれないので、＃1ということで。

  • Codeforces とりあえず20回分ぐらいのA～C(出来たらDまで)埋める。
  • AOJ AOJ-ICPCを350まで埋める,VirtualArenaで良さげな問題集を見つけて解く。
  • ACPC,RUPCの問題を復習
  • ABC D埋め
  • ARC B埋め
  • AGC Cまで埋める
  • yukicoder ☆2埋め,☆3半分くらい埋める。
  • 蟻本 初級編,中級編の熟読and練習問題解き。

割と自分でもかなり目標高めのTODOを設定したつもり。
すべてやりきるのはだいぶ辛いと思うけど,出来たらかなり実力付くと思う。
CODEFESTIVAL2016予選Cまでにある程度達成出来たら良いな。

会津大学競技プログラミング合宿2016参加記

参加記

はじめに

3月にあったRUPC2016で中々良い思いをさせてもらったので、調子に乗って大学生ではないですがACPC2016に参加させていただきました。
tookunn.hatenablog.com

この記事を見た合宿参加者はぜひ参加記を書いて楽しかった思い出を共有しよう！！

1日目

会津大学のある福島県は僕の住む県に隣接しているので当日に在来線に乗って会津若松駅まで行きました。

会津若松駅で@ctylさんと合流し会津大学に向かいましたが早く着きすぎたためお昼を近くのラーメン屋でお昼を済ませてから再度会津大学へ向かいました。

f:id:tookunn:20160919220233j:plain

そして、参加費を払い名札を手に入れるフェイズになった際に,名札の紐が緑,青,黄色,赤となっていてレートの色に対応しているのかという気持ちに勝手になり、自然と緑を選んでしまった...。


チーム決めフェイズを終え会津大の方2人とチームを組ませていただき立命館大学セットをしました。

最初に@somennagasiさんがAをAC。僕はBを担当して1WAを出してAC。@kzyKT_MさんがC,Eを考察しコーディングまで行っていましたが,残念ながら2完で終わりました。
もう少し僕にC,Eを一緒に考察できる実力があればよかったのですが...。申し訳なさ。

解説を聞いた後,人生初タクシーに乗って,会津若松駅に行き,@ctylさん,@yurahunaさん,@kenkooooさんと付近の中華料理屋で夕食を済ませました。

その後@kenkooooさんとは駅で別れ,残りの3人で同じ宿を取っていたので,限界集落にある宿に向かうために電車に乗り,宿の最寄り駅で下車し宿に向かいました。


宿では到着してすぐにお風呂に入った後,22:35からcodeforcesがあったので3人で一緒にでました。

実はcodeforcesに取り組んでいる最中に限界集落にありがちな大きい虫が度々我々3人の邪魔をしてきて辛かった。

codeforces後は即,寝床に着きました。

2日目

2日目はまず,少ない本数の電車に乗るために早起きをして,早々と会津大学へ向かいました。

そして,チームが決まり,立命館の方2人と組ませていただきました。ちなみに2日目は会津大学セットでした。

チーム名の由来としては@1118yoshikawaさんがよく迷子になったり,物をなくしたりするらしくてそこから持ってきました。

コンテストの内容としてはAを@1118yoshikawaさんと@sakisaka_4geruさんに任せてAC。Bは僕が担当してAC。Cを@sakisaka_4geruさんにお願いしていて,dpっぽいというヒントをいただいて,僕が実装してAC(最近dpの問題を多めにやっておいてよかった感)。後は3人で問題を色々見ながらDは何かdfsで行けるのではと思ったけど,通らなくて他の問題を全員で見つつ終了。3完。
3人で集中して1問に取り組むスタイルでやってチームとしてコミュニーションが多く取れたチームだったので良かった。
解説を見てDをAC。ダイクストラ法をするだけだったので解きたみが強かった。

解説終了後は懇親会がありました。


懇親会ではお酒も入り,どんな物事,出来事に関しても競プロっぽい要素をいれていてとても勉強になる会話が飛び交っていた。
競プロでは定数倍は小さいが現実の物事にしてみると2倍,3倍はやばいとかN人の@public_sateさんがいる等々(他にもたくさんあるが紹介しきれず)。
日頃,あそこまで競プロ要素を取り入れた会話を聞かないのでとても楽しかった。
そして写真撮影は@kenkooooさんの「AOJサイコー!!」という掛け声とともにパシャリ。
その後,限界集落に向かう電車の終電が近かったので早々に懇親会会場を後にしました。

3日目

3日目は電車の都合で会場の到着がチーム決めフェイズが終わった後に着きそうだったので,あらかじめチームメンバーをTwitterで募集していたら,
@Yazatenさんが声を掛けてくださって,@Yazatenさんと@dohatsutsuさんのチームに拾ってもらえました。


まず,Aを@Yazatenさん,Bを僕,Cは@dohatsutsuさん,という感じでそれぞれ取り掛かってAC。その後僕はEを眺めつつ考察をずっとしてて,実装のイメージがつかめなくてほぼ座っているだけ状態になってしまっていた。
そんな状態の間に@Yazatenさんと@dohatsutsuさんが次々ACを重ねていってE以外をすべて解いていて強かった。
でも決してお二人は僕を置いてきぼりしないで,今自分たちがどういう問題を解いているかを丁寧に説明したり,Eを一緒に考えてくれたりしてくださって僕もあきらめないでEに取り組めたので良かった。
コンテスト終了後,気付いたらオンサイトとオンライン含めて2位になっていて、非常にありがたいことになっていた。
そして解説を聞き,記念撮影の後,解散をして無事ACPC2016が終了しました。

感想

今回の合宿はRUPC2016以来のリアルに競プロerと触れ合える機会であり、チーム戦だったので、とても楽しかった。
会津若松までの移動も比較的近かったのでとても良かった。
そしてどの大学の問題セットも個人的に良い問題が多くて実りがあった気がする。
僕が泊まった宿は限界集落など色々twitter等で言っていたが、宿のオーナーも良い人だったし、宿の雰囲気もとても良かったので結果としては良い宿でした。
ただ、今回みたいな合宿という目的がある場合は駅前の宿を取った方が移動やその他諸々がラク。
RUPC,ACPC共に僕みたいなICPCを経験したことも無ければ、大学を経験したこともない緑コーダーがここまで楽しめたのだから
まだ合宿に参加したことのない競技プログラミング初心者(僕を含め)等も是非合宿に参加してほしいなと思います。そこで是非僕とチームを組みましょう!!

個人的な思いとしては来年からは社会人なのですが、当然競技プログラミングを続けようと思っていて、
仕事,生活的に余裕があればRUPC,ACPC等にも積極的に参加していきたい(周りから老害と言われ続けるまでいや、むしろ言われ続けても)と思っています。
次参加するときは出されたA,B,C問題だけでなくD以降の難易度の問題も解けるようになっていたいですね。

合宿に参加された各大学の皆さん,社会人の皆さん,本当に3日間お疲れさまでした。
学生の皆さんとは是非CODE FESTIVALでお会いしたいですね。