AtCoder Beginner Contest 236 参加記

2022/1/23に開催されたAtCoder Beginner Contest 236に参加しました。

昨日のARCでは1完で冷えという残念な結果だったので、今回で盛り返しできるようにという気持ちで臨むことにしました。

Rated参加します。昨日のARCでは冷えてしまったので、連敗しないように頑張ります✊
AtCoder Beginner Contest 236 - AtCoder https://t.co/9fc6TmBmes
— devgenjin77 (@devgenjin77) 2022年1月23日

今回の結果

結果は4完。D問題に大分手こずってしまいました。。

それでも、肝心のパフォーマンスは水色まで出てくれまして、なんとかHighestを更新することができましたとさ。

4完でも水パフォが出て、Highest更新しました😂😂
来週の土日も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 236での成績：1449位
パフォーマンス：1309相当
レーティング：1022→1054 (+32) :)
Highestを更新しました！#AtCoder #ABC236 https://t.co/5kkSlPJqf5
— devgenjin77 (@devgenjin77) 2022年1月23日

振り返り

今回はDが解けるのと解けないのでは大分違う状況になりましたね。

A問題

A - chukodai

文字列 $S$ の $a$ 文字目と $b$ 文字目を入れ替えるだけの簡単な問題。

こちらは問題なくACを取ることができました。

提出コード

https://atcoder.jp/contests/abc236/submissions/28721351

B問題

B - Who is missing?

配列 $A$ の中に、どの整数が何回出現したかを配列で管理し、最終的に出現回数が3だった数字を出力すればよい。

こちらも問題なくACが取れました。

因みに、コンテスト後の解説などを見ると、配列 $A$ の全部のxorを取ると答えになるということ。本番でこのような発想が出るようになりたいものですなー。

提出コード

https://atcoder.jp/contests/abc236/submissions/28729131

C問題

C - Route Map

配列 $T$ の要素を全部Setに突っ込んでから、 $S$ の要素について $T$ に含まれていればYes、なければNoを出力すればよい。

こちらも問題なくACを取ることが出来ました。

提出コード

https://atcoder.jp/contests/abc236/submissions/28735054

D問題

D - Dance

一目、あり得る全ての組み合わせについて、しらみつぶしに計算して最大値を求めればよいかと思われる。

ということで、計算途中でどの人が既に選ばれたのかを配列で管理しながら、DFSで探索して最深部で答えを計算するプログラムを組んでみる。

で、これがサンプルまで通ったものの、提出してみればあっさりTLEを喰らってしまう。うーむ、まさかD問題で詰まってしまうとは。。

メモ化して高速化が図れるのかとか、または別の考え方が必要なのかと色々考えてみるが解法は見えずというところでどんどん時間は過ぎてしまう。ちなみにこの時点での順位は3600ぐらいであり、このD問題を落とすとレート下げがほぼ確実であり、かなりピンチである。

で、あれこれ思案した結果、単純な全探索のDFSだと同種のペアも重複して数えてそうなので、ペアを作るときは小さいほうの番号から大きい方の番号にのみ探索をかけていくやり方に限定すればよいのでは思いつく。で、この改良をしたDFSもどきのプログラムでサンプルを通してみると、数段早くなっているようなので、提出してみたらやっとACをもらう事ができました。

このＤが通せた事で順位は一気に1300台まで上昇！なんと茶パフォになりかねないところから一気に水パフォぐらいまで上げることができましたとさ。