ABC405の振り返り

<code>if</code>・<code>else</code>・<code>else if</code>がどのような挙動をするか改めて理解
あと、これからPythonで書いたコードの実行時間はCPythonのものとなります。
## [A問題](https://atcoder.jp/contests/abc405/tasks/abc405_a)(diff:10) ##
面倒な条件分岐
まず $X$ の値で分けて、次に $R$ の値で答えを出せばよいです。
計算量は $O(1)$ です。
実装では、簡潔にするため<code>if</code>文をまとめています。
ACコード(CPython11ms, C++1ms)
```python
R, X = map(int, input().split())
if (X - 1 and 1200 <= R and R < 2400) or (2 - X and 1600 <= R and R < 3000):
  print("Yes")
else:
  print("No")
```
AC時間:2:42
## [B問題](https://atcoder.jp/contests/abc405/tasks/abc405_b)(diff:50) ##
また地味にめんどい
要素ごとのカウントをして、個数が $0$ である要素が存在すれば<code>0</code>を出力します。
あとは後ろから調べていきます。個数が $0$ である要素が初めて存在するようになった時のインデックスを $i$ として答えは $N + 1 - i$ となります。
計算量は $O(N + M)$ です。
ACコード(Cpython10ms, C++1ms)
```python
N, M = map(int, input().split())
A, cnt = list(map(int, input().split())), [0] * (M + 1);
for i in range(N):
  cnt[A[i]] += 1
f = 1
for i in range(1, M + 1):
  if (not cnt[i]) and f:
    print(0)
    f = 0
for i in range(N - 1, -1, -1):
  cnt[A[i]] -= 1
  if (not cnt[A[i]]) and f:
    print(N - i)
    f = 0
```
AC時間:7:07
## [C問題](https://atcoder.jp/contests/abc405/tasks/abc405_c)(diff:102) ##
累積和!
$i$ だけを動かすとき、答えは $\sum_{i = 1}^{N - 1} (A_i \sum_{j = i + 1}^N A_j)$ となります。
これは累積和を使うことで $O(N)$ で求めることができます。
$j$ だけを動かすとき、答えは $\sum_{j = 2}^{N} (A_j \sum_{i = 1}^{j - 1} A_i)$ となります。
これも累積和を使うことで $O(N)$ で求めることができます。さらに、各 $j$ について昇順に求めるので、累積和を配列を使わずに管理しておくこともできます。こちらの方がメモリ消費量が少ないです。
ACコード(前者48ms)
```c++
//前者
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  vector<ll> A(N + 1, 0), sum(N + 1, 0);
  for(int i = 1; i <= N; i++) {
    cin >> A[i], sum[i] = A[i] + sum[i - 1];
  }
  ll ans = 0;
  for(int i = 1; i < N; i++) {
    ans += A[i] * (sum[N] - sum[i]);
  }
  cout << ans << endl;
}
```
```c++
//後者
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  ll A, ans = 0, sum = 0;
  for(int i = 0; i < N; i++) {
    cin >> A, ans += A * sum, sum += A;
  }
  cout << ans << endl;
}
```
AC時間:4:01
## [D問題](https://atcoder.jp/contests/abc405/tasks/abc405_d)(diff:471) ##
経路復元は久しぶりにやったかも
まとめて言うと、「グリッド上での多始点BFSの経路復元」ができれば良いです。
最短経路長を管理する代わりに、「始点からある頂点への最短経路にて、その頂点の一つ前の頂点」($pre$ とします)を管理します。
あとは $pre$ の内容に沿って経路を復元すれば良いです。
計算量は $O(HW)$ です。
経路復元のif文のところで沼りました…条件分岐はちゃんとやりましょう(自戒)
ACコード(142ms)
```c++
#include <bits/stdc++.h>
using namespace std;
//ここからグラフ探索系
using Graph = vector<vector<int>>;
//グラフ探索系終わり
//library end

Graph G;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for(auto &o : S) {
    cin >> o;
  }
  vector<int> Es(0, 0), pre(H * W + 1, -1);
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(S[i][j] == 'E') {
        Es.push_back(i * W + j + 1), S[i][j] = '.';
      }
    }
  }
  G.assign(H * W + 1, vector<int>(0, 0));
  for(int i = 0; i < H - 1; i++) {
    for(int j = 0; j < W; j++) {
      if(S[i][j] != '.' || S[i + 1][j] != '.') {
        continue;
      }
      G[i * W + j + 1].push_back((i + 1) * W + j + 1), G[(i + 1) * W + j + 1].push_back(i * W + j + 1);
    }
  }
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W - 1; j++) {
      if(S[i][j] != '.' || S[i][j + 1] != '.') {
        continue;
      }
      G[i * W + j + 1].push_back(i * W + j + 2), G[i * W + j + 2].push_back(i * W + j + 1);
    }
  }
  queue<int> que;
  for(int o : Es) {
    que.push(o), pre[o] = 0;
  }
  while(!que.empty()) {
    int v = que.front();
    que.pop();
    for(int nv : G[v]) {
      if(pre[nv] != -1) {
        continue;
      }
      que.push(nv), pre[nv] = v;
    }
  }
  for(int o : Es) {
    o--, S[o / W][o % W] = 'E';
  }
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(S[i][j] != '.') {
        continue;
      }
      int d = i * W + j + 1 - pre[i * W + j + 1];
      if(d == W) {
        S[i][j] = '^';
      }
      else if(d == -W) {
        S[i][j] = 'v';
      }
      else if(d == 1) {
        S[i][j] = '<';
      }
      else {
        S[i][j] = '>';
      }
    }
  }
  for(auto o : S) {
    cout << o << endl;
  }
}
```
AC時間:42:57
## [E問題](https://atcoder.jp/contests/abc405/tasks/abc405_e)(diff:1259) ##
少し立式はできましたが二項係数のmodなどがあまりできないので練習します
## 感想 ##
微(パフォ798,レート750)
ratedコン50回目までには入緑します!(追記:達成できませんでした)