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} $ はなぜかうまくいきませんでした。 原因不明です。 解法 数列の要素が答えにどれだけ影響を及ぼすか、とい…

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 桁DPの問題。初めて桁DPについて学んだので記事にします。 桁DPとは？ ・N以下の自然数で条件を満たすものは何通りか？ ・N以下の自然数で条件を満たすものの中で最大のものはいくつか？ みたいな問題で活躍するアルゴリズムです。 説明は少し複…

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

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

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

atcoder.jp LIS問題という有名問題を少し変えた問題です。 LIS問題について 最長増加部分列(LIS)問題は、昇順(または降順)となるような部分列は最長でいくつ作れるか？という問題です。 O(N2)のDPが最初に思いつきましたが、これでは間に合いません。 有名問…

問題のリンク 本当はAtCoder Libraryを使って解くことが想定されている問題ですが、全く使わず解きました。 とりあえずなんでもいいので、遅延評価セグメント木の練習がしたかったので。 転倒数について まず、これがわからないと問題が解けません。 一応問…

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

問題リンク 解法 問題文を読んだだけでは、観覧車がどのような動きをしているのかわかりにくいが、図を書いてみると、中心を(0, 0, L/2)とした半径2/Lの円周上を動いていることがわかる。 まず、与えられた時間の時の現在地の座標が知りたい。 中心を(0, 0, …

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

問題リンク 解法 解説スライドで紹介されていた解法とは違う方法で解いた。(解法2に少し似ているかも) 既にoxが含まれている区間を、右左どちらに広げても必ずoxが含まれることがわかる。 線形時間で問題を解きたいので、lかrを固定したい。今回はlを固定し…

問題リンク 解法 体重・身長の取る範囲が小さいということがとても気になる。 これをどうにか使えないかと考えてみると、二次元平面上に(身長, 体重)のようにプロットして、何らかの方法で条件を満たすそれぞれの範囲内にいくつ点が存在するかを高速に計算で…

問題リンク 解法 公式解説では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, …