AtCoder Regular Contest 157 参加記

AtCoder 競プロ ARC

2023/2/25に開催されたAtCoder Regular Contest 157に参加しました。

atcoder.jp

前回ARCは、なんとか１完達成しましたが、レート的には敗北という残念な結果でした。

今週は結構AHCに時間を取られており、アルゴリズム精進の時間は取れていない中での参加で不安要素もありますが、今回は２完以上を目標として臨むことにします。

今回の結果

今回も、結局１完で終了と言う結果でした。。

ARC157結果
ARC157結果

パフォーマンスはギリ1000に届かずで、今回もレート的には負け。今年のARCは全て負けており、通算５連敗です。

振り返り

A問題以外全然わかりませんでした。

ARC157提出結果
ARC157提出結果

A問題

A - XXYYX

問題一覧をみてると、全体的にXYの並びが多いなあという印象でしたね。

で、今回のA問題は300点問題なので、パフォーマンスを考えると早めに解いておきたいところでしたが、一読したところコーナーケースが潜んでいそうで少し難しいのではという感じでした。

手元でいろんなケースを試してみたものの、これといったシンプルな解法は見つからず。仕方が無いので愚直で解いてみることに。

まず、 XX,XY,YX,YYのうち、ありうるケースを先頭で固定する。

現在の末尾がXの時、XYの残りがある場合は一つ使って末尾をYに、末尾がYの時、YXの残りがある場合は一つ使って末尾をXにする処理を繰り返す。この処理が終了したときに、XYの個数と、YXの個数が両方0でない場合はNG。

次に、一回でも文字列中にXがあった場合はXXを0に、Yがあった場合はYYを0にする。この時点で、XXの個数と、YYの個数が両方0でない場合はNG。それ以外はOK。これをありうる先頭のパターン全てでチェックする。

上記の要領で実装して、なんとかACが取れましたとさ。33分42秒で1完です。

今回は、制約がO(N)で間に合うやつだったのでなんとかループで解きましたが、N=10^{18}のケースがあったらちょっとどうなっていたか分からなかったですね。

でも、なんとか０完を阻止できたのでヨシ。

提出コード

https://atcoder.jp/contests/arc157/submissions/39185526

B問題

B - XYYYX

残りが90分弱あるので、取り組んでみましたが、これといった解法は思いつかずでした。

元から、Xしかないケースや、KがXの個数以下の場合はそれなりに解けそうだが、それ以外のケースをどうするかというところが悩みどころ。

あれこれ試行錯誤しましたが、結局結論を出せないまま、時間切れです。

C問題

C - YY Square

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

D問題

D - YY Garden

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

E問題

E - XXYX Binary Tree

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

F問題

F - XY Ladder LCS

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

これまでの実績

なんとか爆死を免れましたが、停滞モードは継続中です。

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

総括

今回も、０完爆死だけは避けたという結果。こういう回は、A問題をもう少し早く通せないと厳しいですね。。

ARCについては、直近５連敗ということで、かなり苦手意識を持ってしまうところですが、ここを克服しないともっと上にはいけないと思いますので、引き続き今回の復習と、ARC過去問の精進を進めていき、次に備えたいと思います。

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