脳log[20230121]

2023年01月21日 (土) [AtCoder] 今日はウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)があった。終了後に読んだけど F 問題「Guess The Number 2」は中国剰余定理の香りがします。今日の精進はありません。自分のすべての提出。９時半から１時間以上 E 問題「Souvenir」(スーヴェニール？ フランス語っぽい？ 意味は調べなかった。そんな暇はないねん)のバグ取りに費やしていて終了 30 秒前にようやっと５完を確保した。何も難しいところはなかった。ワーシャルフロイド法をやるだけ。それなのに距離におみやげの価値をエンコードする部分で一生バグらせていた。センスないよ。■F 問題の制約を緩めて(あるいは厳しくして) N の全探索で解く方法を考えてたんだけど、えっと、ある周期で循環するグループをいくつか作りたかったんだけど、k 回目で f^k(i) = i になった瞬間に変化が止まるよね。循環させられなくない？■@2023-01-24 １回１回 A 数列を置き換えるとは書いてないのかな。うっかり者の役に立つサンプルをくれ。■N を探索する愚直解法と中国剰余定理を愚直に解く解法ができた。でも P = 2,3,5,7,11,13,17,23,29 としたとして P.sum = 110、P.inject(:*) = 340510170 なんだけど、N の上限が 10^9 だから 10**9/340510170 = 2.93 ということで確率３割の当てもんになる。え、どうするの？ 何回でも提出する？ 法に合成数を使うことで何か変わる？ なんでそんな意地悪するの？■提出 #38300369 (AC / 904 Byte / 78 ms)。29 を除いて 2 と 3 を 4 と 9 に置き換えることで P.sum = 108、P.inject(:*) = 1338557220 > 10**9 にできた。今日の収穫は、中国剰余定理の答えを愚直に求めても許されるとわかったこと。小さい方の法の大きさを上限とするステップで答えが見つかる。これからは中国剰余定理わかりませんであきらめなくて良さそう。