ABC163

色々あったそうでUnratedでしたね。

可もなく不可もないペースだったのですが、Dの途中でUnratedになったので放置して寝てしまいました。というわけで、A~CとDの復習です。

All Submissions - AtCoder Beginner Contest 163

A-Circle Pond

小数点以下まで出力するので、double型で受け取って、2*3.1415をかけて出力しました。サンプルに出ていた数字をコピペしたらいいことに今気が付きました。出力する桁数の指定方法がAPG4bの数値型のところに載っています。

B-Homework

全ての宿題をするのにかかる日数を足し合わせて、夏休みの日数から引きます。もし0以下であれば-1を出力するようにします。

C-management

答えを格納する配列を作り、全探索でそれぞれが上司として何回出てくるかをカウントします。1番の人には上司がいないことに気を付ける必要があります。

D-Sum of Large Numbers

10の100乗というのは、非常に巨大な数字です。これはあまりに大きすぎるので、実質的には+0,+1,+2,.....+Nの違いで各数字を区別していると考えていいです。どういうことかというと、問題文は、K個以上の数字を選ぶとき、その輪としてあり得るものの個数を求める、となっています。つまり、K個、K+1個、…N+1個の選び方をすべて試して、異なる数字は何種類あるかを求める、ということです。このとき、選んできた数が違うと、どのような組み合わせであっても同じになることはありません。たとえば、N+1個から30個選んだときと31個選んだ時では、10の100乗が大きすぎるので同じ数になることはありません。一方、選んできた数が同じ場合は、選び方が異なっても和として出てくる数は同じ場合がありえます。例えば、3個選ぶとして3,4,5と選んだ場合と1,2,9と選んだ場合とでは、和は同じ12になります。そこで、選ぶ数を固定して考えると、K個選んだ時に作りうる和の種類は何通りになるのかを考えればいいということが分かります。それが分かればK以上N+1以下の範囲をすべて計算すればいいということになります。選ぶ数が同じ場合、和を最小にするには0から順に決まった数を、最大にするにはNから順に決まった数を取ればいいということがすぐに分かります。求められた最小値と最大値の間にある数はすべて作ることができるので、(最大値)-(最小値)+1としてやると作ることのできる和の種類が分かります。最大値と最小値は順列の和の公式を用いればO(1)で求められるので、全探索で解き切ることができます。

今回は以上です。

今日の夜にまたABCがあるので今度こそ満足のいく結果になればと思います。