nc = [n/c-1,0].max*c. N を LCM(A,B) と半端に分けて考える代わりに、LCM(A,B)１回分と半端をその他として取り分けて考える。正直よくわかりません。一晩経ってひらめいて試したら AC だっただけ。■■■@kyopro_friends「1 以上 N 以下の整数のうち、2 以上 M 以下の数を約数に持たないものの個数を求めて下さい。[制約] ＊1≦N≦10^{16} ＊1≦M≦20 ＊入力はすべて整数」 DP と包除原理でサンプルの２までは答えが合った>解答。M≦72 のサンプル３は TLE になる。むむむ。関連するマシュマロ質問に「素数の積」とあったので素数だけを取り出してみたらサンプルの３も合ったっぽい(先頭と末尾の数桁の一致を確認)>解答２。まだまだだなあ。■@2023-01-26 今日のお風呂での話。20230124 に中国剰余定理で解いた ABC286-F「Guess The Number 2」の反芻をしているときに、kyopro_friends さんの即興問題とのあいだの共通点に考えが広がって、もてあそんでいるときに「この問題なら、最初から割り算で計算すればオーバーフローのことを気にする必要はないけどねー」の意味がひらめいた。自分の解答２でいうと最後から２行目に N/c という式があって、c というのが素数の積。C++ のように整数型のビット長が固定の言語では c がオーバーフローするおそれが現実的な範囲にある。ここで、割る数(c)を大きくする代わりに割られる数(N)を小さくしていくのも同様にありだなーと、あのツイートはこういう意味だったのかと、一日遅れで頭に血が巡ってきたという話。これがファイナルアンサー>解答３。割る数(a)は M 以下だし割られる数(n)は N 以下。入力を超える数がないからオーバーフローもない。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 にできた。今日の収穫は、中国剰余定理の答えを愚直に求めても許されるとわかったこと。小さい方の法の大きさを上限とするステップで答えが見つかる。これからは中国剰余定理わかりませんであきらめなくて良さそう。S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。」 折りたたまれた用語の説明を読んでいなかった。今回の「部分文字列」は連続部分文字列と呼ばれることもあるものだった。やつあたりに聞こえるだろうけど、知らない人のための用語解説なら折りたたむのも結構だけど、問題の一部としての定義なら隠してはいけないと思う。必ずクリックして開かなければいけないなら(それなしでは問題文が曖昧になるのなら)隠す目的はなんだ。■F 問題。提出 #38104204 (AC / 1984 Byte / 634 ms)。ソースを見るに余裕のなさが窺える。「脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい」。日本語をクラス名にするために Class オブジェクトを明示的に new しているとはずいぶんな余裕のなさ(※日本語は小文字扱いなので(=定数ではないので) class 構文が使えなかった)。間に合うみたいだったのでセグメント木はやめて転倒位置をソート済み配列で管理する当初の方式に BIT 26 本の利用を付け加えた。これを時間内に解くのは無理だよ、量的にも。青 diff でした。青 diff ならもう射程に入ってないといけないんだよなあ。■経緯を忘れてあらためて考えると、転倒位置の管理に BIT を使わない理由がないなあ>提出 #38325205 (AC / 1645 Byte / 593 ms)。BIT 27 本。
見えないことは存在しないことではない」■これはまったくその通りで、周囲を見回して人がいないことを確認する、車が来ていないことを確認するというときに、いる・いないの二値ではなく、いる・いない・陰になっていて確認できていないの三値で景色を塗り分けないといけない。いるの否定(=いることが確認できなかった)がいないではないことを認めなければいけない。しかし、すべての免許保持者が NULL を正しく取り扱えるとあなたは信じられますか。私には無理です。
a*Mb-b*Ma という式を複数の速い提出で見かけた。比例式のような外積のような？ 実行前のオーバーヘッドが Ruby 2.7 より小さい Ruby 2.3 であることを差し引いても 12 ms や 27 ms は速いのでは。■提出 #37756578 (AC / 416 Byte / 60 ms)。テキトーにさっきの式をパクってみたらそれでも AC になった。式の意味がわからない。じゃあ最初の提出では何をやっていたかというと、a と b のペアから MA 対 MB の比率ですでに完成した物質 C を取り除いたときに a と b がそれぞれどれだけ過剰かを１つの値にエンコードして DP のキーにしていた。そのキーを例の謎の式にすると a と b の値をデコードする必要がなくなってエンコードした値そのもので演算ができるらしい。謎。