ABC408参加記

[ABC408](https://atcoder.jp/contests/abc408)に参加しました。
(近況報告:足の裏の皮が剥がれて痛いです。)
# [A - Timeout](https://atcoder.jp/contests/abc408/tasks/abc408_a)
150点問題。carefullyに行きたい。とりあえず、言われたことをそのまま実装する。ヒヤヒヤしながらも提出し、無事AC
<details><summary>提出コード(python,61ms)</summary>

```python
N,S = map(int,input().split())
T = list(map(int,input().split()))
la = 0
flag = True
for i in T:
  if(i - la > S):
    flag = False
  la = i
if flag:print("Yes")
else : print("No")
```
</details>

[AC](https://atcoder.jp/contests/abc408/submissions/66296751) 2:02

# [B - Compression](https://atcoder.jp/contests/abc408/tasks/abc408_b)
unique関数という便利な関数がある。それを使えばいい。(~~set?思いつけなかったけど?~~)

<details><summary>提出コード(C++,1ms)</summary>

```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N;

signed main(){
  cin>>N;
  vector<int> A(N);
  for(int &i:A) cin>>i;
  sort(A.begin(),A.end());
  A.erase(unique(A.begin(),A.end()),A.end());
  cout << (int)A.size() << endl;
  for(auto it = A.begin(); it != A.end(); it++){
    cout << (*it);
    it == prev(A.end()) ? cout << endl : cout << " ";
  }
}
```

</details>

[AC](https://atcoder.jp/contests/abc408/submissions/66301238) 4:18

# [C - Not All Covered](https://atcoder.jp/contests/abc408/tasks/abc408_c)
imosを書くだけ。(~~遅延セグ木?何それ美味しいの?~~)

<details><summary>提出コード (C++,99ms)</summary>

```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N,M;

signed main(){
  cin>>N>>M;
  vector<int> cnt(N+2);
  for(int i = 0; i < M; i++){
    int a,b; cin>>a>>b;
    cnt[a]++;
    cnt[b+1]--;
  }
  int ans = 1e7;
  for(int i = 1; i <= N+1; i++) cnt[i] += cnt[i-1];
  for(int i = 1; i <= N; i++) ans = min(ans,cnt[i]);
  cout << ans << endl;
}
```

</details>


[AC](https://atcoder.jp/contests/abc408/submissions/66308594) 7:46

# [D - Flip to Gather](https://atcoder.jp/contests/abc408/tasks/abc408_d)
$$A = \sum_{l \le i \le N}{(S_i == 0)}$$
$$B = \sum_{r \le i \le N}{(S_i == 0)}$$
$$C = \sum_{r \le i \le N}{(S_i == 1)}$$
$$D = \sum_{1 \le i \le l}{(S_i == 1)}$$
とおくと、$r$を固定して
$$\min_{1 \le l \le r}{A-B+C+D}$$を求めれば良い。
ここで、$-B+C$は定数になるので、$\min{A+D}$を累積minを用いて前計算しておけばいい。

<details><summary>提出コード (C++,25ms)</summary>

```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long

int T;

int solve(){
  int N;
  string S;
  cin>>N>>S;
  //0の累積(逆).
  vector<int> zero(N+2);
  for(int i = N-1; i >= 0; i--){
    zero[i] = zero[i+1] + (S[i] == '0');
  }
  //1の累積.
  vector<int> oone(N+2);
  for(int i = 0; i < N; i++){
    oone[i+1] = oone[i] + (S[i] == '1');
  }
  //1の累積(逆).
  vector<int> rone(N+2);
  for(int i = N-1; i >= 0; i--){
    rone[i] = rone[i+1] + (S[i] == '1');
  }
  //A+Dの最小値.
  vector<int> mini(N+2);
  for(int i = 0; i <= N; i++){
    mini[i] = zero[i+1] + oone[i];
    if(i != 0) mini[i] = min(mini[i],mini[i-1]);
  }
  int ans = N+10;
  for(int r = 0; r <= N; r++){
    int B = zero[r+1];
    int C = rone[r+1];
    ans = min(ans,mini[r] - B + C);
  }
  return ans;
}

signed main(){
  cin>>T;
  for(int i = 0; i < T; i++){
    cout << solve() << endl;
  }
}
```

</details>

[AC](https://atcoder.jp/contests/abc408/submissions/66332194) 30:25 (+1WA)

# [E - Minimum OR Path](https://atcoder.jp/contests/abc408/tasks/abc408_e)
一桁目のbitを確定させる　→　二桁目のbitを確定させる...
という流れの中で、$X$を決め打ちして判定問題をたくさん解く。
<details><summary>提出コード (C++,1553ms)</summary>

```cpp
//N桁目まで行けるな...
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N,M;
vector<vector<pair<int,int>>> G(200001);

//xは目標.
bool hava(int x){
  queue<int> Q;
  Q.push(1);
  vector<bool> visited(N+1);
  visited[1] = true;
  while(!Q.empty()){
    int now = Q.front();
    Q.pop();
    for(pair<int,int> i:G[now]){
      int next = i.first;
      int weigh = i.second;
      if(visited[next]){
        continue;
      }
      if((weigh | x) != x){
        continue;
      }
      visited[next] = true;
      Q.push(next);
    }
  }
  return visited[N];
}

signed main(){
  cin>>N>>M;
  for(int i = 0; i < M; i++){
    int u,v,w; cin>>u>>v>>w;
    G[u].push_back(make_pair(v,w));
    G[v].push_back(make_pair(u,w));
  }
  int ans = 0;
  int cnt = 0;
  bool flag = false;
  //幅優先祭.
  for(int i = 0; i < 30 && (!(hava(ans))); i++){
    for(int j = 0; j < 30; j++){
      if(hava(cnt | (1ll<<j))){
        ans = (ans | (1ll<<j));
        cnt = ans;
        if(hava(ans)) flag = true;
        break;
      }
      else{
        cnt += (1ll<<j);
      }
    }
  }
  cout << ans << endl;
}
```

</details>

[AC](https://atcoder.jp/contests/abc408/submissions/66348642) 65:17 (+1WA)

# [F - Athletic](https://atcoder.jp/contests/abc408/tasks/abc408_f)
ぱっと見、LISっぽい。ということで、セグメントツリー上で考察してみる。
まず、$1 \le |i-j| \le R$は、区間min取得の「区間」の部分をいじればよさげ。
そして、1つ目の条件を考えてみると、これはセグメント木上でのupdate処理を遅らせればいい。
<details><summary>提出コード (C++,257ms)</summary>

```cpp
//遅延セグ木(概念).
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N,D,R;
int INF = -(1e10);

class SegmentTree{
  public:
  int dat[2000009],siz = 1;
  
  void init(int N){
    siz = 1;
    while(siz < N) siz*=2;
    for(int i = 1; i < siz * 2; i++) dat[i] = INF;
  }
  
  void update(int pos, int x){
    pos = pos + siz - 1;
    dat[pos] = x;
    while(pos >= 1){
      pos /= 2;
      dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
    }
  }
  
  int query(int l, int r, int a, int b, int u){
    if(r <= a || b <= l) return INF;
    if(l <= a && b <= r) return dat[u];
    int m = (a + b) / 2;
    int ansr = query(l,r,a,m,u*2);
    int ansl = query(l,r,m,b,u*2+1);
    return max(ansr,ansl);
  }
};

signed main(){
  cin>>N>>D>>R;
  vector<pair<int,int>> HI(N);
  SegmentTree Z;
  Z.init(N+1);
  vector<int> ans(N+1);
  for(int i = 0; i < N; i++){
    int h; cin>>h; HI[i] = make_pair(h,i+1);
  }
  sort(HI.begin(),HI.end());
  for(int i = 0; i < N; i++){
    int h = HI[i].first;
    int idx = HI[i].second;
    int now = max(Z.query(max(1ll,idx-R),min(Z.siz+1,idx+R+1),1,Z.siz+1,1) + 1,1ll);
    ans[h] = now;
    //cout << h << " " << idx << " " << now << endl;
    if(h >= D) Z.update(HI[h-D].second,ans[h-D+1]);
  }
  int aa = 0;
  for(int i:ans) aa = max(i,aa);
  cout << aa-1 << endl;
}
```

</details>

[AC](https://atcoder.jp/contests/abc408/submissions/66358525) 93:21 (+1WA)

# 振り返り
Fまで解いても水perfってことは、今回は6完早解き回だった...ってコト！？
まあ、6完したという点で見ると悪くない出来だったかな。早解きを鍛えます。

ABCDEF 108:21(+3WA)
順位:1069th / 11975
perf:<font color = "00bbff"> 1498 </font>
rating:<font color = "00bbff"> 1354 </font>→<font color = "00bbff"> 1369