2018-10-09

AGC009-B：Tournament

問題

https://beta.atcoder.jp/contests/agc009/tasks/agc009_b

考え方

木DPだが、遷移が重要。今ある親 u から 4 個の子 (v_1, v_2, v_3, v_4)をもつ部分木の場合を考える。ある頂点の深さを cost[p] としておく。

f:id:d_tutuz:20181009051702p:plain

このとき、トーナメントの割当としては以下のようになる。

f:id:d_tutuz:20181009051710p:plain

u は v_1, v_2, v_3, v_4 のいずれとも試合をするが、このとき u の深さが最適に(一番浅く)なるときは、深い場所に一番浅い頂点をもつように、すなわち cost[v_1] >= cost[v_2] >= cost[v_3] >= cost[v_4] となるように割り当てるのが最適である。

このとき u の深さ cost[u] は cost[v_k] を降順にソートしておいて cost[u] = cost[v_k] + k+1 となる

       List<Integer>[] g;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            g = new ArrayList[n];
            g = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new);

            for (int i = 1; i < n; i++) {
                int a = in.nextInt()-1;
                g[a].add(i);
            }
            int ans = dfs(0);
            out.println(ans);

        }

        int dfs(int now) {

            List<Integer> list = new ArrayList<>();
            for (int next : g[now]) {
                list.add(dfs(next));
            }
            Collections.sort(list, Comparator.reverseOrder());
            int ret = 0;
            for (int i = 0; i < list.size(); i++) {
                ret = Math.max(ret, i+1 + list.get(i));
            }

            return ret;
        }

ポイント

実験して遷移を考える

類題

2018-10-09

第3回ドワンゴからの挑戦状予選-D：ネタだけ食べたい寿司

問題

D - ネタだけ食べたい寿司

$n$ つの寿司と $m$ 個の皿がある。シャリのみを食べる時、皿を消費する。シャリのみを食べるのは $m$ 回実施することができるが、 $m$ 回実施したタイミングでその後は寿司を食べることができない。幸福度の最大値を求めよ。

考え方

$i$ 個までの寿司を食べるとするとするとき、 $[1, i-1]$ から $m-1$ 個は効果が大きいシャリのみの寿司を食べて、 $i$ 番目の寿司はシャリのみをたべるのが最適である。ここでいう効果が高いのは、シャリのみを食べたときとそうでないときの差が大きい寿司である。

範囲の $k$ 番目を保持するのは PriorityQueue で実現することができるので、予め $m$ 個はシャリのみの寿司を食べておき、 $[m+1, n]$ まで順に効果の小さいシャリのみの寿司を食べるのをやめて、 $m+1$ 個目についてシャリのみを食べたときの最大値を求めれば良い。

なお、 $n \le m$ のときは常に $n$ 個食べることができるのですべてシャリのみの寿司を食べるのが最適である。

Submission #3767336 - 第3回ドワンゴからの挑戦状予選

どこに着目して考察するべきだったか

$m$ つの寿司はシャリだけ食べてしまったことにすると考えやすい。以降はシャリだけ食べる $m+1$ 個目の寿司について、今までシャリだけ食べたうち、価値の低い寿司はシャリも食べることにすると常に $m$ 個シャリだけ食べたことになる。

また、価値の低い寿司の考え方だが、これはシャリだけ食べたときとそうでないときの価値の差分で考えるとよい。

何がバグっていたか

得た知見

順序関係が定まる $k$ つの要素を保持
差分で判断

類題

2018-10-08

AGC105-B：Colorful Hats

問題

https://beta.atcoder.jp/contests/agc016/tasks/agc016_b

N 匹の猫がいる。猫 i は「自分の除く猫がかぶっている帽子の色の種類数は a_i である」といっている。すべての猫の発言に矛盾しないように帽子を割り当てることができるか判定せよ。

考え方

実験することが大事っぽい。

すべての帽子の色の数を A とする。このとき、ある猫 i が唯一の色の帽子をかぶっていた場合は a_i = A - 1 となり、それ以外の猫は a_j = A となる。まず、数列の最小値と最大値の差は 1 以内におさまる。そうでない場合は割り当てることはできない。

そこで、最大値と最小値の差で場合分けする。

(i) 最大値=最小値となっている場合

N = 4 として以下のように帽子をかぶっていたとする

帽子	R	B	G	E
a_i	3	3	3	3

猫がかぶっている帽子の色がすべて異なる場合は、最大値=最小値となる。
この時、 a_i = A-1 である。

また、N = 7 として以下のように帽子をかぶっていたとする

帽子	R	R	R	B	B	G	G
a_i	3	3	3	3	3	3	3

上記のようにすべての色の帽子が 2 つ以上の猫がかぶっている場合は最大値=最小値となる。

この時、2 * a_i <= N である。

(ii) 最大値 - 最小値 = 1となっている場合

以下のように、数列の値として A と A-1 が存在する場合は同じ色の帽子を 2 つ以上かぶっている猫と、唯一の色の帽子をかぶっている猫がいる。

帽子	R	R	B	B	G	E
a_i	4	4	4	4	3	3

唯一の色をかぶっている帽子の色の数 x は a_i = A-1 となっている値の数である。同じ色の帽子をかぶっている色の数は A - x である。よって

x + 2 * (A - x) <= N かつ (A - x) >= 1

が満たされる条件である。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] a = new int[n];
            int max = -INF, min = INF;
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                max = max(max, a[i]);
                min = min(min, a[i]);
            }

            if (max - min >= 2) {
                out.println("No");
                return;
            }

            if (max == min) {
                if (a[0] == n - 1 || 2 * a[0] <= n) {
                    out.println("Yes");
                    return;
                }
            } else {
                int x = 0;
                for (int i = 0; i < n; i++) if (a[i] == max - 1) x++;
                int y = max - x;
                if (y >= 1 && x + 2*y <= n) {
                    out.println("Yes");
                    return;
                }
            }

            out.println("No");
            return;

        }

ポイント

実験する
条件を整理する

類題

2018-10-07

AGC003-C：BBuBBBlesort!

問題

https://beta.atcoder.jp/contests/agc003/tasks/agc003_c

長さ N の数列 a_N が与えられる。以下の操作をして、数列を単調増加にするよう並べ替える時、操作 1 の最小回数を求めよ。

数列の連続する 2 つの要素を選び、その 2 つの順番を反転する。
数列の連続する 3 つの要素を選び、その 3 つの順番を反転する。

考え方

操作 2 を考えると、偶奇ごとに数を swap するのは任意にしてよいことがわかる。
ソート後の数列を考えると、もとの数列とソート後の数列で index の偶奇が異なる数 a_i については少なくとも 1 回は操作 1 によって偶奇を入れ替えなければならない。偶数ごと奇数ごとの swap は任意にできるので、偶奇を入れ替えるための操作は高々 1 回でよいことがわかる。

また、ある数 a_i について、もとの数列の index とソート後の数列の index の偶奇が異なる場合、別のある 1 つの数 a_j についても偶奇が異なる。a_i と a_j の 2 つの数は 1 回の操作 1 で同時に偶奇を揃えることができる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] a = in.nextIntArray(n);
            int[] as = a.clone();
            Arrays.sort(as);

            long ans = 0;
            for (int i = 0; i < n; i++) {
                int idx = Arrays.binarySearch(as, a[i]);
                if (abs(i - idx) % 2 == 1) ans++;
            }

            out.println(ans/2);
        }

ポイント

満たすべき状態を考える

類題

雑記

偶奇ごとの数列に分けてソートした後、1の操作で転倒数を求めればよいのかな、、、と思いましたが違いました()

2018-10-07

ABC093-D：Worst Case

問題

https://beta.atcoder.jp/contests/abc093/tasks/arc094_b

[1, 10^(10^10)] の参加者がいるプログラミングコンテストがある。高橋君は1回目で A 、2回目で B 位になった。参加者のスコアは 2回のコンテストの順位の積で与えられる。高橋君よりもスコアの小さい参加者の人数を求めよ。

考え方

最大のペアを作るマッチング問題である。

A <= B としておく。

1回目で A よりも小さい A - i の順位をとる場合、2回目で B - i の順位にすることで

(A - i) * (B - i) = AB + (A-B)i - i² < AB

高橋君よりも小さなスコアにすることができる。これは A - 1 人のペアを作ることができる。

1回目で B よりも小さい B- i の順位をとった場合は、上記と同じ議論はできない。AB を超えるペアができるため。

いま、全部で K ペア作ることができると仮定しよう。そのときペアとなる数は以下のようになっているはずである。

f:id:d_tutuz:20181007093421p:plain

K つのペアをとるとき、最大値が AB を超えなければ K ペア作ることができる。そうでないときは K ペア作ることはできない。これは単調性が成立する。

後は K ペア作るときの最大値が AB を超えないか確かめる必要がある。[1, A-1], [A+1,K+1] と [K+1, B+1], [B-1,1] についてはほぼ単調数列になっていて、このペアの最大値は数列の真ん中あたりになる。三分探索で求めることもできるが、真ん中あたりのペアの最大値が AB を超えないか確認すれば良い。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int q = in.nextInt();
            while (q-- > 0) {
                long a = in.nextLong(), b = in.nextLong();
                out.println(calc(a, b));
            }

        }

        long calc(long a, long b) {
            if (a == b) return (a-1) * 2;

            long limit = a * b - 1;
            long l = min(a, b) - 1, r = max(a, b) * 2 - 1;
            while (r - l > 1) {
                long k = (r+l)/2;
                long max = 0;
                for (long i = max(k/2-100, 1); i < k/2+100; i++) {
                    max = max(max, i * (k + 1 - i));
                }

                if (max > limit) {
                    r = k;
                } else {
                    l = k;
                }
            }

            return l - 1;
        }

ポイント

最適な組み合わせを考える

類題

2018-10-06

yukicoder No.741 AscNumber(Easy)

数学

問題

https://yukicoder.me/problems/no/741

10進数表示をしたときに桁が昇順に並んでいる数字を AscNumber とする。
10^N 未満の AscNumber がいくつあるか求めよ。

考え方

[0, 9] の数字から重複を許して N 個選んだ時の数を昇順に並べると1つの AscNumber になる。全単射の関係になっており、よって AscNumber の数の個数は、 [0, 9] の数字から重複を許して N 個選ぶ場合の数と同じである。

よって ${}_{10} \mathrm{H}_N = {}_{N + 9} \mathrm{C}_N$ が解になる。

ポイント

対応で数える

類題

雑記

桁DPでも解けますが、再帰で呼び出すと Stack Overflow になります。

2018-10-03

高速な素因数分解

数学素因数分解

問題

題材は以下の問題です。

https://codeforces.com/contest/1047/problem/C

概要

ある数 $n$ を素因数分解をするとき、通常は $\sqrt n$ までの素数で順に割ればよい。これは計算量 $\sqrt n$ で求めることができる。

今回の場合は、配列 $a_n$ に含まれる $a_i$ のすべての数について素因数分解する必要がある。通常の方法で素因数分解すると $O(n \sqrt n)$ となって 1sec の制約だと TLE してしまう。複数の数を高速に素因数分解する手段が必要である。

minFactor[i] := $i$ に含まれる最小の素因数

とすると、これは事前に [1, MAX] のそれぞれの数 $i$ について minFactor[i] を求めておくことで、数 $n$ を素因数分解する際に、minFactor[i] を用いて $n$ の素因数のみによって割っていくことができる。したがって通常の素因数分解よりも高速に素因数分解することができる。（ただしメモリの制約上 MAX の値が $10^8$ 程度までにおさまる必要がある）