輪郭をなぞるだけのブログ

浅学菲才のためにおそらく嘘も多い

Codeforces Round #637 (Div.2) - D

Codeforces DP DP の復元

DP は比較的すぐに浮かんだのに、復元できなくて詰んだ、反省。

リンク

D. Nastya and Scoreboard
codeforces.com

問題概要

f:id:OutLine:20200424153844p:plain
上図のように数字を点灯させることができる Scoreboard がある。
n 個の Scoreboard の状態が与えられるが、新たに k 個点灯させたときにできる最大数を求めよ。
(与えられた Scoreboard が数字を表示できているとは限らない。)
ちょうど k 個点灯させることで、数字を形成できない場合は -1 を出力せよ。
注意点として、i 番目の入力が左から i 桁目となる。(最初明記されていなかったらしいが…)
また、0 から始める数字列も許容されている。

ここで、Scoreboard の状態は、7 桁の 0 と 1 の羅列で与えられ、i 桁目との対応は下図のようになる。
f:id:OutLine:20200424153947p:plain

制約

1 \leq n \leq 2000
0 \leq k \leq 2000

考察

しばらく考えて、
dp[ i ][ j ] := 左から i 桁見たときに、ちょうど j 個点灯させてできる最大数
と定義する DP が浮かんだ。
ただ、これだとテーブルを string 型で持つ必要があるので、最悪計算量が O(2000^3)となり、MLE となってしまう。
落ち着け、無理だろそんなの。
というわけで、計算量の削減を考える。

string 型で持つのが厳しい制約なので、テーブルの持ち方を変えて、そこから 1 文字ずつ復元するというのが浮かぶ。
まあ、復元分からんとなって時間切れたんですけど。

DP の定義を以下のように変更する。
dp[ i ][ j ] := 右から順に見ていき n - i 個まで見たとき、ちょうど j 個点灯させて数字ができるかどうか
これだと、bool 型でテーブルを持つことができ、計算量が削減できる。

(i, j) = (n, 0) から始めて、(i, j) = (0, k) まで到達できるかどうかを調べる。
できなければ -1 を出力する。
逆から見ていくというのが重要な点で、こうすることで、復元で n 桁目まで到達したときに、0 以外の場所に行ってしまうことが防げる。
(初期値をそのように定めることで、遷移元にはなり得ないから。)

書いていて思ったが、左から遷移して右から復元でもできないことはない。
ただ、復元順とは逆向きに出力しないといけないので、右から遷移させる方が自然だろう。
本番ではそれに気が付かなかったわけであるが…

どういう遷移を辿るかを意識しましょう。(自戒)

コード

数字 x が作れるかどうかの判定を bitset で行っているが、分かりやすいやり方でよい。
bitset はあまり使ったことがなく、個人的に苦手意識があるので、今回使用してみた。
Scoreboard の状態が 2 進数表記で与えられているので、bitset で扱いやすいのではないかと思ったのも動機である。
スマートな初期化の仕方が分からなくて、本番まずそこで躓いたんだけど…

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;

string s[10] = {"1110111", "0010010", "1011101", 
                "1011011", "0111010", "1101011", 
                "1101111", "1010010", "1111111", "1111011"};

// dp[i][j] := n 桁目から始めて (n - i) 個見たときに、
//             未点灯をちょうど j 個点けた状態にできるかどうか
bool dp[2010][2010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<bitset<7>> input(n);     // 現在の Scoreboard の状態
    for(int i = 0; i < n; ++i)  cin >> input[i];

    // bs[i] := 数字 i が作れるときの Scoreboard の状態
    vector<bitset<7>> bs(10);
    for(int i = 0; i < 10; ++i) bs[i] = bitset<7>(s[i]);
    
    dp[n][0] = 1;
    for(int i = n - 1; i >= 0; --i){
        for(int j = 0; j <= k; ++j){
            // ちょうど j 個点灯できる直前の状態がなければ continue
            if(!dp[i + 1][j])   continue;

            for(int x = 0; x < 10; ++x){
                // 数字 x を今見ている Scoreboard で作れるかどうか判定する
                if(bs[x] != (input[i] | bs[x])) continue;

                // 数字 x にするのに、何個必要か
                int add = (input[i] ^ bs[x]).count();

                dp[i][j + add] |= dp[i + 1][j];
            }
        }
    }

    // 未点灯部分をちょうど k 個使う方法が存在しなければ -1 を出力
    if(!dp[0][k]){
        cout << -1 << '\n';
        return 0;
    }

    for(int i = 0; i < n; ++i){
        // 数字を降順に見ていって、遷移元がある数字を出力していく
        for(int x = 9; x >= 0; --x){
            if(bs[x] != (input[i] | bs[x])) continue;
            int dif = (input[i] ^ bs[x]).count();
            if(k - dif >= 0){
                if(!dp[i + 1][k - dif])   continue;
                cout << x;
                k -= dif;
                break;
            }
        }
    }
    cout << '\n';
}
雑記

今回はだいぶ流して書いた。
復元なかなか書く機会がないから、自分の中に落とし込めないな。
書いてからも本当にこれで大丈夫なのか、という気持ちになるし。
そもそも DP を理解できていないということを痛感させられる。

Codeforces Round #632 (Div. 2) - C

Codeforces 数え上げ 連続部分列
問題へのリンク

C - Eugene and an array
codeforces.com

問題概要

長さ n の数列 a が与えられる。区間の和が 0 となる連続部分列を含まない連続部分列の個数を求めよ。

制約

1\leq n\leq 2\times 10^5
-10^9\leq a_{i}\leq 10^9

考察

ある条件を満たす数え上げの問題である。
本番では、さっと順序立てて書けずに、こんがらがって時間を溶かしまくったので、反省として記事を書く。


まず累積和を取る。
例のごとく、
S_{i} := 左から i 個目まで取った時の累積和
としておく。
このとき、区間 [l, r) の和は、S_{r} - S_{l - 1} で求められる。
すると、ある区間 [l, r) の和が 0 になるということは、S を用いて以下のように表現できる。
S_{r} - S_{l - 1} = 0
つまり
S_{l - 1} = S_{r}

(この段落の説明は、後述で図でも示している。)
出力する答えを ans 、今見ている連続部分列を sub としておく。
基本的な方針として、sub を伸ばしていくのだが、新たに追加する要素 a_{r-1} までの累積和 S_{r} の値が、任意の sub の要素までの累積和と異なるならば、そのまま伸ばすことができる。
問題は S_{r} がある場合である。
このときはまず、sub の中で取れる連続部分列の数を ans に加算しておく。
このときに加算される値は、sub の長さを x とすると、 x \times (x+1) \ /\ 2 と計算できる。
sub の左端を l としておき、S_{r} がなくなるまで、l を右に動かしていく。
これは、sub に含まれる要素までの累積和を set などで持っておくと、尺取り法の要領でできる。
ここまでの処理をしてから、連続部分列 sub を伸ばす。
右端が n までいったときにも、最後に x \times (x+1) \ /\ 2 を ans に加算する。

ただ、これだけでは不十分である。
というのも、重複が起こり得るからで、その分を取り除いておく必要がある。
例えば、a = \{1, 3, -4, 1, 2\} であるような場合を考えてみる。
上述の手順で実験する。
f:id:OutLine:20200409195401p:plain
f:id:OutLine:20200409195414p:plain
f:id:OutLine:20200409195429p:plain
ここまでは難なく進むが、問題は次の場合 (r=3) である。
f:id:OutLine:20200409195606p:plain
連続部分列に a_{r-1} を入れようとしているが、S_{r} と等しい累積和が含まれているので、まだ含めることができない。
f:id:OutLine:20200409195947p:plain
まず、上図の矢印で囲まれた [0, 2) で取れる連続部分列の個数を ans に加算しておく。
f:id:OutLine:20200409201532p:plain
次に、上図のように累積和の等しい値がなくなるまで左端を動かす。
f:id:OutLine:20200409201540p:plain
ここまできてようやく連続部分列に a_{r-1} を含めることができる。
f:id:OutLine:20200409201547p:plain
ただ、注意深く見ると分かるが、上図の矢印部分が重複して数え上げられる。
この部分は、後の処理で再び加算されるので、a_{r-1} を含める前に、この連続部分列で取れる連続部分列の個数を ans から差し引いておく。

これで問題が解決できる。


本番では、どのデータ構造が適切かと考えているときに、重複をどう処理すればいいのかという考えに至り、ものすごくこんがらがっていた。
考えを纏めて素早くコードを書けるようになりたい。

コード

本番では尺取り部分を while 文で書いていたが、for 文で書いておく。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int64_t> S(n + 1);
    S[0] = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        S[i + 1] = S[i] + a[i];
    }
    
    int64_t ans = 0;
    int left = 0;       // 今見ている連続部分列の左端
    int len = 0;        // 今見ている連続部分列の長さ
    set<int64_t> st;    // 累積和に関する集合
    st.insert(0);
    for(int right = 1; right <= n; ++right){
        // S[r] が st に含まれていなければ、そのまま連続部分列を伸ばす
        if(st.find(S[right]) == st.end()){
            st.insert(S[right]);
            ++len;
        }
        // S[r] が st に含まれているとき
        else{
            // 直前までの連続部分列で取れる連続部分列の個数を加算
            ans += (int64_t)len * (len + 1) / 2;
            // S[r] がなくなるまで左端を動かす
            while(st.find(S[right]) != st.end()){
                st.erase(S[left++]);
                --len;
            }
            // 後にも数え上げられる重複分を取り除く
            ans -= (int64_t)len * (len + 1) / 2;
            // 右端を伸ばす
            st.insert(S[right]);
            ++len;
        }
    }
    // 残る連続部分列の分を加算
    ans += (int64_t)len * (len + 1) / 2;
    cout << ans << endl;
}
雑記

記事を書くのも久々になってしまった。
相変わらず冗長すぎる。

KMP なり学んだアルゴリズムを書こうと思っていたが、めんどくさくなって下書きに溜まっていく一方である。
ブログを備忘録として用いるために、ちゃんと書こうね…

Atcoder では緑から水 (現在 : 緑)、Codeforces では緑から青 (現在 : 青) をさまよっている。
今回で再び青になった。
全く安定しなくて笑うほかない。

追記

この操作を使える問題には、例えばこれがある。
D - Xor Sum 2

ARC100 E問題 Or Plus Max

競技プログラミング 部分集合列挙 高速ゼータ変換 Atcoder

atcoder.jp

問題概要

長さ2^{N} の整数列 A_{0}, A_{1}, ..., A_{2^{N} - 1} がある。
1 \leq K \leq 2^{N} - 1 を満たすすべての整数 K に対して、次の問題を解く。

  • 整数 i, j に対して、0 \leq i < j \leq 2^{N} - 1, (i or j) \leq K を満たす A_{i} + A_{j} の最大値を求める。ただしここで or はビットごとの論理和を表す。
制約

1 \leq N \leq 18
1 \leq A_{i} \leq 10^{9}

考察 → 実装

ある K を見ているとき、最大値に関わり得る要素の配列上の添え字は K 以下である。
というのも論理和を取っているので、K より大きい添え字が関わると論理和が K より大きくなってしまい、条件を満たさないからである。
K 未満の最大値はすでに決まっているので、新しく最大値になり得るものとして、添え字の論理和が K (以下)となるものを考える。
これは、K を 2 進表記で表したときの部分集合に属する添え字の要素を見ていけばよい。
例えば、K = 6\ (=110) のときは、部分集合は \{000, 010, 100, 110\} となるので、見るべき添え字は \{0, 2, 4, 6\} となる。
これらの要素で最大値と 2 番目に大きい値との和と、K 未満での最大値とを比較すれば、K での答えが求まる。

部分集合列挙であるが、ビット全探索のループの中でもう一度ビット全探索をやってしまうと、O(4^N) かかってしまう。
部分集合列挙を次のように高速化することで、部分集合列挙の計算量は、2^{popcount(S)} とすることができる。
ここで、popcount(S) は、ビット全探索中で今見ている数 S を 2 進表記で表したときに立っているビットの個数のことである。

int S;  // 対象の集合
int subset = S;  // S の部分集合
while(subset){
    /* 部分集合に対する処理をここに書く */
    subset = (subset - 1) & S;  // 部分集合更新
}

読み飛ばしてしまっていたが、蟻本にも載っている。
部分集合列挙をこのように処理することで、ビット全探索の計算量は次のようになる。

\displaystyle\sum_{S=0}^{2^{N}-1} 2^{popcount(S)}

= \begin{eqnarray*} && {}_N C _0\end{eqnarray*} 2^{0} +\begin{eqnarray*} && {}_N C_1\end{eqnarray*} 2^{1} + ... +\begin{eqnarray*} && {}_N C _N\end{eqnarray*} 2^{N}

= \displaystyle\sum_{i=0}^{N} \begin{eqnarray*} && {}_N C _i\end{eqnarray*} 2^{i}

=(2 + 1)^N

= 3^{N}


O(3^N) だと通らないと思ったが、C++ だと 700ms 前後で通ってしまった。

コード
#include <iostream>
#include <vector>
using namespace std;

#define chmax(x, y) x = max(x, y)

int main(){
    int N;
    cin >> N;
    vector<int> A(1 << N);
    for(int i = 0; i < (1 << N); ++i)   cin >> A[i];
    
    int res = 0;
    for(int K = 1; K < (1 << N); ++K){
        int firstmax = max(A[K], A[0]), secondmax = min(A[K], A[0]);
        int subset = (K - 1) & K;
        while(subset){  // 部分集合列挙
            int hoge = A[subset];
            if(hoge > firstmax)     swap(hoge, firstmax);
            if(hoge > secondmax)    swap(hoge, secondmax);
            subset = (subset - 1) & K;
        }
        chmax(res, firstmax + secondmax);
        cout << res << "\n";
    }
}
想定解 (高速ゼータ変換)

この部分集合列挙の操作は O(3^N) の bitDP などで重要になるが、今回の問題では高速ゼータ変換を用いれば、O(N\times 2^{N}) まで高速化できる。
高速ゼータ変換では DP のように値を保存していくことで、O(N \times 2^N) にできる。
O(3^N) の解き方では K の部分集合を列挙していたが、ここでは部分集合から K での最大値と 2 番目に大きい値を更新している感じだろうか。

高速ゼータ変換はまだよく分かっていない。
現時点では DP の一種という印象である。
ほぼ写経したのだが、よく分かっていない段階だと、DP テーブルを使い回さずに書いた方がよかったかもしれない。
理解が進めば書き足すかもしれないが、それは未来の自分に期待しておく。

コード
#include <iostream>
#include <vector>
using namespace std;

#define chmax(x, y) x = max(x, y)
using P = pair<int, int>;

P dp[300005];

// dp テーブルの更新
void update(P& a, P b){
    if(a.first < b.first){
        a.second = max(a.first, b.second);
        a.first = b.first;
    }
    else    chmax(a.second, b.first);
    return;
}

// 最大値になり得る値の取得
int get_value(P& a){
    return a.first + a.second;
}

int main(){
    int N;
    cin >> N;
    vector<int> A(1 << N);
    for(int i = 0; i < (1 << N); ++i){
        cin >> A[i];
        dp[i] = P(A[i], 0);
    }
    
    // 高速ゼータ変換
    for(int i = 0; i < N; ++i){
        for(int K = 0; K < (1 << N); ++K){
            if(K & (1 << i)){
                update(dp[K], dp[K ^ (1 << i)]);
            }    
        }
    }
    
    int res = 0;
    for(int K = 1; K < (1 << N); ++K){
        chmax(res, get_value(dp[K]));
        cout << res << "\n";
    }
}
参考文献

AtCoder ARC 100 E - Or Plus Max (黄色, 700 点) - けんちょんの競プロ精進記録
高速ゼータ・メビウス変換 - Mister雑記
bitによる部分集合の列挙 と 数学的理解 - Ark's Blog

ARC037 C問題 億マス計算

競技プログラミング 二分探索 Atcoder

昨日の ABC155 の D 問題の類題であり、D 問題はこれを引っ張ってきて何とか通せた。
実装を無限にバグらせて、通ったのコンテスト終了 10 分前くらいだけど…


atcoder.jp

問題概要

長さ N の数列 a, b が与えられる。
a_{i} \times b_{j} の計算で現れた N^2 個の値を昇順で並べたときの K 番目にある値は何か。

制約

1 \leq N \leq 30000
1 \leq K \leq N^{2}
1 \leq a_{i} \leq 10^{9}
1 \leq b_{j} \leq 10^{9}

(考察 →) 実装

基本問題っぽいけど、よく分からないとなってた気がする。

まず、愚直に計算してソートは、O(N^2 \log N^{2}) となって間に合わない。

そこで、答えとなる X を決め打ちする。
二分探索でよくある (?) 答えの決め打ちである。
ここで、X が K 番目の値になり得る条件というのは、X 以下の値が K 個以上あることである、と言い換えることができる。
これを二分探索時の判定条件にする。

次に、個数をどう数えるかだが、積が X 以下であるというのは、
a_{i} \times b_{j} \leq X　つまり　b_{j} \leq X / a_{i}
と書くことができる。
この個数も二分探索で求めることができる。
二分探索のために、数列 b をあらかじめ昇順でソートしておく。
a_{i} を見ているとき、a_{i} \times b_{j} が X 以下である個数は、 X / a_{i} より大きくなる最初の位置 (イテレータ) を調べれば、求めることができる。
(そのイテレータを it とすると、it - b.begin() で個数は求まる。)

手順をまとめると、

  1. 数列 b を昇順にソートする。
  2. X を (ng, ok] で二分探索する。 このとき、数列 a の要素を順に見ていき、数列 b の要素との積が X 以下となる個数を数え上げる。 この個数を K と比較して、範囲を狭めていく。

これで、計算量は、ソート部分が O(N \log N)、二分探索部分が O(\ N \log N \times \log(max(a_{i} \times b_{j}))\ ) となり解くことができる。

コード

横着して上限部分を 10^{18} にしている。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
using namespace std;

int64_t N, K;
vector<int64_t> a, b;

// X 以下の数が K 個以上か否か
// K 個以上あれば、(ng, ok] → (ng, mid]
// K 個以上なければ、(ng, ok] → (mid, ok]
bool check(int64_t X){
    int64_t cnt = 0;
    for(int i = 0; i < N; ++i){
        // a_i * b_j が X 以下になる個数を足していく
        cnt += upper_bound(b.begin(), b.end(), X / a[i]) - b.begin();
    }
    return cnt >= K;
}

int main(){
    cin >> N >> K;
    a.resize(N);
    b.resize(N);
    for(int i = 0; i < N; ++i)  cin >> a[i];
    for(int i = 0; i < N; ++i)  cin >> b[i];
    sort(b.begin(), b.end());
    
    // (ng, ok] で二分探索
    int64_t ng = 0, ok = 1e+18;
    while(ok - ng > 1){
        int64_t mid = (ng + ok) / 2;
        if(check(mid))  ok = mid;
        else    ng = mid;
    }
    cout << ok << endl;
}

ABC155 の D 問題は、答えが、負、0、正のうちどの場合かを判定し、0 以外の場合に上述のような操作をしていけば解ける。
それに手こずりすぎていたわけだが…

入水はギリギリならず… (レート : 1197)
Codeforces は無事に水色に戻った。

FUN'S PROJECT LAB のイベントに行ってきた

イベント アニラジ 雑記

本渡楓と楠木ともりの FUN'S PROJECT LAB のイベントに行ってきた。
あまりチケットが取れる期待していなかったのだが、昼の部と夜の部ともに取れた。
本渡上陸作戦は単独イベントまで 4 年いかないくらいかかったのに、ゲストがいるとは言え 1 年足らずで単独イベントってどういうことだ…？(笑)
まあ、4 年前とかはこの沼に嵌ってなかったんだけど。

正直、東京行くのしんどいなあ… (ライブ・イベント前は近場でさえこうなる。) という感じだったが、すごくおもしろくてめっちゃ笑った。
イベント最高 ! 一番好きなイベントです(?)
最近は勉強しなければとようやくなったので、アニメやアニラジをなかなか追いきれないなあと思っていたが、行けてよかった。
また機会があったら行きたい。


写真撮るのに時間かけるのもなあと思い、粗い写真しか取れなかったが、せっかくなので供養しておく。
これすごい。
f:id:OutLine:20200217142518j:plainf:id:OutLine:20200217142509j:plain

レート上がったので耐えたけど、この後の ABC の A 問題でいきなり WA を出して、飛び上がるのであった…(完)

Codeforces で青になった

競技プログラミング

Codeforces で青になった。
上振れすぎだが素直に嬉しい。

f:id:OutLine:20200206182403p:plain
Atcoder まだ緑なんだけど…
ここ数日やる気がなさ過ぎて、何もできていない、やばい。
こんなんでは維持できないなあ…

任意の底の対数を計算

競技プログラミング メモ

競技プログラミングというか、ほとんど高校数学の話ではあるが…
解いた問題のことを書きたいが、気力がないので、簡単な話でお茶を濁しておく。

任意の底の対数を計算したいが、C++ ではそのような関数は用意されておらず、底の変換公式に従って計算する必要がある。
例えば、\log_{A} {B} を計算したい時、
\log_{A} {B} = \frac{\log{B}}{\log{A}}
という等式を用いて計算する。(自然対数の底 e は省略)
数学はほとんど忘却の彼方なので、こんなんあったなあという感じである。
え、公式は覚えるものではないって？
それはそうなんだけど、頭の中で導出できるほどの頭は持ち合わせていないし、紙に書いて導出する気力もない。

あと、注意することとしては、A = 1 のときは実行できない点である。
log {A} = 0 となってしまい、ゼロ除算をしてしまうになるのでいけない。
そもそも底の条件に 1 ではないというのあったわ。
この操作が必要な問題を解いてるときに、少し詰まってしまった。
ゼロ除算を許すな。

// A != 1
double calc_log(double A, double B){
    return log(B) / log(A);
}

【雑記】
最近 Union-Find を連想配列で実装したりしていたが、なんか使いどころなさそうなんだよなあ…
これを使って解いた問題の解説見たら、DancingLinks とか書いてあって知らんって感じだった。
分不相応な問題解いてばかりいる気がするが、力ついてるんかなあ…