【ABC407】AtCoder Beginner Contest 407【C++】

コンテスト名

AtCoder Beginner Contest 407（Promotion of AtCoderJobs）

コンテストURL

https://atcoder.jp/contests/abc407

開催日

2025/05/24 21:00–22:40

---

A: Approximation

解法

• $\lfloor \frac{A}{B} \rfloor$ か $\lfloor \frac{A}{B} \rfloor + 1$ のいずれかが答えである

ABC407A.cpp

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;

    int c = a / b;

    if(abs(c*b-a)<abs((c+1)*b-a)){
        cout << c << endl;
    }else{
        cout << c + 1 << endl;
    }

    return 0;
}

B: P(X or Y)

解法

• $6^2$ 通りを全探索する

ABC407B.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    int x, y;
    cin >> x >> y;

    int cnt = 0;
    for(int i=1; i<=6; i++){
        for(int j=1; j<=6; j++){
            if(i+j>=x || abs(i-j)>=y){
                cnt++;
            }
        }
    }

    printf("%.10f\n", cnt/36.0);

    return 0;
}

C: Security 2

解法

• 後ろから考える
• ボタン B を押しすぎてしまった分は、もう 1 周する

ABC407C.cpp

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

int main(){
    string s;
    cin >> s;

    int cnt = 0;
    for(int i=s.size()-1; i>=0; i--){
        if(cnt%10<=(s[i]-'0')){
            cnt += (s[i]-'0') - cnt%10;
        }else{
            cnt += (s[i]-'0') + 10 - cnt%10;
        }
    }

    cout << cnt + s.size() << endl;

    return 0;
}

D: Domino Covering XOR

解法

• 再帰関数

ABC407D.cpp

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

int h, w;
vector<vector<long long int>> A;
unordered_map<int, long long int> M;

long long int dfs(int pos, int mask){
    if(pos>=h*w){
        long long int res = 0;

        for(int  i=0; i<h*w; i++){
            if(!((mask>>i) & 1)){
                int x = i / w, y = i % w;
                res ^= A[x][y];
            }
        }

        return res;
    }

    if(M.count(mask)){
        return M[mask];
    }

    if((mask>>pos) & 1){
        return dfs(pos+1, mask);
    }

    long long int maxv = dfs(pos+1, mask);
    int x = pos / w, y = pos % w;

    if(x+1<h){
        int down = pos + w;
        if(!((mask>>down) & 1)){
            int nmask = mask | (1<<pos) | (1<<down);
            maxv = max(maxv, dfs(pos+1, nmask));
        }
    }

    if(y+1<w){
        int right = pos + 1;
        if(!((mask>>right) & 1)){
            int nmask = mask | (1<<pos) | (1<<right);
            maxv = max(maxv, dfs(pos+1, nmask));
        }
    }

    return M[mask] = maxv;
}

int main(){
    cin >> h >> w;

    A.assign(h, vector<long long int>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> A[i][j];
        }
    }

    cout << dfs(0, 0) << endl;

    return 0;
}