ABC407個人的備忘録[A-D]

脱「貪欲貧弱」を欲望する男の備忘録です

### コンテスト概要
AtCoder Beginner Contest 407（Promotion of AtCoderJobs）

https://atcoder.jp/contests/abc407

開催日:2025年5月24日 21:00-22:40

## [A - Approximation](https://atcoder.jp/contests/abc407/tasks/abc407_a)
#### 考察
A問題150点はめんどくさそうだよね。実際めんどくさかった。
とりあえず$\frac{A}{B}$を$X\frac{Y}{B}$と帯分数表記にする。
この時$\frac{Y}{B}$が0.5を未満なら$X$,超えるなら$X+1$が答え。

0.5満未満の判定について、今回は$Y$が$\frac{B}{2}$以下かどうかで判定。
ほかにも10倍して1の位が5を超えるかで判定してもいいかも。

#### 提出
``` c++:A.cpp
#include <bits/stdc++.h>
using namespace std;

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

    int ans = a/b;//帯分数の外に出てる部分を求める。
    a %= b;//分子を求める

    if(b/2 >= a) cout << ans << endl;　//分子がb/2以下なら何もしない。
    else cout << ans + 1 << endl;//超えたら1を足す。
}
```

## [B - P(X or Y)](https://atcoder.jp/contests/abc407/tasks/abc407_b)
#### 考察
B問題250点はめんどくさそうだよね。実際そうでもなかった。
$\frac{(それが起こるパターン数)}{(すべてのパターン数)}$が確率の基本。それに当てはめるだけでOK。

まず(すべてのパターン数)は2つのさいころの出る目のパターンすべてなので、$6\times6=36$通り。

後は(それが起こるパターン数)。どうせ36通りなので全部試して当てはまるものを数えればよい。二重ループで難なくAC。

#### 提出
``` c++:B.cpp
#include <bits/stdc++.h>
using namespace std;

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

    double ans = 0,sum = 36;//分母は36確定
    
    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            if(i+j >= x || abs(i-j) >= y) ans++;//当てはまれば分子を1増やす。
            //足してXを超えるか？差がYを超えるか？を確認
        }
    }

    cout << fixed << setprecision(10) << ans / sum << endl;//割っておしまい
}
```

## [C - Security 2](https://atcoder.jp/contests/abc407/tasks/abc407_c)
#### 考察
愚直に考えると、桁数が増えれば増えるほど数の制御が難しくなる。これはボタンBが全部に作用しているから。もう少し考えやすくしたい。
ここでボタンAを「末尾が0なら削除するボタン」、ボタンBを「すべての数字を”前”の数字に置き換えるボタン」に改造。そして、目標の数字を空文字にすることを目標にする。こんな感じで問題をまるきり逆にしてしまう。

こうすればボタンBを適当に押して0になったらボタンA。という風にかなり扱いやすくなる。めんどくさい操作は逆転させると上手くいく典型例。

#### 提出
``` c++:C.cpp
#include <bits/stdc++.h>
using namespace std;

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

    reverse(s.begin(),s.end());//後ろから処理したいので文字列を逆にしておく

    int ans = 0;
    int now = 0;//どれだけ回したかを管理する
    for(auto x:s){
        int n = x - '0';

        n += now;//回った分を調整
        n %= 10;//10の余りで1桁に

        ans += n;
        now += 9*n;//数字を-1進める=数字を9進める
                   //c++は負のmodに弱いので正の数に調整
        now %= 10;

        ans++;//0を消す操作
    }

    cout << ans << endl;    
}
```

## [D - Domino Covering XOR](https://atcoder.jp/contests/abc407/tasks/abc407_d)
#### 考察
D問題425点はめんどくさそうだよね。実際凡ミスした。
今回求めるのはXOR。DPとかでは歯が立たない。大抵の場合全パターンを見るしかない。さて、制約を見るとマス目は大きくても20マス。全パターン見ても余裕そう。

というわけでDFSを使ってドミノの置き方を全パターン試す。あるマス目において「ドミノを置かない」「（置けるなら）ドミノを縦に置く」「（置けるなら）ドミノを横に置く」の3パターンを順々に試しておく。

あとはドミノのないマスにXORをかけて値を出す。それが一番デカかった奴が優勝。
こういうごり押しってプログラミングの醍醐味だよね。

#### 提出
``` c++:D.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<ll>>mp (0);
ll ans;
int h,w;

void DFS(int n){
    if(n == h*w){ //最後まで行ったらXORを計算
        ll sum = 0;
        for(auto x:mp){
            for(auto y:x){
                if(y == -1) continue;
                sum ^= y;
            }
        }

        ans = max(ans,sum);//大きいほうを採用
        return;
    }

    ll i = n/w,j = n % w;//nを行番号と列番号に整形
    /*
     0  1 2  3
     4  5 6  7
     8  9 10 11みたいに順番に調べる。
    */
    DFS(n+1);//置かない場合を調べる

    if(mp[i][j] != -1){//-1の時そこにドミノが置かれてるので無視
        ll a = mp[i][j];
        mp[i][j] = -1;//とりあえずドミノを置く

        if(j+1 < w){
            if(mp[i][j+1] != -1){//横におけるんだったらおいてみる
                ll b = mp[i][j+1];
                mp[i][j+1] = -1;
                DFS(n+1);

                mp[i][j+1] = b;//しっかり元に戻す
            }
        }
        if(i+1 < h){
            if(mp[i+1][j] != -1){//縦におけるんだったらおいてみる
                ll c = mp[i+1][j];
                mp[i+1][j] = -1;
                DFS(n+1);

                mp[i+1][j] = c;//しっかり元に戻す
            }
        }
        
        mp[i][j] = a;//しっかり元に戻す
    }

    return;
}

int main(){
    cin >> h >> w;
    
    mp.resize(h,vector<ll>(w));

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++) cin >> mp[i][j];
    }

    DFS(0);

    cout << ans << endl;    
}
```

## [E - Most Valuable Parentheses](https://atcoder.jp/contests/abc407/tasks/abc407_e)
#### 考察
ぱっと見DPをしたくなるがメモリ爆発不可避なので別の方法を考える。
上手く貪欲で括弧列が作れると考えた。まではよかったんですが。どうやら上手く貪欲を実装できませんでした。

正確には一見良さそうなのはできたんですがＷＡ祭りだったので考察が甘かった。
証明できる力が欲しい。

## 結果
ABCD(1) 4完　35:36

順位　1790位
パフォーマンス　1290

## 感想
最近Ｅ問題が解けてなさすぎる。いまいち考察を詰め切れないんだよな。
どうすればいいんでしょうか？

とりあえず水パフォを復習します。