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

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

あらかじめソートしておき、a_i+a_i+1>a_i+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 により求められる。

E問題、1頂点のみのパスのコストが 0 になると思い込んでいてデバッグに手間取った。