2019-02-04

AtCoder Beginner Contest 117：D - XXOR

問題

https://atcoder.jp/contests/abc117/tasks/abc117_d

考え方

考えていた解法(貪欲)

bitのXORを考える問題なので、bitの桁ごとに考えていこう。bitごとに独立して考えることができる。 $f(X)$ について $X \le K$ という制約がなければ本当にbitごとに上から貪欲でOK。ただし $X \le K$ であるから少し工夫が必要である。

まず各bitごとに $\{A_N\}$ に含まれる $0$ or $1$ のbitの個数を求めよう。上位 $i$ 桁目のビットが $1$ である個数を $cnt_1$ とする。そのとき $X$ の上位 $i$ 桁目のbitが $1$ であれば、 $x = max(cnt_1, n - cnt_1)$ を選択できる。そうでなく $X$ の上位 $i$ 桁目のbitが $0$ であれば $x = cnt_1$ を選ぶしかない。このようにして数を選んだときの和 $\sum 2^i * x$ が解の一つである。

次に $K$ 未満の数で各桁のbitがなるべく多くなる数の集合を求めよう。つまり $11010110_{(2)}, 214_{(10)}$ と表される数を考えると

$01111111_{(2)}, 127_{(10)}$
$10111111_{(2)}, 191_{(10)}$
$11001111_{(2)}, 207_{(10)}$
$11010011_{(2)}, 211_{(10)}$
$11010101_{(2)}, 213_{(10)}$

が候補になる。これらの数は上位 $i$ 桁目のbitが $1$ である場合のみ考えればよいので高々 $logK$ 個である。

あとは候補になる数それぞれについて実際に計算して最大値を求めれば良い。

Submission #4169898 - AtCoder Beginner Contest 117

別解(桁DP)

$dp[d][tight] :=$ 上位 $d$ 桁目まで見て、今の桁まで $K$ ぴったり(tight=1)かどうかの場合の最大値

とする。ぴったりでない場合はゆるい(tight=0)と表現することとする。桁DPは基本的に

ぴったり → ぴったり
ぴったり → ゆるい
ゆるい → ゆるい

の3通りの遷移のみを考えれば良い。(実際はこの問題は $d$ 桁目が 0 の場合と 1 の場合で場合分けするが本質ではない)

よって $d=50$ 程度の数から順番に桁ごとの最大値を求めればよい。 $max(dp[0][0], dp[0][1])$ が解となる。

Submission #4174488 - AtCoder Beginner Contest 117

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

$K$ を超えないような数とXORを取る、ということを考えることが重要。

何がバグっていたか

ある数以下のビットの組み合わせの実装がバグっていた。以下のようにすればよい。

List<Long> list = new ArrayList<>();
for (int i = 50; i >= 0; i--) {
    long tmp = k;
    if ((tmp >> i & 1) == 1) {
        tmp -= 1L << i;
        tmp |= ((1L << i) - 1);
        list.add(tmp);
    }
}

得た知見(典型ポイント)

ある数以下でビットの組み合わせを求める
XORは桁ごとに独立。上位桁から考える。

類題

D - IntegerotS

2019-02-03

SoundHound Inc. Programming Contest 2018 -Masters Tournament-：D - Saving Snuuk

問題

https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d

考え方

解は $0 \le i \le n-1$ なる $i$ 年それぞれについて解を出力する必要がある。各年度それぞれについてダイクストラをするのではTLEになる。

まず $s,t$ からそれぞれの都市への最短距離を求めよう。経路は両替所を $u_k$ とすると $s \rightarrow u_k \rightarrow t$ となるためである。

最短経路が求められたら、制約の厳しいところから考えていこう。その場合は $n-1$ 年から考えていくことになる。このとき使用できる両替所は ${n}$ の両替所のみである。よって経路は一意に決まって $s \rightarrow n \rightarrow t$ となる。 $n-2$ 年の場合は $n-1$ 年の最短経路と $n-2$ の最短距離を比較して小さい値を選択すれば良い。よって $n-1$ 年から考えていくことで各年のコストが $O(1)$ で求めることができたので解を求めることができた。

Submission #4148549 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

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

条件(制約)の厳しいところから考えていく典型である。

何がバグっていたか

得た知見(典型ポイント)

条件の厳しいところから貪欲

類題

2019-02-02

LeetCode：940. Distinct Subsequences II

問題

https://leetcode.com/problems/distinct-subsequences-ii/

文字列 $S$ の部分文字列の個数を $mod(10^9+7)$ で求めよ

考え方

部分文字列DPのverify問題。公式のeditorialでは文字列の重複を許して部分文字列を生成した後、重複分の文字列数を差し引く...という解法になっている。ここではけんちょんさんの記事に従って、部分文字列を作るときに常に辞書順最小が保たれるような遷移をして、重複がないように部分文字列を生成する解法で考える。

重要なのは「同じ部分文字列を得るとしたら、辞書順最小になるように遷移する」ということである。

例として abab について考えてみる。空文字を含めて、12個の部分文字列が生成できる。DP遷移は以下の図のように遷移する(はず...)。 " は空文字とする。

f:id:d_tutuz:20190202222304p:plain — DP遷移図

DPとして個数を数え上げる場合は、部分文字列の情報は不要で単に文字列の数でまとめて足していけばよいことになる。さて、上記のように辞書順最小を保ちながら遷移するためには、今いる位置 $i$ から次の a ~ z が出てくる最小の位置の情報が必要である。これは文字列を後ろから走査することで $O(N)$ で求めることができる。

DP遷移は配るDPで考えることができて、文字列 $S$ の $i$ 文字目以降で最初に文字 $c$ が現れる位置を $next[i][c]$ とすると

$dp[next[i][c]+1] += dp[i]$

となる。DP初期値は空文字を考慮して $dp[0] = 1$ となる。

       public int distinctSubseqII(String S) {

            int MOD = 1_000_000_007;
            int n = S.length();

            int[][] next = new int[n+1][26];
            fill(next, -1);
            for (int i = n-1; i >= 0; i--) {
                for (int j = 0; j < 26; j++) {
                    next[i][j] = next[i+1][j];
                    next[i][S.charAt(i)-'a'] = i;
                }
            }

            int[] dp = new int[n+1];
            dp[0] = 1;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 26; j++) {
                    if (next[i][j] < 0) continue;
                    dp[next[i][j] + 1] += dp[i];
                    dp[next[i][j] + 1] %= MOD;
                }
            }

            int ret = 0;
            for (int i = 0; i <= n; i++) {
                ret += dp[i];
                ret %= MOD;
            }

            ret = ret - 1 + MOD;
            return ret % MOD;

        }

        void fill(int[][] a, int v) {
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[0].length; j++) {
                    a[i][j] = v;
                }
            }
        }

得た知見

辞書順最小を保つために次の文字 c までの最小のindexを保持して配るDPを考える
- 貰うDPで考える場合は next[i][c] の役割も逆になるはず

類題

雑記

なんとなく枝刈りしながらDP遷移を考えている気持ちになりました。DPなので当たり前ですが、遷移がDAGになっていることがよくわかります。

2019-02-02

DISCO presents ディスカバリーチャンネルコードコンテスト2016 予選：C - ロト2

問題

https://atcoder.jp/contests/ddcc2016-qual/tasks/ddcc_2016_qual_c

$K|A_i * A_j$ なる $(i, j)$ の組を求める問題。

考え方

単純に $O(N^2)$ では間に合わないので工夫が必要である。数学をするのだが、以下の式が成り立つ。

$A_i * A_j \% K = 0 \Leftrightarrow gcd(A_i, K) * gcd(A_j, K) \% K = 0$

直感的には $A_i$ は $K$ の素因数のみが $K$ の倍数に寄与するので最大公約数 $gcd(A_i, K)$ をとったとしても結果に影響はない...というイメージである。

$K$ の最大公約数をとることができると各 $A_i$ について同じ数をまとめて数えることができる。 $K$ の約数の個数は十分小さいので全探索できる。

Submission #4144425 - DISCO presents ディスカバリーチャンネルコードコンテスト2016 予選

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

何がバグっていたか

得た知見(典型ポイント)

個数をまとめて計算
要素数をまとめて全探索
倍数判定の言い換え $A_i * A_j \% K = 0 \Leftrightarrow gcd(A_i, K) * gcd(A_j, K) \% K = 0$

類題

2019-02-02

codeFlyer （bitFlyer Programming Contest）オープンコンテスト：B - 交通費

問題

https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b

考え方

各クエリに $O(logN)$ で答える必要がある。

交通費の条件に着目すると、 $|X_i - c| \leq d$ のとき $|x_i - c|$ 円であり、そうでない場合は $d$ 円であることから区間 $[c-d,c+d]$ に含まれる値の個数を求めたい。絶対値で場合分けして、 $c$ の右側の区間 $[c,c+d]$ と左側の区間 $[c-d,c)$ に含まれる個数を求める。

数直線上のある数以下の個数、ある数未満の個数は二分探索で求めることができる。区間の右側に含まれる個数を $cnt_r$ 左側に含まれる個数を $cnt_l$ 、それ以外の個数を $m=n-cnt_r-cnt_l$ とすると求める解は

$(\sum X_i - cnt_r * c) + (cnt_l * c - \sum X_i) + m * d$

である。

Submission #4142816 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト

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

区間の個数を二分探索で求める気持ちになると解ける。

何がバグっていたか

得た知見(典型ポイント)

区間に含まれる個数を二分探索で求める
絶対値を外すように場合分け

類題

2019-02-02

AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019：D - Nearest Card Game

問題

https://atcoder.jp/contests/aising2019/tasks/aising2019_d

考え方

まず、ゲームがすすんだときにどのようにカードが選ばれているか確認する必要がある。高橋くんは上から大きい数を選んでいくので簡単である。青木さんは $x$ に近い数から順にとっていく。高橋くんの選んだカードを T 、青木さんが選んだカードを A とすると一般的には

ATATATAAAATTTT

のようにカードが選ばれることがわかる。ある境界値までは ATAT と高橋くんと青木さんは順番にカードを選ぶことがわかり、その後は青木さんが AAAA 、高橋くんが TTTT とカードを選ぶことが分かる。境界を | で表すことにすると以下のような選び方が存在する。

ATAT|AAATTT <- 青木さんと高橋くんはカードを競合することなく選ぶことができる。
ATATA|AATTT <- $A_6(0-indexed)$ のカードを青木さんと高橋くんで取り合う(高橋くんがとることになる)

さて、カードの選び方がわかったので実装を考える。「高橋くんがカードの大きいほうから $k$ 枚選ぶことができるかどうか？」という判定問題を考えよう。これは単調である。

上から $k$ 枚選ぶとき高橋くんは $A_{N-k}(0-indexed)$ 番目のカードを $k$ 番目に選ぶことになる。このとき青木さんがすで $A_{N-k}$ をとっていなければ、高橋くんは $A_{N-k}$ のカードを選ぶことができる。(なお同じ順番で選ぶ場合は高橋くんが優先なので選ぶことができる。)青木さんが $A_{N-k}$ のカードを何番目に選ぶか求めよう。青木さんが $A_{N-k}$ のカードを選ぶとき、 $d = A_{N-k} - x$ として $[x-d, x+d]$ の値に含まれるカードはすべて選ばれていることになる。 $x-d \le A_i$ を満たす最小の $i$ を $s$ とすると $A_{N-k}$ のカードは $(n - 1 - k + 1) - (s - 1)=n-k-s+1$ 番目に選ばれることになる。

よって「高橋くんがカードの大きいほうから $k$ 枚選ぶことができるかどうか？」の解は「 $n-k-s+1 \ge k$ であれば選ぶことができる。そうでない場合は選ぶことができない。」となる。

AAATTT のとり方が分かれば、あとは偶奇ごとに分けた累積和を足せば ATATAT の T のカードの合計は簡単に求めることができる。

Submission #4142667 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019

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

まずはなによりもカードの選び方がどうなるか分かる必要がある。これは $N=10$ くらいのケースを考えればわかりそう。選び方の境界を求めるには「高橋くんが上から $k$ 枚選ぶことができるか？」という判定問題を考えればよいことがわかると実装がシンプルになりそう。計算量は $O(logN)$ だけ悪化するがほぼ無視できる。

何がバグっていたか

二分探索で ATAT|AAATTT or TATA|AATTT を満たす最大の $t$ の値を求めようとするとバグった...。

得た知見(典型ポイント)

区間の境界を二分探索で求める
判定問題を考える

類題

2019-01-30

DISCO presents ディスカバリーチャンネルコードコンテスト2019 本戦：B - 大吉数列 (Array of Fortune)

問題

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b

考え方

条件の数式 $a_j \le a_i - K\ (i \lt j)$ をぐっと睨む。条件を満たす個数が大きくなる場合は $i$ になるべく大きい数を置く場合である。 $a_i$ の大きい順に左から考えていくと $1 \le a_i \le N$ なる $a_i$ について条件を満たす数列の個数は一意に決まって、それは $max(a_i-k,0)$ 個である。

よって $r=0$ になるまで $a_i$ が大きい数から順番に左から数列を構築すると条件を満たす数列が構築できる。 $r \lt 0$ になる $a_i$ の場合はスキップする。条件を満たす数列に含まれない残りの数 $a_j$ は、残りの数をソートして、左から順におけば、 $1 \le K$ より、ソート済の数列の残りの数によって条件を満たす個数は $0$ になるので、構築することができた。