atcoder.jp 水diff後半にしては簡単？ D問題になってたらdiffが下がりそう。 解法 次のようなDPを考えます。 dp[i][j][k] ← (i, j)にいる時、既にi行でk個のアイテムを拾った場合の最大値 また、二次元配列Gを次のように定義します。 G[i][j] ← (i, j)に落ち…

atcoder.jp ABC214のD問題に似ていたので解きました。 解法 lとrを全探索していたらO(N2)になるため、間に合いません。 なので、個々の要素が答えにどれだけ寄与するか、という主客転倒の考え方を使ってときます。 小さい要素ほど、多くの区間に置いて最小値…

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そのままだ。 いまいる都市…

atcoder.jp 解法 行に対して操作を行った場合、列には何も影響を及ぼさないことから、行と列は別々に考えても問題ないことがわかる。 今回問われているのは、どの要素も使用してない行や列を全て削除したときに、それぞれの要素の座標はどうなるか？というこ…

atcoder.jp 解法 参考: 桁DPについて nizi-24.hatenablog.com 桁DPをしよう。 dp[i][smaller][k] ← i: 上から何桁目まで確定しているか、smaller: 未満フラグ、k: 今までに何個0以外の数字が登場したか 遷移するときには、0かどうかで場合分けすればよい。 …

atcoder.jp 一応自力ACはしたのですが、理解が曖昧だったので学んだことをメモしておこうと思います。 下の記事の解説がわかりやすかったです。 drken1215.hatenablog.com math-stan.com 解法 iとjを分離できれば、前計算を行って高速に答えを求めることがで…

atcoder.jp 解法 ぱっと見、部分和問題かなと思うが、O(N2)になってしまうため間に合わない。 他の方法を考えてみると、 ・なぜか区間が与えられている ・Kが小さい ・区間は共通部分を持たない と怪しい部分がたくさんあることに気づく。 区間を利用して高…

atcoder.jp 解法 再帰によって条件を満たすそれぞれの確率を求めようとすると、3100以上の計算量が必要になる場合がある。 愚直に解こうとすると指数時間になってしまう場合、DP(メモ化再帰)が有効になる場合は良くある。 そこで、3つの硬貨の数の取りうる場…

問題リンク ワーシャルフロイド法は名前も知っていたし、使う問題も解いたことがあったが、アルゴリズムの理解が足りなかったため、この問題はコンテスト中に解くことができなかった。 解法 ワーシャルフロイド法は、 dp[k][s][t]: k以下の頂点を中継してよ…

問題リンク 解法 a,b,cのなかにKが持っていない素因数を持っている数が含まれることはないので、a,b,cは必ずKの約数だとわかる。 後は約数の中から条件を満たす組を全探索できれば良いが、最大5000個以上の約数を持つ可能性があるのでN3では間に合わない。 (…

問題リンク 解法 公式解説では2分探索の解法が紹介されていましたが、自分はクエリ先読みで解きました。 $ K_1, K_2, … , K_Q $ と $ A_1, A_2, …, A_N $ をそれぞれ昇順にソートして、先頭から順に突き合わせて、クエリの答えを先に求めておくことを考えま…

問題リンク 解法 $ O(N\log N) $ の解法です。 O(N2)でも間に合うのですが、制約を勘違いしていたので、O(NlogN)の解法を考えました。 まず、開区間のまま考えるとややこしいので全て閉区間に変換することを考えます。 $ l_i≠l_j, r_i=l_j $ の時、 $ [l_i, …

問題リンク B問題にしては難しかった。 解法 N回操作した後の赤色のボールの数はC×D×Nなので、一回の操作でC×D個の赤ボールを追加するとしても問題ない。 そうすると赤ボールの数が青ボールの数以上になるのはいつか、という問題になる。 一回の操作で赤ボー…