torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

グラフ

TopCoder SRM 594, Division 1, Level 2 : FoxAndGo3

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706 概要 '.', 'x', 'o' からなる盤面が与えられる。 盤面上のセル同士が辺を共有するとき、それらは隣接していると見做される。 与えられる状態で 'o' 同士は隣接していない…

Codeforces #203, Division 2, B : Resort

問題文 http://codeforces.com/contest/350/problem/B 概要 N 頂点からなる有向グラフがあり、各頂点には 0 または 1 の属性が付与されている。 各頂点について、それを終点とする辺の始点が与えられる。 次の条件を満たすパスの内、長さが最大のものを一つ…

TopCoder SRM 591, Division 1, Level 1 : TheTree

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12746&rd=15703 概要 次の制約を満たす木の最大の直径を求めよ。 一つのノードを選び、これを V とする V から最も遠いノードへの距離を D とする x ( 1 ≦ x ≦ D ) について、V から距離 x…

Codeforces #200, Division 2, B : Simple Molecules

問題文 http://codeforces.com/contest/344/problem/B 概要 三頂点からなるグラフがある。 このグラフは多重辺を許可し、ループを許可しない。 グラフの各頂点について、次数が指定される。 その制約を満たすグラフを構築できるならば、そのときの辺の張り方…

TopCoder SRM 589, Divisin 1, Level 2 : GearsDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12729&rd=15701 概要 N 個の歯車があり、それぞれの色は赤、緑、青のいずれかである。 噛み合っている歯車どうしは、互いに逆向きにしか回転できない。 また、同じ色の歯車は同じ方向に回…

Codeforces #192, Division 2, B : Road Construction

問題文 http://codeforces.com/contest/330/problem/B 概要 整数 N と、M 個の数のペア が与えられる。 次の条件を満たす N 頂点の無向グラフを構築せよ。 全ての頂点対について、二点間距離は二歩以下 二点 間には辺が無い

TopCoder SRM 584, Division 1, Level 1 ( Division 2, Level 2 ) : Egalitarianism

概要 N 人の市民がいて、それぞれの友達関係が与えられる。 友達同士であるような二人の市民について、その所持金の差が d 以内になるようにしたとき、任意の二人の市民(友達同士でなくてもよい)の所持金の差の最大値はいくらになるか求めよ。 解が無限大…

TopCoder SRM 583, Division 1, Level 1 : TravelOnMars

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12608&rd=15503 概要 リング状に N 個の街がある。 i 番目の町からは距離 以内の街へ一回で移動できる。 スタート地点とゴール地点が与えられたとき、最小で何回移動する必要があるか求め…

TopCoder SRM 583, Division 1, Level 2 : TurnOnLamps

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12606&rd=15503 概要 N 頂点からなる木があり、木の各辺には 0 か 1 が割り当てられている。 この木に対して、二頂点を結ぶパス(一意に定まる)上の辺の数字を入れ替える操作ができる。 …

TopCoder SRM 581, Division 1, Level 2 : TreeUnion

概要 V 個の頂点から成る二つの木 T1, T2 が与えられ、この二つを V 本の辺で結ぶ。 より詳しくは次の手順で辺を張る。 0 ? V - 1 の順列をランダムに一つ選び P とする 各 i ( 0 このとき、相異なる K ( 3

Codeforces #182, Division 2, D : Yaroslav and Time

問題文 http://codeforces.com/contest/302/problem/D 概要 XY 平面上に N 個の点があり、最初 1 番( 1-indexed )の点にいて、n 番の点に移動したい。 点から点に移動するとき、そのマンハッタン距離 * d の費用がかかる。 1 番と n 番以外の点では、 だけ…

TopCoder SRM 573, Division 1, Level 1 : SkiResorts

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12468&rd=15493 概要 あるスキー場には、N 箇所の "場所" があり、いくつかの道によって繋がれている。 スキーでの移動は、同じ高さの場所か、より低い高さの場所にのみ可能である。 各場…

Codeforces #170, Division 2, C : Learning Languages

問題文 http://codeforces.com/contest/278/problem/C 概要 ある会社には n 人の従業員がおり、m 個の公用語がある。 一人の従業員に一つの言語を教えるコストが 1 である。 各社員が使える言語の情報が与えられるので、全ての社員が互いに(他の社員に通訳…

AtCoder Regular Contest #011, C : ダブレット

問題文 http://arc011.contest.atcoder.jp/tasks/arc011_3 概要 ある単語について、文字を一文字置換する操作が許される。 与えられた辞書を使って、start から last まで変換するときの手順を求めよ。

TopCoder SRM 566, Division 1, Level 1 : PenguinSledding

概要 グラフの頂点数と辺の情報が与えられる。 「このグラフを二次元平面上にどのように配置しても辺が交差しない」ような辺の選び方の総数を答えよ。

Codeforces #149, Division 2, C : King's Path

問題文 http://codeforces.com/contest/242/problem/C 概要 × のチェス盤にキングが置かれている。 キングを ( x0, y0 ) から ( x1, y1 ) まで移動させたい。 使用可能なセルの情報が与えられるので、最小の移動回数を出力せよ。 移動できない場合は -1 を出…