2023/2/18に開催されたAtCoder Regular Contest 156に参加しました。
前回ARCは、0完終了という散々な結果でした。今回はそのリベンジを果たすべく、少なくとも1完以上は達成しようという気持ちで臨むこととします。
AHCの途中ですが、ARCにRated参加します。
— devgenjin77 (@devgenjin77) 2023年2月18日
今回は1完以上できるようにがんばります✊
AtCoder Regular Contest 156 - AtCoder https://t.co/BvpcvMD5qQ
今回の結果
有言実行。なんとか、1完を確保することができましたとさ。
しかしながら、パフォーマンスはギリギリ緑というところで、結局レートは大幅に下がってしまいました。これでARCだけでみると4連敗です。
1完緑パフォで惨敗😢
— devgenjin77 (@devgenjin77) 2023年2月18日
また出直してきます
devgenjin77さんのAtCoder Regular Contest 156での成績:2042位
パフォーマンス:806相当
レーティング:1148→1118 (-30) :(#AtCoder #ARC156 https://t.co/ktMklBxxNx
振り返り
ほぼほぼA問題に時間を持ってかれました。
A問題
一読した印象としては、スッキリとしたシンプルな解法を見つけないといけない問題かなという感じ。ただ、隣接するコインを同時に操作できないという制約がなんとも微妙だなあ。
とりあえず、1
の位置が奇数同士とものと偶数同士のものはペアで消せる。
よって、奇数位置にある1
の数と偶数位置にある1
の数が両方偶数ならOKで最小の操作回数は1
の数を2で割ったものという感じで実装。
これで通ってくれるかと思い、提出してみたが、そんなに甘くはなく、WA×3で失敗。。
では、1
の数全体が偶数ならOK?という感じで修正してみたが、これもWA。。
ならばと、ノート上で小さいケースをいろいろ試してみる。すると、110
と011
がどうも達成不可で、0110
は3回で達成可能というのがわかってくる。
少し邪道っぽいが、このコーナーケースの考慮を追加したプログラムを投げてみる。が、、結局ACは取れず。。
順位表を見てると、すでにA問題は1000ACをゆうに超えている状態。自分が何に気づいていないのかがわからずで、忸怩たる思いに駆られましたが、2連続0完はなんとか避けようという気持ちで、検討を続行しました。
延々と考えた後、1
の数が全体で2個で且つ隣接している状態、且つさっきのコーナーケースに該当しないパターンなら2回というのが考慮に漏れているのがわかってくる。もう最後のお願いという感じで、この実装を入れてみたら、なんとか無事ACを取ることができましたとさ。75分27秒3ペナで1完。
コンテスト終了後、解説を見てると、邪道かと思ったコーナーケース判定が公式でも必須だったことに少し驚き。
まあ、あまりスッキリした解法にこだわるのも実戦上よくないかという教訓を得たA問題でした。
提出コード
https://atcoder.jp/contests/arc156/submissions/38981468
B問題
順位表上、ある程度のAC数がある問題だったので、ワンチャンあるかという思いで取り組んでみる。
しかしながら、まともな解法すら思いつかずで終了。
途中、回分の操作途中で使える最大のMexを掛け算すれば良いのかと思いましたが、実装してみると、どうも重複カウントしている模様。よって、二項係数の組み合わせが必要なのかなという感じでしたが、結局どうすれば良いのかが分からずじまいでした。
C問題
問題すら見ておりません。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
今回のARCも結局負け。またレート1100切り間近まで落ちてしまいました。
総括
今回は、なんとか0完爆死だけは避けたという結果でした。パフォーマンス的にはあまり良くない結果でしたが、なんとかA問題を通し切ったことは良かったです。
来週もARCがあるということなので、AHCと並行での作業になりますが、今回の復習を行い、次に備えたいと思います。
ということで、また次回も頑張ります。