AtCoder Beginner Contest 084
AtCoderを初めて4ヶ月
んーー...やっぱりTwitterのFFは強いですね...
負けずにがんばります
まだ舞える
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の解法は一発で思いつきたかった...精進しましょ