2018-06-27から1日間の記事一覧

AOJ 0324 Downhill Race

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324 解法 ダイクストラで解く. 与えられるグラフはDAGになっていて,この上で2回違う条件で最短経路を求めたい.しかし依存関係にあるので独立にはできない. こういうときは1回目と2回…

AOJ 0322 Slates

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322 解法 二分探索で解ける. 左が欠けているやつを考えるときは末尾から比べたいので,各文字を反転した文字列集合も別に持っておく. 与えられた石版に ? がある場合は26文字全通り試す…

AOJ 0321 Investigation of Club Activities

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321 解法 union find 木を使うと楽? union find の各集合がどのクラブに属するかを別に vector で持っておく. a と b が同じ部活に所属している場合,マージするのだが違うクラブに属し…