2022/4/16に開催された、ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)に参加しました。
先週の土日は、ARC、ABCと2連チャンでコンテストがありましたが、なんとか連勝することができて、一時期は3桁に落ちたレートもHighest付近まで戻すことに成功しました。
今回は、この流れのまま水色になれるようにと、水色パフォを目標として臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年4月16日
水パフォ目指して頑張ります✊
ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248) - AtCoder https://t.co/q51UZm6pO2
今回の結果
しかしながら、今回は4完を確保するのが精一杯でした。。
パフォーマンスは3桁しか出ておらず、今回は下げという結果になりました。
次、頑張ります😓
— devgenjin77 (@devgenjin77) 2022年4月16日
devgenjin77さんのユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)での成績:2439位
パフォーマンス:961相当
レーティング:1064→1054 (-10) :(#AtCoder #ユニークビジョンプログラミングコンテスト2022(ABC248) https://t.co/BvBTpwqagm
振り返り
D問題でだいぶ手こずってしまいました。。
A問題
数字のみからなる文字列より0
から9
までのうち一つだけ欠落している数字を求める問題。
愚直にやると手間がかかりそうなので、なんか上手い解法が無いかなー、、と考えたら、0
から9
までを足した時の合計から文字列内にある数字を引いていけば答えになるのでは?というアイデアが浮かんできた!
そのまま実装してみて、問題なくAC。大体愚直に解いてみることが多いA問題でしたが、今回は上手い解法が思いついて気分良いスタートが切ることが出来ました。
1分43秒で1完。
提出コード
https://atcoder.jp/contests/abc248/submissions/31003859
B問題
スライムの数が以上になるまで、にを掛けた回数を求めれば良い。
なおオーバーフローを避けるために、long
型で取るようにしないといけない。
ということで、あとは実装をして提出。こちらも問題なくACが取れました。
3分38秒という、個人的には良好なタイムで2完。
提出コード
https://atcoder.jp/contests/abc248/submissions/31007400
C問題
一読して手強そうな問題と思ったら、DPでやる問題でした。最近はC問題からDPが出るようになったんだね。
ということで、DP配列を以下のように定義する。
数列を番目まで決めた時に、合計がになる場合の数。
初期値は、とし、番目の値を決めるとき、 および について、の時、 に を加算する。
少しバグ取りに手間取ったりしましたが、なんとか実装に漕ぎ着け、ACを取ることができました。
25分1秒での3完。ここまでは、まあまあな内容かと。
提出コード
https://atcoder.jp/contests/abc248/submissions/31021992
D問題
なんかセグ木でやるには難しそうな配列に対するクエリの問題。
とりあえず、の上限値が限定されているので、各数値ごとに出現した位置を管理する配列を作る方法が効きそうな予感だけはした。
そこで、まずは各数値について、出現位置をTreeSetで管理し、各クエリについては、位置が以上、以下のサブセットを返すような実装を行う。
が、、サンプルは通ったものの、あえなくTLEを喰らってしまう。。
今度は、各数列の位置について、番目の状態ではどんな数字が何回現れたかと管理するHashMapを生成すれば良いのではと考えてみたが、インスタンス生成時間が相当ネックになるらしく、これもあっさりとTLEを喰らってしまう。。
ということで、結局、各数値について出現位置を配列で管理し、開始と終了の位置を二分探索でやるしかないのかなーということで、あとはなんとか実装してみる。
これが添字ミスなどで何回かWAを喰らってしまうものの、一応TLEはしないということでなんとか諦めずにバグ取りを行い、終了5分前というところで、なんとかACを取り切ることができました!
95分2秒の5ペナでやっと4完。なんとか爆死はまぬがれた模様。。
提出コード
https://atcoder.jp/contests/abc248/submissions/31041502
E問題
一応問題に目を通したものの、残り5分足らずという状況ではまともな考察すら出来ず。ここで時間切れとなりました。
F問題
問題すら見れておりません。
G問題
問題すら見れておりません。
H問題
問題すら見れておりません。
これまでの実績
上がればHighest更新というところでしたが、ここでまた足踏み状態となりました。
総括
今回はあえなく4完緑パフォという結果でしたが、もう少しD問題を早く片付けられたら現レートの維持以上ができたところだったかと。Dの実装方針について既存のライブラリの活用にこだわりすぎたあまり、無駄に時間をかける結果になったのが反省点となります。
また次回も頑張ります。