スポンサーサイト

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

Croc Champ 2012 - Final

2012/04/27
Croc Champ 2012 - Final

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

問題

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

A. Headquarters

長さ n の命令列が与えられる。
各命令は
・ 上に一マス進む or 左に一マス進む
・ 上に一マス進む or 右に一マス進む
・ 下に一マス進む or 左に一マス進む
・ 下に一マス進む or 右に一マス進む
・ 上下左右のいずれかに一マス進む
のどれか一つ。
この命令列を実行し終えたとき、ちょうど原点にいた。
スタート位置としてありうるマスはいくつあるか?

1 ≦ n ≦ 2・10^5

B. Zoo

二次元平面上に n 個の望遠鏡と m 羽のフラミンゴがいる。
一つの望遠鏡で、同一直線上にあるフラミンゴを同時に見ることができる。
見ることができるフラミンゴの数を最大化せよ。( 同じフラミンゴを複数の望遠鏡から見たときは別々にカウントする )

1 ≦ n ≦ 10^6
1 ≦ m ≦ 250
望遠鏡 i は位置 (i, 0) にある
フラミンゴ i は位置 (x[i], y[i]); 1 ≦ x[i], y[i] ≦ 10^9 にいる

C. Cyclic Coloring

頂点数 n, 辺数 m の有向グラフ G が与えられる。
G の各頂点を k 色以下で彩色する。
このとき、G のすべての有向辺 u -> v に対して color[u]+1 == color[v] でないといけない。
ここで、color[u] は頂点 u に塗った色の番号で、+ は mod k での和。
このような彩色が可能な最大の k ( 1 ≦ k ≦ n ) を求めよ。

1 ≦ n, m ≦ 10^5

解答

A.
まず、問題文ではゴールが原点だと言っているけど、原点からスタートして何通りのゴールに着きうるか? と言い換えても同じこと。
このほうが考えやすいのでこう言い換えることにする。
実験していると、到達可能なマスの集合はつねに ( 軸から 45 度回転した ) 長方形になることに気付く。
UL, DR のときは一辺の長さが +1 される。
UR, DL のときはもう一方の一辺の長さが +1 される。
ULDR のときは、両方の辺の長さが +1 される。

おもしろい問題だった。
http://www.codeforces.com/contest/183/submission/1631318

B.
候補になる直線 ( 望遠鏡からの視線 ) は、フラミンゴを一羽だけ通るか、二羽以上のフラミンゴを通るか。
二羽以上のフラミンゴを通る直線は O(m^2) 個しかないので、全部調べることができる。
各直線について、それを見ることができる望遠鏡は高々 1 つしかないので、各望遠鏡で最大何羽のフラミンゴを見ることができるかを表す配列を用意しておいて、各直線ごとに配列を更新していくようにすればいい。
日本語で説明しにくいのでソースコードを読むのがいいと思う。
同一直線上にあるかどうかの判定は ccw を使った。

ちなみに、一つの直線で最大いくつの点を貫けるかという問題は典型も典型で、ほとんどいたるところのオンラインジャッジに類題があると思う。もう 5 回は見た。
ナイーブにやって O(m^3), 偏角でソートして O(m^2 log m), ハッシュテーブルを使って O(m^2) でできることが知られている。多分 O(m^2) よりは速くならないと思う。
http://www.codeforces.com/contest/183/submission/1631447

C.
有向グラフというのは ( たぶん ) ひっかけで、グラフを無向グラフとして見るのがポイント。

とりあえず、連結成分ごとに調べる。
一つの頂点に色を塗ると、隣接する頂点の色は自動的に決まっていって、連鎖的にその連結成分の頂点の色がすべて決まる。
このとき、塗った色に矛盾がないかを見ればいい。
k を小さいものから一つずつ調べていては間に合わない。
そこで、k == INF として ( つまり mod 計算をしないで ) 色を塗ってみる。
color[u] + 1 == color[v] の関係が崩れるところが問題になる。矛盾を起こさないためには、ようするに k が (color[u] + 1) - color[v] の約数であればいい。
この条件から最大の k を求めることができる。

各連結成分に対して最大の k が求まったら、上記の議論と同じ理由から、それらの k の最大公約数が答えになる。

スタックオーバーフローがこわかったので BFS で書いたけど、DFS でも大丈夫らしい。
http://www.codeforces.com/contest/183/submission/1631952
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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