2011-01-23から1日間の記事一覧
keyword 2部グラフ 最小点カバー C++ 概要 蟻本を参考にして解いた。2部グラフでは|最小点カバー|=|最大マッチング|なので2部マッチングする。ソース略。
keyword 集合 C++ 概要 要素が[1..T](T 要素が小さいのでどうとでもなる。多分setに突っ込んでset >に突っ込むのでも余裕で間に合う(これだと計算量O(T^2*log T * P * log(P))。setは定数が重いのでvectorでuniqueとか使って定数分早くした。多分union-find…
keyword 平方分割 概要 蟻本を参考にして解いた。2分探索の範囲が広かったり、分割の数が適切でなかったりしてTLEを何度も出した。分割の数を2の巾にして割り算や余りの計算をビット演算に書き直したら通った。ソース略。
keyword C 概要 入力はa+b=cの形で与えられる。a,b,cは7桁以下の10進数。rev(a) + rev(b) = rev(c)であるかどうか判定する問題。 やるだけ、としか。
keyword 幅優先探索 C++ 概要 2次元平面の原点に少女がいる。少女は第一象限を1秒に1マス動ける(4近傍のいずれか)。隕石がM( 幅優先するだけ。ただし安全地帯は[0..302]*[0..302]の中から探さないといけないことに注意。何故か[0..301]*[0..301]でも通った。…