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