競技プログラミング練習記 No.37【ABC124練習】

初回 -> [はじめに](https://qiita.com/easychoco/items/a9ae28aca97cfe47091f)

[ABC124](https://atcoder.jp/contests/abc124)を解きました。
4完です！

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-| 9ms|
| B |  4min |-| 7ms|
| C |  5min |ハミング距離| 10ms|
| D | 60min |ランレングス圧縮・しゃくとり法| 8ms|



## A - Buttons
```c++
  int a, b;
  cin >> a >> b;
  cout << max({a + b, a * 2 - 1, b * 2 - 1});
```
ボタン1とボタン2について、
ボタン1を2回
ボタン2を2回
ボタン1を1回、ボタン2を1回
のうち、最も点数が大きくなる押し方が答えですね。
`std::max`関数はタプルを利用することで3要素の比較ができます。

## B - 	Great Ocean View
``` c++
  int n, h;
  cin >> n;
  int max_h = 0, ans = 0;
  for(int i = 0; i < n; ++i)
  {
    cin >> h;
    if (max_h <= h)
    {
      max_h = h;
      ans++;
    }
  }
  cout << ans;
```
入力を受けながら、これまでにもらったものの最大値を記憶します。
そうすると、次の入力を受けた時に「海を眺められる旅館」かどうかわかります。


## C - 	Coloring Colorfully
``` c++
  string s;
  cin >> s;
  int len = s.length();

  string s01 = "";
  string s10 = "";
  for(int i = 0; i < len / 2; ++i)
  {
    s01 += "01";
    s10 += "10";
  }
  if (len & 1)
  {
    s01 += "0";
    s10 += "1";
  }

  int dist01 = 0;
  int dist10 = 0;
  for(int i = 0; i < len; ++i)
  {
    if (s[i] == s01[i]) dist01++;
    if (s[i] == s10[i]) dist10++;
  }
  cout << min(dist01, dist10);
```
入力文字列の文字を入れ替えて、少ない入れ替え回数で
"01010101..." または
"10101010..." 
のどちらかの文字列にする問題ですね。

言い換えると、入力文字列と
"01010101..." または
"10101010..."
の文字列との[ハミング距離](https://www.google.com/search?ei=EA8FX-r3G76Kr7wP9ue7yAg&q=%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2&oq=%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2)を求める問題といえますね。

入力文字列と同じ長さの
"01010101..." と "10101010..."
という文字列を作り、実際にハミング距離を求めます。
求めた距離のうち小さい方が答えになります。

## D - Handstand


``` c++
  int n, k;
  string s;
  cin >> n >> k >> s;
  vector<int> enc(1, 1);
  for(int i = 1; i < n; ++i)
  {
    if (s[i - 1] == s[i]) enc.back()++;
    else enc.emplace_back(1);
  }

  ll ans = 0;
  bool startWithZero = (s[0] == '0');
  int start_i = (startWithZero != (k & 1));

  ll sum = 0;
  if (start_i < enc.size()) sum += enc[start_i];
  for(int i = 1; i <= k; ++i)
  {
    if (start_i - i >= 0) sum += enc[start_i - i];
    if (start_i + i < enc.size()) sum += enc[start_i + i];
  }
  ans = max(ans, sum);

  for(int i = start_i + 2; i < enc.size(); i += 2)
  {
    if (i - k - 2 >= 0) sum -= enc[i - k - 2];
    if (i - k - 1 >= 0) sum -= enc[i - k - 1];
    if (i + k - 1 < enc.size()) sum += enc[i + k - 1];
    if (i + k - 0 < enc.size()) sum += enc[i + k];
    ans = max(ans, sum);
  }
  cout << ans;
```
まとまりごとに状態を切り替える問題ですね。
こういう問題は[ランレングス圧縮](https://www.google.com/search?ei=Ew8FX7S9FYnWmAXX5ZLgBA&q=%E3%83%A9%E3%83%B3%E3%83%AC%E3%83%B3%E3%82%B0%E3%82%B9%E5%9C%A7%E7%B8%AE&oq=%E3%83%A9%E3%83%B3%E3%83%AC%E3%83%B3%E3%82%B0%E3%82%B9%E5%9C%A7%E7%B8%AE)を使うとわかりやすくなります。

余談ですが、順番（≒可逆性）が必要ないときはヒストグラムを使ったりもします。
情報は圧縮すればするほど高速に処理できるようになるので、どこまで圧縮するか・どこまで可逆性を持たせるかの見極めは大事です。
今回は順番が大事なのでランレングス圧縮を使っています。

今回は、`k`回切り替えた後、逆立ち(`1`)の状態になっているものの最大サイズを求める問題ですね。
ランレングス圧縮をしているので、圧縮した配列上で、`i`を中心に`k`回切り替えた場合のサイズがどうなるかを考えます。
実際に試してみると、`i`を中心とした長さ`2k+1`の範囲の要素の和が求めるサイズだとわかります。

つまり、言い換えると、ランレングス圧縮した配列上で、長さ`2k+1`の範囲の和を最大化する問題といえます。
配列上での和を、範囲をずらしながら求めることになるので、しゃくとり法が使えますね。

`i`の始点は「入力文字列が`0`で始まるか`1`で始まるか」・「`k`が偶数か奇数か」によって変わるので注意です。
これを実装すると上のようになります。

以上です。ありがとうございました。