2022/4/9に開催されたAtCoder Regular Contest 138に参加しました。
今回のARCコンテストはA問題から400点問題ということで、場合によっては0完してしまうかという懸念もありますが、なんとか爆死を回避すべく1完は確保したいという気持ちで臨むこととしました。
Rated参加します。とりあえず0完爆死しないように頑張ります✊
— devgenjin77 (@devgenjin77) 2022年4月9日
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138) - AtCoder https://t.co/2pTuhW6Zo1
今回の結果
で、今回は苦戦したものの、なんとか2完を確保することに成功しましたー。
肝心のパフォーマンスは、緑上位辺り。なんとかレートは上昇という結果になりましたとさ。
なんとか2完確保です😆
— devgenjin77 (@devgenjin77) 2022年4月9日
devgenjin77さんの大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)での成績：1428位
パフォーマンス：1198相当
レーティング：1012→1032 (+20) :)#AtCoder #大和証券プログラミングコンテスト2022Spring(ARC138) https://t.co/6vPPm10mfa
振り返り
Aで相当もたついてしまったのが反省点です。
A問題
解法は早めに思いつきましたが、実装に時間をかけすぎました。。
まず、入力された整数列を、先頭
項目までの
と
項以降の
に分けて考える。
各に対して、
となる最大の
に対して、
を最小化すれば答えが求まる。
最大のを探すところがネックになるが、区間最小を求めるセグ木を使って二分探索すれば良いかというところまでは早めに見通せました。
で、早速実装に取り掛かりましたが、これまでコンテスト本番でセグ木を使ってこなかったので、大分実装にもたついてしまいました。。
また、最大のを検索するところで、ac-libraryから移植してきたセグ木のmaxRightかminLeft関数が使えるかというところを検討してたら、あっというまに時間を溶かしてしまい、気づいてみたらコンテスト開始1時間経過してしまいました。。。
結局、肝心の二分探索は、自力実装をすることでとりあえず提出。なんとかA問題をACすることができ、0完爆死は回避することができましたとさ。
79分16秒という、かなり残念なタイムで1完。後で見ると、A問題のAC数が想定以上に多かったので、びっくりしました。
提出コード
https://atcoder.jp/contests/arc138/submissions/30820232
B問題
空の数列に対して、操作A,Bの繰り返しを行うことで、整数列
に一致させることができるかという問題。
とりあえず、整数列の状態から、操作A,Bの逆操作を繰り返すことで、空の数列にできるかという観点で考える。
で、とりあえずざっくりと検討してみると、操作Aを行なった後は、数列の先頭は必ず
になり、操作Bを行なった後は、末尾が必ず
になるということから、
の末尾が
の場合、Bの逆操作として、末尾の
という要領の解法を立ててみる。
あとは、flip操作を行う時に、の要素全てをflipするのではなく、比較する値をflipすることで、高速化を図ればなんとかなるかと。
で、サンプルは通ったので、証明が完全でないながらも、とりあえず投げてみたらば、これがあっさりACが取れてくれましたとさ。
103分13秒というだいぶ微妙なタイムで2完を確保。この時点で、一応順位も1300台に乗せたので、レート下げはないかというところでホッとしました。
C問題
残り時間が20分足らずというところで、なんとか問題文を見てみましたが、解法が降りて来ずで時間切れ。。
一応、青Diffということらしいので、今週じっくりと検討してみることにします。
D問題
問題すら見れておりません。
E問題
問題すら見れておりません。
F問題
問題すら見れておりません。
これまでの実績
前回に続いての2連勝！とりあえず、この勢いを大事にしたいものです。
総括
今回は、A問題が400点ということで、だいぶ構えてしまった結果、A問題で相当時間を掛けてしまいました。
解法が見えていただけに、もう少し早く提出することもできたかという思いもあるので、少し残念な気持ちです。
まず当面の課題として、セグ木の使い方に慣れてないというところが今回時間がかかった原因というところがあるので、その辺りを中心に対策をしていこうと思います。
ということで、また次回も頑張ります。
