はるのぶろぐ。

情報系大学生ハルが、ゆるゆるとIT関係についてや日々の雑記を綴ります。ちょっとだけ、あなたの役に立てる、そんなブログを目指しています。

【AtCoder】超初心者のためのモノグサプログラミングコンテスト2022C問題の解説【C言語】【ABC238】

参加してます!ポチッとお願いします

記事名と
URLをコピー

こんにちは、情報系大学生のハル(Blog_IT_haru)です。

引用した公式の解説にも書かれていますが、C言語での今回のC問題、むずすぎるっぽいです。

Pythonなどの多倍長整数が使える言語を使うか、C++ACLに入っているmodintなどを使うと実装が容易です。

引用:Editorial - Monoxer Programming Contest 2022(AtCoder Beginner Contest 238)

私は、自力では解けませんでした。

おそらく、オーバーフローとかが原因だと思います。

なので、ACを取れているコードを参考に復習し、考え方などを理解した上で、必要な知識などを書きました。

ちなみに、A問題とB問題の記事も書いているのでぜひ。

【AtCoder】超初心者のためのモノグサプログラミングコンテスト2022A問題の解説 - ハルの初心者プログラミング部

【AtCoder】超初心者のためのモノグサプログラミングコンテスト2022B問題の解説 - ハルの初心者プログラミング部

f:id:Blog_IT:20220207184108p:plain

問題

C問題

f(x)はx以下であり、xと桁数が等しいという条件を満たす正の整数の個数とする。

このとき,整数 N が与えられるので、f(1)+f(2)+⋯+f(N) を求める。

入力:N

制約:1≤N<1018

正解率

灰コーダー、茶コーダーの正解率、Twitterや解説を見ていても、難しい問題だったと伺えます。

灰コーダー正解率:15.9 %

茶コーダー正解率:59.3 %

緑コーダー正解率:80.6 %

引用:【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する! - Qiita

解き方・コード

提出 #29108224 のコードを参考にしました。↓

Submission #29108224 - Monoxer Programming Contest 2022(AtCoder Beginner Contest 238)

また、A,Bは考え方の解説もやってたんですが、今回は難しいので、公式のYouTubeを参照いただければと思います。

ただ、コメントアウトを見てくれれば、ある程度は何をしているのか分かると思います。

考え方

  1. 桁の数字ごとに分けて考える。
  2. それぞれの桁数ごとで考えると、その和は等差数列になるのでその総和が答え

引用:AtCoder Beginner Contest 238(ABC238) - 接着剤の精進日記

コード

#include <stdio.h>
#define MOD    998244353
int main() {
    /*nは読み取る数*/
    long long N;
    /*pは、その桁の最初の数1,10,100というふうに増えていく*/
    long long p;
    /*答え*/
    int ans;
    /*nを読み取る*/
    scanf("%lld", &N);
    /*pとansの初期化*/
    p = 1;
    ans = 0;
    /*答えを求める*/
    long long X,Y;
    while (1)
        if (p > N/10) {
            /*pが9じゃないとき*/
            X=(N-p+1)%MOD;
            /*nまでを足している*/
            /*公式YouTubeの考え方*/
            ans = (ans + X * (X + 1) / 2) % MOD;
            break;
        } else {
            /*下一桁が9までを足している*/
            Y = (p * 9) % MOD;
            ans = (ans + Y * (Y + 1) / 2) % MOD;
            p *= 10;
        }
    printf("%d\n", ans);
    return 0;
}

解説が書かれているサイト

AtCoder公式のページにある、ユーザによる解説のサイト

AtCoder Beginner Contest 238 C問題 digitnum - Kazun の競プロ記録

AtCoder公式の解説

Editorial - Monoxer Programming Contest 2022(AtCoder Beginner Contest 238)

Editorial - Monoxer Programming Contest 2022(AtCoder Beginner Contest 238)

公式のYouTube

31:24からC問題の解説です。

www.youtube.com

必要な知識

Modの考え方

余りを求める問題かつ、オーバーフローの恐れがあるほど、大きい数字を扱うので、Modの考え方が必要です。

↓を参照すると良いと思います。

合同式(mod)の意味とよく使う6つの性質 | 高校数学の美しい物語

等差数列の考え方

等差数列の和の考え方が必要です。

↓を参照すると良いと思います。

等差数列の和の公式の例題と証明など | 高校数学の美しい物語

他、C言語の一般的な使い方が必要です。

ざっと、今回新たなものは、下のような感じです。

  • while→for文と似たような感じだけど、終了条件をwhileの中に書けるので、今回はwhileを使用しています。
  • long long→intより大きい値もOKなものです。今回は、オーバーフローするほど大きい値を使っているので、intだとだめです。
  • %→余りを求める演算子のひとつです。

↓以下の記事でその他必要なものは解説しています。

blog-it.hatenablog.com

blog-it.hatenablog.com

まとめ

いかがでしたか?

超初心者の灰色コーダーには、すごい難しかったです。

特にシグマなんて高校ぶりだし…笑

C言語自体も初心者には難しいかもしれませんね。

\ほんとの初心者の方は、本で学ぶのもおすすめ!/

以下の記事でおすすめ本紹介しています!

blog-it.hatenablog.com

この記事がいいな、と思ってくれたら、SNSなどで拡散したり、

ブックマークやコメントなどしてくれると励みになります!

下の方とサイドバーにある、サポートもお待ちしています!

更に、読者になってくれたら、お返しに私も読者になります!

また、この記事の内容についてなにかありましたら、

お問い合わせ、コメント、TwitterのDMなどによろしくお願いします。

それでは。