競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。火木土日に更新予定です。お金について考えています。

競技プログラミング~ABC164~

おはようございます。しほみんです。

 

ABC164の復習します。D問題が自分としては結構難しかったのですが、解説見たらもう何ともなさ過ぎてちょっと辛いです。やっぱD問題が解けないことが問題ですねえ...。

 

atcoder.jp

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは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問題まで解けないと緑にはなれないので、ちゃんと見直したいなあと思います。もっと頑張らないとなあ....

 

 

 

ではでは。