スポンサーサイト

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

Codeforces Round #124 (Div. 1)

2012/06/12 22:00 ~ 24:00
Codeforces Round #124 (Div. 1)

ブログを書く時間がなかなかとれないので、時間があるうちに一気に書く。

Tags : プログラミング Codeforces 未解決

結果

A: AC
B: AC
C: AC
D: -
E: -
21322205


問題

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

A. Lexicographically Maximum Subsequence

長さ 10^5 以下の文字列が与えられるので、その辞書順最大の部分列を求めよ。

B. Infinite Maze

サイズ n × m の迷路 ( 各マスは何もないか壁かのいずれか ) が与えられる。
同じ形の迷路を縦横に貼り合わせてできる無限に大きい迷路において、スタート地点が指定されたとき、どこまでも遠くにいけるかどうか判定せよ。

1 ≦ n, m ≦ 1500

C. Paint Tree

n 頂点の木と n 個の平面上の点が与えられる。
頂点と点を 1 対 1 に対応させることで、木を平面上に描画することを考える。
木のどの二辺も ( 端点以外で ) 交わらないような対応を一組求めよ。
どの三点も同一直線上にない。
解の存在は保証されている。
解が複数あるときはどれを答えてもいい。

1 ≦ n ≦ 1500

解答

A.
できるだけ遅いアルファベットを先に使うのがいい。
また、一番遅いアルファベットが複数あるときは、それらを全部使うのがいい。

なので、'z' から 'y', 'x', ..., 'a' の順に調べていって、遅いアルファベットを優先的に拾うようにすればいい。
文字で説明しにくいのでコードを読む方がいいかもしれない。

O(C・length) ( C はアルファベットの種類数 )
http://www.codeforces.com/contest/196/submission/1787837

B.
入力で与えられるサイズ n × m の迷路を 1 ブロックと呼ぶことにする。

どこまでも遠くに行けるとして、そのルートを通ったときにどのようなことが起こるか考える。

無限に多くのマスを通るのだから、そのようなルートでは、二つの異なるブロック A, B があって、A の位置 (x, y) と B の位置 (x, y) を共に通っているはず。 ( 鳩ノ巣原理 )

逆に、このような A, B があるとき、どこまでも遠くに行けることもわかる。
なぜなら、迷路は単に同じ形をコピーして作られているから。 ( A から B に行けたとすると、今度はその B を新たに A だと思えば、新しい B が見つかる。 )

この条件の判定は難しくなくて、単に、最後にどのブロックにおいて位置 (x, y) を訪れたかを覚えながら BFS すれば調べられる。

難しいけどおもしろい問題。

O(n・m)
http://www.codeforces.com/contest/196/submission/1790162

C.
まず、木は好きなように根を決めて根つき木として扱う。

点集合の中で y 座標が最小の点 O を求めて、それを根に割り当ててみる。
残った点たちをいくつかの部分木に分配しないといけない。
部分木たちが交わらないようにしたい。
そのためには、残りの点を O を中心としたときの角度でソートして、角度の小さい順に部分木のサイズ分だけ点を割り当てていけばいい。
( ここで三点が同一直線上にないことが利いている )

あとは、部分木について再帰的に問題を解けばいい。

角度を毎回 atan2 で測っていたら TLE したけど、前計算するようにしたら間に合った。

問題を読んだときから、いかにも分割統治のにおいがしていた。
最初は x 座標でソートして同じようにすればできると思って、それを書いていた。それだと sample 2 でいきなりこけてしまって、間違いに気付けたのはラッキーだった。

O(n^2 log n)
http://www.codeforces.com/contest/196/submission/1799807



赤くなった。
今まで自分の実力に今ひとつ自信を持てなかったけど、少しは自信を持てるようになった気がする。
SRM の方はまだまだ黄色のまんなかくらいなので、そっちも引き続きがんばる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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