今回は良かったぞ。

AtCoder Beginner Contest (ABC) 089の個人的解法解説とレビューです。

問題はAtCoder公式からどうぞ。

A - Grouping 2

最大化問題。できるだけ3人グループを作っていきたい。

3人グループの数はN/3で求められる。

ここでちょっと考えると、N-N/3の答えは1か2。この余りをどっかのグループに押し込んでしまえばいい。

よって、N/3を出力すればいい。main関数がたったの4行だった。

B - Hina Arare

P W Gのひなあられが存在することが保証されている。

つまり、Yが存在すればFour、存在しなければThreeを出力すればいい。

名前の先頭の文字しか使わないので、残りの情報は切り捨てる。

名前がMで始まる人の数をtop[0]、Aで始まる人の数をtop[1]……とする。

「M,A,R」で始まる3人を選んだと仮定する。この場合の組み合わせ数はtop[0]*top[1]*top[2]で求められる。

うまくループを回して、全ての仮定パターン(5 C 3=10通り)の組み合わせの和を求める。

long longを使わないとバグることに注意(1WAした)。

計算量はO(Q)かO(H*W)ぐらいだと予測。

なんとかして、キューに対してO(1)で答えられるようにしたい。

最初はdp[i][j]=iからjまでのコストという形でメモ化再帰しようとしたが、O{(H*W)²}かかるので断念。そもそもメモリ確保ができない。

いろいろ考えてたら累積和を使う方法が降ってきた。

rui[i]={i%D(i%D!=0の場合),D(i%D==0の場合)}の場所からiの場所までのコストと定義。

すると、D<iを満たすiに対して、 rui[i]=rui[i-D]+(i-Dの場所からiの場所までのコスト)と計算できる。

キューに対しては、rui[r]-rui[l]を出力する。

計算量はO(H*W+Q)。

D問題でだいぶ止まってたんですが、なんとか解けました。

計算量の削減目標を持って考えるの、大事だと思います。

結果はこんな感じ。

3次関数グラフみたいになった、やったね

Rate:810→899(+89),Highest
perf:1363,Highest

水色レートとれたぜ pic.twitter.com/y9kFavmkrz
— Arc@競プロ (@arcslab123) March 4, 2018

最高の成績でした(｀・ω・´)