2023/2/11に開催された、Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289)に参加しました。
前回のABCでは、難易度の関係もありましたが3完という消化不良の内容でした。今回はなんとか5完ぐらい達成してレートを上げていきたいところです。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年2月11日
今回こそ5完以上できるようにがんばります✊
Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289) - AtCoder https://t.co/gkpUQkbMxM
今回の結果
なんとか5完を確保することができました。有言実行という感じです。
パフォーマンスは、水色の真ん中ぐらい。一時は下落傾向だったレートも大分戻してきました。
有言実行の5完達成😂😂
— devgenjin77 (@devgenjin77) 2023年2月11日
devgenjin77さんのSky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289)での成績:1051位
パフォーマンス:1476相当
レーティング:1105→1148 (+43) :)#AtCoder #Sky株式会社プログラミングコンテスト2023(ABC289) https://t.co/z9OakYAyBd
振り返り
Dでの小ミスが少し痛かったですが、あとは自分なりに無難にまとめることができました。
A問題
0
を1
に、1
を0
に置き換えるだけの問題。
上手いやり方などを考えるのも時間のムダという気がする。とりあえず愚直に置き換える処理を書いて提出。問題無くACが取れましたとさ。
1分19秒で1完。
提出コード
https://atcoder.jp/contests/abc289/submissions/38780493
B問題
B問題にしては、問題文を読み解くところから難しく、大分手を焼きました。
問題文を理解した後も、実装方針を立てるところで大分悩みましたが、サンプルを見てみると”レ”が直後に来る数字は一旦Stackに積んで、”レ”が来ないタイミングで全て積んだ順に出していくといい感じになるかという印象。
通るかどうか半信半疑状態でしたが、とりあえず実装して提出したら、なんとかACを取ることができました。
8分18秒で2完。今回は少し苦戦した感じです。
提出コード
https://atcoder.jp/contests/abc289/submissions/38786575
C問題
制約の見た目上、bit全探索使うやつだという印象の問題。
本番でbit全探索書くのは少し久しぶりかという感じで、思い出しながら実装を進めました。
一応、サンプルの全ケースも通して問題ないことを確認した後提出。無事ACを取り切ることができました。
17分28秒で3完。ちょっと慎重にやりすぎて時間が掛かっているなあという印象です。
提出コード
https://atcoder.jp/contests/abc289/submissions/38791659
D問題
順位表を見てると、今回のDは大分早い段階でたくさん解かれている印象。これは早く解かんとレートに大きくひびくかなという感じでした。
で、問題を見てみると、これがDPの典型のような問題。
実装方針としては、地点0からスタートして、通り分の移動先を調べ、モチが配置されていない場所ならキューに積んでいく。あとはキューに積んだ場所からさらに通り分の移動先を調べていくというBFSっぽい解き方で実装。
で、サンプルが通ったので出してみたら、これがTLE。。。
一度踏んだ場所を二回以上調べないという基本的な実装が抜けておりました。少し手直しして提出後AC。
30分58秒1ペナで4完。この小ミスが響いたか、Dを解いた時点で順位は1600ぐらい。Eが解けないと負けもあるかという状況でした。
提出コード
https://atcoder.jp/contests/abc289/submissions/38797609
E問題
ちょいと難しそうな問題。
一読したところ、各ケース毎のグラフについて、なんらかの法則性を見出して小さい計算量で解く問題かもしれないと思ったが、良い考えは思いつかず。
仕方ないという感じで、とりあえず各ケースごとのグラフで愚直に探索するやり方で実装してみることに。一旦DFSっぽく実装してみるが、途中で方針転換してBFSの最短経路を求めるような感じの実装に変更。
なんとかサンプルが通る実装ができたので、投げてみたらなんとかACと取ることができましたとさ。
62分12秒1ペナで5完。ここで順位はギリギリ3桁に入るところまで上昇。とりあえず、勝ちは確定したかというところです。
提出コード
https://atcoder.jp/contests/abc289/submissions/38807142
F問題
時間が余ったので、目を通してみたものの、何もわからず。順位表から見ても黄diffはありそうかという感じなので、半ばあきらめモードに入りました。
一応、G問題も同じぐらいの難易度っぽいので、Fは諦め。
G問題
一読すると、各商品について、どこまで単価を吊り上げることで売り上げを最大化できるかという問題の模様。
多分計算量的には厳しいが、をソートして、各商品ごとに三分探索とかすれば解は出せるのではないかと推測。
もう最後の悪あがき的な状態で、実装は進めてみたものの、実装がバグっているのかサンプルすら通らないという体たらく。結局、提出すらできずで時間切れになりましたとさ。
結局、この問題は全然しらないアルゴリズムが必要だった模様。また、履修しておきます。
Ex問題
問題すら見れておりません。
これまでの実績
大分レートを戻すことに成功。今度こそ、この勢いで入水したいところです。
総括
今回は、1ミスがあった事以外は、なんとか自分なりにいい結果が出せた回だったかと思います。
当面の目標としては、入水してレートを維持するというところにあるので、そろそろ青パフォを狙えるところまで実力を上げていきたい所。
来週は、ARC、ABCと立て続けに開催がある週なので、まずはここで入水できるように準備をしていきたいと思います。
ということで、また次回も頑張ります。