ABC407の振り返り

sheyasutaka 参戦!
## [A問題](https://atcoder.jp/contests/abc407/tasks/abc407_a)(diff:26) ##
150点要素どこ?
$\frac{A}{B}$ 計算して小数第一位を四捨五入すればOKです。計算量は $O(1)$ です。
ちなみに $B$ が偶数だと $\frac{A}{B}$ の小数部分が $0.5$ となり答えが一意に定まらない可能性があるので、「$B$ は奇数」という制約があると思います。
ACコード(CPython11ms,C++1ms)
```python
A, B = map(int, input().split())
print(round(A / B))
```
AC時間:1:59
## [B問題](https://atcoder.jp/contests/abc407/tasks/abc407_b)(diff:55) ##
全パターン列挙ができる!
1つ目のサイコロの出目を $i$ 、2つ目のサイコロの出目を $j$ として、$6 \times 6$ パターンを全て考えれば良いです。計算量は $O(1)$ です。
誤差で1ペナを食らってしまいました…
ACコード(1ms)
```c++
#include <bits/stdc++.h>
using namespace std;

int main() {
  int X, Y, cnt = 0;
  cin >> X >> Y;
  for(int i = 1; i < 7; i++) {
    for(int j = 1; j < 7; j++) {
      cnt += (i + j >= X) || (abs(i - j) >= Y);
    }
  }
  cout << fixed << setprecision(9);
  cout << cnt / (double)36 << endl;
}
```
AC時間:4:27
## [C問題](https://atcoder.jp/contests/abc407/tasks/abc407_c)(diff:295) ##
「逆から考える」が大事
操作を逆からすることにしましょう。画面に表示される文字列を $t$ とし、$t$ ははじめ $S$ であるとします。
- <strong>ボタンA</strong>を押すと、$t$ の末尾の数字が $0$ ならそれが削除される。
- <strong>ボタンB</strong>を押すと、$t$ に含まれる全ての文字が、それぞれ前の数字に置き換わる。ここで、$1$ から $9$ までの数字については前の数字は $1$ 小さな数を表す数字とし、$0$ の前の数字は $9$ とする。

この操作を $t$ が文字列になるまで繰り返したときの操作回数の最小値を求めればよいことが分かります。ではどのように最小値を達成できるでしょうか。
まず、ボタンAを押すタイミングを考えましょう。これは、$t$ の末尾の数字が $0$ になったときに押すべきです。
次に、ボタンAを1度押した後、次にボタンAを押すまでにボタンBを押す回数を考えましょう。これは、(ボタンAを1度押した後の $t$ の末尾の数字)回押せばよいです。
これで操作回数を最小にする方法が分かりました。次に最小値の計算方法を考えます。
まず、削除する数字の個数は $|S|$ 個であるので、ボタンAを押す回数は合計で $|S|$ です。
次に、ボタンBに関しては、(ボタンAを $i$ 回押すことで、$i$ 個数字が削除されたときの $t$ の末尾の数字)を $B_i$ として、合計 $\sum_{i = 0}^{|S| - 1} B_i$ 回です。$B_i$ は、$(S_{|S| - i} - \sum_{k = 0}^{i - 1} B_k) \mod 10$ で昇順に求めることができます。
よって、最小値は $|S| + \sum_{i = 0}^{|S| - 1} B_i$ です。
計算量は $O(|S|)$ です。
実装において、$B$ を陽に構築せずに解くこともできます。
ACコード(9ms)
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  string S;
  cin >> S;
  ll ans = 0;
  for(int i = (int)S.size() - 1; i >= 0; i--) {
    ans += ((S[i] - '0') - ans + (ll)1e18) % 10;
  }
  cout << ans + S.size() << endl;
}
```
AC時間:24:06
## [D問題](https://atcoder.jp/contests/abc407/tasks/abc407_d)(diff:930) ##
盤面の状態を全列挙してドミノ配置の条件を満たすか確認する…というのをしたかったのですが条件の判定方法で詰まり、そのままACできませんでした
逆に、条件を満たす配置を全列挙する、という方法でやると上手くいくっぽいです。
全列挙に関しては再帰などでやると良いと思います。「この盤面がドミノ配置としてありえるか」のbool配列を持っておくことで重複をなくして計算量を減らす(定数倍高速化になる?)ことができます。
計算量は $O(HW2^{HW})$ です。
ACコード(14ms)
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int H, W;
vector<int> ok;
void dfs(ll v) {
  if(ok[v]) {
    return;
  }
  ok[v] = 1;
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if((v >> (i * W + j)) & 1) {
        continue;
      }
      if(i < H - 1 && (~(v >> ((i + 1) * W + j)) & 1)) {
        dfs(v ^ (((1 << W) + 1) << (i * W + j)));
      }
      if(j < W - 1 && (~(v >> (i * W + j + 1)) & 1)) {
        dfs(v ^ (3 << (i * W + j)));
      }
    }
  }
}

int main() {
  cin >> H >> W;
  vector<vector<ll>> A(H, vector<ll>(W));
  for(auto &o : A) {
    for(ll &p : o) {
      cin >> p;
    }
  }
  ok.assign(1 << (H * W), 0);
  dfs(0);
  ll ans = 0;
  for(int k = 0; k < (1 << (H * W)); k++) {
    if(!ok[k]) {
      continue;
    }
    ll tmp = 0;
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        tmp = tmp ^ ((k >> (i * W + j) & 1) ? 0 : A[i][j]);
      }
    }
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}
```
## 感想 ##
下(パフォ704,レート759)
D問題の変化に追いつきたい、あと5完がしたいです