ながめも

競技プログラミングについて

トップ > コンテスト参加記 > AtCoder HHKB プログラミングコンテスト2020 参加記

AtCoder HHKB プログラミングコンテスト2020 参加記

コンテスト参加記 AtCoder 企業コン ABC グリッド 数え上げ 対称性 区間 区間の重なり 尺取り法

ABCE青パフォでした。Dが難しかったですね・・・。

A - Keyboard

問題へのリンク

解説

if文。

実装

int main() {
    char s, t;
    cin >> s >> t;
    if(s == 'Y'){
        cout << char(t - 'a' + 'A') << endl;
    }
    else{
        cout << t << endl;
    }
}

B - Futon

問題へのリンク

解説

ある点から右と下を見ます。

実装

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    cin >> S;
    int ans = 0;
    auto IsIn = [&](int i,int j) -> bool{
        return 0 <= i && i < H && 0 <= j && j < W;
    };
    rep(i,H)rep(j,W){
        if(S[i][j] == '#')continue;
        rep(k,2){
            int nx = i + dx[k];
            int ny = j + dy[k];
            if(not IsIn(nx, ny))continue;
            if(S[nx][ny] == '#')continue;
            ans++;
        }
    }
    cout << ans << endl;
}

C - Neq Min

問題へのリンク

解説

pの値がintにおさまるので、ある値が出てきたかどうかのflagを持って全て回していいです。

実装

int main() {
    int N;
    cin >> N;
    vector<ll> p(N);
    vector<bool> used(200010, false);
    rep(i,N){
        cin >> p[i];
    }
    int idx = 0;
    rep(i,N){
        used[p[i]] = true;
        while(used[idx]){
            idx++;
        }
        cout << idx << endl;
    }
}

D - Squares

問題へのリンク

解説

これめちゃくちゃ難しいですね・・・。 公式の解説が丁寧なので追って実装しました。 特に、

  • 正方形の重なりを区間の重なりに言い換える
  • xとyが対称なので独立に考えてよく、また値が同じなので結果も同じ値になる
  • 最初に余事象とった後にもう一回余事象を取る

あたりがすごく難しいと思いました。とにかく、言い換え、対称性などの力が求められる問題だと感じます。

実装

#include <atcoder/modint>
using mint = atcoder::modint1000000007;
void solve(){
    ll N, A, B;
    cin >> N >> A >> B;
    mint X4 = (N-A-B < 0) ? 0: mint(N-A-B+1) * mint(N-A-B+2) / 2;
    mint X3 = 2 * X4;
    mint X2 = (N-A+1)*(N-B+1) - X3;
    mint X1 = X2 * X2;
    mint zen1 = mint(N-A+1)*mint(N-B+1)*mint(N-A+1)*mint(N-B+1);
    mint ans = zen1 - X1;
    cout << ans.val() << endl;
}

E - Lamps

問題へのリンク

解説

いわゆる主客転倒というものです。ある座標に注目して、その座標が照らされる条件を考え、その割り振りを考えます。

ある頂点が照らされる条件は

  • その頂点が'.'である
  • 上下左右につながってる'.'の中に、少なくとも1つランプが点灯してる
  • つながっていないところはなんでも良い

です。 上下左右につながっている点の個数がわかればいいので、尺取りみたいにして実装しました。 多分もっと綺麗な実装があると思いますが。

実装

#include <atcoder/modint>
using mint = atcoder::modint1000000007;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    cin >> S;
    ll K = 0;
    rep(i,H)rep(j,W){
        K += S[i][j] == '.';
    }
    vvec<int> dh(H,vec<int>(W, 0));
    vvec<int> dw(H,vec<int>(W, 0));
    vvec<int> d(H,vec<int>(W, 0));
    rep(i,H){
        int r = 0;
        for(int l = 0; l < W;){
            while(r < W && S[i][r] == '.'){
                r++;
            }
            for(int k = l; k < r; k++){
                dh[i][k] = r - l;
            }
            if(l == r){
                l++;
                r++;
            }
            else l = r;
        }
    }
    rep(j,W){
        int r = 0;
        for(int l = 0; l < H;){
            while(r < H && S[r][j] == '.'){
                r++;
            }
            for(int k = l; k < r; k++){
                dw[k][j] = r - l;
            }
            if(l == r){
                l++;
                r++;
            }
            else l = r;
        }
    }
    rep(i,H)rep(j,W)d[i][j] = dh[i][j] + dw[i][j] - 1;
    mint ans = 0;
    rep(i,H)rep(j,W){
        if(S[i][j] == '#')continue;
        ans += (mint(2).pow(d[i][j]) - 1) * mint(2).pow(K - d[i][j]);
    }
    cout << ans.val() << endl;
}

F - Random Max

問題へのリンク

まだ見てません。