2022/4/10に開催されたAtCoder Beginner Contest 247に参加しました。
昨日のARCでは、なんとか2完を確保することができ、レートを上昇させることができました。
今日のABCでは、昨日の流れを引き継いでレート上昇につなげるべく、5完という目標を立てて臨むこととしました。
Rated参加します！とりあえず目標は5完というところで✊
— devgenjin77 (@devgenjin77) 2022年4月10日
AtCoder Beginner Contest 247 - AtCoder https://t.co/N08EZKJUZi
今回の結果
そして、今回はなんと目標通りの5完を達成することが出来ましたー！まさしく有言実行です。
久々の水色パフォーマンスも達成し、レートは大幅上昇。Highestにもう少しというところまで戻すことができましたとさ。
目標の5完達成＋水パフォで3連勝😂😂😂
— devgenjin77 (@devgenjin77) 2022年4月10日
来週も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 247での成績：1341位
パフォーマンス：1319相当
レーティング：1032→1064 (+32) :)#AtCoder #ABC247 https://t.co/gyu9WfEzoj
振り返り
前半はそこそこ順調に進み、E問題は力技で通すことに成功しました。
A問題
文字列をビット列とみなし、右に1ビットシフトした結果を出力すればよい。
とはいえ、ビット演算に落とし込むのも逆に手間がかかるという事で、”0” + の先頭3文字を出力する実装を行い、問題なくACを取る事が出来ました。
1分40秒で1完。まずまずのスタートです。
提出コード
https://atcoder.jp/contests/abc247/submissions/30847874
B問題
見た目だいぶややこしそうな問題かと思いましたが、全探索が普通に通りそうな制約だったので、ゴリ押しで実装することに。
各に対して、
となる全ての
について、姓の一致(
または、
)及び名の一致(
または、
)をチェックし、姓、名両方について一致が一回でもあった場合、答えはNoとする。
上記の要領で実装し、なんとかACを取る事が出来ました。
11分20秒で2完。少し時間を掛けすぎたきらいがあります。
提出コード
https://atcoder.jp/contests/abc247/submissions/30856383
C問題
再帰で実装すればよいかという考えが最初に浮かんだので、とりあえず再帰で実装しきることにしました。
で、実装後、としてローカルで実行してみると、とりあえずそれっぽい出力で動くものの、多少実行速度に懸念が出てきたので、一応メモ化の処理も入れてみてから提出。とりあえず問題なくACが取れましたとさ。
でもあとでよくよく考えると、再帰を使わなくても大丈夫そうだし、だいぶ無駄な実装もしてたかなという印象。また、復習がてら書き直すことにしてみますか。
22分45秒で3完。とりあえず、大きな問題は無しというところ。
提出コード
https://atcoder.jp/contests/abc247/submissions/30864288
D問題
クエリ1のをペアオブジェクトでキューに突っ込んで置き、クエリ2の
を使い切るまで、ペアオブジェクトをキューから取り出せばOKな感じがする。
ちなみに、後で知ったのですが、こういう手法をランレングス圧縮というんだそうな。
とりあえず、解法は見えたので、あとは実装して問題なくACすることができました。
39分41秒で4完。あと1時間あるので、目標の5完目が現実味を帯びてきました。
提出コード
https://atcoder.jp/contests/abc247/submissions/30872695
E問題
問題としては、やや難解という印象だが、区間の最大、最小を考慮するというところで、とりあえずセグ木を使えばなんとかなるかと考えました。
ということで、とりあえずは区間最大、最小を計算するセグ木をそれぞれ用意します。
その後、を固定してから、区間最大が
となる
の範囲及び区間最小が
となる
の範囲を二分探索で求め、重複する範囲を数え上げて答えに追加する。これを全ての
に対して実行するという実装を行いました。
範囲を求める二分探索の実装でだいぶ手こずってしまい、且つ最初の提出でＷＡを喰らうなどしてだいぶ焦りましたが、なんとか時間内に修正し、ACを取る事が出来ました。
89分46秒1ペナで5完。このあたりで1300位ぐらいまで上げる事ができたので、なんとかレート上昇ぐらいはあるかと一安心できました。
提出コード
https://atcoder.jp/contests/abc247/submissions/30888032
F問題
終了まで10分程度あった為、問題を一読することまではしましたが、何もわからず。
結局、ここで時間切れとなりました。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
ここ最近は停滞ムードが続いておりましたが、なんとかHighest付近まで戻すことができました。
総括
今回のE問題は、あえてセグ木を使わなくても解ける問題だったようですが、上手い解法が降りてこない時に間に合わせの実装としてライブラリが使えるようになったのは一つの成長の印かと思います。
反省点としては、C問題などでは、多少複雑な実装をしてしまい、多少時間ロスをしたのが少し悔やまれます。
とりあえず、レートの方はHighest付近まで戻せたので、この勢いで水色に行けるように頑張りたいと思います。そのためには、今後、当たり前のように水パフォが取れるようにならないといけないですがね。
ということで、また次回も頑張ります。
