tookunn’s diary

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

Codeforces #395 Div2 A~C

A問題

考察

周期Nと周期Mが重なる数をカウントする

Editorialを見ると,Z / lcm(N,M)が解になるらしい。

ソースコード

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

public class A {
	int N,M,Z;
	int[] a;
	public void solve() {
		N = nextInt();
		M = nextInt();
		Z = nextInt();
		a = new int[Z + 1];
		for(int i = N;i <= Z;i+=N){
			a[i] |= 1;
		}

		for(int i = M;i <= Z;i+=M){
			a[i] |= 2;
		}

		int ans = 0;

		for(int i = 0;i <= Z;i++){
			if(a[i] == 3){
				ans++;
			}
		}

		out.println(ans);
	}

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

B問題

考察

i回目のstep時、i番目より前のペアはもう値が交換されることはない。

数列aのi番目とN+1-i番目のペアはiを2で割った余りが1の場合、値を入れ替える
計算量はO(N)

ソースコード

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

public class B {
	int N;
	int[] a;
	public void solve() {
		N = nextInt();
		a = new int[N];
		for(int i = 0;i < N;i++){
			a[i] = nextInt();
		}

		for(int i = 0;i < N / 2;i++){
			if(i % 2 == 0){
				int tmp = a[i];
				a[i] = a[N-1-i];
				a[N-1-i] = tmp;
			}
		}

		for(int i = 0;i < N;i++){
			if(i != 0)out.print(" ");
			out.print(a[i]);
		}
		out.println();
	}

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

C問題

考察

まず,適当にrootを決めてそこからBFSをしてrootと色が違う頂点に達したらその頂点を覚えておく。

その覚えた頂点が取り除く頂点の候補である。

そして、その頂点を取り除いた時に、残った複数の部分木がそれぞれ単一色の木になるかをBFSで調べていく。

正直TLEになるかと思ったけど800msぐらいで通った。

ソースコード

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

public class C {
	int N;
	int[] c;
	ArrayList<Integer>[] graph;
	boolean[] use;

	public int root(int v) {
		for (int u : graph[v]) {
			if (use[u])
				continue;
			use[u] = true;
			return root(u);
		}

		return v;
	}

	@SuppressWarnings("unchecked")
	public void solve() {
		N = nextInt();

		graph = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			graph[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < N - 1; i++) {
			int u = nextInt() - 1;
			int v = nextInt() - 1;
			graph[u].add(v);
			graph[v].add(u);
		}

		c = new int[N];
		for (int i = 0; i < N; i++) {
			c[i] = nextInt();
		}
		use = new boolean[N];
		use[0] = true;
		int root = root(0);

		ArrayList<Integer> takeNode = new ArrayList<Integer>();

		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		boolean[] used = new boolean[N];
		q.add(root);
		while (q.size() > 0) {
			int p = q.poll();
			if (used[p])
				continue;
			used[p] = true;

			for (int u : graph[p]) {
				if (c[u] != c[p]) {
					takeNode.add(u);
				} else {
					q.add(u);
				}
			}
		}

		takeNode.add(root);
		for (int i : takeNode) {

			ArrayDeque<Integer> qq = new ArrayDeque<Integer>();
			boolean[] visited = new boolean[N];
			boolean flag = true;
			for (int j : graph[i]) {
				qq.add(j);
				visited[j] = true;
			}
			visited[i] = true;

			out : while (qq.size() > 0) {
				int p = qq.poll();

				for (int k : graph[p]) {
					if (visited[k])
						continue;
					visited[k] = true;
					if (c[k] != c[p]) {
						flag = false;
						break out;
					} else {
						qq.add(k);
					}
				}
			}

			if (flag) {
				out.println("YES");
				out.println(i + 1);
				return;
			}
		}

		out.println("NO");

	}

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