接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > hhkb2020 > HHKB プログラミングコンテスト 2020

HHKB プログラミングコンテスト 2020

hhkb2020 AtCoderBeginnerContest ABC

atcoder.jp

A - Keyboard

制約全然見てなかったのでTが1文字以上だと思ってた
'a', 'b', 'c'の3通りなのでif文
提出コード

void solve(){
    char S;
    string T;
    cin >> S >> T;
    if(S == 'Y'){
        REP(i,T.size()){
            if(T[i] == 'a') T[i] = 'A';
            if(T[i] == 'b') T[i] = 'B';
            if(T[i] == 'c') T[i] = 'C';
        }
        cout << T << endl;
    }
    else{
        cout << T << endl;
    }
}

B - Futon

マス(i,j)とマス(i+1, j)(i + 1 \lt H)が '.' のとき
あるいは、マス(i,j)とマス(i, j+1)(j + 1 \lt W)が '.' のとき答えを1加算していけばいい
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    REP(i,H) REP(j,W){
        if(i < H-1) if(fi[i][j] == fi[i+1][j] and fi[i][j] == '.') ans++;
        if(j < W-1) if(fi[i][j] == fi[i][j+1] and fi[i][j] == '.') ans++;
    }
    cout << ans << endl;
}

C - Neq Min

C++ならsetを使うと楽
0 \leq x \leq Nの整数xをsetに入れておく
その後p_iをsetから消去し、setに入っている最小の整数を出力すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    set<int> st;
    REP(i,202020) st.insert(i);
    REP(i,N){
        int m;
        cin >> m;
        st.erase(m);
        cout << *st.begin() << endl;
    }
}

D - Squares

難しい
コンテスト終わり際に縦横独立でいいじゃーんになったけど間に合わず
以下解説を参考
全体の場合の数から2つの正方形が重なる場合の数を引いてあげればいい
縦横独立に考えていいので、縦（or 横）のみを考えたときに2つの正方形が重なる場合の数（x_2）の二乗x_2^2を全体から引けばいい
これはAとBの置き方(N-A+1) \times (N - B + 1)からAとBが重ならない場合の数（x_4）を引くと求めることが出来る
x_4は赤と青を区別せずに考えた時、○正○正○○のように並べる場合の数となる（正は赤と青を区別しない正方形）
これは全体の個数N - A - B + 2から2個選ぶ_{N-A-B+2} C _2通りとなる
実際には赤青、青赤の2通りの並び方があるので
(N-A-B+2)\times(N-A-B+1)通りとなる
よってx_4 = (N-A-B+2)\times(N-A-B+1)となりx_2 = 2 \times x_4
したがって(N - A + 1) ^2 \times (N - B + 1) ^2 - x_2 ^2が答え
提出コード

void solve(){
    ll N, A, B;
    cin >> N >> A >> B;
    if(A + B > N){
        cout << 0 << endl;
        return;
    }
    mint ans = (N - A + 1) * (N - A + 1);
    ans *= (N - B + 1) * (N - B + 1);
    mint x4 = mint(N - A - B + 2) * mint(N - A - B + 1) / 2;
    mint x2 = mint(N - A + 1) * mint(N - B + 1) - x4 * mint(2);
    cout << ans - x2 * x2 << endl;
}

E - Lamps

各マスが答えにどれだけ寄与するかを考える
照明のおけるマスの個数をsumとする
あるマス(i, j)が光るには自分自身を含めた、その上下左右4方向で壁に当たるまでのマスの個数のどれかが光っていればいい
この個数をcntとすると、cntが全部光っていない場合以外はマス(i,j)が光ることになる
よってこの場合の数は2 ^ {cnt} - 1となる
また、マス(i,j)が光っているとき、残りのsum - cntの照明が光っていても光っていなくても変わらないのでその分をかけ合わせた(2 ^ {cnt} - 1) \times (2 ^ {sum - cnt})がマス(i, j)の答えに寄与する回数となる
後は、照明のおける各マスの総和を求めればいい
愚直に上下左右のマスの個数を数えると間に合わないので予め累積和で求めておく
累積和を求めるパートはABCで既出
atcoder.jp

提出コード

int UP[2020][2020],DOWN[2020][2020],LEFT[2020][2020],RIGHT[2020][2020];

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    ll sum = 0;
    REP(i,H) cin >> fi[i];
    REP(i,H) REP(j,W) if(fi[i][j] == '.') sum++;
    REP(i,H){
        int cur = 0;
        for(int j=0;j<W;j++){
            if(fi[i][j] == '#') cur = 0;
            else cur++;
            RIGHT[i][j] = cur;
        }
    }
    REP(i,H){
        int cur = 0;
        for(int j=W-1;j>=0;j--){
            if(fi[i][j] == '#') cur = 0;
            else cur++;
            LEFT[i][j] = cur;
        }
    }
    REP(j,W){
        int cur = 0;
        for(int i=0;i<H;i++){
            if(fi[i][j] == '#') cur = 0;
            else cur++;
            UP[i][j] = cur;
        }
    }
    REP(j,W){
        int cur = 0;
        for(int i=H-1;i>=0;i--){
            if(fi[i][j] == '#') cur = 0;
            else cur++;
            DOWN[i][j] = cur;
        }
    }
    mint ans = 0;
    REP(i,H) REP(j,W){
        if(fi[i][j] == '#') continue;
        ll cnt = UP[i][j] + DOWN[i][j] + LEFT[i][j] + RIGHT[i][j] - 3;
        ll res = sum - cnt;
        ans += mint(modpow(mint(2), cnt) - 1) * modpow(mint(2), res);
    }
    cout << ans << endl;
}