2017-07

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 が偶数かどうか.
スポンサーサイト

Flat35

解いたことがあったので Java で参加.
6 問中 5 問通した.終了後 3 分で 6 問目を通した.
ミスが多い.解法をもうちょっと丁寧に詰めてから送ろう.

A: Blackjack (Aizu 2024) (JAG 2005)


カードの列が与えられるので,ブラックジャックのディーラーをシミュレーション.
ルールは,16 以下か,17 かつ 11 計算しているエースがあればヒット.

和と 11 計算しているエースをもてばよい.

B: Divisor is the Conqueror (Aizu 2026) (JAG 2005)


カードが与えられる.今までに出したカードの和の約数のものが次に出せる.
すべて出せるかどうか判定し,可能なら一例を出力する.
カードはトランプ 52 枚の部分集合.

ゲームを後ろから行って,手持ちのカードの和の約数のみが出せる,というルールと同じ.
状態は 5^13 = 1,220,703,125 だが map にメモできた.

前から行う (状態として今までの和も必要) と TLE した.

C: Eight Princess (Aizu 2025) (JAG 2005)


円上に並んだ N 個の椅子に 8 人が座る.
隣り合った 2 席,あるいは向かい合った 2 席 (N が偶数のときのみ) の両方に座ることはできない.
座り方は何通りあるか.
(答) <= 10^14.

N が偶数のとき,
0 番の椅子を使うと固定し,
(1, 1 + N/2), (2, 2 + N/2), ..., (N - 1, N - 1 + N/2) の順に見ていく DP.
状態は椅子の組,使った人数,前回どちらの番号を使ったかで N * M * 2.
最後に N * 7! 倍する.

N が奇数のときは,上の DP の簡易版で解いた.
二項係数からも計算できる.

自明な O(2^N N) を組んでデバッグに用いた.

D: Gather on the Clock (Aizu 2028) (JAG 2005)


n 枚のカードが円形に並んでいる.
1 枚とり,時計回りに次の残っているカードに重ねることを繰り返す.
重ねるとき,その 2 枚のカードの数の差の絶対値が得点に加算される.
得点の最大値.
n <= 100.

O(n^3) の区間 DP.
円なので配列を 2 倍した.
dp[i, j) = max{ dp[i, k) + dp[k, j) + |card[i] - card[k]| | i < k < j }.

k として i + 1 と j - 1 しか考えていなくて 1WA.

E: Reading a Chord (Aizu 2027) (JAG 2005)


コードの構成音が与えられるので,あり得るコードネームをすべて,任意の順で出力する.
考えるコードは基本的な 3 和音か 4 和音と,高々 1 つのテンションがついたもの.
オクターブは無視.

十分少ないので,最初に全生成してみた.

mM7 をはじく際に,substring(1) で見ていた (C#mM7 などがはじけない).
作った文字列で判定するのは危なかった.

F: Traffic (Aizu 2036) (JAG 2006)


交差点に信号 (周期的) がついている最短路問題.スタートとゴールは交差点と交差点の間.
街のサイズは 100 * 100 以下.

ある交差点に縦 or 横向きで入ってくる最短時間,を Dijkstra で求める.
交差点を全く経由しないケースに注意.

信号の初期状態が縦のときに,横のときと同様に扱おうと初期時刻を負にずらして考えたが,ずらす時間を間違えた (縦の時間ではなく横の時間).
Dijkstra のスタートを入れるとき,縦向きのときに横向きのフラグ (1 でなく 0) を使っていた.コピペ時の修正忘れ.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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