ABC-C第7弾

![result.png](https://qiita-image-store.s3.amazonaws.com/0/218584/7cd5575f-3d4e-4561-14a6-d394c9a30626.png)




- [バチャバチャ](https://not-522.appspot.com/contest/5963164948627456)
- 「列」と「経路」の解説書けてないけど1か月以内に書きます。はい。



# ABC031 「[数列ゲーム](https://beta.atcoder.jp/contests/abc031/tasks/abc031_c)」

## 考察

- 高橋君が適当な場所に点を打ったとき、青木君が点を打つ場所は$N-1$通りある。
- $N-1$通りの中で青木君が選ぶのは、青木君の得点が最大になるような場所である。
- よって、高橋君が点を打ったときの青木君の得点は一意に決まる。それと同時に高橋君の得点も確定できる。



## 解法

1. 高橋君が$i$に点を打つ。
2. そのとき青木君が点を打つ$N-1$通りを全て試す。そして、青木君の得点が最大となる場合の両者の得点を記録する。
3. 高橋君の得点は、2で記録された高橋君の得点の内の最大値である。



## [コード](https://beta.atcoder.jp/contests/abc031/submissions/2337509)

```C++
#include <bits/stdc++.h>
using namespace std;

int N;
int a[100];

int main() {
   // 入力
   cin >> N;
   for (int i = 0; i < N; i++) cin >> a[i];

   int ans = -1e8;
   for (int i = 0; i < N; i++) { // 高橋君が点を打つ
      int maxA = -1e8, maxT = -1e8;
      for (int j = 0; j < N; j++) { // 青木君が点を打つ
         if (i == j) continue;

         // 2つの丸とその間にある配列を取り出す
         vector<int> v;
         for (int k = min(i, j); k <= max(i, j); k++) {
            v.push_back(a[k]);
         }

         // 青木君と高橋君の得点をそれぞれ求める
         int size = v.size(), sumA = 0, sumT = 0;
         for (int k = 0; k < size; k++) {
            if (k % 2 == 0) {
               sumT += v[k];
            } else {
               sumA += v[k];
            }
         }

         // 青木君の点数に応じて、青木君と高橋君の得点を更新
         if (sumA > maxA) {
            maxA = sumA;
            maxT = sumT;
         }
      }
      // 答えを更新
      ans = max(ans, maxT);
   }

   cout << ans << endl;

   return 0;
}
```





## 感想

- 配列の領域外参照、使う配列をミスる、添え字をミスる、をやらかして無限に時間が溶けたため解けなかった。
- なんかちょっと複雑な問題だなーと思った。解くに、青木君の得点に応じて高橋君の得点が決まるところ。
- でも、ちゃんと考えればそんなに難しくない問題なのでACしたかった。。。


# ABC032 「[列](https://beta.atcoder.jp/contests/abc032/tasks/abc032_c)」

## 部分点

### 解法

- 愚直に試す
- $0 \leq K \leq 10^9$なので、ループ中にかけ算でオーバーフローが起こることはない。
- ただ、数列中に$0$が含まれる場合は注意する必要がある。途中でオーバーフローが起きたら$0$に到達する前にループを抜けてしまうため、うまく判定できない場合がある。なので、$0$が含まれるかどうかは最初に判定してやる。


### コード

- [部分点コード](https://beta.atcoder.jp/contests/abc032/submissions/2337658)

## 満点

- しゃくとり法ちょっとわかんないので、他のしゃくとり法の問題が出てきたときに再度考える。




# ABC033 「[数式の書き換え](https://beta.atcoder.jp/contests/abc033/tasks/abc033_c)」

## 解法

- `a*b*c*, ..., *z`みたいな掛け算を1つの塊としてみる。
- 塊が途切れた時、つまり`+`が来た時に掛け算の塊の中に$0$があるかどうかを判定する。
- 塊の中に$0$があるならば掛け算の塊は$0$になる。$0$が無いとき、掛け算の塊の1つ$0$に置き換えればその塊は$0$になる。
- こんな感じの操作を繰り返してく

## 実装


### [コード](https://beta.atcoder.jp/contests/abc033/submissions/2339459)

```C++
#include <bits/stdc++.h>
using namespace std;

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

   int cnt = 0, n = s.size();
   bool zero = false;
   for (int i = 0; i < n; i++) {
      if (s[i] == '0') zero = true;
      if (s[i] == '+') {
         if (!zero) cnt++; // 0がなければカウントをインクリメント
         zero = false; // '+'が来たら無条件でzeroを初期化する
      }
   }

   // !zeroは、最後の区間に0がないなら1プラスするという意味
   cout << cnt + !zero << endl;

   return 0;
}
```



- コンテスト中は[こんな感じに](https://beta.atcoder.jp/contests/abc033/submissions/2336702)キューを使って解いた。
- でも、キューを使うのは明らかに無駄なので、リファクタリングした。
- 上位陣の中には、式の最後に`+`を付け加えて処理しやすくしていた人もいたので、この方法使えるなーって思った。このコードが[これ](https://beta.atcoder.jp/contests/abc033/submissions/2339508)



## 感想

- コンテスト中はキューを使うという奇行に出てしまった。キューは数式扱うのに便利だった気がしたのでキューを使ったのだが。。。
- 式の最後に`+`を付け加えるのは頭いいなーって思った。


# ABC034 「[経路](https://beta.atcoder.jp/contests/abc034/tasks/abc034_c)」
- 著者が数弱なため、まともな内容が書けません。


# ABC035 「[オセロ](https://beta.atcoder.jp/contests/abc035/tasks/abc035_c)」

## 解法

- 愚直にやっていては間に合わないのでいもす法を使う。
- いもす法は区間をすべて書き換えずに、左端と右端+1だけ書き換え、最後に累積和を取る。

### [コード](https://beta.atcoder.jp/contests/abc035/submissions/2339556)

```C++
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int N, Q;
ll a[222222];

int main() {
   cin >> N >> Q;
   for (int i = 0; i < Q; i++) {
      int l, r;
      cin >> l >> r;
      l--, r--;
      a[l]++, a[r+1]--;
   }

   for (int i = 1; i < N; i++) {
      a[i] += a[i-1];
   }

   // 偶数なら0、奇数なら1を出力
   for (int i = 0; i < N; i++) {
      if (a[i]%2==0) {
         cout << 0;
      } else {
         cout << 1;
      }
   }
   cout << endl;

   return 0;
}
```