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

atcoder.jp 解法 類題1 蟻本にのっているAOJの問題。 poj.org 類題2 典型90問の1問目。 atcoder.jp 最大値の最小化をしろということなので、二分探索を考える。 探索する条件としては、「K以下の切断回数で答えをXにできるか？」 なぜK以下でよいかというと…

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を使って解くことが想定されている問題ですが、全く使わず解きました。 とりあえずなんでもいいので、遅延評価セグメント木の練習がしたかったので。 転倒数について まず、これがわからないと問題が解けません。 一応問…

セグメント木 セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。 セグメント木を理解するために役立つリソース かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。 part1では、セグメント木の雰囲…

AOJの問題 区間和の取得は普通にできるが、更新は工夫が必要。 二分木は区間和を保持する。 また、遅延配列はINFで初期化しておこう。これはフラグとして利用する。(更新後の値として与えられる可能性があるため、0はフラグの値として使えない。) 更新すべき…

AOJの問題 RMQ and RUQ、RSQ and RAQからそれぞれ関数をとってきて貼り付けただけでは解けない。 加算の際に多少工夫が必要。 RMQ and RUQでは、2分木に区間和を保持していたが、今回必要なのは区間の最小値なので、それを保持する。 加算の際には、区間の全…

AOJの問題 RSQ&RAQのコードを少し変更しただけ。 区間更新の場合は加算と違って、普通に値を代入するだけでよい。 遅延配列の要素は、更新クエリで与えられることのない値で初期化すること。これがフラグの代わりになる。 実装 #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

AOJの問題 区間加算と区間和の取得を同時にこなさないといけないので、普通のセグメント木だと難しくなってくる。 そこで、遅延評価セグメント木を導入する。 普通のセグメント木では、区間更新にO(nlogn)だけかかってしまうが(区間更新・一点取得の場合は別…

問題 nodeの値を保存しているだけではどの値がいつ更新されたモノなのかがわからないので、更新された時間も保持しておくことにする。 値を取得するときは、子から見ていって最新の更新時刻を持つnodeの値が現在の値になる。 管理する情報が増えただけで後は…