脳log[20250603]

2025年06月03日 (火) [AtCoder] 精進。ABC096-D「Five, Five Everywhere」(水 diff)。提出 #66415672 (AC / 85 Byte / 212 ms)。サンプル以外のケースが２つしかないのね。N=55 とあとはなんだろう(N=5 はサンプルにある)。解答のマジックナンバーも５だった。タイトルに偽りなし。解けてみたらこれ以外にないという感じだけど、解けない。この問題は何度も埋め損ねて残っている問題のひとつだった。N が小さいし候補となる素数の数も知れてるし、実際に組み合わせてみてフィルタするうまい方法がないかを最初は考えた。でも 50 の 5 乗に近い組み合わせは考えられない。その次に、特定の余りの組み合わせが特定の余りに限定されるということがあるなと思って、２とか３とか４の余りについて考えていた。２の余りによる分類は偶数奇数ということでほぼ意味がない。２以外の素数はすべて奇数なので。問題が５個の組み合わせでなく偶数個の組み合わせだったら、奇数を組み合わせてできあがる数は２より大きい偶数(≠素数)だということで簡単だった。次に３の余りを考えたけど、ポンコツだったのは、３で割って１余る数は必ずしも偶数ではないんですよ。３の倍数も奇数に限らない。それが偶数だ奇数だと勘違いして無駄に時間を使った。次に４。４で割った余りによる分類は偶奇偶奇と分かれるので、それで３で割った余りを勘違いしたんだろうなあ。４で割る理由は奇数の素数を２派に分けられるから。でも分けて嬉しいことはなかった。次が……。