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

2022/5/28に開催された、NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)に参加しました。

atcoder.jp

ここ最近のABCコンテストでは水パフォを目標としてましたが、全く結果が出せておらずで直近3連敗中。

今回はとにかく連敗を止めるぞという気持ちで臨むこととしました。

今回の結果

で、今回は久しぶりの5完達成となりました!

ABC253結果
ABC253結果

パフォーマンスは、ギリギリ水パフォに到達。とりあえず連敗を止めることができましたー。

振り返り

5完出来た割には凡ミスが続いており、反省材料が多い回でした。

ABC253提出結果
ABC253提出結果

A問題

A - Median?

とりあえず、A \le B \le Cの場合Yesと表示する処理を書いて提出。そのまま、結果を見ずにB問題に行ったが後でWAを喰らっている事に気付いてびっくりw

2回目の提出では、念には念を入れ、3要素を配列に入れてソートを行い、Bが真ん中の要素と一致するかどうかを判定するように実装。なんとかACが取れました。

9分19秒1ペナで2完。

提出コード

https://atcoder.jp/contests/abc253/submissions/32009589

B問題

B - Distance Between Tokens

2点それぞれの座標を求めてマンハッタン距離を求めればよい。こちらは問題なくACが取れました。

7分21秒で1完。

提出コード

https://atcoder.jp/contests/abc253/submissions/32007577

C問題

C - Max - Min Query

xとその個数をTreeMapで管理し、クエリ3を処理するときには、TreeMapのキーから最大値と最小値を取得して計算すればよい。

処理時間内に収まるか少し心配だったが、なんとかACを取ることができました。

16分9秒1ペナで3完。

提出コード

https://atcoder.jp/contests/abc253/submissions/32015370

D問題

D - FizzBuzz Sum Hard

とりあえず、全体の合計から、Aの倍数の合計、Bの倍数の合計をそれぞれ引き、重複して引いたABの倍数の合計を足せば良いように見える。

というわけで、あとは等差数列の和の公式をググって実装し、サンプルが通ったので提出。。としたもののあえなくWA。。。

場合分けが悪いのかと思ったが、よくよく考えるとABの倍数でなくABの最小公倍数で考える必要があった模様。修正してなんとかACが取れましたとさ。

39分7秒3ペナで4完。痛いミスが続きましたが、久々の5完目が狙えそうな状況です。

提出コード

https://atcoder.jp/contests/abc253/submissions/32029359

E問題

E - Distance Sequence

開始40分程度で順位表では800ACぐらい行っているので、今回のE問題はなんとか解きたい所。

先ず当初の考察としては、動的計画法を用いて、 dp\lbrack i \rbrack \lbrack j \rbrack := i個目の要素がjである場合の数、という感じで考えればよさそう。

また、その際遷移を効率化するため、直前の要素を累積和を求めておけば処理時間内に解けそうな感じがする。

ということで、実装してサンプルを試したところ、全然答えが合わない。。と思ったら、そもそも隣同士の差の絶対値がK以上であるところ、K以内という致命的な誤読をしてましたw

で、とりあえず修正後サンプルが通ったので提出したら、これがWA。。今度はK=0のコーナーケースに対応できておりませんでした。。。

ということで、ボロボロとミスが続きながらもなんとか修正して、最後ACを取り切ることができました。

76分56秒4ペナで5完。なんとか今回で連敗が止まりそうです。

提出コード

https://atcoder.jp/contests/abc253/submissions/32045892

F問題

F - Operations on a Matrix

順位表を確認した時はAC数が400台であり、だいぶ手ごわい問題のようだが、なんとか考察してみる。

が、、全く解法が思いつかずでこのまま時間切れ。今の実力で解ける問題ではありませんでした。

後で解説を読むと、いもす法をBITで使う形だったようで、本番中はこれが全く思いつかずでした。

G問題

G - Swap Many Times

問題をチラ見しましたが、何も思いつかずで即時撤退。

Ex問題

Ex - We Love Forest

問題すら見れておりません。

これまでの実績

とりあえず連敗を止めることに成功しました。

コンテスト実績
コンテスト実績

総括

今回は5完を達成したものの、A問題から凡ミスでWAを出したほか、問題文の誤読、コーナーケースの考慮不足などで多くのペナをくらってしまったのが反省材料です。

また、各問題のDiffを見てみるとE問題までが緑Diffというところなので問題セットのおかげで5完まで行けたというのもあるかと。

まだまだ修正すべき点はたくさんあるようなので、このあたりを振り返りして、また次回に臨みたいと思います。

ということで、また次回も頑張ります。