AtCoder Beginner Contest 407

## A - Approximation

[問題文](https://atcoder.jp/contests/abc407/tasks/abc407_a)

O(1)

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

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

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

```math
a \bmod b > b / 2
```

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

```C++: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)

[問題文](https://atcoder.jp/contests/abc407/tasks/abc407_b)

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

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

```C++: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

[問題文](https://atcoder.jp/contests/abc407/tasks/abc407_c)

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

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

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

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

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

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

```C++: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++: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

[問題文](https://atcoder.jp/contests/abc407/tasks/abc407_d)

### 類題

[D - Hanjo](https://atcoder.jp/contests/abc196/tasks/abc196_d)

計算量についてアドバイスをくれた方がいました。
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++: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++:C++
    // 何も置かない
    dfs(graph, bit, n+1LL, num);
```

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

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

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

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

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

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

```C++: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;
} 
```