pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #396 (Div. 2) A,B,D,E

C 問題は読めなかったので省略します。

http://codeforces.com/contest/766

A. Mahmoud and Longest Uncommon Subsequence

a≠b なら a, b のうち長い方(同じ長さならどちらでも)は共通しないため、max(|a|,|b|)が答えになる。a=b のときは存在しない。


B. Mahmoud and a Triangle

三角形の成立条件は、(最も長い辺)<(他の辺の和)であること。ai を最長の辺としたとき、aiより短いできるだけ長い辺を 2 つ持ってくればいい。

あらかじめソートしておき、ai+ai+1>ai+2 となる i が存在するかを判定するだけで良い。


D. Mahmoud and a Dictionary

文字列 x の対義語として仮想的に !x という文字列を追加する。x と y が類義語であるという関係は辺 (x,y)、辺(!x,!y)を張ることに対応できる。x と y が対義語であるという関係は、xと!yが類義語であるという関係に言い換えられるので、辺(x,!y),辺(!x,y) を張ることに対応できる。これらを踏まえると union-find で処理できることが分かる。

辺を張るとき x と !x が連結になってしまうならその処理をスキップする。


E. Mahmoud and a xor trip

ビットごとにばらして考えると、各頂点の値は 0/1 になり問題は簡単になる。やるべき処理はコスト 1 のパスの総数を求めることだが、これは単純な木 DP により求められる。