Tenka1 Programmer Beginner Contest-D:IntegerotS

問題

ある数 kn つの組 (a_i, b_i) が与えられる。n つの組からいくつか a_i を選び、価値の総和を  \displaystyle  \sum b_i とする。選んだそれぞれの a_i の or が k を超えないようにするとき、価値の最大値を求めよ。

考え方

満たすべき条件について考える。条件は「選んだ a_i の or が k 以下にならなければならない」ということである。or をとったときに k 以下になる数について考える。

例えば k = 0011010(2) とすると、or をとったときの k 以下になる数の候補としては、

  • 0011010(2)
  • 0001111(2)
  • 0010111(2)
  • 0011001(2)

である。つまり ki ビット目が 1 であるとき、 i ビット目を 0 として i-1 ビット目以降を 1 とした数が候補となる。すべての候補になりうる数について、各 a_i との or をとって条件を満たす価値の総和を求めればよい。

Submission #3428078 - Tenka1 Programmer Beginner Contest

ポイント

  • 条件を満たす場合について考える

類題

ARC043-B:難易度

N 問の問題があり、それぞれ難易度は D_1, D_2, ..., D_N である。以下の条件を満たすように 4 問選ぶときの選び方の数を求めよ。

  • 2 問目の難易度は 1 問目の難易度の 2 倍以上である。
  • 3 問目の難易度は 2 問目の難易度の 2 倍以上である。
  • 4 問目の難易度は 3 問目の難易度の 2 倍以上である。

考え方

DPで求めることができる。問題 D_ij 番目の問題となるように選ぶ選び方を dp_{D_i, j} とすると、DP遷移は

 \displaystyle dp_{D_i, j} = dp_{D_i, j} + \sum_{k=1}^{\lfloor\frac{D_i}{2}\rfloor} dp_{k, j-1}

となる。愚直にループすると O(N^2) となるが、 \displaystyle \sum_{k=1}^{\lfloor\frac{D_i}{2}\rfloor} dp_{k, j-1} については BIT などで区間和を O(logN) で求めることができるから、全体としては O(NlogN) で求めることができる。

※実装のポイントとしては、BITの配列の添字が j 番目に対応しているということでしょうか。

       static int m = 100010;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] d = in.nextIntArray(n);
            Arrays.sort(d);

            BIT[] bit = new BIT[5];
            for (int i = 0; i < 5; i++) {
                bit[i] = new BIT(m);
            }

            bit[0].add(0, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < 5; j++) {
                    int v = d[i] / 2;
                    int u = bit[j-1].query(v);
                    bit[j].add(d[i], u);
                }
            }

            out.println(bit[4].query(100000) % MOD);

        }

ポイント

  • DPの遷移を考える
  • 前の状態に依存するのでDPを考える

類題

雑記

BIT を DP に応用できる問題にはじめて出会いました。

Codeforces Round #516(Div.2)

解いた問題を振り返ります。

A.Make a triangle!

問題概要

Problem - A - Codeforces

3 辺 a, b, c が与えられる。a, b, c の各辺にいくつか数を足して三角形になるようにするとき、足す数の最小値はいくつか?

制約

1 <= a, b, c <= 100

考え方

三角形の成立条件は a + b > c かつ b + c > a かつ c + a > b です。各辺に0 <= i, j, k <= 100 を足して三角形が成立するときのi + j + k の最小値を出力すれば良いです。

Submission #44293160 - Codeforces

B.Equations of Mathematical Magic

問題概要

Problem - B - Codeforces

t 個の a_i が与えられる。 a_i - x_i = a_i xor x_i となるような x_i の個数を各 x_i について求めよ。

制約

  • 1 <= t <= 1000
  • 0 <= a <= 230-1

考え方

まず条件より x は x <= a であることはすぐに分かります。各ビットごとに考えていくことにします。この時 a の i ビット目が 0 の場合は x の i ビット目は 0 よりありません。a の i ビット目が 1 の場合は x の i ビット目は 0 または 1 を取ることができます。 1 - 0 = 1 ∧ 1 xor 0 = 1 と 1 - 1 = 0 ∧ 1 xor 1 = 0 からわかります。よって a のpopcount を k とすると 2k が解となります。これを各 a_i について求めれば良いです。

Submission #44297466 - Codeforces

C.Oh Those Palindromes

問題概要

Problem - C - Codeforces

n 文字の文字列 s が与えられる。文字列に含まれる回文の数を最大にするように s をいくつか並び替えて t とする時、t を求めよ。複数存在するときはどれを出力しても良い。

制約

  • 1 <= n <= 105

考え方

ababa という文字列が与えられた時、最大の回文数は 9 となります。なるべく文字が対称になるように文字を構成すれば良さそうという気持ちになると、同じ文字を連続して並べても最大の回文数は満たされることがわかります。よって実は s をソートするだけで条件を満たす t を構成することができます。

Submission #44302408 - Codeforces

D.Labyrinth

問題概要

Problem - D - Codeforces

n 行 m 列のマスが与えられる。初期位置として r, c が与えられる。左方向への移動は最大 x 回、右方向への移動は最大 y 回の範囲で初期位置から移動するとき、到達できるマスの最大値はいくつか?

制約

  • 1 <= n, m <= 2000
  • 1 <= r <= n, 1 <= c <= m
  • 0 <= x, y <= 109
  • マス.は移動可能、*は移動不可

考え方

初期値からx, y の制限を満たすように BFS をする。ただし移動する際に、なるべく上下の移動を優先的に行い、次に左右の移動を行うようにしたい。なぜなら以下のような場合があるためです。

※黄色のマスが初期位置。答えはすべてのマスに移動可能なので 47 です。 f:id:d_tutuz:20181015231516p:plain

このような場合、上下への移動をコスト 0 、左右への移動をコスト 1 すると 01BFS(01BFS自体の説明は別途) ができます。各マスにそれまで左右に移動した回数を保持しておいて、x, y の制約を超えないように 01BFS で移動したとき、移動可能なマスの数が解になります。

Submission #44336872 - Codeforces

E.Dwarves, Hats and Extrasensory Abilities

問題概要

Problem - E - Codeforces

インタラクティブ問題。n つの点を出力する必要がある。まずある 1 点 (x_i, y_j) を出力する。その 1 点に対して黒 or 白 と色付けされる(この部分はインタラクティブで実行時によって変わる)。すべての n つの点に黒 or 白の色付けがされたとき、最後に黒の点群と白の点群を分割するような直線になるように (a, b), (c, d) を出力せよ。

制約

  • 1 <= n <= 30
  • 0 <= x, y <= 109
  • 0 <= (x_1, y_1), (x_2, y_2) <= 109

考え方

構築問題です。なるべくシンプルに構築したい気持ちになります。なので 1 直線上で各点を構成するようにするとします。まず 2 点は任意に決めることができます。3 点目以降は直前の点の色の結果を踏まえてどこに点を打つか決めます。このようにして黒と白の点が直線上で連続した集合になるように点を決めることができそうです。そのようにして構成した点は 1 直線上にあるので、最後 2 点の位置を (l, y), (r, y) とすると、(l, y-1), (r, y+1) によって同色で分割することが可能になります。

さて、1 点目は l = 0 として (0, y) に、2 点目は r = 10^9/2 として (10^9/2, y) に点を打つことにします。3 点目以降の打ち方は二分探索の要領で l, r の座標の中点 m に打てばよいです。3 点目の点の色によって l = m とするのか、r = m のか決まります。3 点目が 2 点目と同色だった場合はより x 軸の大きい値に点を打つことになるので l = m となり、同色でなかった場合は、 x 軸のより小さい値に点を打つことになるので r = m となります。これを n まで繰り返すことで条件を満たす点を打つことができます。

なお、以下の図は、最初の 2 点が同色だった場合とそうでない場合の 3 点目の打ち方を示した図になります。同色だった場合は l = 10^9/2, r = 10^9 となり、そうでない場合は l = 0, r = 10^9/2 となります。

f:id:d_tutuz:20181016000840p:plain

Submission #44337705 - Codeforces

雑記

pretest では D も通ってまさかの自己最高の 4 完になるかと思いましたが、system test で落ちてしまいました。普通のBFSをしてしまったため、上の D のケースで 46 となってしまい・・・。

AGC013-B:Hamiltonish Path

問題

https://beta.atcoder.jp/contests/agc013/tasks/agc013_b

N 頂点 M 辺の単純無向連結グラフが与えられる。以下の条件を満たすパスを構築してください。

  • 2 個以上の頂点を通る
  • 同じ頂点を 2 度通らない
  • パスの少なくとも一方の端点と直接辺で結ばれている頂点は、必ずパスに含まれる

制約

  • 2 <= N <= 10^5
  • 2 <= M <= 10^5
  • 2 <= A_i < B_i <= N

考え方

まず構築はサンプルは無視するのが基本。条件について考える。3つ目の条件「パスの少なくとも一方の端点と直接辺で結ばれている頂点は、必ずパスに含まれる」が重要。パスの端点になる頂点については、端点と隣接している頂点はパスに含まれる必要があるので、ある頂点から DFS したときにどこにも遷移できないような頂点が端点となる。

ある頂点から DFS を 2 度行って、それぞれどこにも遷移できなくなった頂点がパスの端点となる。

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

            int n = in.nextInt(), m = in.nextInt();
            List<Integer>[] g = new ArrayList[n];
            g = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new);
            for (int i = 0; i < m; i++) {
                int a = in.nextInt()-1, b = in.nextInt()-1;
                g[a].add(b);
                g[b].add(a);
            }

            boolean[] used = new boolean[n];

            List<Integer> fore = new ArrayList<>();
            Deque<Integer> stack = new ArrayDeque<>();
            stack.add(0);
            used[0] = true;
            fore.add(0);
            while (!stack.isEmpty()) {
                int now = stack.remove();
                for (int next : g[now]) {
                    if (!used[next]) {
                        stack.add(next);
                        used[next] = true;
                        fore.add(next);
                        break;
                    }
                }
            }

            List<Integer> back = new ArrayList<>();
            stack.add(0);
            while (!stack.isEmpty()) {
                int now = stack.remove();
                for (int next : g[now]) {
                    if (!used[next]) {
                        stack.add(next);
                        used[next] = true;
                        back.add(next);
                        break;
                    }
                }
            }

            Collections.reverse(back);
            back.addAll(fore);

            out.println(back.size());
            for (int i = 0; i < back.size(); i++) {
                if (i > 0) {
                    out.print(" ");
                }
                out.print(back.get(i)+1);
            }
            out.print("\n");

        }

ポイント

  • どのような頂点が端点になりうるか考える
  • 構築はサンプルを捨てる

類題

雑記

グラフ上である頂点から 2 方向に操作を実施することはよくみる。

ARC102-E:Stop. Otherwise...

問題

https://beta.atcoder.jp/contests/arc102/tasks/arc102_c

K 面サイコロを N 回振る。サイコロは区別しない。各 i (2, 3, ..., 2K) について以下の条件を満たす場合の数を求めよ。

  • どの異なる2つのサイコロの出目の和も i にならない

制約

  • 1 <= K <= 2000
  • 1 <= N <= 2000

考え方

基礎

まずサイコロを区別しないで N 回振るときの出目の組の場合の数について考える。各サイコロの出目を区別したとして出目を l_1, l_2, ..., l_N とすると、l_1 <= l_2 <= ...<= l_N となるような (l_1, l_2, ..., l_N) の組の数である。これは [1, K] のうち N 個を重複して選ぶ場合の数と同じである。


さて、問題について考える。例として、 K = 14, i = 7 の場合について考えてみる。

「どの異なる2つのサイコロの出目の和も i にならない」という条件について考える。i が奇数の場合と偶数の場合で a + b = i (a <= b) なる (a, b) の組の個数が変わるので多少解法が異なる。まず i が奇数の場合について考える。

(A) a + b = i = 7 となる 2 つの数 (a <= b) の組み合わせは (1, 6), (2, 5), (3, 4) の 3 通りである。この 3 通りの数については条件を満たすためには、それぞれ、(a_i, b_i) のいずれか 1 つ選ぶ、またはどちらも選ばない、ような組み合わせが考えられる。

(B) a + b = i とならない K の出目 (7, 8, 9, 10, 11, 12, 13, 14) については任意個選ぶことができる。

一般化して考えよう。(A)を満たすように選ぶ時の場合の数は (a_i, b_i) の組の個数を n とし、(a_i, b_i) のいずれかから 1 つのみ選ぶ組み合わせを m 選ぶとする。(B)については (A)に含まれない N - 2n の数から N-m 個を重複して選ぶのだが、(A)で選んでいる m 個の数については任意個選んでよいので N-2n+m の数から N-m 個を重複して選ぶ組み合わせの数が求める解である。

 {}_{n} \mathrm{C} _m * 2^m * {}_{N-2n+m} \mathrm{H} _{N-m}

次に i が偶数の場合について考える。K = 14, i = 8 としよう。

(A) a + b = i = 8 (a <= b) なる組は (1, 7), (2, 6), (3, 5), (4, 4) の 4 通りである。条件を満たすためには (4, 4) である a = b の組はなかったこととすると、奇数の場合と同じ考え方で求めることができる。

(a_i, b_i) の組の個数を n とすると、n-1 つの組から 1 つのみ選ぶ組み合わせを m つ選ぶとする。さらに a = b である数を除くのでのこりの K - 2(n-1) + m - 1 の数から N-m つ選ぶ組み合わせになるが、 a = b なる数は 1 個まで選ぶことができる。

a = b の数を選ぶ場合と選ばない場合は排反であるからそれぞれの和をとって解が求めることができる。

 {}_{n-1} \mathrm{C} _m * 2^m * ({}_{N-2(n-1)+m-1} \mathrm{H} _{N-m} + {}_{N-2(n-1)+m-1} \mathrm{H} _{N-m-1})

Submission #3388960 - AtCoder Regular Contest 102

ポイント

  • 条件を満たす数の組み合わせと満たさない組み合わせを分けて考える
  • 重複組合せ

参考

sigma1113.hatenablog.com

類題

雑記

丁寧な場合分けが大切ですね。条件を満たさない組み合わせを数えようとして残念なことになりました...

AGC019-B:Reverse and Compare

問題

https://beta.atcoder.jp/contests/agc019/tasks/agc019_b

文字列 A = a_1a_2a_3...a_n が与えられる。i <= i <= j <= n なる i, j を選んで部分文字列 a_i...a_j を反転させるという操作をするとき、操作によって何通りの文字列を得ることができるか。

考え方

求めるものは異なる文字列の数である。操作によって同じ文字列になる (i, j) について考える。

たとえば A=abcdb として (2, 5) を選択して反転すると A=abdcb となる。これは (3, 4) を選んで反転させた文字列と同じである。結論としては、(i, j) として選んだ文字の端点 a_i, a_j が a_i = a_j となる場合は別の a_i' ≠ a_j' (i < i', j' < j) なる a_i' ≠ a_j' によって同じ文字列を得ることができる。

よってすべての n(n-1)/2 通りの (i, j) の選び方から a_i = a_j となるような (i, j) を選ぶ場合の数を引けば良い。

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

            char[] s = in.nextString().toCharArray();
            long n = s.length;

            long[] a = new long[26];
            for (char c : s) {
                a[c-'a']++;
            }

            long ans = n * (n-1) / 2;
            for (long l : a) {
                ans -= l * (l-1) / 2;
            }
            out.println(ans + 1);
        }

ポイント

  • 求める数はなにか
  • 同じ結果になる場合はどのような場合か

類題

AGC023-C:Painting Machines

問題

https://beta.atcoder.jp/contests/agc023/tasks/agc023_c

N 個のマスがあり白く塗られている。ある操作で i, i+1 を黒く塗ることができる。順列 P(1, 2, ..., N-1) によってすべてのマスを黒く塗るとき、はじめてすべてのマスが黒く塗られるまでの回数 k が何通りあるかそれぞれ求めよ。

制約

2 \leq N \leq 10^6

考え方

何が簡単に求めることができるだろうか。条件を緩めて求めやすい数はないか?という意識で方針を探索することが重要。

ちょうど k 回の操作ですべてのマスが黒くなる場合の数を数えると、k-1 回までは少なくとも 1 つのマスは白くなっており、k 回目の操作ですべて黒くなる場合を考えなければならない。これは数えにくい。

ちょうど k 回で塗る場合の数ではなく、k 回以下ですべて塗る場合の数を考えると k-1 回以下ですべて塗られている場合も含めて k 回ですべて塗られていればよいので、数えやすくなる。k 回以下ですべてのマスを塗る場合の数が何通りにあるか求める。

k 回以下で塗るときの必要条件は、

(A). 1, n-1k 回の中に必ず含まれる
(B). (a_1 \lt a_2, ..., \lt a_{n-1} として) 1 \leq a_i - a_{i-1} \leq 2

である。((B). によって順列の対象となる数が決まるイメージ)

(A). については 1 通りである。(B). については a_i - a_{i-1} = 1 となる回数を aa_i - a_{i-1} = 2 となる回数を b とすると以下が満たされる必要がある。

  •  a+2b = N-1
  •  a+b = k-1

上記を満たす a 個の 1b 個の 2 の順列、 a_1, a_2, ..., a_{n-1} である k つの数の順列, それ以外の n-1-k つの順列の積が k 回以下ですべてのマスを塗る場合の数となる。

あとは、ちょうど k 回の場合の数 = k 回以下の場合の数 - k-1 回以下の場合の数 であるから、求めることができる。

ポイント

  • 何が求められるか。求めやすいか考える

類題