競プロという名の光
最近溶けそうなほど暑いですね。こんばんは。
そんな中、最近競プロ（AtCoder）始めてみました。いつまでやるかは未定です。
そこで、AtCoder始めたぜ記念カキコと、昨日解けなかったB問題の解説をしようと思います。
競プロ始めてみた件
理由
何かコンペをしたい！という欲求が湧いてきたため。
今までだったらkaggleをやっていたのだけど、
・基本チーム戦
・結果出るのが数か月と長い
・潤沢なリソースがない
という理由から、ちょっと最近出るのがおっくうになっていました。
そこで、2時間くらいで終わるし、なんかプログラミング出来たらカッケーな！
と思い、参加しました。
あ、C++の練習にもなるかな、という理由もありました。
なぜC++の練習をしたかったかというと、かっこよいからです。
大変なところ
まず、ABCという初心者歓迎コンテストに出場する時間を確保するところが大変。
毎週土曜日の21時スタートなのですが、基本土曜日というのは飲み会が入ります。
そのため、飲み会はすべて金曜日に実施するか、早く切り上げて酔ったまま参加することになります。
これは、学生の頃やっておきたかった。それか、土曜の朝にやってくれないかな。
あとは、比較的ハードルは低いかなと思います。
C++のデバッグ環境も、ググればいろいろヒットします。これとか参考にしました。
【VScode＋WSLで始める】競プロ用C++デバッグ環境構築 - Qiita
（私は、このやり方だとincludeパスをうまく読み込めなかったので、Remote – WSLを使う方法に一部修正しました）
ただ、これはまだ私は来ていないですが、モチベ管理が大変なのだろうなと思います。
最初の色の茶色であっても、10回程度コンテストに出ないとなれないそうです。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiita
今までの戦歴
ABC 256 : ABC
ARC 142 : nothing
ABC 257 : A
ARC 143 : A
という、輝かしい成績です。
どのコンテストも、最後解けなかった問題は、解法は思いついているんだけどもプログラミング的にアウトという感じでした。
例えばABC 256は、繰り返す試行の途中の状態の持ち方を複雑にしてエラーが起きて通らなかったり、
例えばARC 142は、long longの型で扱えばよかったものintやらdoubleやらでずっとこねくり回していたり…
まぁ、このあたりは経験積んでいくしかないですかね。
とりあえずは、茶色を目指して基本的な問題を取っていく方針です。
ということで、今回は昨日のB問題を解説しようと思います。（これも、プログラミング的に知っておくべきことがあったので）
ARC143 B問題の解説
問題
N×Nのマス目の各マスに1からN^2までの整数を1つずつ書き込む方法であって、どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を998244353で割ったあまりを求めてください。
・そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する。
・そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する。制約：1 <= N <= 500
このような問題でした。
まず最初に見たとき、998244353ってなんや…暗号か？と思いました。
解答方針
[ARC143] B - Counting Grids｜syamashi｜note
この方の考え方が分かりやすいです。
軽くまとめると、問題文の中の「少なくとも一方を満たすようなものの個数」というのを直接数え上げるのは面倒（or条件だから）なので、余事象を考えます。
そうすることで、問題文の2つの条件のand条件の個数を求めて、全通り（N^2の階乗）から引けば答えが出ます。
この方針は何となくコンテスト中にできていたんですが、、途中の数が大きすぎてlong longでも収まらなくなりました。さぁ大変。
そこで、今後も覚えておくべきポイントとして、2つをここに書き記します。
知っとこポイント①：modの世界
1つ目は、modの計算についてです。
mod自体は私も知っていました。何かで割った時のあまりですよね。
11 ≡ 3 (mod 4)
です。11÷4をしたとき、余りは3なので。
ただ、桁数が大きすぎるものを扱うときに、modを使うのがプログラミングの世界では常識らしいです。
イメージとしては、10^10と10^11をかけると、10^21ですよね。
AtCoderにおいて、最強の型であるlong long型ですが、これでも10^19くらいまでしか扱えません。つまり、上の計算式は普通にやるとオーバーフローします。
ではどうするか。
10^10と10^11を掛け合わせる前に、それぞれmod 998244353 を取ります。
10^10 ≡ 17,556,470 (mod 998244353)
10^11 ≡ 175,564,700 (mod 998244353)
そして、それらを掛け算して、さらにmod 998244353を取ります。
17,556,470 × 175,564,700 = 3,082,296,388,609,000 ※ この数は非常に大きいですが、10^15オーダーなのでlong longに格納可能です。
3,082,296,388,609,000 ≡ 329,696,899 (mod 998244353)
そうして出てきた329,696,899という数字、これは何と 10^21のmod 998244353を取った数と等しいのです！！
つまり、mod 998244353を最後にどうせ求めるなら、途中の式もmod 998244353を取っておくとオーバーフローせずに計算できちゃうということです。
今は掛け算でやりましたが、足し算と掛け算はそのまま途中をmodとっても結果が変わりません。
ただ、引き算と割り算（特に割り算）はちょっと注意が必要です。
そのあたりの細かいことは、この記事がめちゃくちゃ参考になりました。この記事ではmodを別の数で取ってますが、考え方は一緒です。
コンテスト中、「998244353」でググったらフーリエ変換とか出てきて泣きそうでしたが、この記事で救われました。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
覚えること
10^19を超えるような数を扱うときは、modを使って計算しちゃおう！
知っとこポイント②：順列、階乗の計算
さて、こっちはどちらかというと実装ではまった点。
この問題を解くとき、順列や階乗の計算をします。
階乗は、5! = 5*4*3*2*1 などすべて掛け算だけで表せますね。
ただ、順列は公式通り考えると、n P r = n! / (n-r)! となります。そのため、実装で割り算を使います。
以下の記事がその実装を解説しています。
【基本C++】順列のプログラム - Qiita
これを使ってしまうと、ポイント①で触れたようにmodを考える上で注意が必要な割り算が出てきてしまいます。
その場合、ポイント①で参考に挙げた記事内に実装がありますが、さらにforループを回す必要が出てきてしまいます。
そのため、コードは複雑になり（順列のメソッドの中に、modの割り算をするような処理を加える）、forループが追加で入るので計算量も増えます。
ということで、順列の実装はこちらの方法を代わりに使いました。
こちらは、割り算ではなく、forループを後ろから考えることで掛け算だけで済ましています。
確かに、例えば7P3なら7*6*5で後ろから掛け算していけば終わりですよね。
【C++】順列を求めるプログラム - Qiita
覚えること
順列の計算は、掛け算だけで行おう！
自分の回答
私は前者の方法で最初実装していて、TLE（制限時間の2秒以内に計算が終わらない）になってしまいました。
ただ、後者の方法に変えたら、AC（すべてOK）になりました。
ACしたコードを載せておきます。自分用ですが、コメントとかもきれいにつけてみました。
ただ、おそらく競プロerの常識とは違う書き方になっているはず。
Submission #32801198 - AtCoder Regular Contest 143
・こう書いた方がより良いよ
・計算量のオーダーがこれからこれに変わったからTLEがACになったんだよ
というコメント、あれば非常にうれしいです。お待ちしております。
おわりに
ちょっと散文チックな記事になってしまいました。
昨日の復習をしていて、modで計算することに少し感動したので、こうして記事にしてみました。
こういうの、情報系の人なら大学で学ぶんだろうか。
kaggleもそうだったけど、全くの初心者から中級者になるとき、誰かコーチしてくれる人がいると効率が段違いだなぁ、とひしひしと感じております。
ただ、AtCoderは書籍とかブログも充実してるので、kaggleよりはやりやすそう。
とりあえず飽きるまでは、頑張っていきます。
