CF Beta Round 27

もんもん。

A.Spit Problem

通った。
お互いにつばをかけあうラクダ同士がいるかどうか。配列にいれといて適当に探した。

B.Traffic Lights

落ちた。
d地点に1つの信号機があるlメートルの一本道を車が毎秒vメートルで進む。赤信号ならば待たなければならない。緑信号はg秒、赤信号はr秒の繰り返し。
問題を勘違いしたか、小数の計算でなんかミスったか。未確認。

C.Mail Stamps

通った。
郵便をA市からB市に出すとスタンプを"A B"か"B A"と押される。いくつかの市を経由して郵便が出されたとする。スタンプの組がn個与えられ、その組から「どこからどういう風に経由してどこへ出した郵便か」を出力。2通りのうち1つを出力せよ。
中継でない市を2つ探して、そこから戻らないように進むだけ。
最初何を勘違いしたか、ダイクストラで最適解を出さないといけないと思って書いてしまったけど、最悪のケースでTLEになるから問題読み直して気づいた。。。

D.Ant on the Tree

間に合わなかった。
蟻さんが(グラフ理論的な)木をrootからすべての頂点を通ってrootに戻りたい。ただし、辺は2回だけ通ることができて、さらに訪れる葉の順番が決まっている。このとき、蟻さんの移動は可能かどうか。
愚直に書いてみたけどWAだった。

E.Quarrel

未読。

反省

ちょっとゆっくりやりすぎた。
Cの問題をちゃんと計算量考えてたら全然時間かかんなかったのに。。。
レートは+112だった。やった。