AtCoder Beginner Contest 276 参加記

2022/11/5に開催されたAtCoder Beginner Contest 276に参加しました。

atcoder.jp

直近で参加したアルゴリズムRatedコンテストでは、良い成績が出ずで3連敗中。

今回はなんとか連敗を止めるべく、水パフォを目標として臨むこととしました。

今回の結果

5完を達成!タイムは60分切っているぐらいなので、そこそこいい結果が出たかと。

ABC276結果
ABC276結果

肝心のパフォーマンスは水色の中ぐらい。最近の連敗で溶かしたレートを少し取り戻すことができました。

振り返り

今回、E問題が緑Diffぐらいだったので、如何に早く解くかがパフォーマンス向上のカギだったかと。

ABC276提出結果
ABC276提出結果

A問題

A - Rightmost

StringクラスのlastIndexOfというメソッドを使うだけ。

1分28秒で1完。

提出コード

https://atcoder.jp/contests/abc276/submissions/36222109

B問題

B - Adjacency List

B問題でグラフ出てくるか?とおもったが、よくみると隣接リストを実装できるかという感じの問題だった。

隣接リストはグラフ問題で実装し慣れているので、あとはやるだけ。問題なくACが取れました。

7分19秒で2完。

提出コード

https://atcoder.jp/contests/abc276/submissions/36229635

C問題

C - Previous Permutation

nextPermutationなら、今までで用意したライブラリにあったが、その逆をやるメソッドは無かった。。

どうもC++なら標準ライブラリ一発で解けそうだが、慣れてないC++を書くのもなあ。。だけど、一から実装を考えると、ドツボにハマりそう。。と、いうことでググってコピペする方針で解くこととしました。

「previous permutation java」という感じのキーワードでググって、それっぽい実装をローカルにコピペ。サンプル2がちゃんと通る事を確認してから、提出することで、なんとかACを取り切ることができましたとさ。

21分23秒で3完。正直、自力で解くのが難しかったので、なんとかACがとれて良かったです。。

提出コード

https://atcoder.jp/contests/abc276/submissions/36237201

D問題

D - Divide by 2 or 3

以下の要領で解きました。

  • 配列Aの全ての値について、2で割り切れるなら2で割る。3で割り切れるなら3で割るを繰り返す。このとき、Aの各要素について2、3で割った回数を覚えておく。

  • 2、3で割ったあとのAの値が全て同じでない場合、答えは-1。

  • 上記以外の場合、答えは、各要素について2及び3で割った回数の合計から、(2で割った回数の最小値×要素数+3で割った回数の最小値×要素数)を引いた数となる。

とこんな感じで実装したら。問題なくACを取ることができましたとさ。

33分17秒で4完。今回は5完以上はいけそうなペースです。

提出コード

https://atcoder.jp/contests/abc276/submissions/36241784

E問題

E - Round Trip

Dが解けたところぐらいで、E問題のAC数を見ると、すでに1000に到達しそうな勢いなので、この問題が解けないと順位がやばそうな感じではある。

とりあえず、問題を読んでみる。一見すると、迷路をBFS探索してスタートに戻った時に4歩以上歩いてたらYes的なやり方で解けるかと思った。

しかし、実際実装してみると、そんなに簡単でない模様。結局、探索中のマスに到達した最小のコストを管理してると、結局スタート地点に戻れないという現象が生じていた。

ということで、先ずスタート地点から上下左右に一歩進んだところを探索する。以降はそれぞれBFSでマスを探索するときに、初手が上下左右どれだっかの情報を探索中のマスに記録していき、初手の向きが異なったもの同士が同じマスに到達できたらYesという感じで実装。

これがうまく嵌ったようで、一度の提出でACがとれましたとさ。

59分42秒で5完。順位は一時1000位を切るぐらいまで上昇。なんとか水色パフォは確保できそうです!

提出コード

https://atcoder.jp/contests/abc276/submissions/36249929

F問題

F - Double Chance

残り40分程度はあったので、問題文を見る。

まず、k行目の答えとして、k-1行目の答えの分子に\Sigma_{i=1}^{k} max(A_i, A_k) \times 2 + A_kを足してk^2で割るということは何となくつかめたが、キモとなる計算の効率化のところが、思いつかない。

セグ木なりBITなりを使えばいいのかなーと思いながらも結論はまとまらず。結局まともな実装もできぬまま、時間切れになりましたとさ。

G問題

G - Count Sequences

問題すら見れておりません。

Ex問題

Ex - Construct a Matrix

問題すら見れておりません。

これまでの実績

一応、レートが1100を切るという事態は避けることができました。今度こそ停滞することなく入水を目指したいところです。

コンテスト実績
コンテスト実績

総括

今回、E問題までが難易度がそこそこだったことと、比較的早めに解くことができたことで良いパフォーマンスが取れました。

今回見えた課題としては、F問題に結構時間が使えたのに解けなかったという事。BITを工夫して使うことでACが取れたようですが、あまりこのライブラリを使いこなせていなかったのが良くなかったようです。

今後に向けて、コンテスト中に解ける問題のレベルを上げていく必要があると感じました。引き続き、水、青Diffの過去問の精進に力を入れていきたいと思います。

ということで、また次回も頑張ります。