競技プログラミング
atcoder.jp 公式解説とは違う方法らしい。 解法 この問題は、頂点 $ U_i $の子要素で根からの距離が $ D_i $である頂点はいくつか、というクエリに回答せよ、と言い換えられる。 複数のクエリに回答する問題 複数のクエリに回答する問題は、次のような解法パ…
atcoder.jp 解法 全探索しようとするとO(2N)になってしまうような問題はDPで解けることが多い。 なので、DPで解くことを考えてみる。 i回目の操作F, Gは次のように言い換えられる。 左端と左からi + 1番目の値を計算して、現在の左端と入れ替える ここで、i…
atcoder.jp 解法 愚直に数列を前から順に見ていこうとすると、計算量はO(N)になり、N ≦ 1010の制約では、時間がかかりすぎてしまう。 なので、計算量を落とす方法を考える必要がある。 mod 〇〇で考えられる問題で鳩ノ巣原理が使えるというのは典型。 この問…
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 解法 香辛料の消費量は、整数以外も選択できるがどこかで調整すればすべて整数にすることができるので、最初から整数で考えてよい。 ナップザックDP感があるので、普通にDPするしようとすると、 dp[i][w] ← i番目までの料理を作った時、香辛料をw…
atcoder.jp 制約を見て半分全列挙とかいうやつじゃないか、と気づいた。 勉強したことなかったので記事にします。 半分全列挙について 簡単にいうとbit全探索もしくは何重かfor文全探索を、二分探索などで高速化しようという考え方のこと。 下の記事の解説が…
atcoder.jp 解法 エラトステネスの篩で素数かどうか判定する代わりに、素因数の種類を数えればOK。 N ≦ 107 でも間に合うんですね。 実装 K=1のときは場合分けした方が実装が楽だと思った。 void solve(long long N, long long K) { if (K == 1) { c(N-1) re…
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 解法 この問題は、0→iに重み$ T_i $の辺と、i→i+1に重み$ S_i $の辺があるグラフと見ることができます。 ここで、0とは高橋君のことを指します。 これで、頂点0からiまでの最短距離は？という問題に変換することができました。 これはダイクスト…
atcoder.jp 水diffになってるけど、適切な位置に出題されていれば茶〜緑ぐらいの難易度だと思った。 考察 dist[i] ← 始点からiまでの最短距離 n.w ← 辺の重み とする。 各頂点を始点としてダイクストラをして、頂点iから元の頂点へ戻る辺を通る時にdist[i] +…
atcoder.jp 解法 問題を見てすぐに下のようなDPが思い浮かんだ。 dp[i][j] ← (i, j)へ行く場合の数 ただ、愚直に遷移しようとすると1つのマスにつき、H+W回ぐらいの遷移が必要になるのでこれでは間に合わない。 手を動かして、DPテーブルがどのような値をと…
atcoder.jp bitDPについて初めて学んだのでメモしておく。 bitDPとは？ 下の記事たちがわかりやすい。 algo-logic.info qiita.com 解法 巡回セールスマン問題であることが制約や問題名から読み取れる。 この問題の説明は下の記事でもされているので省く。 al…
atcoder.jp 解法 s’を文字の配列とみて、前からイテレータを動し、tと一致する文字を１文字ずつ探すことを考える。 最小値を求めたいので、一回一回のイテレータの移動は小さい方がよい。 この最小の移動を高速に求めるには、事前処理＋二分探索が有効になる…
atcoder.jp 解法 DPがしたくなる見た目をしているが、O(NM)になって間に合いそうにない。 あまり気が乗らないのだが、貪欲法で解けないかどうか考えてみることにする。 報酬を最大化したいので、なるべく報酬が大きい労働を優先的に選択したくなる。 かつ、…
atcoder.jp 解法 木上のDFSを理解していますか？って感じの問題。 訪れていない都市を優先的に移動を繰り返すということで、深さ優先探索と同じ方法であることがわかる。 訪れていない都市がない時、元の都市に戻るという動作もDFSそのままだ。 いまいる都市…
