AtCoder Beginner Contest
atcoder.jp ゲーム系の問題でDPをするときはメモ化再帰の方が書きやすい気がする。 解法 $ S_i $か0かの選択をする際に、その選択をした結果7の倍数を作れるor作れないことが分かれば、常に最適な行動を取れる。 ということで、前の桁から$ S_i $か0かの選択…
atcoder.jp 公式解説とは違う方法らしい。 解法 この問題は、頂点 $ U_i $の子要素で根からの距離が $ D_i $である頂点はいくつか、というクエリに回答せよ、と言い換えられる。 複数のクエリに回答する問題 複数のクエリに回答する問題は、次のような解法パ…
atcoder.jp 解法 T - 0.5分後というのは、T-1分後と言い換えることができる。 T-1秒をこえて、料理を食べることができない場合、ただのナップザックDPで解くことができる。 具体的にDPの定義は次のようになる。 dp[i][j] ← i番目の料理まで食べるかどうか決…
atcoder.jp 解法 次のように定義する。 操作1、N が K で割り切れるとき、N を N/K に置き換える 操作2、そうでないとき、N を N−K に置き換える 場合分けして考える。 操作2だけでNを1にできるような数 これは、N-1の1以外の約数すべてが該当する。 理由 m…
atcoder.jp 解法 島をノード、橋を辺とするグラフを考える。 グラフの辺を削除するというのを、高速なアルゴリズムで実装するというのは難しい。 そのため、辺の削除をUnionFind-Treeなどを使って辺をつなげていくことで同じことを表現できないかを考えるこ…
atcoder.jp 解法 3つの条件を上から順に条件1、条件2、条件3と呼ぶことにする。 3つ目の条件が存在しない場合、次のDPで解くことができる。 dp[i][j][k] ← 長さiでi-1文字目がj、i文字目がkであるような条件1,2を満たす文字列はいくつあるか 遷移をする際に…
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文字しかないことを利用するパターンだ。 この問題も利用できる。 …
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つのグループに分けて、それぞれのグループごとに問題の選び方を全探索…
atcoder.jp 解法 操作を逆順にして、Nから順に減らしていくことを考える。 魔法A: 箱の中からボールを1つ減らす 魔法B: 箱の中のボールを1/2にする という操作に置き換えられる。 Nが奇数のときは魔法Aを使えば必ずNは偶数になるため、次に魔法Bを使うことが…
atcoder.jp 解法 愚直に解こうとするとO(2N)で絶対間に合わない。 Aはmax、Bは総和が条件として示されているため、A[i] ≦ 5000という制約が気になる。 この制約があることで、Bの和が5000より大きい数になるような集合は考えなくて良いことになる。 Bの要素…
atcoder.jp 解法 二次元グリッドの問題はHとWの制約が同じことが多いが、この問題はHだけが何故かとても小さい。 あからさまに怪しいのでHの小ささを利用したくなる。 そこで、bit全探索を使って横方向の切り方を全探索することにする。 縦方向の切れ目の入…
atcoder.jp 解法 絶対値を外すことができれば、(i, j)と(i', j') を分離できるので計算しやすくなる。 そこで、i ≧ i'かつ j ≧ j' という条件をつけることにする。 これで絶対値の中が必ず0以上になるため、絶対値を外して計算できるようになる。 i < i' か…
atcoder.jp 解法 都市から都市への移動を繰り返すという行為が、DPで遷移するというのに酷似しているため、DPをしたくなる。 次のようなDPを考える。 dp[i][j] ← i日目に都市jにいる旅の仕方は何通りか ただ問題文通りにK回、N個の町から通れる道を使って遷…
atcoder.jp 解法 問題を簡単に言い換えると、同じ種類のコンテストには連続でしか出場できないという条件を満たす、コンテストへの出場の仕方は何通りですか？ といった感じになる。 DPで解くことを考えてみる。 どの種類のコンテストへの出場経験があるか、…
atcoder.jp 解法 $ A_i B_i $はなるべく小さい方が数列Bの総和は小さくなる。 数列Aの要素にそれぞれ適当な値をかけて、全て同じ値を作り出したいのだから、$ A_i B_i $は数列Aの要素の最小公倍数にすると最小になることがわかる。 最小公倍数はとんでもなく…
atcoder.jp ※なぜかmathjaxでK-1を下付き文字として表示できないので、この記事ではK=Aとします。 $ X_{i-1} $ は正しく表示されるのに、$ X_{K-1} $ はなぜかうまくいきませんでした。 原因不明です。 解法 数列の要素が答えにどれだけ影響を及ぼすか、とい…
