追記:今後色々書くときははてなブログを利用します。この記事も今後編集するときははてなブログ版を利用します。
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とする。¹

このままでは式に自己ループが含まれている($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...この数字はあの数字ですね！ミュウ²を含めるのならけつばんも含めてほしかったな〜()
256種類の初代ポケモン³を代表した151匹をぜひ入手しようと沢山の初参加者が来るはずです。
ぜひ参加してください！

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