読者です 読者をやめる 読者になる 読者になる

YNU.cpc

横浜国立大学競技プログラミング部 ( YNU.cpc )

活動日記 day12

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

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

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