Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

4完3WA。

各問題

A - Saturday

一文字目はTuesdayとThursdayがかぶってるのですが、二文字目はo, u, e, h, rで独立しているので、そこを見るのが一番早そうです。(ただし今気づいた)

実戦では文字列全体を比較するif文を気合で書きました...。(でも公式解説もこれですね!?)

B - Split?

列ごとに倒せていないピンを集計し、スプリットの条件に当てはまっているかを全探索すればよいです。サンプルちゃんと通していれば、1ピンを倒しているかどうかの判定で引っかかることはないでしょう。

最初、一列飛ばしでしか条件をチェックせずに1WA...。

C - Index × A(Continuous ver.)

左から順に考えます。

最初の B1 = (B_A1, B_A2, ... , B_AM) に対しての値は B_A1 + 2 * B_A2 + ... M * B_AM で次の B2 = (B_A2, B_A3, ... , B_AM+1) に対しての値は B_A2 + 2 * B_A3 + ... M * B_AM+1 です。B2 - B1 = - (B_A1 + B_A2 + ... M * B_AM) + M * B_AM+1となり、つまり一つ範囲を移動するたびに、元の範囲のAの和を引いて追加される位置のAにMを掛けたものが加算されます。範囲の和はあらかじめ累積和を取っておくことで求められるので、全体でO(N)で解けることになります。

D - Index × A(Not Continuous ver.)

DはDPのDです。制約もDPと言ってます。

というわけ?で、i文字目まででj文字取った時の最大値、でDPをすればよいです。

自分はテンプレにINF = 10^9+1LINF = 10^18+1を用意しているのですが、DPの初期値に前者を使ってしまい2WA。あほすぎる。

E - Erasing Vertices 2

なーんもわからず。にぶたん?

まとめ

ちょっと不出来だけど、水パフォはキープかなーと思ってたら、ちょっと足らなかった...。