2017-10

Latest Entries

スポンサーサイト

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

Univ. of Aizu ICPCPC 2011 TT 17 DIV1

2 時間程度遅れて参加.7 問中 5 問読んで 5 問通した.

A: Mirror Clock (UVa 11650)


時刻が与えられるので,時計を鏡で反転させて読んだときの時刻を答える.

分に直して -1 倍した.
01:00-12:59 で表す模様.

B: Circular (UVa 967)


[a, b] の整数で,各桁の数字を巡回置換していっても素数にしかならないものの個数を数える.
100 <= a <= b <= 1,000,000

桁が奇数のみなので dfs で作っていった.
愚直にやっても通るかもしれない.
判定は sprintf して適当に.

C: Conic Distance (UVa 10495)


円錐の側面上の 2 点が頂点からの角度と向きで与えられるので,円錐の側面上での 2 点の最短距離を求める.

展開図で考える.角度の差 (<= π) を (底面の半径)/(母線) 倍すればよい.

D: String Partition (UVa 11258)


数字の列が与えられるので,32bit 符号付き整数たちになるように区切って,和を最大化する.
長さ L <= 200.

leading zero は許されないことになっているが許しても変わらない.O(L^2) の DP.
0 をちゃんと処理すれば O(L).

E: Texas Trip (UVa 11243)


平面上の N 点が与えられるので,それらをすべて含む最小の正方形 (任意の向き) を求める.
N <= 30.

N <= 1 は別途処理.
各 2 点の方向とそれに垂直な方向を列挙してソート.
すると各区間内の方向で見る場合は,上下左右の端に来る点は変わらず,
bounding box の縦横の長さはそれぞれ単調 (たぶん).
なので max{ (縦), (横) } は減ってから増える形になる (たぶん) ので,
三分探索で最小が求まる.



コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/1-df2b23eb

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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