AtCoder Beginner Contest 029
これまた続けてだいぶ楽な問題だなぁ。
結果
18:59 13位相当
開始時刻 2017/08/15 14:13:00 提出履歴
A: 複数形 - AtCoder Beginner Contest 029 | AtCoder
0:26(AC)
S + “s"を出力して終わり。
B: カキ - AtCoder Beginner Contest 029 | AtCoder
1:56(CE)→7:14(AC)
順当に実装すれば終わり。
C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder
6:39(AC)
深さ優先探索でどんどん出力していけば終わり。
D: 1 - AtCoder Beginner Contest 029 | AtCoder
18:59(AC)
各位について1の数を数えて、足し算すれば答えが出る。
例えば10の位では、0が10個、1が10個、2が10個…9が10個という計100個の周期で数字が現れる。より一般的に言えば、10nの位では、各数字が10n回、計10n+1回の周期である。
次に、10nの位について、何回1が出るかを考える。0からNまでで、周期はN/(10n+1)回あり、そのうち1は10n回出てくる。それに加えて、周期外であっても、下限を0、上限を10n回として1が出現する可能性がある。1が出現するのは、10n番目から2*10n-1番目まで。いい感じに調整してこれも加える。これを各桁に対して行い、全ての総和が答え。
感想
続けて楽な問題が来ると、次は難しいんじゃないかと怖くなるね。