スポンサーサイト

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

Codeforces Round #120 (Div. 2)

2012/05/17 00:30 ~ 02:30
Codeforces Round #120 (Div. 2)

ジャッジが止まって no contest

Tags : プログラミング Codeforces

問題

問題セットの原文はここを参照。

A. Vasya and the Bus
n 人の大人と m 人の子どもがバスに乗っている。
どの子どももちょうど一人の大人に引率されている。
運賃は ( 大人も子どもも ) 一人当たり 1 円。ただし、一人以上の子どもを引率している大人は 1 円引きされる。

ありうる合計運賃の最大値を最小値を求めよ。
ただし、可能な割り当てが存在しない場合は Impossible と答えよ。

1 ≦ n, m ≦ 10^5

B. Surrounded

平面上の二円 ( 内部を含まない ) が与えられるので、それらの間の距離 ( 一番近いところ ) を求めよ。

C. STL

"pair" と "int" だけからなる文字列
( たとえば、pair pair int int int )
が与えられるので、
pair<pair<int,int>,int>
のように、正しく括弧をつけよ。
正しい括弧付けが存在しない場合はそれを報告。

D. Non-Secret Cypher

長さ n の整数列が与えられる。
これの部分文字列で、同じ数を k 個以上含むようなものの個数を求めよ。

1 ≦ k ≦ n ≦ 4・10^5

E. Counter Attack

無向グラフ G が与えられる。
G の補グラフの連結成分をすべて求めよ。

1 ≦ 頂点数 ≦ 5・10^5
0 ≦ 辺数 ≦ 10^6

※ G の補グラフとは、G と同じ頂点をもち、G の辺があるところには辺がなく、G の辺がないところには辺があるグラフのこと。

解答

A.
大人が一人もいない場合、子どもが一人もいない場合は例外処理する。
それ以外のときは、子どもを一人の大人に集中させると運賃最大、できるだけばらけさせると運賃最小になる。

問題文が難解だし、場合わけを間違いやすいので、A にしてはかなり難しかったと思う。

O(1)
http://www.codeforces.com/contest/190/submission/1698909

B.
1. 一つの円がもう一つの円の内部にあるとき
2. 二円が交差するとき
3. それ以外のとき
で場合わけ。
1 と 3 のときは、円の半径と中心間の距離から計算できる。
2 のときは、ただちに答えは 0 とわかる。

これも正しく場合分けるのはそれなりに難しいと思った。

O(1)
http://www.codeforces.com/contest/190/submission/1699120

C.
おもしろい問題。
サンプルを見た瞬間に何をさせたいのかわかるという点もいい。

再帰下降型の構文解析と同じようにできる。
ただし、すべての入力を読み終わったかを最後に確認するのを忘れないこと。 ( これを忘れて WA を出した )

O(n) ( n は単語数 )
http://www.codeforces.com/contest/190/submission/1698898

D.
尺取法。
今注目している区間に k 個以上の重複する数があるかどうかは、座標圧縮 + RMQ を使った。RMQ の代わりに set を使っても同じ計算量で解ける。

O(n log n)
http://www.codeforces.com/contest/190/submission/1700872

E.
解けなかったので editorial を見た。

未訪問の頂点を set に入れておく。
set が空になるまで、次をくり返す。

set から一つの頂点 u を取り出し、u を含む連結成分を求めることを考える。
補グラフ上で BFS をする。u から始める。
今いる頂点 u から未訪問の頂点 v に移動したいとする。
辺 (u, v) が元のグラフ G の辺に含まれていたら移動できない。
そうでなければ移動できて、set から v を削除する。
(u ,v) が G の辺かどうかは、G の辺をあらかじめソートしておくと、二分探索で求められる。

計算量がちょっと読みにくいけど、set から頂点が削除されないのは全体で高々 2・m 回であることに注意すれば、O(m log m) くらいになっていることがわかる。
set の初期化の分とあわせて、全体の計算量は O(m log m + n log n) でおさえられる ( はず... )

O(m log m + n log n)
http://www.codeforces.com/contest/190/submission/1710432
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。