おはようございます。しほみんです。
ABC164の復習します。D問題が自分としては結構難しかったのですが、解説見たらもう何ともなさ過ぎてちょっと辛いです。やっぱD問題が解けないことが問題ですねえ...。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスを安定的に1000以上とる。
今回は、ABCの3完、15分、1WAですね。最近、ABC問題が非常に単純なため、遅いとレートが上がらないです。D問題がきちんと解けないと、ダメだと思いましたね。今回はパフォーマンス536で、パフォーマンスも800→776でまた緑に戻りました。
D問題までちゃんと解けたので今日はDまで振り返ります。思いつかないなあ....
ここから解説です。
A問題
羊がS匹、狼がW匹います。
狼は羊以上の匹数以上いるとおそいます。
羊が食べられられるときはunsafe、食べられないときはsafeを出力せよ
まあ、S > Wであれば食べられないので、safe、それ以外はunsafeを出力します。
（構成例）
if( S >W)
Console.WriteLine("safe");
else
Console.WriteLine("unsafe");
B問題
高橋君モンスターは体力A,攻撃力Bです。
青木君モンスターは体力C,攻撃力Dです。
高橋君、青木君の順でモンスターは攻撃します。
どっちかが先に0になったらその方が負けです。
高橋君が勝つならYes、青木君が勝つならNoで答えよ。
これも素直に攻撃を繰り返して実行してみましょう。そして、どちらかが0になった時点でその結果を出力しましょう。
解くに値も残す必要がないので直接ひいちゃってよい気がします。
やり方としては
1. CからBを引く。
2. Cが0以下ならYesを出力して終了
3. AからDを引く。
4. Aが0以下ならNoを出力して終了
構成例のように無限ループで終わったときにreturnで終了するのが一番すんなりしてますね。
（構成例）
while(true)
C -=B;
if(C <= 0)
Conosole.WriteLine("Yes");
return;
A -= D;
if(A <= 0)
Conosole.WriteLine("No");
return;
C問題
N回くじ引きをして、それぞれSiという景品を手に入れました。
何種類の景品を手に入れましたか？
まあ、普通にここでDictionary型で数えたりとかしてると時間オーバーします。（これで1WAやらかした）
同じ文字列が入ってしまうとカウントを減らさないとなりません。ということは同じ文字列があるときだけ数えなければよいのです。
具体的には、文字列を全部入れてみて、ソートします。
すると、同じ文字列があると、それぞれ並ぶので前後を比較するだけで済みます。
例えば、
apple,orange,orange,appleと順に出たら、ソートすると、
apple,apple.orange,orangeになります。
ということで、頭からひとつ前を比較して、違う文字列のところだけcountを足せばよいです。
最初は、あらかじめ1つはあるので、count = 1として、違うものが出たら足すとコードが単純になります。
（構成例）
int count = 1;
array (ここにあらかじめ文字列を入れておく）
for(int i = 1;i < n;i++)
if(array[i] != array[i -1])
count++;
Console.WriteLine(count);
D問題
文字列Sがあります。この部分列を10進法にしたとき2019の倍数になるのは何通りありますか？
今回の難敵ですね....あんまりうまく見つけられずに苦しんでいました。桁DPとか考えてましたが普通に無理じゃない？と思って書いたらTLEでした。
ここでもっと考察をしないとならないなと思いました。
ここで、各桁について素直に考えます。
Sは、S.Length桁です。そして、i桁目までの数を考えます。
このときのmod2019を考えます。これをTiとします。
このとき、i桁とj桁を考えます。
iとj桁のmode2019が一致するとき、これは割り切れるので組に入ります。
例えば、1817181711224を考えます。
これは、(i, j) = (1,5)(5,9)(9,13)桁目までを選択すると答えが出ます。
例えば、5 - 13桁目までは181711224は2019で割るとあまりが1224です。
そして、10 -13桁でだと、1224は2019で割るとあまりが1224です。
よって、この二つを引いた181710000は割り切れます。
二つのあまりが一致するからです。
つまり、Ti（i = 0 - s.Length)を、下i桁分の数を考えたときのmod2019とすると、
Ti = Tjのときが求めるiとjになります。
よって、それぞれの桁についてTiを求めて、あらかじめ、0-2018までで格納して入れておきます。このTiを求めるときなのですが、もう一歩工夫が必要です。
ただし、T0は便宜上0にして入れます。（こうすることで都合よく計算できます）
Ti+1からTiを求めるときはTi+1 = Ti +（（10の i 乗）*（i桁目の数））mod 2019で漸化式を立てます。
ここで、追加する項目は繰り返し二乗法で解けます。
あとはそれぞれ0-2018で入っている数をNとすると、N*(N-1)/2通りになるのでそれで出力します。
これを実装していくだけです。って言われても厳しいよなあって感じです。桁DPとmodをとても理解してないとなかなか手が出ないなあって感じです。
ここで必要な知識は
・桁DP
・MODを考慮した繰り返し二乗法
・メモ化（あまり0-2018に該当するものは保存）
です。
詳しくはコードを見てください。
最後に....
こういう難しいD問題まで解けないと緑にはなれないので、ちゃんと見直したいなあと思います。もっと頑張らないとなあ....
ではでは。
