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