2022/8/21に開催されたAtCoder Beginner Contest 265に参加しました。
土曜のARCでは、思う様な結果が出ず、レートを減らしてしまうことに。
ということで、今回のABCでは、なんとか土曜の負けを取り戻せる様に、水パフォあたりは出してみようという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年8月21日
水パフォ出して、昨日の負けを取り戻せるように頑張ります✊
AtCoder Beginner Contest 265 - AtCoder https://t.co/P6ode24AcY
今回の結果
で、今回は久々の5完達成という、嬉しい結果に!
そして、なんとABCでは自身初の3桁順位を達成!ギリギリ青パフォを達成するという出来過ぎの結果で、レートはHighestを大きく更新しました!!
5完で青パフォ達成!
— devgenjin77 (@devgenjin77) 2022年8月21日
レートも爆上げしました😂😂😂
この勢いで、早く入水できるように頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 265での成績:743位
パフォーマンス:1600相当
レーティング:1062→1129 (+67) :)
Highestを更新しました!#AtCoder #ABC265 https://t.co/MUzXvinytu
振り返り
今回は、大きなミス無く終えることができて、良かったです。
A問題
個のりんごを全部円ずつで買ったときの金額と、円で個を買えるだけ買って、残りを個当たり円で買った時の金額を比較する。
1回の提出で問題なくACが取れました。
2分45秒で1完。
提出コード
https://atcoder.jp/contests/abc265/submissions/34201202
B問題
問題文のとおりシミュレーションするだけの問題。
残り時間と消費時間がイコールの場合、移動できないという条件に少し違和感を持ちましたが、ちゃんとサンプルを確認して間違いが無い様に実装し、提出1回でACが取れました。
12分50秒で2完。
提出コード
https://atcoder.jp/contests/abc265/submissions/34210566
C問題
少し実装が面倒だが、グリッド上の移動をシミュレーションするだけ。
ループを考慮して、一度移動したマスを管理するようにする。
こちらも、問題なくACを取ることができました。
22分56秒で3完。
提出コード
https://atcoder.jp/contests/abc265/submissions/34217888
D問題
D - Iroha and Haiku (New ABC Edition)
まず、数列の累積和を求めておき、尺取り法の要領で、合計がとなる区間があるかを求める。
次に、該当する区間が見つかったら、この区間の左端からの合計が、およびになる区間があるかを、それぞれ二分探索で求める。
これらの条件が全て満たせたら、答えがYesとなる。
実装はやたらと手こずりましたが、なんとか提出一回でACを取ることができました。
45分45秒で4完。
提出コード
https://atcoder.jp/contests/abc265/submissions/34228845
E問題
残りが50分以上というところで、なんとか5完を達成したいところだが、最初に問題を読んだ限りでは上手い解法は思いつかず。
グラフ的な考え方が必要なのか、それとも包除原理的な解き方が必要なのかと色々検討したものの、イマイチぱっとしない。
で、時間をかけて思いついたのが、の最大がというところで、計算量ぐらいのDPは行けそうという考えから、
- 合計回ワープしたうち、1つ目のワープを回、2つ目のワープを回した時の通り数。
こんなDPができるのでは無いかと想定。
各ワープの回数が分かれば、どの座標に移動するかが高速に求まり、障害がある座標への移動であれば通り数をゼロとする。
そうでなければ、3種類のワープのうち、どれを増やしたかを考慮した遷移を実装すればよい。
で、これで本当に通るかが少し不安でしたが、なんとか頑張って実装を終え、サンプルまで通ったので提出。なんと1回でACを取り切ることが出来ました!
90分48秒で5完。これぐらいの難易度のDPを本番中に解き切ったのは初めてです!
提出コード
https://atcoder.jp/contests/abc265/submissions/34242845
F問題
残り時間が10分弱ありましたので、一応問題文を見てみましたが、何も思いつかず。
ここで、時間切れとなりました。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
青パフォゲットで、Highestを大きく更新。水色コーダーへ一歩近づくことが出来ました。
総括
今回のE問題が解けたのは素直に嬉しいです。
今回の結果が単なるまぐれ当たりで終わってしまわないように、今後も安定して水パフォ以上の結果をだせるように精進を重ねていこうと思います。
ということで、また次回も頑張ります。