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

この投稿はQiitaに投稿した記事の移植版です。今後色々書くときははてなブログを利用します。

A~Eの5完、775位で1646perfでした。
目次

A- 3.14

問題リンク

https://atcoder.jp/contests/abc314/tasks/abc314_a

問題情報

Point	100
TimeLimit	2sec
MemLimit	1024MB
Difficulty	30

解説

新ジャッジコンテストでも出ました、ABC264-Aの類題です。 問題文から3.14...をコピペして、先頭からN+2文字を切り出したものを出力すれば良いです。

ACコード

#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	135

解説

に賭けた人の一覧を作成し、その中から賭けた個数が最小の人たちを昇順に出力すればよいです。

ACコード

#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()をしていますが、std::stable_sort()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	342

解説

まず、二次元配列を作成します。は色で塗られた文字の位置(昇順)です。 ここで実装を楽にするために一つ、巡回シフトについて考察を行いましょう。

graph LR
  1 ~~~ 2 ~~~ 3 ~~~ 4 ~~~ 5

このリストを巡回シフトすると、以下のようになります。

graph LR
  5 ~~~ 1 ~~~ 2 ~~~ 3 ~~~ 4

では最初のリストを巡回シフトしていきましょう。 まず2番目の要素を1にします。このとき1は1番目にあるので、1番目の要素と2番目の要素をswapします。

graph LR
  2 ~~~ 1 ~~~ 3 ~~~ 4 ~~~ 5

次に3番目の要素を2にします。このとき2は1番目にあるので、1番目の要素と3番目の要素をswapします。

graph LR
  3 ~~~ 1 ~~~ 2 ~~~ 4 ~~~ 5

残りもやっていきましょう。

graph LR
  4 ~~~ 1 ~~~ 2 ~~~ 3 ~~~ 5

graph LR
  5 ~~~ 1 ~~~ 2 ~~~ 3 ~~~ 4

気づきましたか？ 2~番目の要素について2番目から一回ずつ先頭要素とswapを行うと巡回シフト後のリストを得ることができます。 これを文字列で実装することでACできます。

ACコード

#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	585

解説

多分色々方法はあるだろうが考えるのが面倒だったのでstd::bitsetで愚直に解きました。 注意点ですが間違ってもクエリ2、クエリ3はfor文等で処理しないでください。 メンバ関数のset()、reset()を使わないと高速化できません。

ACコード

#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	1722

解説

期待値DPです。 dpテーブルは 既にポイント持っているときの「ポイント以上獲得するまでの支払金額の期待値」で、 0です。 漸化式を求めます。 私はこの問題の解説を見ながら求めました。

以降は0以上以下の全てのについてdpテーブルの初期値を 0とします。*1 このままでは式に自己ループが含まれている( 0の場合)があるので、式変形をします。 ここで配列$D$を定義し、の中の0の個数とします。

これで自己ループを除去できました。 dpテーブルの更新は後ろからです。

ACコード

#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	30	135	342	585	1722	1736	2301	2938
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を知らなければ崖速解きで負けてました

*1:0が足し算の単位元であることを利用しています。例えばこのような実装の場合追加の処理が必要になります。