Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2470-b738d363
この記事にトラックバックする(FC2ブログユーザー)

Timus 1997 - Those are not the droids you're looking for (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1997

問題概要

とある店に客が入ってきた,出て行ったというログが $n$ 個与えられる.
どの客が入ってきて,出て行ったかは分からないが,その時間 $t_i$ と,入ってきたのか出て行ったのかがわかる.
すべての客は,$a$ 秒以上滞在するか,$b$ 秒以下しか滞在しないかのどちらかである.
また,必ず $1$ 秒以上滞在する.
また,ログをとる前にいた客や,ログを取った後にいた客などはいない.
ログに矛盾がないかを調べ,矛盾がないなら各客の滞在した時間帯のうち,考えられるものを $1$ つ出力する問題.
$2 \leq n \leq 1000$
$1 \leq a,b,t_i \leq 10^9$
$b+1 < a$

解法

入ってきた回数,出て行った回数が一致しないなら矛盾.
後は,それぞれ入ってきたログと出て行くログが対応付けられるかどうかを調べて2分グラフの最大マッチング.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2470-b738d363
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。