2023/7/9に開催されたAtCoder Regular Contest 164に参加しました。
昨日のABCで惨敗を喫してしまい、レートの方はとうとう1100を切るぐらいのところまで落ちてしまいました。
本来なら、昨日の負けを取り戻すべく頑張る、と言いたいところですが、今年に入ってからARCでは全く良い結果が出てません。
いつものようにRated参加はしますが、まずは１完を目標に、レートを必要以上に落とさないようにという感じで臨むこととしました。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年7月9日
まずは１完。レートを大きく落とさないように頑張ります✊
AtCoder Regular Contest 164 - AtCoder https://t.co/FWr2cyD4j1
今回の結果
A問題は解けませんでしたが、なんとかB,C問題を解き切り、２完という上々の結果になりました。
ARCでは、久々の水色パフォーマンスを獲得。なんとか1100台にレートを戻すことが出来ました。
BCが解けて、なんとか水パフォをゲットです😂
— devgenjin77 (@devgenjin77) 2023年7月9日
次も頑張ります✊
devgenjin77さんのAtCoder Regular Contest 164での成績：1161位
パフォーマンス：1309相当
レーティング：1092→1116 (+24) :)#AtCoder #ARC164 https://t.co/JEUPvRnecC
振り返り
A問題は散々苦労して解けずでしたが、BとCが意外とあっさりと解けてくれました。
A問題
今回もA問題は300点問題なので、焦らず考えれば解けるはず、、のはずが、問題を読んでみて全然分からず。。
なんか、３進数っぽい雰囲気はあるなという感じだが、具体的にどう計算していけば良いかがよくわからん。
色々悩みながら、すでに３０分程度経過したところで順位表を見ると、すでにＡ問題のＡＣ数は900に達しようかというところ。このままＡ問題が解けないと、灰パフォの下位ぐらいの爆死という結果になりかねません。
苦し紛れに、メモ化DFSでなんとか解けるかと実装してみたものの、結局TLEを喰らってしまい、万事休す。
仕方なく、A問題は一旦諦め、B問題に賭けてみることにしました。
B問題
これも問題を一読したところ、全然わからんという状態。。が、なんとか爆死を回避するためには解かないといけない問題。幸い、AC数はそこそこ付いているので、そんなに難解なアルゴリズムが必要ではないはず。
とりあえず、YesとNoの判定問題であることから、答えがYesのサンプル１とNoのサンプル２で何が異なるかという点に着目してみる。
まず、サンプル２は色違いの頂点を結ぶ辺のみで構成されており、実際に操作の挙動をシミュレーションしてみると、元居た頂点に戻ることは出来なさそう。
結局、色違いの頂点を交互に使って移動することはできるが、最後に同色同士の頂点を結ぶ辺が無いと元居た頂点に戻れないという感じになりそうな気がする。
ということは、Union-Findを使って、まず色違いの頂点を結ぶ辺で連結成分を構成させてから、同じ連結成分内に、同色の頂点を結ぶ辺があればOKでは？
半信半疑状態でしたが、実装してみたら、なんともあっさりとACが取れましたとさ。
80分16秒で、やっと1完。とりあえず、大負けは回避することができてホッとしました。
提出コード
https://atcoder.jp/contests/arc164/submissions/43430634
C問題
Bを解いた勢いで、C問題に挑んでみる。これもB問題と同じぐらいAC数が付いてるので、なんとかなればと。
この問題は、いわゆるゲームの必勝法的な問題。この手の問題の考え方としては、ミニマックス法が適用できそうである。先手番は後手番が得ることができる最大の利益を最小化する戦略を取ればよい。
そこで先手番が取れる戦略として、であるカードが存在する場合、その差が最大のカードをひっくり返し、ない場合は、表と裏の数の差が最小のものをひっくり返すのがよさそう。
逆に後手番は、であるカードがある場合、その差が最大のカードを取り、ない場合は、表と裏の数の差が最小のものを取るのがよさそうである。
実装としては、であるカードの表と裏の数の差を、降順の優先度付きキューを使って最大値を管理し、逆に裏の数が大きいカードの表と裏の数の差は昇順の優先度付きキューを使って最小値を管理すればシミュレーションができる。
ということで、提出してみたら、これもあっさりとACが取れましたとさ。
103分13秒で2完。当初、A問題解けずで絶望状態でしたが、なんとか勝ち確のところまで挽回する事ができました。
因みにですが、あとで公式解説を見ると、初期状態で、であるカードの数の偶奇によって場合分けするという、なんとも天才的な解法が解説されており、目ぼしいところの提出を見ていると、確かにその解法で解いてるということで、ちょっぴり負けた気分になりました。
提出コード
https://atcoder.jp/contests/arc164/submissions/43433256
D問題
問題すら見ておりません。
E問題
問題すら見ておりません。
F問題
問題すら見ておりません。
これまでの実績
1日でレート1100台に復活です。
総括
今回、A問題が解けずという体たらくでしたが、なんとか挽回することが出来て良かったです。
さらに、ARCの本番でC問題まで解けたのも大分久しぶりでした。難易度の兼ね合いもあるかと思いますが、良い結果が出ると、モチベーションも上がるというものです。
ということで、また次回も頑張ります。
