devgenjin77’s blog

AtCoder Beginner Contest 335(Sponsored by Mynavi)参加記

AtCoder 競プロ ABC 企業主催コンテスト

2024/1/6に開催された、AtCoder Beginner Contest 335（Sponsored by Mynavi）に参加しました。

2024年最初のRatedコンテスト。昨年は入水を果たしたものの、現状緑落ちという状態なので、今年は早めの再入水を決めて水色をキープし、入青を伺えるようになることを目標に頑張っていこうと思います。

ということで、今回は再入水に向けて、勝ちを収められるようにがんばります。

Rated参加します。
２０２４年最初のコンテスト。とりあえず勝ちで始められるように頑張ります✊
AtCoder Beginner Contest 335（Sponsored by Mynavi） - AtCoder https://t.co/y6rnbpbeS6
— devgenjin77 (@devgenjin77) 2024年1月6日

今回の結果

気合いを入れてはみたものの、４完という残念な結果で終了です。

ABC335順位表

パフォーマンスは、惜しくも水色に届かず。一応、勝ちを収めたものの、少し物足りなさが残る結果でした。

４完終了でしたが、なんとか勝ち😅
devgenjin77さんのAtCoder Beginner Contest 335（Sponsored by Mynavi）での成績：1980位
パフォーマンス：1185相当
レーティング：1162→1165 (+3) :)#AtCoder #ABC335（SponsoredbyMynavi） https://t.co/kdFIuQiJxa
— devgenjin77 (@devgenjin77) 2024年1月6日

振り返り

E問題のTLEを解消することができませんでした。

ABC335提出結果

A問題

A - 202<s>3</s>

文字列 $S$ の末尾を4に変えて出力するだけ。

実装して、問題なくAC。1分16秒で1完です。

提出コード

https://atcoder.jp/contests/abc335/submissions/49061659

B問題

B - Tetrahedral Number

$x, y, z$ を、それぞれ $0$ から $N$ まで全部試して、 $x + y + z \le N$ なら出力という感じの全探索でOK。

こちらも問題なくAC。3分18秒で2完です。

提出コード

https://atcoder.jp/contests/abc335/submissions/49066589

C問題

C - Loong Tracking

以下考察。

$i$ 回目の移動後の、頭のパーツの位置の $x$ 座標、 $y$ 座標を、それぞれ $posx \lbrack i \rbrack$ $posy \lbrack i \rbrack$ とする。
2のクエリが来た時、 $p$ の値が、1のクエリの回数以下の場合、答えは、1のクエリの回数から、 $(p - 1)$ を引いた回数の移動後の頭のパーツの位置になる。
2のクエリが来た時、 $p$ の値が、1のクエリの回数より大きい場合、答えは、 $x$ 座標が、 $p$ から1のクエリの回数を引いた値。 $y$ 座標が、 $0$ となる。

という感じの実装で提出したら、問題なくACが取れましたとさ。20分50秒で3完。

元々の全パーツの位置を配列で持っておけば、分岐が要らないようにできてシンプルになったかなあという印象ですが、まあACが取れたのでよし。

提出コード

https://atcoder.jp/contests/abc335/submissions/49082063

D問題

D - Loong and Takahashi

考察してみると、 $N \times N$ サイズのグリッド上で、左上から始めて時計回りに $1$ ずつインクリメントしながら移動していくという感じの実装でOKかという感じです。

ということで、少し実装に苦労したものの、問題なくACが取れましたとさ。

36分20秒で4完です。

提出コード

https://atcoder.jp/contests/abc335/submissions/49094184

E問題

E - Non-Decreasing Colorful Path

考察してみると、広義単調増加なパスでない場合は、得点が $0$ になるということで、 $A_u \gt A_v$ の場合は、 $u$ から $v$ への辺を引かない有向グラフとして定義すれば良いのではないかという感じ。

あとは、頂点 $1$ から始めて、BFSを使って、各頂点毎の最大得点を計算し、最終的に、頂点 $N$ の得点を見ればOKかと。。

ということで、実装してみたら、WAこそ無いものの、TLEという結果に。。。

もう少し考察して、 $A$ の値が同じ頂点で直接辺が引かれている場合、Union-Findを使って、頂点を同一視することで計算量が落とせるのでは？という考えが浮かぶ。

が、、これを実装するものの、TLEが少し減っただけで通らず。

結局、TLEを解決することができずで時間切れになりましたとさ。

F問題

F - Hop Sugoroku

Eが解けないので、これならなんとかなるかと目を通したものの、なにもわからずで終了。

G問題

G - Discrete Logarithm Problems

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

これまでの実績

今年最初のコンテストをなんとか勝ちで終えました。

コンテスト実績

総括

Eは惜しいところで解けませんでしたが、これも実力不足というもの。次回ABCまでにきっちりと復習していこうと思います。

あと、Fは平方分割だった模様。これもまだまだ理解できていないアルゴリズムなので、これを機会に勉強していきます。

ということで、今年も１年競プロを頑張ります。