LoginSignup
2
1
@DeltaStruct

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

Last updated at Posted at 2023-08-17

追記:今後色々書くときははてなブログを利用します。この記事も今後編集するときははてなブログ版を利用します。
A~Eの5完、775位で1646perfでした。

A- 3.14

問題リンク

問題情報
Point 100
TimeLimit 2sec
MemLimit 1024MB
Difficulty 30

解説

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

ACコード

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;
}

Info Score
MaxExecTime 1ms
MaxUseMemory 3644KB
CodeSize 241Byte

B- Roulette

問題リンク

問題情報
Point 200
TimeLimit 2sec
MemLimit 1024MB
Difficulty 135

解説

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

ACコード

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;
  }
}

Info Score
MaxExecTime 2ms
MaxUseMemory 3828KB
CodeSize 662Byte

この提出では2回std::sort()をしていますが、std::stable_sort()1回でもACできます。

Info Score
MaxExecTime 2ms
MaxUseMemory 3712KB
CodeSize 637Byte

C- Rotate Colored Subsequence

問題リンク

問題情報
Point 300
TimeLimit 2sec
MemLimit 1024MB
Difficulty 342

解説

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

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

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

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

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

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

ACコード

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;
}

Info Score
MaxExecTime 50ms
MaxUseMemory 15124KB
CodeSize 402Byte

D- LOWER

問題リンク

問題情報
Point 400
TimeLimit 2sec
MemLimit 1024MB
Difficulty 585

解説

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

ACコード

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;
}

Info Score
MaxExecTime 588ms
MaxUseMemory 4400KB
CodeSize 561Byte

E- Roulettes

問題リンク

問題情報
Point 475
TimeLimit 2sec
MemLimit 1024MB
Difficulty 1722

解説

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

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

以降は0以上$M$以下の全ての$i$についてdpテーブルの初期値を$dp_i = $ 0とする。1

このままでは式に自己ループが含まれている($S_{k, j} =$ 0の場合)があるので、式変形をします。
ここで配列$D$を定義し、$D_k = S_k$の中の0の個数とします。

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

\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

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コード

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 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を知らなければ崖速解きで負けてました
次の次はABC317、ゲームフリークスポンサー回です。
なんと151種類のオリジナルポストカードが151人に一枚ずつ(?)配布されます。
151...この数字はあの数字ですね！ミュウ2を含めるのならけつばんも含めてほしかったな〜()
256種類の初代ポケモン3を代表した151匹をぜひ入手しようと沢山の初参加者が来るはずです。
ぜひ参加してください！

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

  2. 確定ではないです。151といえばあのへんだよなーってだけです。 ↩

  3. そういう系の動画を見るのですが、初代ポケモンのポケモン内部番号が8bit整数で表されていて事実上256匹のポケモンが存在するみたいな話を聞いたことあります。化石型けつばんとか、幽霊型けつばんとか、アネ"デパミ"とかけつばんにもいろいろな種類があるらしいです。勿論バグとしてこういう挙動するんだーて思いながら見てるだけで初代持ってません。第7世代だけです。 ↩

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1