AtCoder Regular Contest 140 参加記

2022/5/15に開催されたAtCoder Regular Contest 140に参加しました。

atcoder.jp

昨日のABCで、再度の水パフォに届かずの負けをくらって迎えた今回のARC。とりあえず、A、Bは300点、400点という配点だそうなので、この2問を仕留める事ができるといいなーという気持ちで臨むことにしました。

今回の結果

でで、今回の結果は、やっとのことで1完を確保できたというところです。。

ARC140結果
ARC140結果

パフォーマンスは緑の中ぐらいというところで、今回も負けという事になりました。

振り返り

A問題だけで、ほとんどの時間を使ってしまいました。。

ARC140提出結果
ARC140提出結果

A問題

A - Right String

最初の内は問題の意味があまり理解できておらずでした。

とりあえずf(S)の値の最大はN。これをより小さくするには、SをあるNの約数の長さで等分割して、すべての分割した文字列が同じ値にできれば、その約数がf(S)の値になるので、これを求めればよい、ということを理解するまでに40分以上かかりました。

ただ、これで解方の糸口は見つかったというところ。

ただ、なぜか文字の置き換えの計算が合わないらしく、何回かそれっぽい実装を提出したもののWAを連続で喰らってしまう。。うーむ、比較の方法が根本的に違うのだろうか。

大分あきらめかけたころに、等分割した文字列を同じ値にそろえるには、各桁に存在する文字のうち一番多い文字に合わせるのが一番ベストだとやっと気づく。これでダメなら仕方なしという感じで実装を進めて提出したところ、やっとACが取れましたとさ。

91分56秒の5ペナで1完。とりあえず、0完爆死を避けることが出来たので、まあヨシとしましょう。

提出コード

https://atcoder.jp/contests/arc140/submissions/31726323

B問題

B - Shorten ARC

見た目、結構複雑そうなこの問題。

あまり時間がないので、考察も雑になりがち。とりあえず文字列をStringBuilderに突っ込んで置き、奇数回目の処理では、"AARCC"という並びを見つけることを優先し、存在する場合"ARC"に置き換え、ない場合は"ARC"を探して、あれば置換するという風な処理を書いてみました。

が、サンプルは通るものの、提出したらTLEだらけ。。改善方法も思いつかずで、時間切れ終了となりましたとさ。

C問題

C - ABS Permutation (LIS ver.)

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

D問題

D - One to One

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

E問題

E - Not Equal Rectangle

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

F問題

F - ABS Permutation (Count ver.)

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

これまでの実績

今週の土日は連敗。。停滞モードが続きます。

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

総括

とりあえず、今回のARCは0完が回避できただけでも良かったなという回でした。

ARCはアルゴリズムを暗記するというよりは、考察がメインというところなので、解法が降ってこないとどうしようもないという感じ。

しかし、経験を積むことである程度地力は付くかと思いますので、いままで通りボチボチ取り組んでいこうかというところです。

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