2022/10/16に開催されたAtCoder Regular Contest 151に参加しました。
昨日のABCは所用のため参加できずでしたが、今週はARCがある週。
現在、レートは入水まであと少しというところまで来ているので、ここいらでなんとか水パフォをとって入水を決めようという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年10月16日
とりあえず2完以上、そして水パフォをとって入水できるようにがんばります✊
AtCoder Regular Contest 151 - AtCoder https://t.co/vw5juBJbhr
今回の結果
残念なことに、1完をとるのがやっとという有様でした。
今回はなんと、久々の茶パフォ。。レートを大きく落としてしまい、水色コーダーへの道のりも遠いものとなってしまいました。
なんとか1完したものの、茶パフォを喰らいレートは暴落しました😭😭
— devgenjin77 (@devgenjin77) 2022年10月16日
また、次回頑張ります。
devgenjin77さんのAtCoder Regular Contest 151での成績：2097位
パフォーマンス：615相当
レーティング：1176→1131 (-45) :(#AtCoder #ARC151 https://t.co/xRIHoXS7YY
振り返り
A問題を解き切るだけで精一杯でした。
A問題
最近のARCでは、毎回A問題が鬼門なのだが、今回のA問題もやたらと難しく感じる。。
まず、問題文を理解するまで10分程度。その後の方針を立てるのにもやたら時間がかかり、開始から30分経っても、ほぼ解法がわからない状態。。
とりあえず、ここぐらいから方針らしきものが立ってくる。とりあえず、となる
に着目すれば、
の個数が奇数の場合は、そもそも答えを作ることができないので、
が答えとなる。
次に、となる
をソートした配列を両端キューで管理することを考えてみる。
まず、キューの先頭からを取得したときに、
のうち
である方を
にする。次に、キューの末尾から位置
を取り出し、
のうち、さきほど
に変えた方とは違う方に対して01をひっくり返せばなんとかなるかと。。
が、これはWA。。
次に、の場合は、
にしてもいいじゃないかと気づき、実装に追加してみるが、これも結局ＷＡ。。
その後もあれやこれやと試してみたが、何もわからず。気が付けば開始からゆうに1時間を経過しており、0完爆死が現実的なところとして見えてきました。。。
仕方がないので、ある程度開き直って貪欲っぽい処理でなんとかならんか考えてみる。
キューの先頭からを取得したときに、
のうち
である方を
にするが、その時変えなかった方については、先頭から貪欲にみて、
を
にすることで、ハミング距離を一緒にできるかを試してみる。
出来なかった場合は、後ろからみて、を
にすることでハミング距離を一緒にする。
こんな感じで実装したら、やっとこさACを取ることができましたとさ。
87分54秒3ペナとボロボロになりながらも、なんとか1完。この時点で、順位は2000位ぐらい。。
てゆうか、大分解かれすぎだろ。そんなに簡単か？この問題。。
提出コード
https://atcoder.jp/contests/arc151/submissions/35732263
B問題
とりあえず、30分ほど余しているので、検討に着手してみるが何もわからず。
半ば戦意喪失のまま時間切れとなりましたとさ。
C問題
問題すら見ておりません。
D問題
D - Binary Representations and Queries
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
前回ARCは、1完でもかすり傷でしたが、今回は大ダメージを喰らってしまいました。。
総括
今回は、もう0完で爆死とならなかったのが、せめてもの救い。前回も書きましたが、ARCは、問題セットの相性が結果に大きく響きますな。
とりあえず、過ぎたことは考えても仕方なし。次回以降また気持ちを切り替えて臨もうと思います。
ということで、また次回も頑張ります。
