AtCoder Beginner Contest 129

D - Lamp

https://atcoder.jp/contests/abc129/tasks/abc129_d

方針

上から 行目、左から 列目のマスを と書きます。 に明かりを設置したときに、

• 左右方向に照らせるマスの数(自身を含む)を
• 上下方向で照らせるマスの数(自身を含む)を

とします。答えは の最大値です。最後の は、自身をダブルカウントしている分です。

を求めるには、まず障害物のないマスが左右方向につながった領域の、左端を見つけます。そこから障害物に達する or グリッドをはみ出すまで右側へ移動しながら、この領域の幅を数えていきます。こうして幅 を求めてから、 と代入していけばよいです。

あるマスが障害物のない領域の左端であるための条件は、「 に障害物が無い」かつ 「 に障害物がある or がグリッドの左端()」となります。

ソースコード

#include<bits/stdc++.h>
using namespace std;

int H, W;
vector<vector<int>> LR, UD;
vector<string> S;

int dfsX(int h, int w, int dx){
    // (h,w) ：探索の現在位置。
    //  dx   ：障害物のない領域の左端からこのマスまでの幅。
    if(w+1>=W || S[h][w+1]=='#'){
        // これ以上右へ進めない場合は dx を返す。
        LR[h][w] = dx;
        return dx;
    }

    // まだ右へ行ける場合は、右へ移動し dx を一つ増やす。
    LR[h][w] = dfsX(h,w+1, dx+1);
    return LR[h][w];
}

int dfsY(int h, int w, int dy){
    // dfsX と同じことを上下方向にやる
    if(h+1>=H || S[h+1][w]=='#'){
        UD[h][w] = dy;
        return dy;
    }
    UD[h][w] = dfsY(h+1,w, dy+1);
    return UD[h][w];
}

int main(){
    cin >> H >> W;
    S = vector<string>(H);
    for(int i=0; i<H; i++){
        cin >> S[i];
    }

    // LR と UD を求める。
    LR = vector<vector<int>>(H,vector<int>(W,0));
    UD = vector<vector<int>>(H,vector<int>(W,0));
    for(int h=0; h<H; h++) for(int w=0; w<W; w++){
        // (h,w) が障害物の無い領域の左端 or 上端のときに探索を始める。
        if(S[h][w]=='.'){
            if(w==0 || S[h][w-1]=='#'){
                LR[h][w] = dfsX(h,w,1);
            }
            if(h==0 || S[h-1][w]=='#'){
                UD[h][w] = dfsY(h,w,1);
            }
        }
    }
    
    int ans = 0;
    for(int h=0; h<H; h++) for(int w=0; w<W; w++){
        ans = max(ans, LR[h][w] + UD[h][w] - 1);
    }
    cout << ans << endl;
}

反省

• 左右や上下を LR や UD としてまとめるのではなく、公式の解説のように別々に取り扱った方が楽だった気がします。
• 今回実装した dfsX のような再帰的な処理は書き慣れていないのですが、別に無理に再起を使わなくても書けましたね。最初に浮かんだ方針で実装してしまう前に、一呼吸置けるようになりたいです。

E - Sum Equals Xor

https://atcoder.jp/contests/abc129/tasks/abc129_e

方針

の二進数表記の、上から数えて ビット目を と書きます。ここで index は 0 始まりとします。例えば のとき、 や となります。 も同様に定義します。また、 を2進数表記したときのビット数を とします。

まず となるとき、 の各ビットに現れる 1 は高々 1 個になります。すなわち です。これを前提に、 となる条件を考えます。
ここで の中にある 1 の数を としておきます。

(1) のとき
となればよいです。これはすなわち

• のとき
• のとき

となることと同値です。つまり となるビットは 固定で、 のビットは の 2 通りが許されることになりますから、適切な の組み合わせは 通りです。

(2) のとき
このとき と を上位ビットから比較していくと、あるところまでは が成立し続けますが、どこか ( k ビット目とします) で となります。そして、k ビット目よりも下位では の組み合わせが何であるかに関わらず、 は変わらず成立します。
よって、 となる条件は、適当な が存在して以下を満たすことです：

• 
• かつ

これは例えば10進数で と と比較するとき、上位 2 桁は一致しているが、3桁目が の方が小さいため、 と判断できることの2進数版になります。

ではこのときに の組合わせが何通りになるかを考えます。

(2-1) のとき
問題文の条件より ですから、 となってしまえば、 の残りのビット : ～ に関わらず が成立します。
よって、0ビット目は で固定。残り ビットは のどれでもよいので、適切な の組み合わせは 通りとなります。

(2-2) のとき
このとき、 でなければいけません。この元で、

• 0 ビット目から k-1 ビット目までは が成立するので、(1) と同じように考えて 通りになります。
• k ビット目は かつ ですから、 の1通りです。
• k+1 ～ N-1 ビット目は、 であればよいので、 通りです。

以上合わせて、 通りです。

(2-3) のとき
でなければいけません。このときは、(2-2) の3つ目の条件のみ無視すればよく、 通りとなります。
ただし、 のとき (2-2) は ですから、(2-2)の式はそのまま使えます。

以上合わせて、 として答えは次式で求められます。ここでシグマは なる についてのみ和をとります。
　

ソースコード

シグマの中の 3 のべき乗は繰り返し二乗法で求めました。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll mod_pow(ll n, ll p, ll mod){
    // return (n^p) % mod
    if(p==0) return 1;
    ll res = mod_pow(n*n%mod, p/2, mod);
    if(p%2==1) res = res * n % mod;
    return res;
}

int main(){
    string L;  cin >> L;
    ll N = L.length();
    ll mod = 1e9+7;

    // d を求める。
    // d[i] = 2^(L[0]～L[i] の中にある 1 の数) 
    vector<ll> d(N,0);
    d[0] = 2;
    for(int i=1; i<N; i++){
        if(L[i]=='0') d[i] = d[i-1];
        else d[i] = 2*d[i-1]%mod;
    }

    ll ans = 0;

    // (1) の場合
    ans += d[N-1];

    // (2) の場合
    for(int k=0; k<N; k++){
        if(L[k]=='0') continue;  // L[k] = 1 についてのみ和を取る

        ll tmp = 1;
        if(k>0){
            // k=0 のときは (2-2) の 1 つ目の条件を無視する
            tmp = tmp*d[k-1]%mod;
        }
        // (2-2) の 3 つ目の条件
        tmp = tmp*mod_pow(3, N-k-1, mod)%mod;

        ans = (ans +tmp)%mod;
    }    
    cout << ans << endl;
}