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

2022/9/3に開催された、NEC プログラミングコンテスト2022(AtCoder Beginner Contest 267)に参加しました。

ここ数回のABCコンテストでは5完達成が続き、レートの方もいい感じで上がってきております。目標としていた水色にもだいぶ近づいてきました。

今回のコンテストは、とりあえず水パフォを目指し、さらに水色コーダーに近づこうという気持ちで臨むこととしました。

Rated参加します。
今回も水パフォ取れるように頑張ります✊

NEC プログラミングコンテスト2022 (AtCoder Beginner Contest 267) - AtCoder https://t.co/gEvPKNbDUk
— devgenjin77 (@devgenjin77) 2022年9月3日

今回の結果

前回に続いて、5完を確保することに成功しました！

パフォーマンスは、水色の真ん中ぐらいまで出て、レートは大幅に上昇。水色コーダーに、さらに一歩近づくことができました！

5完水パフォで勝ち！😂😂😂
devgenjin77さんのNEC プログラミングコンテスト2022 (AtCoder Beginner Contest 267)での成績：1195位
パフォーマンス：1411相当
レーティング：1149→1178 (+29) :)
Highestを更新しました！#AtCoder #NECプログラミングコンテスト2022(ABC267) https://t.co/madYjsaOTS
— devgenjin77 (@devgenjin77) 2022年9月3日

振り返り

E問題をなんとか解き切ることができました。

A問題

A - Saturday

IF文を5通り書くだけの問題。

問題文からのコピペが面倒だが、やるだけの実装をして提出。問題なくACが取れました。

1分41秒で1完。まあまあの時間という印象。

提出コード

https://atcoder.jp/contests/abc267/submissions/34531429

B問題

B - Split?

だいぶ実装がめんどくさそうな問題。なんらかの法則性を見つけて簡潔に実装できるかとおもったが思いつかずだったので、ゴリ押しの実装で挑むことにしました。

まず、問題文の通り、ピンが立っているかどうかを保持する配列を作成する。

つぎに、この配列を左から見て、ピンが立っている→ピンが立っていない→ピンが立っているというパターンが存在するかを判定すればOK。

実装時間がやたらとかかってしまい、判定部分にバグが無いか大分心配でしたが、なんとか一度の提出でACが取れました。

11分52秒で2完。少し手こずった感があるタイム。

提出コード

https://atcoder.jp/contests/abc267/submissions/34540034

C問題

C - Index × A(Continuous ver.)

一読して、累積和を使えば解けるかという問題。

まず、 $A_1$ から $A_M$ までの連続部分列について、答えを計算する。

つぎに、連続部分列を、右に一つずらして答えを計算する時に、前の答えから、 $A_1$ から $A_M$ までの累積和を引いて、 $M \times A_{M + 1}$ を足すという工夫をすることで、計算量を減らすことができる。

あとは、連続部分列が右端に到達するまで同様の要領で計算していけば良い。

ということで、あとは実装して、なんとか1回の提出でACを取り切ることができました。

24分30秒で3完。ここまでは、まあまあの内容です。

提出コード

https://atcoder.jp/contests/abc267/submissions/34547219

D問題

D - Index × A(Not Continuous ver.)

C問題とは違い、今度は連続で無くても良いパターンの問題。制約などをみると、これはDPするやつだと直感でわかった。

$dp\lbrack i \rbrack \lbrack j \rbrack :=$ $A$ を $i$ 個目まで見て、 $B$ に $j$ 個採用した時の最大値。
遷移は、 $dp\lbrack i \rbrack \lbrack j \rbrack = max(dp\lbrack i - 1 \rbrack \lbrack j - 1 \rbrack + (j \times A\lbrack i \rbrack ), dp\lbrack i - 1 \rbrack \lbrack j \rbrack)$