AtCoder Grand Contest 059 参加記

2022/12/4に開催されたAtCoder Grand Contest 059に参加しました。

atcoder.jp

前回のAGCの時、緑コーダーでの参加だったのでUnratedでした。その時に、次回AGCこそは入水してRated参加するぞという事を言っていたような気がするのですが、現時点で入水できていないためUnrated参加です。

まあ、Rated参加できないことは残念なのですが、そこは仕方なし。とりあえず1完できれば御の字かという感じで臨むことにしました。

今回の結果

0完です。

AGC059結果
AGC059結果

なんか、今回は0完でも水パフォはあったようですが、Unratedなので関係ありません。

振り返り

A問題だけで、3時間フルに使いましたが、結局解き切ることはできませんでした。

AGC059提出結果
AGC059提出結果

A問題

A - My Last ABC Problem

とりあえず、問題を読んだところでは、手強そうな問題という印象しかなかった。それでも、なんとか解く手段はないかと検討してみる。

あれこれ考えた挙句、一案として、DPが使えそうかということで、以下のDPで考えてみる。

dp \lbrack i \rbrack \lbrack j \rbrack :=先頭からi文字目までを、文字j ( 0:= A, 1 := B, 2 := C ) で揃えるために必要な操作回数。

で、L,Rの範囲内の答えは、min(dp \lbrack R \rbrack \lbrack 0 \rbrack - dp \lbrack L - 1 \rbrack \lbrack 0 \rbrack, dp \lbrack R \rbrack \lbrack 1 \rbrack - dp \lbrack L - 1 \rbrack \lbrack 1 \rbrack, dp \lbrack R \rbrack \lbrack 2 \rbrack - dp \lbrack L - 1 \rbrack \lbrack 2 \rbrack)

という感じ。

ということで、遷移を考えて実装。一応サンプルは通ったので、これでなんとかという感じで投げてみました。

しかしながら、結果はWA。。。よくよく調べると、これでダメなケースは結構ありました。。

仕方なく他のやり方がないか検討したが、結局わからず。3時間フルで使うも結局解けずじまいでした。

B問題

B - Arrange Your Balls

問題ぐらいはチラ見しましたが、なにもわからず。

どうも、AC数はA問題よりはるかに多かったようなので、この問題に賭けといたほうがよかったのかもしれません。。

C問題

C - Guessing Permutation for as Long as Possible

問題すら見ておりません。

D問題

D - Distinct Elements on Subsegments

問題すら見ておりません。

E問題

E - Grid 3-coloring

問題すら見ておりません。

F問題

F - LIDS

問題すら見ておりません。

これまでの実績

UnRatedにつき、レート変化はありません。

コンテスト実績
コンテスト実績

総括

今回もUnratedでの参加となったAGC。結局0完だったので、Unratedでよかったのかもしれません。

一応、月内には次のAGCもあるということですので、次回に向けて今回の復習をできるだけやっておこうと思います。

ということで、また次回も頑張ります。