2011-06

Latest Entries

スポンサーサイト

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

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。