Codeforces Round 889 (Div. 1)

　A1とCの二完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 889 (Div. 1) A1とCの二完。
A1 大きい数を作ってそれで他を変えていく方針
B 二乗DPしか分からない！　二乗でも通るのかと投げてみたけどやっぱりTLE。
C A[i]がA[i+1]+xで消える確率を計算。折り返して場合の数を求めるのは覚えてたけど、細部が分からずカタラン数を復習した。

— titia (@titia_til) July 29, 2023

B. Earn or Unlock

　bitsetを使うと解けるらしいという情報を得てAC。

・問題が部分和問題に似ているので、DPするしかなさそう。

・（コンテスト中は）PyPyによるACがなく、C++でも実行時間が長いものが多い

　ということから、コンテスト中もbitsetの利用は疑ったはずなのだが、良い方法が思いつかなかった。

　実際は、部分和問題のときと同じ要領でDPテーブルを持てば解ける。

　DP[i]=1で、ちょうどindex iまで使える状態、ということを表すとすると、

・初期状態はDP[0]=1、他は0

・DP[i]=1のとき、iまでの累積和-iが答えの候補。

・DP[i]=1のとき、index i以降で1となっているものについて、DP[i+A[i]]=1と遷移させれば良い。これは、DP>>=i, DP|=(DP<<A[i]), DP<<=iのように表せる。

　となり、解ける。

　なお、現在はPyPyでのACもあるが、bitsetを書くのが簡単そうだったので久しぶりにC++を使ってみたら、昔ほど書くのに抵抗ない気がした。VSCODEを使ったら、いつのまにかボタン一つで実行できるようになっていたのも嬉しい（前はできなかったのに、なぜ？）。