問題 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403 解法 頂点に重み付きの価値がついているグラフの最大独立集合を求める問題。 なので枝刈り探索によって解くことができる。具体的な枝刈り方法はwataさんのスライドのp.28以…

問題 文字列Sを部分列に含む回文であって長さが最小であるもののうち、辞書順でk番目のものを求めよ。 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362 解法 まずは最小長さを求め、最小長さとなるような回文の個数を数え上げる…

問題 bitからなる異なる 個のbit列が与えられる。1回の質問でbitを1つ明らかにできるとき最悪でも何回の質問でbit列を1つに特定できるか求めよ。 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302 解法 まず前計算として、 cnt[S…

問題 JOI 2010 本戦の問題 問題リンク：AOJ 0552 解法 かなり難しかった。 そのままの座標だとマンハッタン距離が扱いずらいので45度回転をする。すると、例えばと変換すれば距離はで求められるようになる。点群の最遠点対の距離はで求まり、s,tで分離して考…

9/18-9/20に行われた会津大学競技プログラミング合宿2019に参加してきました。

問題 問題リンク：There is No Alternative N頂点M辺の重み付き無向グラフが与えられる。最小全域木を構成するとき、どのような構成でも必ず使用するような辺の本数とそのコストの総和を求めよ。 解法 最小全域木に1つ辺を追加したとき、その辺によって作ら…

問題 問題リンク：ばらばら饅頭 解法 各重さの饅頭の個数を状態に持ってメモ化再帰をすることを思いつくが より、最悪 程度のパターンが存在するため厳しい。 パターンを減らすため、先に決めて損のない組み合わせを貪欲に取り除いておくことを考える。する…

問題 問題リンク 解法 訪れる順によって移動時間が変わる。一方、いままで訪れた蔵が同じであれば次に移動するときにかかる移動時間も同じである。 よって、今後どう移動するかはいままでの経路順によらないので、訪れた蔵の集合と現在地のみを状態として持…

問題 問題リンク 解法 ある区間内の山をすべて重ねたとする。このとき山の順序は変わらないので最終的にできる山の状態は、その重ねる順序によらない。 よって、区間を決めれば操作順を無視できるので、その最小コストのみが分かっていればよい。また、ある…

CatChecker | Aizu Online Judge 問題概要 文字列Sが与えられる。Sが猫の鳴き声か判定したい。猫の鳴き声は次のように定義される。 空文字列""は猫の鳴き声 X,Yが猫の鳴き声ならば、'm'+X+'e'+Y+'w'は猫の鳴き声 以上で定義されるものだけが猫の鳴き声 Sが猫…

問題概要 価値が vi 重さが wi であるような N 種類の品物と、容量が W のナップザックがあります。i 番目の品物は mi 個まで選ぶことができます。選んだ品物の重さの総和が W を超えないように選んだとき、価値の合計の最大値を求めてください。 問題リンク…

問題概要 N頂点A辺からなる重み付き有向グラフがあり、各辺の重みは文字列で与えられます。始点から終点への文字列が辞書順で最小になるような経路を選んだときのその文字列を出力してください。ただし始点から終点への経路が存在しない、または無制限に辞書…

ACPC2018 9/19~9/21の3日間会津合宿に参加してきました. 運営の会津大、立命館、北大のみなさん、スポンサーのfixstarsさんありがとうございました. Day1 会津大の会場に集合30分前に到着. 名札を受け取って空いている席へ. この時点では参加者の中に知り合…

問題リンク https://onlinejudge.u-aizu.ac.jp/problems/2419 問題概要 H*Wのマス目上を上下左右に移動します。Sからスタートし全てのMを一回以上通りながらGにたどり着くのにかかる最短時間を求めてください。隣り合うマス目の移動には1秒かかりますが穴の…