2022/10/8に開催されたAtCoder Beginner Contest 272に参加しました。
今週は、ABC、ARCと連続で開催される週。この土日で大きくレートを上げるために、まずはこのABCで水パフォを取っていこうという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年10月8日
今回も水パフォ目指して頑張ります✊
AtCoder Beginner Contest 272 - AtCoder https://t.co/Le2mcGagmR
今回の結果
だいぶ苦戦しましたが、なんとか5完を達成することが出来ました!
パフォーマンスは水色の後半あたりという望外の結果となり、順位は久々の3桁台!レートは大きく上がって、Highest更新。水色まで後少しというところまできました。
5完水パフォで、レートは爆上げ😂😂
— devgenjin77 (@devgenjin77) 2022年10月8日
この勢いで入水できるように頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 272での成績:833位
パフォーマンス:1542相当
レーティング:1136→1184 (+48) :)
Highestを更新しました!#AtCoder #ABC272 https://t.co/2CIsizRxJl
振り返り
E問題がなんとか通ってくれたので、だいぶレートが上がってくれました。
A問題
数列の合計を求める問題。とりあえず、読み込んだの値を随時合計に足し込めば良い。
1分0秒で1完。最近のA問題では、だいぶ簡単な方だったかと。
提出コード
https://atcoder.jp/contests/abc272/submissions/35467677
B問題
- 人と人が同じ舞踏会に参加したことがあるか。
上記の配列を作成し、あとは各舞踏会に参加した人の内容から、参加した組を全探索し、参加した組をTrueで更新する。全部Trueで埋まっていたら、答えはYes。
ということで、あとは実装して一発でAC。
7分27秒で2完。多少時間が掛かりすぎかもしれません。
提出コード
https://atcoder.jp/contests/abc272/submissions/35474292
C問題
の異なる要素の和を全探索すると、の計算量が掛かりTLEとなる。
ただし、答えを偶数に限定すると、奇数足す奇数のケースか、偶数足す偶数のケースに限定される。
よって、のうち、一番大きい奇数と二番目に大きい奇数の和と、一番大きい偶数と二番目に大きい偶数の和を比較して大きい方を出せば良い。
あとは、偶数、奇数がそれぞれ2つないケースなどに気をつけて実装。一発でACが取れました。
13分46秒で3完。ここまでは、かなり順調にきています。
提出コード
https://atcoder.jp/contests/abc272/submissions/35478453
D問題
以下の要領で解きました。
マスから、マスに到達するときの最小の操作回数。
初期値は、 、それ以外はとする。
マスから始めて、移動できるマスをBFSの要領で全探索する。移動元の操作回数+1が、遷移先の操作回数より小さい場合、遷移先の操作回数を、移動元の操作回数+1で更新。移動先のマスの情報をキューに突っ込む。
の移動先を〜の範囲で固定したとき、ぞれぞれのに対するの移動先は、という関係になることから、が平方数であり、かつが〜の範囲内になる時に限定される。
前計算で、以下の平方数を求めておき、Setに突っ込むなりすると、ある整数が平方数かどうかの判定を高速化できる。
とこんな感じで実装したらサンプルが通ったので、提出したら、なんとかACをとることができましたとさ。
41分25秒で4完。これで、なんとか爆死はなさそうです。
提出コード
https://atcoder.jp/contests/abc272/submissions/35490301
E問題
順位表からすると、だいぶむずそうなこの問題。内容をみてみると、確かに手強そうである。
が、F以降はそれ以上に絶望的な難易度のようなので、なんとかE問題を解き切るしかなさそう。
ということで、解法を検討してみるが、うまいやり方が思いつかず。。
が、、よくよく考えてみると、回それぞれの操作に対して、Mexになり得る値は〜に限定されることから、のそれぞれの要素について、何回目の操作で〜の値になるかを確認すればよさそう。
ということで、回目の操作で現れる〜の範囲の整数の集合として管理しておく。またのそれぞれの要素について、操作後の値が、〜の範囲になる操作回数とその値をもとに配列を更新していく。
あとは、〜回の操作をしたときのMexは、上記の配列を〜まで存在するかどうかを見ていくこととする。
やたら処理時間がかかりそうな実装になったので、提出時はTLEだけが心配。
実際、ジャッジ中はTLEになるかどうかという動きを見せてましたが、なんとか1400ms台で耐えてくれました!
87分17秒で5完。これでなんと順位は830位まで上昇。水色は余裕で突破できそうです!
提出コード
https://atcoder.jp/contests/abc272/submissions/35504135
F問題
一応時間はあったので、問題文を見ましたが、なにも思いつかず。ここで時間切れとなりました。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
ここ最近の停滞ムードを抜けて、レートは大幅に上昇!念願の入水までもう少しです。
総括
最近は、過去のABCの問題の解き直しなどに注力してますが、その成果がいい感じに出てきているように感じます。
ただ、レートの方も、水色間際まで来ましたので、これからのABCでは水色パフォが最低限のノルマになってきますね。そのためには、青Diff程度の問題が本番ACできるように、練習問題のレベルを上げていきたいと思います。
ということで、また次回も頑張ります。