2023/4/8に開催されたAtCoder Regular Contest 159に参加しました。
前回のARCでは、0完爆死を喰らいレートを大きく減らす羽目になりました。今回は、なんとか1完を死守しようという感じで臨んでみます。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年4月8日
前回ARCでは、0完爆死を喰らってしまいましたので、今回は最低1完を目指して頑張ります✊
AtCoder Regular Contest 159 - AtCoder https://t.co/0vz9BfM5A8
今回の結果
で、、なんとか、1完を死守することに成功しましたとさ。
1完だと、今回も冷えかなあ、、なんて思ってましたが、蓋を開けてみるとなんと緑パフォ上位まで取れていました。プラス1ですが、ARCでは久々の勝ち。
ちなみに、ARC6連敗中でしたが、連敗を止めることにも成功しましたとさ。
1完で冷えかと思ったら、ギリギリ助かりました。
— devgenjin77 (@devgenjin77) 2023年4月8日
明日も頑張ります。
devgenjin77さんのAtCoder Regular Contest 159での成績:1410位
パフォーマンス:1117相当
レーティング:1113→1114 (+1) :)#AtCoder #ARC159 https://t.co/W4OOajeaTO
振り返り
B問題を解き切ることができませんでした。
A問題
行列の行列を縦行、横列コピーした巨大な行列を探索する問題っぽいが、が同じ頂点については同様に扱えるはずなので、結局、頂点から頂点への最短経路問題となる。結局個コピーするのは考慮する必要はない。
あとは、どうやって最短経路を求めるかだが、クエリの個数が最大100個程度ということで、クエリ毎にダイクストラでも間に合うかなあという感じだったので、それで実装を進めました。
結局、考えは間違ってなかったようで、最初の提出はケアレスミスで1ペナを喰らったものの、修正後、問題なくACを取ることができましたとさ。
34分2秒1ペナで1完。なんとか、宣言通り0完を回避することができました。
提出コード
https://atcoder.jp/contests/arc159/submissions/40415878
B問題
問題を読んでみたが、何もわからずだったので。とりあえず愚直で求めるプログラムを書いてみました。
これが実行してみると、処理が進む毎に削除するGCDが同じものを繰り返すか、大きくなっていく感じになる模様。
よって、同じGCDを減算する回数を効率的に求めることができればというところだったのですが、結局上手い解法が見つからず。
一応、サンプルは通る解も作って見たものの、TLEを喰らう有様。結局、時間いっぱいまで悪あがきしましたが、解けずで終了となりました。
C問題
問題すら見ておりません。
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
今回はプラス1という結果でしたが、負けるよりは随分ましです。
総括
今回のB問題は惜しかったですが、まあ解けなかったのは仕方なし。次回に向けて復習をしていこうと思います。
また、一応ARCの連敗も止まりましたが、かなりギリギリの結果だったので、次のARCでまた勝てるかはだいぶ難しそうという感じがします。また次回良い成績が出せるように精進していきます。
ということで、また次回も頑張ります。