2017-10

Latest Entries

スポンサーサイト

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

UAPC 2011

5 時間 12 問.
J と L 以外の 10 問を通した.
最初に F, G から始めて,その後は standings を追っていく感じで解いていった.
序盤はそこそこの好ペースで進められた.終盤は L と戦ったが敗北.

A: It's our delight!!


ある時刻 (時・分) と,その後のある時刻 (分のみ) が与えられるので,時間帯ごとに分類しつつ,差が 8 分以下なものの割合を求める.差は 15 以内であることが保証されている.

差を求めるには mod 60 でよい.

B: Watchin' TVA


30 分アニメ N 本の放送スケジュールが与えられるので,見たい作品の集合は必ず見つつ最大何本見れるか求める.
N <= 500.

必ず見るものと被っているのを除いて,前から貪欲にとっていく.
前半部は容易な O(N^2) で組んだ.

C: Yanagi's Comic


マンガのあるページのコマ割りが与えられるので,読む順番を求める.
縦横に平行な幾何.線分がコマに当たるか,などを判定する.

サイズが小さいので問題文の指示通りに実装.

D: The House of Huge Family


辺の終点がすべて異なる N 頂点の有向グラフが与えられる.辺には非負とは限らないコストがついている.
いくつかの辺を壊した後,頂点集合を空でない 2 つに分けて,どちらからどちらへも行けないようにしたい.かかる最小コストを求める.
N <= 100.

無向グラフと考えてよい.
コスト負の辺はすべて壊す.残ったグラフに対して最小全域カットを求める.O(N^3).

グラフの形状 (各連結成分のサイクルが 1 個以下) に注意すれば,正の辺を 3 本以上切るのは無駄なのでそれで試すこともできる.真面目にサイクル検出すれば線形だけれど煩雑.

負の辺を放置したまま最小全域カットに投げてしまって 1WA.

E: Legend of Storia


円の内部を凸とは限らない N 角形が円周にそってくるくるする.回転の支点になる座標を最初の Q 個求める.
N <= 25,Q <= 100.

毎ステップシミュレーション.
各頂点が円周にぶつかるための回転角 (最小に),ぶつかる位置が今の支点からどれだけ回った位置か (最大に) を計算.円と円の交点で求まる.

支点となる頂点は O(N) 周期 (たぶん.せいぜい O(N^2)) なので,サイズが大きくても何かできる.

F: Cutting a Chocolate


長方形のチョコレートが左の辺と右の辺を結ぶ線分たちで m 個の領域に区切られている.チョコレート上にはアーモンドが n 個ある.
領域を 2 人で分配する.1 人は連結した領域たちがほしい.もう 1 人は合計面積 S 以上がほしい.
面積がほしい人がもらうアーモンドの個数を最小化.
m <= 30,000,n <= 30,000.

アーモンドがどの領域に属すかは二分探索で求まる.部分和をとっておく.
後半のステップは連結区間の先頭を決めた後末尾を二分探索したが,尺取で線形でも解ける.

G: School of Killifish


2 次元長方形領域の RMQ.
(縦) * (横) <= 10^6,(クエリ数) <= 10^4.

メモリがつらい.クエリ数がそんなに多くないので平方根に逃げた.
各行各列に対しては segment tree を作って,さらに 30 * 30 ごとに最小値を保存した.

最初 vector でとったら MLE した.書き間違えによるとりすぎがあったが直しても MLE.vector が勝手に余分にとってくれたっぽい.
配列・ポインタに修正したとき修正ミスで WA.

H: Squid Multiplication


1 個の偶数と N 個の奇数からなる集合について,2 元の積 N(N+1)/2 通りから復元する.
N <= 250,(集合の元) < 2^31.

積のうち奇数のものを全部かけて N - 1 乗根をとれば奇数の元たちの積.
偶数のものを全部かけて,それで割って,N 乗根をとると偶数の元がわかって,あとは復元.
そのまま掛け算できないので,log で計算して,exp したときの前後を見て条件をみたしたら答えた.

全部かけなくても,順序に着目.積のうち偶数のものの小さいほうから 2 個,奇数のうち最小のものを見れば偶数の元が求まる.この方法なら適切に約分すればオーバーフローせず済む.

I: FIMO sequence


数列に対するクエリを処理する.前半とは,n 項あったら最初の ceil(n/2) 項を指す.
・末尾に追加 (追加される数はすべて異なる).
・前半のラストを取り出して削除.
・(前半/後半) の (最小値/最大値) を求める.
・今 (前半/後半) にある数のうち,「今の状態から前半のラストを削除することを繰り返すと仮定した場合」における,(最小値/最大値) となりうる数のうち (小さい/大きい) 方から i 番目を求める.
(クエリ数) <= 200,000,(数列の長さの最大値) <= 20,000.

4 つめのクエリは prefix や suffix の最小値として現れる数のうち i 番目を求めることになる.
deque を前半・後半に 3 本ずつ用意.スタックで,中央がスタックのトップのイメージ.1 本には値をそのまま入れ,残る 2 本にはトップに向かっていくにつれ (最小値/最大値) が更新されたときにその値を入れる.
・前半や後半のサイズが変わるときはトップ付近でやりとりして実現できる.
・追加は deque としての機能を利用する感じで,最小値や最大値の deque からは無価値となった部分を削除.末尾から削除しないのでこれでよい.計算量はならしで線形 (たぶん).
・4 つめのクエリは deque でのランダムアクセスを用いる.

K: Rearranging Seats


r * c の長方形上に席が並んでいて,席替えをする.全員が隣に移らなければならない.可能か否か.

r * c が偶数かどうか.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/7-62900b2d

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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