2022/11/5に開催されたAtCoder Beginner Contest 276に参加しました。
直近で参加したアルゴリズムRatedコンテストでは、良い成績が出ずで3連敗中。
今回はなんとか連敗を止めるべく、水パフォを目標として臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年11月5日
現在3連敗中なので、まずは水パフォを取って連敗を止められるよう、頑張ります✊
AtCoder Beginner Contest 276 - AtCoder https://t.co/dyquhlb3wu
今回の結果
5完を達成!タイムは60分切っているぐらいなので、そこそこいい結果が出たかと。
肝心のパフォーマンスは水色の中ぐらい。最近の連敗で溶かしたレートを少し取り戻すことができました。
5完水パフォで連敗脱出しました!
— devgenjin77 (@devgenjin77) 2022年11月5日
次回も水パフォ以上取れるよう頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 276での成績:1106位
パフォーマンス:1387相当
レーティング:1103→1135 (+32) :)#AtCoder #ABC276 https://t.co/muZfR5fTjE
振り返り
今回、E問題が緑Diffぐらいだったので、如何に早く解くかがパフォーマンス向上のカギだったかと。
A問題
StringクラスのlastIndexOfというメソッドを使うだけ。
1分28秒で1完。
提出コード
https://atcoder.jp/contests/abc276/submissions/36222109
B問題
B問題でグラフ出てくるか?とおもったが、よくみると隣接リストを実装できるかという感じの問題だった。
隣接リストはグラフ問題で実装し慣れているので、あとはやるだけ。問題なくACが取れました。
7分19秒で2完。
提出コード
https://atcoder.jp/contests/abc276/submissions/36229635
C問題
nextPermutationなら、今までで用意したライブラリにあったが、その逆をやるメソッドは無かった。。
どうもC++なら標準ライブラリ一発で解けそうだが、慣れてないC++を書くのもなあ。。だけど、一から実装を考えると、ドツボにハマりそう。。と、いうことでググってコピペする方針で解くこととしました。
「previous permutation java」という感じのキーワードでググって、それっぽい実装をローカルにコピペ。サンプル2がちゃんと通る事を確認してから、提出することで、なんとかACを取り切ることができましたとさ。
21分23秒で3完。正直、自力で解くのが難しかったので、なんとかACがとれて良かったです。。
提出コード
https://atcoder.jp/contests/abc276/submissions/36237201
D問題
以下の要領で解きました。
配列の全ての値について、2で割り切れるなら2で割る。3で割り切れるなら3で割るを繰り返す。このとき、の各要素について2、3で割った回数を覚えておく。
2、3で割ったあとのの値が全て同じでない場合、答えは-1。
上記以外の場合、答えは、各要素について2及び3で割った回数の合計から、(2で割った回数の最小値×要素数+3で割った回数の最小値×要素数)を引いた数となる。
とこんな感じで実装したら。問題なくACを取ることができましたとさ。
33分17秒で4完。今回は5完以上はいけそうなペースです。
提出コード
https://atcoder.jp/contests/abc276/submissions/36241784
E問題
Dが解けたところぐらいで、E問題のAC数を見ると、すでに1000に到達しそうな勢いなので、この問題が解けないと順位がやばそうな感じではある。
とりあえず、問題を読んでみる。一見すると、迷路をBFS探索してスタートに戻った時に4歩以上歩いてたらYes的なやり方で解けるかと思った。
しかし、実際実装してみると、そんなに簡単でない模様。結局、探索中のマスに到達した最小のコストを管理してると、結局スタート地点に戻れないという現象が生じていた。
ということで、先ずスタート地点から上下左右に一歩進んだところを探索する。以降はそれぞれBFSでマスを探索するときに、初手が上下左右どれだっかの情報を探索中のマスに記録していき、初手の向きが異なったもの同士が同じマスに到達できたらYesという感じで実装。
これがうまく嵌ったようで、一度の提出でACがとれましたとさ。
59分42秒で5完。順位は一時1000位を切るぐらいまで上昇。なんとか水色パフォは確保できそうです!
提出コード
https://atcoder.jp/contests/abc276/submissions/36249929
F問題
残り40分程度はあったので、問題文を見る。
まず、行目の答えとして、行目の答えの分子にを足してで割るということは何となくつかめたが、キモとなる計算の効率化のところが、思いつかない。
セグ木なりBITなりを使えばいいのかなーと思いながらも結論はまとまらず。結局まともな実装もできぬまま、時間切れになりましたとさ。
G問題
問題すら見れておりません。
Ex問題
問題すら見れておりません。
これまでの実績
一応、レートが1100を切るという事態は避けることができました。今度こそ停滞することなく入水を目指したいところです。
総括
今回、E問題までが難易度がそこそこだったことと、比較的早めに解くことができたことで良いパフォーマンスが取れました。
今回見えた課題としては、F問題に結構時間が使えたのに解けなかったという事。BITを工夫して使うことでACが取れたようですが、あまりこのライブラリを使いこなせていなかったのが良くなかったようです。
今後に向けて、コンテスト中に解ける問題のレベルを上げていく必要があると感じました。引き続き、水、青Diffの過去問の精進に力を入れていきたいと思います。
ということで、また次回も頑張ります。