AtCoder始めました【abc163】

こんにちは。

競技プログラミングの、AtCoderを始めました。

atcoder.jp

そういうのって、ガチ勢じゃないと歯が立たないのかと思ってたら、初心者でもできるレベルから問題があると知ったので。

今まで3回やりましたが、Cまでは解けて、Dは、言われればそうかぁって感じだけど解けない。って感じ。

提出した解答と、反省を書く

4/19(sun)のABC163（4回目）から。

atcoder.jp

昼間寝ちゃって、起きたら21:10くらいでした。ABC163は21時からなので、出遅れた！と思って開始。

今回Unratedでした。悲しい。

A

A - Circle Pond

提出

AC Submission #12120122 - AtCoder Beginner Contest 163

#include <stdio.h>
#include <math.h>
int main(){
    int R;
    scanf("%d", &R);
    printf("%lf\n", (double)R*2*M_PI);
    return 0;
}

最初IEが出ては？ってなったけど通ってた。めでたし。

B

B - Homework

提出

AC Submission #12127805 - AtCoder Beginner Contest 163

#include <stdio.h>
typedef long long LL;

int main(){
    LL N, M;
    scanf("%lld%lld", &N, &M);
    LL buf, shukudai = 0;
    for(LL i=0; i<M; i++){
        scanf("%lld", &buf);
        shukudai += buf;
    }
    LL ans = N-shukudai;
    printf("%lld\n", ans>-1 ? ans: -1);
    return 0;
}

コメントすることなし。めでたし。

C

C - management

提出

AC Submission #12131466 - AtCoder Beginner Contest 163

#include <stdio.h>

int main(){
    int N, buf;
    scanf("%d", &N);
    int A[300000] = {};
    for(int i=0; i<N-1; i++){
        scanf("%d", &buf);
        A[buf]++;
    }
    for(int i=1; i<=N; i++){
        printf("%d\n", A[i]);
    }
    return 0;
}

最初、Aを入れる配列を

int A[N+1] = {};

ってやってコンパイルしたらエラー↓

c.c:6:11: error: variable-sized object may not be initialized
    int A[N+1] = {};

が出たので（可変長配列は初期化できない）、確かに。と思って

int A[N+1];

にしたら、forループで初期化してないのにインクリメントして変になった（それはそう）ので結局デカ目に用意した。

めでたし。

D

D - Sum of Large Numbers

解説は本家を見てもらうとして、その方針はバッチリだったんですけど…………

提出

WA Submission #12142614 - AtCoder Beginner Contest 163

回答が、10⁹+7で割ったあまりを要求しているので

#define LIMIT 1000000007

として計算するたびに%LIMITをかましていたんですけど、うまくいかんかったです。（これは入力例3も通ってなかったけど一応提出したやつ）

修正

結論としては、計算は間違っていないので%LIMITをとるのを一番最後だけにしました

AC Submission #12152031 - AtCoder Beginner Contest 163

時間外ですが通過！めでたし。

反省

どうやら、mstdn.jpの人にお伺いを立てたところ、むやみに剰余をとったためバグったようです。

結局最後に剰余とるだけでいいということは、計算途中ではオーバーフローしてないんすねぇ。

今回は計算途中で出てくる可能性がある値は

1から2x10⁵の和 ≒ 2x10¹⁰ これはlong long でおさまる（このスケールがでてくる時はkがでかいので、最大値と最小値で差し引きすると"被り"が大きくて大した値にならない（下のグラフでもわかる））
ループの中で加算する値（buf = summax(k, N) - summin(k) + 1;）はNを固定してkを変えるとx>0で単調減少する

www.desmos.com