AtCoder Beginner Contest 314 (ABC314) A~E C++解説

<!--
colorcode
灰:#808080
茶:#804000
緑:#008000
水:#00C0C0
青:#0000FF
黄:#C0C000
橙:#FF8000
赤:#FF0000
-->
**追記:今後色々書くときは**[**はてなブログ**](https://deltastruct.hatenablog.com)**を利用します。この記事も今後編集するときは**[**はてなブログ版**](https://deltastruct.hatenablog.com/entry/abc314)**を利用します。**
A~Eの5完、775位で1646perfでした。
## A- 3.14
### 問題リンク
https://atcoder.jp/contests/abc314/tasks/abc314_a
### 問題情報
|||
|:--:|:--:|
|Point|100|
|TimeLimit|2sec|
|MemLimit|1024MB|
|Difficulty|<font color="#808080">30</font>|
### 解説
<a href=https://atcoder.jp/contests/newjudge-2308-algorithm/tasks/abc264_a>新ジャッジコンテストでも出ました、ABC264-A</a>の類題です。
問題文から3.14...をコピペして、先頭からN+2文字を切り出したものを出力すれば良いです。
### ACコード
```cpp:ABC314-A.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  string s = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
  cout << s.substr(0, n+2) << endl;
}
```
https://atcoder.jp/contests/abc314/submissions/44489104
|Info|Score|
|:-:|:-:|
|MaxExecTime|1ms|
|MaxUseMemory|3644KB|
|CodeSize|241Byte|
## B- Roulette
### 問題リンク
https://atcoder.jp/contests/abc314/tasks/abc314_b
### 問題情報
|||
|:--:|:--:|
|Point|200|
|TimeLimit|2sec|
|MemLimit|1024MB|
|Difficulty|<font color="#808080">135</font>|
### 解説
$X$に賭けた人の一覧を作成し、その中から賭けた個数が最小の人たちを昇順に出力すればよいです。
### ACコード
```cpp:ABC314-B.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n;
  vector<set<int>> A(n);
  for (auto& a:A){
    int s,t;
    cin >> s;
    for (int i(0);i < s;++i) (cin>>t),a.emplace(t);
  }
  int x; cin >> x;
  vector<int> B; int k(0);
  for (auto& a:A){
    if (a.find(x)!=a.end()) B.emplace_back(k);
    ++k;
  }
  sort(B.begin(),B.end(),[&A](const int& x,const int& y){
    return (A[x].size()<A[y].size());
  });
  int i(0);
  for (auto a:B){
    if (A[a].size()!=A[B[0]].size()) break;
    ++i;
  }
  cout << i << endl;
  sort(B.begin(),B.begin()+i);
  for (int l(0);l < i;++l){
    cout << B[l]+1 << endl;
  }
}
```
https://atcoder.jp/contests/abc314/submissions/44495585
|Info|Score|
|:-:|:-:|
|MaxExecTime|2ms|
|MaxUseMemory|3828KB|
|CodeSize|662Byte|

この提出では2回[std::sort()](https://cpprefjp.github.io/reference/algorithm/sort.html)をしていますが、[std::stable_sort()](https://cpprefjp.github.io/reference/algorithm/stable_sort.html)1回でもACできます。

https://atcoder.jp/contests/abc314/submissions/44604252
|Info|Score|
|:-:|:-:|
|MaxExecTime|2ms|
|MaxUseMemory|3712KB|
|CodeSize|637Byte|
## C- Rotate Colored Subsequence
### 問題リンク
https://atcoder.jp/contests/abc314/tasks/abc314_c
### 問題情報
|||
|:--:|:--:|
|Point|300|
|TimeLimit|2sec|
|MemLimit|1024MB|
|Difficulty|<font color="#808080">342</font>|
### 解説
まず、二次元配列$p$を作成します。$p_i$は色$i$で塗られた文字の位置(昇順)です。
ここで実装を楽にするために一つ、巡回シフトについて考察を行いましょう。
```mermaid
graph LR
  1 ~~~ 2 ~~~ 3 ~~~ 4 ~~~ 5
```
このリストを巡回シフトすると、以下のようになります。
```mermaid
graph LR
  5 ~~~ 1 ~~~ 2 ~~~ 3 ~~~ 4
```
では最初のリストを巡回シフトしていきましょう。
まず2番目の要素を1にします。このとき1は1番目にあるので、1番目の要素と2番目の要素をswapします。
```mermaid
graph LR
  2 ~~~ 1 ~~~ 3 ~~~ 4 ~~~ 5
```
次に3番目の要素を2にします。このとき2は1番目にあるので、1番目の要素と3番目の要素をswapします。
```mermaid
graph LR
  3 ~~~ 1 ~~~ 2 ~~~ 4 ~~~ 5
```
残りもやっていきましょう。
```mermaid
graph LR
  4 ~~~ 1 ~~~ 2 ~~~ 3 ~~~ 5
```
```mermaid
graph LR
  5 ~~~ 1 ~~~ 2 ~~~ 3 ~~~ 4
```
気づきましたか？
2~$k$番目の要素について2番目から一回ずつ先頭要素とswapを行うと巡回シフト後のリストを得ることができます。
これを文字列で実装することでACできます。
### ACコード
```cpp:ABC314-C.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n, m; cin >> n >> m;
  string s; cin >> s;
  vector<int> A(n); for (int& a:A) cin >> a;
  vector<vector<int>> B(m);
  for (int i(0);i < n;++i){
    B[A[i]-1].emplace_back(i);
  }
  for (auto& a:B){
    for (int i(1);i < a.size();++i){
      swap(s[a[0]],s[a[i]]);
    }
  }
  cout << s << endl;
}
```
https://atcoder.jp/contests/abc314/submissions/44500160
|Info|Score|
|:-:|:-:|
|MaxExecTime|50ms|
|MaxUseMemory|15124KB|
|CodeSize|402Byte|
## D- LOWER
### 問題リンク
https://atcoder.jp/contests/abc314/tasks/abc314_d
### 問題情報
|||
|:--:|:--:|
|Point|400|
|TimeLimit|2sec|
|MemLimit|1024MB|
|Difficulty|<font color="#804000">585</font>|
### 解説
~~多分色々方法はあるだろうが考えるのが面倒だったので~~[std::bitset](https://cpprefjp.github.io/reference/bitset/bitset.html)で愚直に解きました。
注意点ですが**間違ってもクエリ2、クエリ3はfor文等で処理しないでください**。
メンバ関数の[set()](https://cpprefjp.github.io/reference/bitset/bitset/set.html)、[reset()](https://cpprefjp.github.io/reference/bitset/bitset/reset.html)を使わないと高速化できません。
### ACコード
```cpp:ABC314-D.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
  bitset<(int)(5e5)> B;
  int n; string s; cin >> n >> s;
  char c;
  for (int i(0);i < n;++i) if ('a'<=s[i]) B[i] = 1,s[i]=s[i]-('a'-'A');
  int q, a, b; cin >> q;
  for (int i(0);i < q;++i){
    cin >> a >> b >> c;
    if (a==1){
      --b;
      s[b]=c;
      if ('a'<=s[b]) B[b] = 1,s[b]=s[b]-('a'-'A');
      else B[b]=0;
      continue;
    }
    if (a==2) B.set();
    else B.reset();
  }
  for (int i(0);i < n;++i) cout << (char)(s[i]+(B[i]?'a'-'A':0));
  cout << endl;
}
```
https://atcoder.jp/contests/abc314/submissions/44507074
|Info|Score|
|:-:|:-:|
|MaxExecTime|588ms|
|MaxUseMemory|4400KB|
|CodeSize|561Byte|
## E- Roulettes
### 問題リンク
https://atcoder.jp/contests/abc314/tasks/abc314_e
### 問題情報
|||
|:--:|:--:|
|Point|475|
|TimeLimit|2sec|
|MemLimit|1024MB|
|Difficulty|<font color="#0000FF">1722</font>|
### 解説
期待値DPです。
dpテーブルは$dp_i = $ 既に$i$ポイント持っているときの「$M$ポイント以上獲得するまでの支払金額の期待値」で、$dp_M = $ 0です。
漸化式を求めます。
私は[この問題](https://atcoder.jp/contests/abc263/tasks/abc263_e)の解説を見ながら求めました。
```math
dp_i = min_{0 \le k < N} \, \frac{1}{P_i}(\, \sum_{j=0}^{P_i} dp_{min(i+S_{k, j}, M)} \,)+C_k
```
:::note warn
以降は0以上$M$以下の全ての$i$についてdpテーブルの初期値を$dp_i = $ 0とする。[^1]
:::
このままでは式に自己ループが含まれている($S_{k, j} =$ 0の場合)があるので、式変形をします。
ここで配列$D$を定義し、$D_k = S_k$の中の0の個数とします。
```math
dp_i- \frac{D_k}{P_i}dp_i = min_{0 \le k < N} \, \frac{1}{P_i}(\, \sum_{j=0}^{P_i} dp_{min(i+S_{k, j}, M)} \,)+C_k
```
```math
\frac{P_i-D_k}{P_i}dp_i = min_{0 \le k < N} \, \frac{1}{P_i}(\, \sum_{j=0}^{P_i} dp_{min(i+S_{k, j}, M)} \,)+C_k
```
```math
dp_i = min_{0 \le k < N} \, \frac{1}{P_i-D_k}(\, \sum_{j=0}^{P_i} dp_{min(i+S_{k, j}, M)} \,)+\frac{P_i}{P_i-D_k}C_k
```
これで自己ループを除去できました。
dpテーブルの更新は後ろからです。
### ACコード
```cpp:ABC314-E.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
  // dp[i]=min((1/P[k])(dp[min(i+j, m))+C[k])
  // 自己ループも消す
  int n, m,t; cin >> n >> m;
  vector<double> dp(m+1);
  vector A(n, vector<int>(2));
  for (auto& a:A){
    cin >> a[0] >> a[1];
    a.reserve(a[1]+2);
    for (int i(0);i < a[1];++i) (cin>>t),a.emplace_back(t);
  }
  vector<int> C(n);
  for (int i(0);i < n;++i) C[i] = count(A[i].begin()+2, A[i].end(), 0);
  set<double> S;
  for (int i(m-1);i > -1;--i){
    S.clear();
    double p, t;
    int l(0);
    for (auto& a:A){
      p = (double)1/(double)(a[1]-C[l]),t = 0;
      for (int j(0);j < a[1];++j) t+=dp[min(i+a[j+2], m)];
      S.emplace((p*t)+(double)(a[0]*a[1]/(double)(a[1]-C[l]))); ++l;
    }
    //for (auto a:S) cout << a << ' ';
    //cout << endl;
    dp[i] = *S.begin();
  }
  //for (auto a:dp) cout << a << ' ';
  cout << dp[0] << endl;
}
```
|Info|Score|
|:-:|:-:|
|MaxExecTime|3ms|
|MaxUseMemory|3956KB|
|CodeSize|923Byte|
## 感想
こんな感じの成績でした
||A|B|C|D|E|F|G|Ex|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|Point|100|200|300|400|475|475|575|625|
|TimeLimit|2sec|2sec|2sec|2sec|2sec|2sec|2sec|2sec|
|MemLimit|1024MB|1024MB|1024MB|1024MB|1024MB|1024MB|1024MB|1024MB|
|Difficulty|<font color="#808080">30</font>|<font color="#808080">135</font>|<font color="#808080">342</font>|<font color="#804000">585</font>|<font color="#0000FF">1722</font>|<font color="#0000FF">1736</font>|<font color="#C0C000">2301</font>|<font color="#FF0000">2938</font>|
|ACTime|1:51|8:59|15:42|27:17|79:24|-|-|-|
|Penalty|0|1|0|0|0|-|-|-|

トータル1475点、775位で1646perfです。
レート変動は1054(+90)、Highest更新しました。

EFが475点だったので激戦になるかと思いきやなんと期待値の問題。
一回は絶望しました。
結果的に「Sugoroku3」を過去問で見たことがあり、解説を見ながら漸化式を求められて良かったです。
青diffでしたね。Dが茶diffなので期待値DPを知らなければ崖速解きで負けてました
次の次はABC317、ゲームフリークスポンサー回です。
なんと151種類のオリジナルポストカードが151人に一枚ずつ(?)配布されます。
151...この数字はあの数字ですね！ミュウ[^2]を含めるのならけつばんも含めてほしかったな〜()
256種類の初代ポケモン[^3]を代表した151匹をぜひ入手しようと沢山の初参加者が来るはずです。
ぜひ参加してください！

[^1]:0が足し算の単位元であることを利用しています。例えば[このような実装](https://atcoder.jp/contests/abc314/submissions/44662662)の場合追加の処理が必要になります。
[^2]:確定ではないです。151といえばあのへんだよなーってだけです。
[^3]:そういう系の動画を見るのですが、初代ポケモンのポケモン内部番号が8bit整数で表されていて事実上256匹のポケモンが存在するみたいな話を聞いたことあります。化石型けつばんとか、幽霊型けつばんとか、アネ"デパミ"とかけつばんにもいろいろな種類があるらしいです。勿論バグとしてこういう挙動するんだーて思いながら見てるだけで初代持ってません。第7世代だけです。