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 この問題は下の問題とほぼ同じだった。 atcoder.jp ↓自分の記事 nizi-24.hatenablog.com 解法 絶対値によってiとjが分かれている問題は、絶対値を外してiとjを独立に計算すると良いことが多い。 $ x_i ≧ x_j $としても一般性を失わない($ x_i < x…

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 強連結成分分解を初めて学んだので、メモしておくために記事にします。 アルゴリズムの正当性とかはまだちゃんと分かっていない気がするので、役に立ったリソースだけまとめておきます。 高校数学の美しい物語ってグラフ理論の解説とかもしている…

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

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以下の自然数で条件を満たすものの中で最大のものはいくつか？ みたいな問題で活躍するアルゴリズムです。 説明は少し複…