ALGO ARTIS プログラミングコンテスト2023 秋(AtCoder Regular Contest 168)参加記

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

2023/11/19に開催された、ALGO ARTIS プログラミングコンテスト2023 秋(AtCoder Regular Contest 168)に参加しました。

atcoder.jp

所用で２週連続ABCを不参加にしておりましたが、直近コンテストでは緑落ちを喰らっている身分だけに、さっさと水色に戻しておきたいところ。

今年は１年通じてARCで苦い記憶しか無いところですが、なんとか再入水を狙えるところまで行ければという感じで挑んでみました。

今回の結果

目標の２完には届かずでした。

ARC168順位表
ARC168順位表

で、前回参加したABCに続いて茶パフォを喰らってしまい、レートは暴落。再入水がさらに遠のく結果になりましたとさ。

振り返り

Aで余計なペナを喰らうわ、BではWAが取れないわで散々な内容でした。

ARC168提出結果
ARC168提出結果

A問題

A - <Inversion>

初回の考察では、 x_1=N とし、 S_i が<の場合、 x_{i+1}=x_i+1 。

そうでない場合 x_{i+1}=x_i-1 として、 x の転倒数を求めるのが良いかと思い実装してみたら、サンプル４が合わず。。

よくよく考えると、<で区切ったところで大きく差をつけることで、転倒数の最小化が図れるような気がする。ということは、結局>の連続を見て、それぞれの転倒数を計算して合計すれば良いのでは。。

で、結局この考察が当たりだったのですが、初回提出はオーバーフローでWAを喰らってしまい、余計な1ペナを喫してしまいました。

36分40秒1ペナで1完です。

提出コード

https://atcoder.jp/contests/arc168/submissions/47760433

B問題

B - Arbitrary Nim

grundy数かなあという問題。正直、grundy数は最近まともに勉強し始めたところなので、あまりよく理解できてない。。

とりあえず考察してみると、Aの全てのxorが0でない場合は、普通のNimのようにすれば先手が必勝のためkの上限は無し。

Aの全てのxorが0の場合どうするかだが、これが全然分からずで、サンプルを見ながら、Aの最大値マイナス１とか、Nの偶奇で判定してみたりとか色々考察してみてはとりあえず提出するなどしてみましたが、一向にWAが取れず。。

結局、時間いっぱい使って解き切れずでした。

C問題

C - Swap Characters

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

D問題

D - Maximize Update

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

E問題

E - Subsegments with Large Sums

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

F問題

F - Up-Down Queries

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

これまでの実績

さらに水色が遠のいてしまいました。また年内に再入水できるように頑張ります。

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

総括

一か月振りのARCでしたが、今回も結局惨敗となりました。やはり考察を積み重ねて解法を導くというところがまだまだ苦手なんだという印象です。

とはいえ、いつまでも実力不足を嘆いていても仕方なし。また次回に向けて、今回の復習をしていこうと思います。

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