AtCoder Beginner Contest (ABC) 089 レビュー
今回は良かったぞ。
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
を出力すればいい。
C - March
名前の先頭の文字しか使わないので、残りの情報は切り捨てる。
名前がMで始まる人の数をtop[0]
、Aで始まる人の数をtop[1]
……とする。
「M,A,R」で始まる3人を選んだと仮定する。この場合の組み合わせ数はtop[0]*top[1]*top[2]
で求められる。
うまくループを回して、全ての仮定パターン(5 C 3
=10通り)の組み合わせの和を求める。
long long
を使わないとバグることに注意(1WAした)。
D - Practical Skill Test
計算量はO(Q)
かO(H*W)
ぐらいだと予測。
なんとかして、キューに対してO(1)
で答えられるようにしたい
。
最初はdp[i][j]=iからjまでのコスト
という形でメモ化再帰しようとしたが、O{(H*W)2}かかるので断念。そもそもメモリ確保ができない。
いろいろ考えてたら累積和を使う方法が降ってきた。
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次関数グラフみたいになった、やったね
— Arc@競プロ (@arcslab123) March 4, 2018
Rate:810→899(+89),Highest
perf:1363,Highest
水色レートとれたぜ pic.twitter.com/y9kFavmkrz
最高の成績でした(`・ω・´)