2022/7/16に開催されたAtCoder Regular Contest 144に参加しました。
ここ最近のコンテストでは、レートが上がったり下がったりで、停滞ムードが漂っている状況。
とりあえず、今回のARCは、Bが400点問題ということで、2完できればなんとかレートが上がるかなという感じだったので、2完を目標として挑むこととしました。
Rated参加します。とりあえず2完以上目指して頑張ります✊
— devgenjin77 (@devgenjin77) 2022年7月16日
AtCoder Regular Contest 144 - AtCoder https://t.co/1A3xaDqWjb
今回の結果
で、結果としては、1完で終了という悲しい結果に。。
パフォーマンスは緑にすら届かずで、レートは大幅に下げてしまうことになりましたとさ。
1完で冷え😢
— devgenjin77 (@devgenjin77) 2022年7月16日
また、次回頑張ります。
devgenjin77さんのAtCoder Regular Contest 144での成績：2443位
パフォーマンス：792相当
レーティング：1036→1013 (-23) :(#AtCoder #ARC144 https://t.co/MpQfRfHQPI
振り返り
B問題が二分探索だということに、まったく気がつきませんでした。
A問題
最初のうちは、よくわからずだったが、サンプルの解答を見ると、ある程度の法則性が掴めてきた。
の時、
となる
を最大化する時、
に
以上の数字が含まれていると必ず損をしてしまうので、
上記のような
で埋めるようにすれば良い。
ということで、とし、
は、題の条件を満たし且つ、できるだけ
を下位に埋めた数字とすることに。
あとは実装して提出したら、なんとか一発でACが取れてくれましたとさ。
16分55秒で1完。順位表をみたら、この時点でA問題のACが1000以上付いてたので、少し時間使いすぎかと反省しました。
提出コード
https://atcoder.jp/contests/arc144/submissions/33261534
B問題
サンプルデータから検討してみると、整数列の最小値に
を足し、最大値に
を引くことを繰り返し、操作後の
を求めるのが正当なように見える。
ということで、実装方法を色々考えてみるが、セグ木を使ったやりかたでは実装は無理そう。
ならばと、最大値と最小値を管理する優先度付きキューを使うことでなんとかなるかと実装してみるが、これは上手くいかず。。
残り時間はたくさんありましたが、いかんせん実装方法は思いつかずで、このまま時間切れとなりましたとさ。
で、コンテスト後に解説をみると、二分探索を使うのが正解とのこと。本番中は全く思いつかずだったので、この点は反省したいです。
C問題
一応、少し問題を見たものの何もわからず。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
今回は、大幅な下げ。レート3桁台も見えてきてしまいました。
総括
B問題が二分探索と気づけなかったのが、一番の反省点。このぐらいの典型が思いつかないようでは、まだまだ勉強不足ですね。
とりあえず、日曜のABCではレートを落とさないように頑張るのみです。
ということで、また次回も頑張ります。
