ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)参加記

2022/4/16に開催された、ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)に参加しました。

atcoder.jp

先週の土日は、ARC、ABCと2連チャンでコンテストがありましたが、なんとか連勝することができて、一時期は3桁に落ちたレートもHighest付近まで戻すことに成功しました。

今回は、この流れのまま水色になれるようにと、水色パフォを目標として臨むこととしました。

今回の結果

しかしながら、今回は4完を確保するのが精一杯でした。。

ABC248結果
ABC248結果

パフォーマンスは3桁しか出ておらず、今回は下げという結果になりました。

振り返り

D問題でだいぶ手こずってしまいました。。

ABC248提出結果
ABC248提出結果

A問題

A - Lacked Number

数字のみからなる文字列Sより0から9までのうち一つだけ欠落している数字を求める問題。

愚直にやると手間がかかりそうなので、なんか上手い解法が無いかなー、、と考えたら、0から9までを足した時の合計45から文字列内にある数字を引いていけば答えになるのでは?というアイデアが浮かんできた!

そのまま実装してみて、問題なくAC。大体愚直に解いてみることが多いA問題でしたが、今回は上手い解法が思いついて気分良いスタートが切ることが出来ました。

1分43秒で1完。

提出コード

https://atcoder.jp/contests/abc248/submissions/31003859

B問題

B - Slimes

スライムの数がB以上になるまで、AKを掛けた回数を求めれば良い。

なおオーバーフローを避けるために、long型で取るようにしないといけない。

ということで、あとは実装をして提出。こちらも問題なくACが取れました。

3分38秒という、個人的には良好なタイムで2完。

提出コード

https://atcoder.jp/contests/abc248/submissions/31007400

C問題

C - Dice Sum

一読して手強そうな問題と思ったら、DPでやる問題でした。最近はC問題からDPが出るようになったんだね。

ということで、DP配列を以下のように定義する。

dp \lbrack i \rbrack \lbrack j \rbrack :=数列Ai番目まで決めた時に、合計がjになる場合の数。

初期値は、dp \lbrack 0 \rbrack \lbrack 0 \rbrack = 1とし、i番目の値を決めるとき、0 \le j \lt NM および 1 \le k \le Mについて、j + k \le NMの時、dp \lbrack i \rbrack \lbrack j + k \rbrack dp \lbrack i - 1 \rbrack \lbrack j \rbrack を加算する。

少しバグ取りに手間取ったりしましたが、なんとか実装に漕ぎ着け、ACを取ることができました。

25分1秒での3完。ここまでは、まあまあな内容かと。

提出コード

https://atcoder.jp/contests/abc248/submissions/31021992

D問題

D - Range Count Query

なんかセグ木でやるには難しそうな配列に対するクエリの問題。

とりあえず、A_iの上限値が限定されているので、各数値ごとに出現した位置を管理する配列を作る方法が効きそうな予感だけはした。

そこで、まずは各数値について、出現位置をTreeSetで管理し、各クエリについては、位置がL以上、R以下のサブセットを返すような実装を行う。

が、、サンプルは通ったものの、あえなくTLEを喰らってしまう。。

今度は、各数列の位置について、i番目の状態ではどんな数字が何回現れたかと管理するHashMapを生成すれば良いのではと考えてみたが、インスタンス生成時間が相当ネックになるらしく、これもあっさりとTLEを喰らってしまう。。

ということで、結局、各数値について出現位置を配列で管理し、開始と終了の位置を二分探索でやるしかないのかなーということで、あとはなんとか実装してみる。

これが添字ミスなどで何回かWAを喰らってしまうものの、一応TLEはしないということでなんとか諦めずにバグ取りを行い、終了5分前というところで、なんとかACを取り切ることができました!

95分2秒の5ペナでやっと4完。なんとか爆死はまぬがれた模様。。

提出コード

https://atcoder.jp/contests/abc248/submissions/31041502

E問題

E - K-colinear Line

一応問題に目を通したものの、残り5分足らずという状況ではまともな考察すら出来ず。ここで時間切れとなりました。

F問題

F - Keep Connect

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

G問題

G - GCD cost on the tree

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

H問題

Ex - Beautiful Subsequences

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

これまでの実績

上がればHighest更新というところでしたが、ここでまた足踏み状態となりました。

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

総括

今回はあえなく4完緑パフォという結果でしたが、もう少しD問題を早く片付けられたら現レートの維持以上ができたところだったかと。Dの実装方針について既存のライブラリの活用にこだわりすぎたあまり、無駄に時間をかける結果になったのが反省点となります。

また次回も頑張ります。