こんにちは、情報系大学生のハル（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(x)はx以下であり、xと桁数が等しいという条件を満たす正の整数の個数とする。
このとき,整数 N が与えられるので、f(1)+f(2)+⋯+f(N) を求める。
入力：N
制約：1≤N<1018
正解率
灰コーダー、茶コーダーの正解率、Twitterや解説を見ていても、難しい問題だったと伺えます。
灰コーダー正解率：15.9 %
茶コーダー正解率：59.3 %
緑コーダー正解率：80.6 %
解き方・コード
提出 #29108224 のコードを参考にしました。↓
Submission #29108224 - Monoxer Programming Contest 2022（AtCoder Beginner Contest 238）
また、A,Bは考え方の解説もやってたんですが、今回は難しいので、公式のYouTubeを参照いただければと思います。
ただ、コメントアウトを見てくれれば、ある程度は何をしているのか分かると思います。
考え方
- 桁の数字ごとに分けて考える。
- それぞれの桁数ごとで考えると、その和は等差数列になるのでその総和が答え
コード
#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問題の解説です。
必要な知識
Modの考え方
余りを求める問題かつ、オーバーフローの恐れがあるほど、大きい数字を扱うので、Modの考え方が必要です。
↓を参照すると良いと思います。
合同式(mod)の意味とよく使う６つの性質 | 高校数学の美しい物語
等差数列の考え方
等差数列の和の考え方が必要です。
↓を参照すると良いと思います。
等差数列の和の公式の例題と証明など | 高校数学の美しい物語
他、C言語の一般的な使い方が必要です。
ざっと、今回新たなものは、下のような感じです。
- while→for文と似たような感じだけど、終了条件をwhileの中に書けるので、今回はwhileを使用しています。
- long long→intより大きい値もOKなものです。今回は、オーバーフローするほど大きい値を使っているので、intだとだめです。
- %→余りを求める演算子のひとつです。
↓以下の記事でその他必要なものは解説しています。
まとめ
いかがでしたか？
超初心者の灰色コーダーには、すごい難しかったです。
特にシグマなんて高校ぶりだし…笑
C言語自体も初心者には難しいかもしれませんね。
＼ほんとの初心者の方は、本で学ぶのもおすすめ！／
以下の記事でおすすめ本紹介しています！
この記事がいいな、と思ってくれたら、SNSなどで拡散したり、
ブックマークやコメントなどしてくれると励みになります！
下の方とサイドバーにある、サポートもお待ちしています！
更に、読者になってくれたら、お返しに私も読者になります！
また、この記事の内容についてなにかありましたら、
お問い合わせ、コメント、TwitterのDMなどによろしくお願いします。
それでは。
