LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 407

Last updated at Posted at 2025-05-25

A - Approximation

問題文

O(1)

a / bの割り算の結果が、a / bに近いか、a / b + 1に近いか、判定する問題です。
制約として、

正整数Aと正の奇数Bが与えられます。

正の奇数Bとなっているので、必ずどちらかに近い結果になります。
a / bの余りを見ると良さそうです。

a \bmod b > b / 2

trueならa / b + 1
falseならa / b

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int a, b;
    cin >> a >> b;
    if((a % b) > b / 2) cout << a / b + 1 << endl;
    else cout << a / b << endl;
    return 0;
}

B - P(X or Y)

問題文

N=6としてO(N^2)(もしくはO(1))

全探索しましょう。
サイコロの２つの目を全探索しても36パターンです。
少数のfixed << setprecision((n))を勉強する問題です。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

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++;
            }
        }
    }
    cout << fixed_setprecision(9) << (double)cnt / 36.0 << endl;

    return 0;
}

C - Security 2

問題文

O(|S|)
良くある逆手順で探索する問題ですね。

全て0の文字列でも、文字列の長さは必ずボタンを押します。
sの長さを保持しましょう。

C++
    int n = s.size();

逆手順で探索します。
ボタンBを押した回数をカウントします。

対象の桁の数字 - 今まで押したボタンBの回数

にて対象の桁の数字が1桁目にあり、ボタンAを押す前の数字aを求めます。
aをmod10をして、1桁目の数字を求めます。
aが負の数の時、10を加算して正の整数にします。
この時のaが、対象の桁の数字が1桁目の時にボタンBを押した回数になります。
cntにaを加算してボタンBを押した数の合計を求めていきます。

C++
    int cnt = 0;
    while(s.size()){
        char c = s.back();
        int a = (c - '0') - cnt;
        a %= 10;
        if(a < 0) a += 10;
        cnt += a;
        s.pop_back();
    }

考察ができました。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

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

    int n = s.size();
    int cnt = 0;
    while(s.size()){
        char c = s.back();
        int a = (c - '0') - cnt;
        a %= 10;
        if(a < 0) a += 10;
        cnt += a;
        s.pop_back();
    }
    cout << cnt+n << endl;

    return 0;
}

D - Domino Covering XOR

問題文

類題

D - Hanjo

計算量についてアドバイスをくれた方がいました。
O(3^HW)(実際はより高速なはずのO(HW*2^HW)より速いのでこの計算量解析も間違っている可能性が高い)

O(3^20)
3^20 = 3486784401
制約でHWが20の時にこのぐらいかなと考えました。

全探索の問題です。
制約はH, W <= 20ではなく、

H * W <= 20

です。
コンテスト中はh*w=400と読み間違えました。
難問だと思い込んでいました。
h * w <= 20なら全探索で簡単な問題です。

今回は深さ優先探索を使用します。
分岐処理は、

  • 何もタイルを置かない
  • 横向きにタイルを置く
  • 縦向きにタイルを置く

これをH*Wのマスの数だけ判定しましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

ll H, W;
ll ans, sum;

// graph:マスの情報
// bit:どのマスにタイルが置かれているか
// n:現在探索しているタイルの場所
// num:タイルを置いたマスの値をxorして累積した値
void dfs(vector<vector<ll>>& graph, ll bit, ll n, ll num){
    // 終了条件
    if(n >= H * W){
        // 最大値の判定
        ans = max(ans, sum ^ num);
        return;
    }
    // 現在の探索の位置
    ll y = n / W;
    ll x = n % W;
    // 何も置かない

    // 縦向きにタイルを置く

    // 縦向きにタイルを置く
}

int main() {

    cin >> H >> W;
    vector<vector<ll>> graph(H, vector<ll>(W, 0));
    rep(i, H) rep(j, W) cin >> graph[i][j];
    rep(i, H) rep(j, W) sum ^= graph[i][j];

    dfs(graph, 0, 0, 0);

    cout << ans << endl;

    return 0;
}

問題文と制約からここまでコーディングができます。

  • sumは全てのマスの値をxorした値
  • ansは回答になる最大値
  • H,Wは入力から受け取るグラフの高さと横幅
  • graphはマスの情報
  • bitどのマスにタイルが置かれているか
  • nは現在探索しているタイルの場所
  • numはタイルを置いたマスの値をxorして累積した値

何もタイルを置かないは、

C++
    // 何も置かない
    dfs(graph, bit, n+1LL, num);

縦、横向きにタイルを置く時は、y,xの位置の情報が入ります。
nの値から探索のy,xの位置を計算します。
y = n / W, x = n % Wで計算できます。

縦向きにタイルを置く時、すでにタイルが置かれているか判定します。

C++
if(x+1LL<W && !(bit&(1LL<<(y*W+x+1LL))) && !(bit&(1LL<<n)))

縦向きにタイルを置く時、すでにタイルが置かれているか判定します。

C++
if(y+1LL<H && !(bit&(1LL<<((y+1LL)*W+x))) && !(bit&(1LL<<n)))

2マス分の判定が必要です。
考察が終わりましたね。
コーディングしましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

ll H, W;
ll ans, sum;

void dfs(vector<vector<ll>>& graph, ll bit, ll n, ll num){
    if(n >= H * W){
        ans = max(ans, sum ^ num);
        return;
    }
    // 現在の探索の位置
    ll y = n / W;
    ll x = n % W;
    // 何も置かない
    dfs(graph, bit, n+1LL, num);
    // 縦向きにタイルを置く
    if(x+1LL<W && !(bit&(1LL<<(y*W+x+1LL))) && !(bit&(1LL<<n))){
        ll b = bit|(1LL<<(y*W+x+1LL))|(1LL<<n);
        dfs(graph, b, n+1LL, num ^ graph[y][x] ^ graph[y][x+1]);
    }
    // 縦向きにタイルを置く
    if(y+1LL<H && !(bit&(1LL<<((y+1LL)*W+x))) && !(bit&(1LL<<n))){
        ll b = bit|(1LL<<((y+1LL)*W+x))|(1LL<<n);
        dfs(graph, b, n+1LL, num ^ graph[y][x] ^ graph[y+1][x]);
    }
}

int main() {

    cin >> H >> W;
    vector<vector<ll>> graph(H, vector<ll>(W, 0));
    rep(i, H) rep(j, W) cin >> graph[i][j];
    rep(i, H) rep(j, W) sum ^= graph[i][j];

    dfs(graph, 0, 0, 0);

    cout << ans << endl;

    return 0;
}
1
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?