コンテスト中AC:A〜E D - Longest X E - Graph Destruction D - Longest X 連続させたい個数をm個に固定すると、S連続する部分列のうち、m個の要素を含むものについて、いずれか1つでも全てXにできれば、連続m個を達成できます。 必要な操作回数は、部分列に…

問題 Baby-step giant-stepによる解法とWeb公式解説の理解メモ 公式解説の理解 をで割って良い理由 の時に解なしになる理由 Baby-step giant-stepによる解法 公式解説の理解 公式解説 をで割って良い理由 とします。 を変形し、 とします。 はの倍数となる必…

コンテスト中AC:A,B A - Smaller XOR B - Range Point Distance A - Smaller XOR 以下、整数は2進数で表現するものとします。 N = 10101としてシミュレートしてみます。 (1) xの4ビット以降に1がある場合 例えば、x = 100000とすると、 100000 XOR 010101 = …

コンテスト中AC:A~D E問題も解いたので記載しておきます。 B - Takahashi's Secret C - Final Day D - Linear Probing E - Integer Sequence Fair B - Takahashi's Secret に有向辺がある有向グラフとみなすと、これは、 ・閉路がただ一つ存在する ・全ての…

コンテスト中AC:A,B コンテスト後に自力AC:C,D,G B - KEYENCE building C - ABC conjecture D - Project Planning G - Divisors of Binomial Coefficient B - KEYENCE building a*bの積の部分を考えると、a,bは1〜1000までの組み合わせとなり、N=20を考慮し…

注:解説は独自のものなので、誤った部分がある可能性があります。 コンテスト中はしっかりと証明はできず、実際に書いてみて法則を探しました。証明ができていないと、考慮できていないケースなどが存在する場合が多々あるので、証明できるようにしたいとこ…

コンテスト中AC:A〜E こちらの解説は独自の見解であり、間違った情報を含む場合があるのでご注意ください。 B - Counting Arrays 公式解説の方法をC++のstringで実装したところTLEしました。色々な処理が必要な場合、stringはかなり遅いようです。 第一選択…

はじめに 離散対数問題についての問題がAtCoder Beginner Contestで出題され、色々と調べてみたので、その内容をメモします。 離散対数問題 を満たす最小の整数kを求める問題です。 これを求めるアルゴリズムにBaby-step giant-stepがあります。 Baby-step G…

解説なしAC はレプユニット数という呼ばれ、その一般項はなので、この問題の一般項はです。 2や9を無視できれば、を求める問題になり、フェルマーの小定理などで解けそうという感じなので、2と9をどうにかします。 とします。 Kに2を含む場合 XがKの倍数であ…