エイシングプログラミングコンテスト2021（AtCoder Beginner Contest202)に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが926でした。
相変わらずD問題が解けそうで解けない。E問題は問題を見た感じだとUnion Find Treeをうまく使えばなんとかできそうな気がした。D問題が解けなくて手を出してないから実際はどうなのか知らないけど。
ABC200からレーティングが800を超えて緑に帰ってこれたけど、今のところずっと緑に居続けられてる。前回緑になったときはその次からどんどんレーティング落としてなかなかに悲惨だった。
A - Three Dice
問題文の通りに計算をして出力するだけ。いつもどおりの難易度のA問題だった。
B - 180°
これもA問題同様問題文の通りに処理をすれば良い。
結局6を9に、9を6に置き換えるのと、文字列を反転させるなり後ろから順番に表示させるなりすれば良い。
文字列の扱いに慣れていれば特に困らない難易度だと思う。
C - Made Up
求めたいものは条件を満たすの組み合わせ数だけど、制約を見ると
なので二重ループで処理しようとすると計算量が最大で
になってTLEになりそうだと予想できる。処理するならループ1重でやらないといけない。
結局、数列Aにはどの値が何個あって、はどの値が何個あるのかを数えて組み合わせ数を計算すれば良い。
具体的には
がs個あって
がt個あれば
組あることになる.。
D - aab aba baa
結局バグが取れなくて解けなかった。バグが取れなかったというよりアルゴリズムがちょっとまずいだけな気もするけど。
たぶん、先頭から順番にaかbかを決めていけばいいと思う。先頭から順番に、i文字目がaとするとi+1文字目以降の並びな何通りあるか計算して、Kと比較するとaのままで良いかaの範囲外になるからbにするかを判断してってのを繰り返していく。
問題なのは、並びが何通りあるのかを計算するのに最大で60!を計算しないといけないけどちょっと値が大きすぎるからC++だと計算ができないっぽい。
こんな時さっさとPythonで書き直して提出できれば良いのかなあ。
