AtCoder Beginner Contest 084

AtCoderを初めて4ヶ月

んーー...やっぱりTwitterのFFは強いですね...

負けずにがんばります

f:id:Kutimoti:20171230234219p:plain

まだ舞える

A - New Year

48という数字がぱっと出てくれるようになりたい

B - Postal Code

C#ならstring.Splitがあるので、簡単に書けるのですが...C++無いので、

string S; cin >> S;

S[A]がハイフン、 それ以外がハイフン以外とすればOK

C - Special Trains

いろんな要素がごちゃごちゃしてわかりにくかったけど、整理すれば簡単

結局すべきなのは、次に乗れる時間

次に乗れる時間は

開通式の時間、または、次に来る電車

次に来る電車の時間は今の時間をnowとすると

next = now以上のF[i]の倍数のうち最小のもの

となる

つまりその駅で乗った時の時間は

max(S[i], next)

これで回せばおk

D - 2017-like Number

最初愚直にしたらTLE頂いたので、なんとかしないとなぁというところでしたが

まず、素数かどうかの判定ですが

個人的にエラトステネスのふるいが書きやすいと思います

FOR(n,2,100000)
{
    if(prime[n] == 0)
    {
        prime[n] = 1;
        for(int i = n + n;i <= 100000;i+=n)
        {
             prime[i] = -1;
        }
    }
}

直感的で普通に早い

あとは数のカウントですが、 lからrまでの2017に似た数の個数は

1からrまでの個数 - 1からlまでの個数 + (lが素数なら 1 そうでなければ 0)

1からnまでの個数は簡単に数え上げられますね

for(int i = 3;i <= 100000;i++)
    {
        memo[i] = memo[i - 1];
        if(i % 2 == 1 && prime[i] == 1 && prime[(i + 1) / 2] == 1) memo[i]++;
    }

これでAC

感想

Dの解法は一発で思いつきたかった...精進しましょ