概要 有向グラフと目標頂点が与えられる． 目標頂点への往復経路が最も大きい頂点を探す． 解法 Dijkstraやるだけ． 復路の計算は与えられたグラフに対してDijkstra法を使えば簡単に求まる． 往路の計算は与えられたグラフの辺を逆向きにしたグラフにDijkstr…

蟻本の問題番号と，問題名の対応が間違ってた． 概要 負閉路検知やるだけ． const int INF = 100000000; typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> </edge>…

概要 無向グラフが与えられるので，他のすべての頂点への距離の平均が最も小さい頂点を探す． 解法 Warshall-Floydやるだけ． const int INF = 100000000; int N, M; int d[310][310]; int c[310]; int main(){ scanf("%d%d", &N, &M); for(int i = 0; i <= …

概要 2種類の集合があって，2つの要素が異なる集合に属しているという情報と，2つの要素が同じ集合に属すかどうか問うクエリが来る． 解法 蟻本の練習問題と同様の考え方を用いる．要素vについて，集合Aに属している事象Avと，集合Bに属している事象Bvを用意…

概要 コストa[i]と評価値s[i]の組の列がある． この中から，N（奇数）個の要素をコストの合計がFを超えないように選び，メディアンを最大化したい． 解法 メディアンはソートしたときの中央値であり，中央の値以外には影響をうけないことを利用する． N = 2K…

概要 100個以下の要素からなる(S[i],F[i])の列がある．(-1000 この列からいくつかの要素を選び，S[i]，F[i]の総和をとる． S[i]の総和とF[i]の総和が0を下回らないという条件のもとで，S[i]とF[i]の総和を最大にする． 解法 S[i]について降順にソート． dp[i…

蟻本の練習問題を消化中 概要 K種類のブロックがあって，i番目のブロックは高さhiであり，ci個だけある．また，ブロックの一部がhiを超えるとまずい． ブロックを積み上げていくとき，到達できる高さの最大はいくつか． 解法 ブロックを高さ制限でソート． d…

7月11日のICPC国内予選にチーム"Takoyaki-man"として参加してました．結果は，4問完答ミスなしで39位でした．事故がなければ予選通ってます． チーム編成 メンバー 学年 役割 備考 僕 大学4回生相当 C以降を解く ぺろぺろキャンディグラフ 後輩A 大学2回生相…