torus711 のアレ

主に競技プログラミングの問題について書きます

グラフ

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 を出…