atcoder.jp 解法 全探索しようとするとO(2N)になってしまうような問題はDPで解けることが多い。 なので、DPで解くことを考えてみる。 i回目の操作F, Gは次のように言い換えられる。 左端と左からi + 1番目の値を計算して、現在の左端と入れ替える ここで、i…

atcoder.jp 解法 N!の約数を順に列挙していこうとすると、N次第ではN!がとてつもなく大きい数になってしまうため、現実的ではない。 そこで、約数を素因数を組み合わせた結果と考えることにする。 具体的には、1 ~ Nまでの数をそれぞれ素因数分解し、それぞ…

atcoder.jp 解法 愚直に数列を前から順に見ていこうとすると、計算量はO(N)になり、N ≦ 1010の制約では、時間がかかりすぎてしまう。 なので、計算量を落とす方法を考える必要がある。 mod 〇〇で考えられる問題で鳩ノ巣原理が使えるというのは典型。 この問…

atcoder.jp 解法 Kの倍数かどうかがわかればよいので、 は mod Kで考えてよい。 さらに、 という数列を順に調べることをK+1回繰り返せば、鳩ノ巣原理で必ずループが始まる。 そのため、 という数列を順に調べることをK回繰り返して、その中にKの倍数があれば…

atcoder.jp 解法 偶奇にしか興味がないため、mod 2で考えてよい。 次のように場合分けして考える。 のとき と のどちらもが偶数、または奇数であることがわかる。 そのため、どちらかの偶奇が決定されると、もう片方の偶奇も自動的に判明する。 のとき と の…

atcoder.jp 解法 制約的にも桁DPがしたくなる。 そこで次のDPを考える。 dp[i][j] ← 下からi桁目までみた時、13で割った数がjであるような場合は何通りあるか 上からi桁目としてもいいが、計算が楽なので下から見ていくことにした。 次のように遷移する。 こ…

atcoder.jp 解法 問題文通り実装してもO(N2)で間に合わない。 XOR演算を繰り返すため、ビットごとに考えたくなる。 そこで位ごとに、ビットが立っているかどうかをA[i]すべてで調べ、いくつビットが立っているかを計算することにする。 A[i] ≦ 260 なので、6…

atcoder.jp 解法 最大値の最小化と聞くと二分探索が思い浮かぶ。 そこで答えで二分探索できないか考えてみることにする。 修行なしでメンバーと食べ物を最適にマッチングするには、食べ物を昇順、メンバーを降順に並び替えて同じ番号を組み合わせれば良い。 …

atcoder.jp 解法 モンスターは昇順に並び替えておく。 一番初めのモンスターに爆弾を当てるには最大で、X[0] + D * 2 までの座標で使用する必要がある。 なるべく別のモンスターに当てたいので、ギリギリ倒せる座標で使用した方がいい。 これを全てのモンス…

atcoder.jp 解法 クエリの内容的にセグメント木を使いたくなる。 セグ木には、区間の文字がそれぞれ何個ずつあるかという情報を乗せたい。 文字列に関する問題でよくあるのは、英小文字が26文字しかないことを利用するパターンだ。 この問題も利用できる。 …

適当に追加していきます。 最大値の取り方 set<int> st; st.insert(1); st.insert(2); auto mx = st.rbegin(); // 最大値へのイテレータ cout << *mx << endl; // 2 st.erase(mx); // 最大値を削除する cout << *mx << endl; // 1 multisetで一つだけ要素を消去す</int>…

atcoder.jp 解法 それぞれの鍵を買うか否かの選択をM回することになるので、愚直に全探索しようとするとO(2M)になるが、制約的に時間が足りない。 そこでDPができないかを考えてみる。 愚直解がO(2n)になってしまう時、DPを使うと無駄な計算を省いて高速化で…

atcoder.jp 解法 クエリ1とクエリ2だけだった場合、queueを使うだけで解けるのでとても簡単。 ただ、クエリ3が与えられるたびにソートしていると、全体計算量O(N2 logN)になって間に合わない。 上記のように、クエリ1とクエリ2はqueueで実現できるので、問題…

atcoder.jp 木を切る問題が出ると二分探索を思い出す。 解法 データ構造に切断点の位置を挿入しながら、二分探索をする。 二分探索をして、切断点の左端と右端がどこかを高速に調べることができる。 二分探索をするにはソートされている必要があるので、挿入…

atcoder.jp 解法 k=0の時は元の数列のまま、転倒数を求めればよい。 愚直に求めようとするとO(N2)になるが、BITを使うとO(NlogN)で求めることができる。 具体的には、下の記事がわかりやすい。 scrapbox.io あとはk=1~N-1の時を考えればよいが、k=iからk=i+1…

atcoder.jp 解法 テレポートが使えなければ、BFSするだけで解ける。 テレポートを無制限に使用できるとすると大量の辺が追加されることになって、時間内に探索を完了するのが難しくなる。 そこで、同じ文字のテレポートは１回しか使用できないという制限を加…

atcoder.jp 解法 全探索しようとするとO(2N)になり、制約が N ≦ 40 なのでこれでは間に合わない。 そこで、半分全列挙というテクニック使ってO(2N/2)で解くことを考える。 N個の問題を2つのグループに分けて、それぞれのグループごとに問題の選び方を全探索…