2022/9/3に開催された、NECプログラミングコンテスト2022(AtCoder Beginner Contest 267)に参加しました。
ここ数回のABCコンテストでは5完達成が続き、レートの方もいい感じで上がってきております。目標としていた水色にもだいぶ近づいてきました。
今回のコンテストは、とりあえず水パフォを目指し、さらに水色コーダーに近づこうという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年9月3日
今回も水パフォ取れるように頑張ります✊
NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267) - AtCoder https://t.co/gEvPKNbDUk
今回の結果
前回に続いて、5完を確保することに成功しました!
パフォーマンスは、水色の真ん中ぐらいまで出て、レートは大幅に上昇。水色コーダーに、さらに一歩近づくことができました!
5完水パフォで勝ち!😂😂😂
— devgenjin77 (@devgenjin77) 2022年9月3日
devgenjin77さんのNECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)での成績:1195位
パフォーマンス:1411相当
レーティング:1149→1178 (+29) :)
Highestを更新しました!#AtCoder #NECプログラミングコンテスト2022(ABC267) https://t.co/madYjsaOTS
振り返り
E問題をなんとか解き切ることができました。
A問題
IF文を5通り書くだけの問題。
問題文からのコピペが面倒だが、やるだけの実装をして提出。問題なくACが取れました。
1分41秒で1完。まあまあの時間という印象。
提出コード
https://atcoder.jp/contests/abc267/submissions/34531429
B問題
だいぶ実装がめんどくさそうな問題。なんらかの法則性を見つけて簡潔に実装できるかとおもったが思いつかずだったので、ゴリ押しの実装で挑むことにしました。
まず、問題文の通り、ピンが立っているかどうかを保持する配列を作成する。
つぎに、この配列を左から見て、ピンが立っている→ピンが立っていない→ピンが立っているというパターンが存在するかを判定すればOK。
実装時間がやたらとかかってしまい、判定部分にバグが無いか大分心配でしたが、なんとか一度の提出でACが取れました。
11分52秒で2完。少し手こずった感があるタイム。
提出コード
https://atcoder.jp/contests/abc267/submissions/34540034
C問題
C - Index × A(Continuous ver.)
一読して、累積和を使えば解けるかという問題。
まず、からまでの連続部分列について、答えを計算する。
つぎに、連続部分列を、右に一つずらして答えを計算する時に、前の答えから、からまでの累積和を引いて、を足すという工夫をすることで、計算量を減らすことができる。
あとは、連続部分列が右端に到達するまで同様の要領で計算していけば良い。
ということで、あとは実装して、なんとか1回の提出でACを取り切ることができました。
24分30秒で3完。ここまでは、まあまあの内容です。
提出コード
https://atcoder.jp/contests/abc267/submissions/34547219
D問題
D - Index × A(Not Continuous ver.)
C問題とは違い、今度は連続で無くても良いパターンの問題。制約などをみると、これはDPするやつだと直感でわかった。
を個目まで見て、に個採用した時の最大値。
遷移は、
当初、初期値の設定に不具合があり、サンプルがなかなか通らなかったのですが、なんとか実装を完了し、1回の提出でACを取り切ることが出来ました。
42分27秒で4完。とりあえず、5完は行けそうなペースです。
提出コード
https://atcoder.jp/contests/abc267/submissions/34556310
E問題
現在可能な操作のうち、一番コストが低い操作を貪欲に実行し続け、最終的に一番高かったコストが何だったかを答える問題かというところかと。
ということで、まずは、各頂点とそれを削除するためにかかるコストを前もって計算しておき、コストの昇順で管理する優先度付きキューに突っ込んで、先頭から処理していけばよい。
ということで、現状可能な操作のうち、一番コストの低い順から削除し、さらに、削除する操作を行なった頂点に隣接する頂点が既に削除されている場合は、そのコストも計算に入れてコストの最大値を計算するという感じで組んでみる。
で、なんとかサンプルが通る実装ができたものの、提出したらWAを大量に食らってしまう。。。
なにがダメなのかよくわからなかったが、とりあえず頂点を削除したときに、隣接する頂点を削除するコストを新たに計算し直してからキューに突っ込むような実装にしてみる。
すると、多少実行時間がかかったものの、なんとかACを取り切ることが出来ましたとさ。
83分46秒2ペナで5完。ちなみに、公式解説では二分探索が想定だったようですが、その筋は全く考えられておりませんでした。
提出コード
https://atcoder.jp/contests/abc264/submissions/34019512
F問題
一応、15分以上残り時間がありましたので、問題は読んでみたものの何もわからず。
これで時間切れとなりました。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
念願の水色コーダーに、あと少しで手が届くというところまで伸びてきました。
総括
ここ数回は、非常に調子が良く、レートの方も上昇傾向が続いています。
念願の水色まであと少し。とりあえず、日曜はARCがあるので、ここで入水できるように頑張るだけです。
ということで、また次回も頑張ります。