ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)参加記

2023/1/21に開催された、ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)に参加しました。

atcoder.jp

ここ最近のABCでは4完止まりが続いており、レートの方も停滞気味。

今回は、そろそろ5完以上取ってレートを上げていこうという気持ちで臨むこととします。

今回の結果

結局、今回も4完止まりになりましたとさ。

ABC286結果
ABC286結果

パフォーマンスは、なんとか4桁を確保というところで、今回は負け。停滞モードは、まだまだ続くのでした。

振り返り

D問題ですこしやらかしてしまい、E問題は解き損ねてしまいました。

ABC286提出結果
ABC286提出結果

A問題

A - Range Swap

A問題にしては、だいぶややこしい問題を出すなあという印象。問題文の意図を読み解くのに時間がかかってしまいました。

読み解いてみれば、単に区間  \lbrack P, Q  \rbrack  \lbrack R, S  \rbrackを交換すればよいということで、あとは単純にfor文で実装。

実装に少し時間がかかりましたが、一発でACが取れました。

6分17秒で1完。最近のABCでは一番時間が掛かったA問題でした。

提出コード

https://atcoder.jp/contests/abc286/submissions/38194228

B問題

B - Cat

個人的には、A問題より簡単な気がする。

Javaだと、Stringクラスのreplaceメソッドを呼ぶだけの実装でOK。問題なくACが取れました。

7分50秒で2完。

提出コード

https://atcoder.jp/contests/abc286/submissions/38195747

C問題

C - Rotate and Palindrome

最初解法が分からずで詰みそうでしたが、なんとか解法が閃きました。

どの状態からでもB円払う操作を \lfloor \frac{N}{2} \rfloor回行えば回文になるということから、A円の操作を0回~N - 1回行った時のB円払う必要がある操作の回数を全部試せば最小のコストが求まる。

あとは実装。問題なく一度の提出でACが取れましたとさ。

16分52秒で3完。

提出コード

https://atcoder.jp/contests/abc286/submissions/38202117

D問題

D - Money in Hand

ナップザックDPの応用かという見た目の問題。

とりあえず、 dp \lbrack i \rbrack \lbrack j \rbrack := i番目までの硬貨を使って、j円払えるかというDP配列を作成。

あとは遷移を書いて提出。。といったところだったが、WA。。。

遷移処理で下らないバグを埋めてしまったようです。都合8分程度費やしてやっと解決。

36分18秒2ペナで4完。少しもったいない結果になりましたが、E問題で取り戻せればと。。

提出コード

https://atcoder.jp/contests/abc286/submissions/38209942

E問題

E - Souvenir

どうもワーシャル–フロイド法を使って最短経路を求める問題という事らしいが、土産の価値の最大を求めるということで少しひねりを入れてみたという感じ。

とりあえず、最短経路という前提で、土産の価値の最大を求めるにはどうすればいいのかがよくわからん。

とりあえず、クエリ毎にDFSしてみたらどうかと実装してみたら、WAは出ないもののTLEで終了。。

ではメモ化DFSしたらどうかと改造したら、今度はTLEは無いもののWAが出てしまう。

あれこれ試行錯誤しても、結局ACは取り切れずで時間切れになりましたとさ。

F問題

F - Guess The Number 2

とりあえず、問題に目を通しましたが、わからず。制約の110にも深い意味がありそうだが前提知識が無かったので単純に意味不明でした。

中国剰余定理。この後、履修しておきます。

G問題

G - Unique Walk

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

Ex問題

Ex - Don't Swim

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

これまでの実績

まだまだ、停滞モードは続きます。いつになったら入水できるのやら。

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

総括

今回のE問題が解き切れなかったのは、アルゴリズムの理解不足なのか、実装力の不足なのか。とりあえず、解けないといけない問題だったので、そのあたりは残念です。

最近、平日は毎日競プロの精進に時間を充てていいるのですが、なかなか結果が出ないのがもどかしいところ。しかし、力をつけていけば、いつかレートは後から付いてくると信じて、今後も精進とコンテスト参加を続けていきます。

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