AtCoder Beginner Contest 036
C.座圧
問題
https://beta.atcoder.jp/contests/abc036/tasks/abc036_c
数列 a_n = {a_1, a_2, ... , a_n} が与えられる。以下の条件を満たす数列 b_n を求めよ。
- a_i < a_j ⇒ b_i < b_j
- a_i = a_j ⇒ b_i = b_j
- 上記2つの条件を満たす数列 b_n のうち b_i の最大値が最小
方針
a_nの順序を保つ必要がある。またa_\iの要素が大きくなるにつれ、b_iの要素も大きくなる。求められている条件を満たすスうれはa_iの要素がa_n全体のうち、何番目に大きいかを求めることによって求められる。これは例えばTreeSetを使用してa_iの順序を求め、Mapでa_iとa_iのindex(a_nにおいて何番目に大きいか)をセットで保持しておけば高速に求められる。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(); int[] a = in.nextIntArray(n); TreeSet<Integer> set = new TreeSet<>(); for (int i = 0; i < n; i++) { set.add(a[i]); } Map<Integer, Integer> map = new HashMap<>(); int i = 0; for (int num : set) { map.put(num, i++); } for (int num : a) { out.println(map.get(num)); } }
雑記
特になし。1次元の座圧を応用する問題があれば問いてみたいですね(みかけたことがないので)
D.塗り絵
問題
https://beta.atcoder.jp/contests/abc036/tasks/abc036_d
N個の要素の木が与えられる。i番目の辺は a_i と b_i を結ぶ。以下の条件を満たすN個の要素を黒か白で塗る塗り方は何通りか。
- 辺の両端が黒になってはいけない
方針
ある要素(ここでは0から始める)を黒または白で塗ると仮定する。0に紐づく隣接点の塗り方は、0が黒の場合は白のみに限り、0が白の場合は黒か白どちらでも塗ることができる。
f(i, c) := 要素 i を色 c で塗る塗り方の数
とする。また、黒で塗る時は c = 0, 白で塗るときは c = 1 とする。
0の隣接点をn_i,n_jとする。0を黒で塗る場合はf(0, 0) = f(n_i, 1) * f(n_j, 1)、白で塗る場合はf(0, 1) = f(n_i, 0) * f(n_j, 0) + f(n_i, 0) * f(n_j, 1) + f(n_i, 1) * f(n_j, 0) + f(n_i, 1) * f(n_j, 1) 通りである。よってそれぞれの要素の隣接点を貪欲にもとめていけば求まる。ただし、木を遷移するときに、親の要素に遷移するような遷移方法を除かないといけない。メモ化テーブルの変数として含めると、状態がO(n2)となりTLEする。これは木を0から葉へ遷移する時に使用する辺のみのグラフを構築すればよい。無向木を有向木に変更するようなイメージである。以下の実装の場合は上手く枝刈りできているので問題なかった。ただ無向木を有向木にするテクニックはどこかで使えそう。
int n; List<Integer>[] g; long[][] memo; public void solve(int testNumber, InputReader in, PrintWriter out) { n = in.nextInt(); g = new ArrayList[n]; g = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new); for (int i = 0; i < n-1; i++) { int a = in.nextInt()-1, b = in.nextInt()-1; g[a].add(b); g[b].add(a); } memo = new long[n][2]; long ans = rec(0, 1, -1) + rec(0, 0, -1); out.println(ans % MOD); } long rec(int now, int color, int p) { if (memo[now][color] > 0) { return memo[now][color]; } long ret = 1; for (int to : g[now]) { if (to == p) continue; if (color == 1) { ret = (ret * (rec(to, 0, now) % MOD + rec(to, 1, now) % MOD)) % MOD; } else if (color == 0) { ret = (ret * rec(to, 1, now) % MOD) % MOD; } } return memo[now][color] = ret % MOD; }
雑記
初見では黒を塗る数を決め打ちすれば貪欲に求める?とか全体の2nの塗り方から両辺が黒になる塗り方(つまり辺の選び方)を引けばいいのでは?とか考えていた。後者が明確にNGな理由はわかっていないが、実際の解答よりも多く塗れることになっていたので、塗れないパターンも塗れると数え上げていると思われる。
ポイント
- ある要素の塗り方をf の関数で表すことで漸化式を構築することができる。解(=数え上げの通り)を仮定することは重要
- ある条件を仮定すれば貪欲に求まる(つまり初見の方針は一部正しかった)
- 木DP