活動日記 day12

活動内容 :
コンテスト ( チーム戦、他大学の練習会に参加 )
コンテスト : Virtual Arena: Room 3301
アジア地区大会 2011 Kuala Lumpurサイト

コメント :
解けた問題
A : 実装問題。書く。
C : ２つの論理式が等しいか？変数に乱数を入れて適当な回数だけ２つの式の計算結果が一致するかをチェックする。
D : 2次元平面上にいくつかの点と線が存在する。線と点の間に他の点が存在しない場合、その点は線から見えるものとする。存在する点の60%以上の点が見えるか？　各点について、そこから上下左右で一番近い点を列挙する（lower_boundで）。点と一番近い点の間に線分があるかどうかを判定する（これもlower_bound）。
G : ２つの文字列a、bがある。aの後ろとbの先頭で同じ部分文字列が何か所存在するか？　ローリングハッシュをマップにつめる。
H : ２次元平面上にいくつかの点とロボットが存在する。ロボットが点aから点bに移動するために必要な移動回数は？　コストが1なのでBFSをする。

解けなかった問題
B : BITを使うらしい。
E : 一般マッチングで解けるらしい。一応本番中にtutte行列で完全マッチングを求めるコードを投げるもWA。そもそも問題概要を勘違いしている？（今の解釈だと同じサイズの部屋が２つ以上あると...）
F : サンプル出力を見て実装問題だと思い後回しにしていた。
I : 最初はどの方向でも良いので進んで、後は一番原点から遠ざかる場所に進むようなコードを書いたがWA。コーナーケースは見つけたものの...