2022/9/4に開催されたAtCoder Regular Contest 148に参加しました。
一時は、入水目前までレートを上げたものの、ここ2回のRatedコンテストで大敗し、レートは暴落。入水までの道のりは遠いものとなりました。
今回は、なんとかこの連敗を止めて、とりあえず、この悪い流れを断ち切ろうという気持ちで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2022年9月11日
ここのところRated2連敗中なので、とりあえず連敗を止められるように頑張ります✊
AtCoder Regular Contest 148 - AtCoder https://t.co/IFAzVoiMPD
今回の結果
終盤まで苦戦し、あわや0完爆死かというところを、なんとか滑り込みで2完達成という、いいのか悪いのかよくわからん結果でした。
パフォーマンスは、なんとか緑上位まで持ってきたものの、すこし勝ちに及ばずという結果。残念ながら連敗を止めることはできませんでしたが、爆死は免れたのでヨシかと。
2完緑パフォで、惜しくも冷えました😩
— devgenjin77 (@devgenjin77) 2022年9月11日
ただ今回0完爆死もある展開だったので、なんとか持ち堪えたというところです。
devgenjin77さんのAtCoder Regular Contest 148での成績：1444位
パフォーマンス：1071相当
レーティング：1114→1110 (-4) :(#AtCoder #ARC148 https://t.co/Y0AZO3dM77
振り返り
A問題で、ドはまりしてしまいました。
A問題
とすると、余りの種類数は必ず
以下になるので、この問題は、余りの種類数を
にできるかという問題だということは分かった。
あとは、試すべきの候補をどのくらい絞れるかというところ。
まずは、のうち最小の要素を素因数分解して、その素因数を
の候補にしてみる。が、これはサンプルすら通らずでＮＧ。
この辺で、解法のアイデアがまったく出てこず、30分ほど悩んで時間を溶かしてしまう。。
仕方がないので、サンプル３の答えがどうなるかを愚直に計算してみた時、実はの隣同士の差分が関係するのではないかと推察。
ということで、をソートして、隣同士の差分をとり、その差分の最小値を素因数分解すればなんとかなるかというところで組んでみると、なんとかサンプルが通る実装が完成。
が、、提出してみたらＷＡ。。。
結局、１時間程度掛かったところで、一旦この問題は撤退。順位表上、そこそこ解かれているＢ問題に取り掛かることとしました。
ーーー
とりあえず、なんとかB問題を解き切りました。終了まで残り10分を切っている状態ですが、なんとかAも解けないかと悪あがきしてみる。
で、前半時点で試してなかった、以下の2処理を入れてみることに。
で操作したときに、種類数が
なら、そこで答えを
の隣同士の差分をソートした時の最大値を素因数分解する。その素因数全部を
の候補として試す。
で、これがなんとか当たってくれたようで、終了1分前というギリギリのところで、ACを取り切ることができました。
118分32秒5ペナという、ボロボロの内容でしたが、なんとか2完を確保しました。
ちなみに、公式解説では、GCDを計算するというのが解法だということでしたが、本番中は、全く思いつきませんでした。
提出コード
https://atcoder.jp/contests/arc148/submissions/34801402
B問題
と
を適切に決めて、1回の操作で辞書順最小の文字列にしましょうという問題。
まず、は
のうち一番左にあるpの位置というのは直感でわかった。
あとは、をどうするかというところだが、まずは
の中でもっともpが連続している部分列の右端じゃないかと推察。
そのような候補が2つ以上ならどうするかという問題もあるが、まずは候補のうち、最も左側のものをということにしてみる。
で、これで出してみたら、WA。。。
仕方がないので、そのような候補全てについて、操作を試し、できた文字列の最小を求めるという方向でやってみる。
これが、もしかしてTLEするかと思ったが、なんとかその懸念は不要だったもよう。とりあえず、ACを取ることができました。
108分15秒1ペナという、酷いタイムですが、なんとか1完を確保。
因みに、公式解説では、は全探索でも行けるということでした。うーん、ムダなＷＡを取ってしまったのが少し悔やまれる。
提出コード
https://atcoder.jp/contests/arc148/submissions/34799682
C問題
順位表から見ると、ある程度のAC数があったので、ワンチャンあるかと問題文を確認してみましたが、何もわからず。。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
Rated3連敗となりました。非常にもどかしい展開です。
総括
今回は、連敗を止めるどころか、0完爆死を喰らいかねない展開でしたが、なんとかギリギリ耐えたというところでした。
しかし、ここ最近のARCでは、いい結果が出てないですな。やはり、ABCの過去問精進に偏っているのが原因かもしれません。
また、今回の結果を振り返って、次回に向けて精進していきたいと思います。
ということで、また次回も頑張ります。
