脳log[20220807]

2022年08月07日 (日) [AtCoder] 精進１。第５回PAST-K「的あて」。期待値がさっぱりすぎて公式解説の行間を埋めることさえできず、こちらのユーザー解説のお世話になりました。■提出 #33868500 (AC)。この問題に取り組んだのは今回が初めてではなく、今日の提出の９割はすでに書いてあった。的を一直線に並べて添字を１次元に変換したところでバグらせてそのままだった。１行目の右端と２行目の左端が隣り合っているかのような処理をしていたのがバグの原因。馬鹿が横着するから……。■■■精進２。本命はこちら先週あった LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）-E「Sugoroku 3」(ぎりぎり青 diff)。期待値がわからんすぎて「E問題は自己ループのある期待値の問題なのだ！　EDPC Jと同じようにして自己ループを無視すれば、累積和を使って解けるのだ！」とヒントをもらってもさっぱりだったので先に「的あて」を解説付きで解いたのだった。■提出 #33870546 (AC / 362 Byte / 206 ms)。答えを出す流れは「的当て」と同じ。最初は有理数(Rational)で答えを出したけど、遅すぎるかもしれず、Ruby でなければそんな便利クラスはないかもしれず、分子と分母を分けて書き直して提出した。■累積和の通分をどうするんだ、と思って最初に Rational を使ったんだけど、Ruby でこの問題１番目の提出である #33836504 にそれっぽい処理は見当たらない。９行目で普通に引き算してる。分母のモジュラ逆数を掛けた結果は小数で割り算した結果と同じような扱いをして構わないってこと？(もちろん法が共通する限りにおいて)■提出 #33871015 (AC / 265 ms)。うん、そうみたい。逆元の計算が余りをとる計算より高コストだから若干遅くなるけど、通分は必要なかった。mod の世界がわかっていないということがわかってしまったね。■この問題は以前「解答の提出フォーマットがすでに謎なんだけども」と書いていたのと同じ提出フォーマットなんだけど、これってたぶん(たぶん！)割り算があるときの mod をどう計算するかという定義が書いてあるのだと思うんだよね。だから「Q/R を mod P で答える」という理解でいいと思う。読んでもそうとは理解できないけど、それ以外にないでしょ、というのはわかる。そして計算方法はこのときから知ってる>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった」。