Entries

スポンサーサイト (この記事を編集する[管理者用])

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

UVa 12299 - RMQ with Shifts (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12299

問題概要

要素数100000以下の整数列Aが与えられる.
250000個以下のクエリを順番にこなす問題.
 クエリ1) 区間[L,R]が与えられるので,数列のその区間の最小値min(A[L], A[L+1], ..., A[R])を求める
 クエリ2) M要素 (10以下ぐらい) の正整数B[k]が与えられるので,同時にA[B[k]]をA[(B[k]+1) mod M]に置き換える.(circular shift)

解法

Segment Treeまたは平方分割.
クエリ2で変更される要素の数は少ないので,愚直に更新してやれば良い.

UVa 12298 - Super Poker II (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12298

問題概要

トランプ.ただし数字は1以上13以下ではなく,それぞれ4以上の合成数に対して,4種類のカードが存在する.
各スーツから1枚ずつ選んで,和がnにする方法は何通りあるかを,[a, b]の範囲のすべてのnについて,求める問題.
ただし,使用禁止カードが10000枚以下指定されている.
bは50000以下.

解法

DPする.単純に行うとO(b^2)程度必要になるが,FFTを使ってO(b log b)程度に落とす.

UVa 12295 - Optimal Symmetric Paths (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12295

問題概要

N*Nのグリッドが与えられる.各マスには1以上9以下の数字が書かれている.
左上から右下に移動するパスのうち,右上から左下に向かう対角線について対照なパスのみを考える.
その中で,通ったマスの合計値を最小化するようなパスは何通りあるかを求める問題.

解法

対角線まで移動したらあとは一意に定まる.
対角線の向こうのセルの数字を,対角線の手前の対応するマスのコストに足しておいて,対角線まで移動することを考えれば良い.
ダイクストラしながら,最小値を取るパターンの数もついでに計算する.

UVa 12294 - RPG battles (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12294

問題概要

RPGでN個 (1000以下) の戦闘を与えられた順番にこなさなければいけない.
全部に勝つ戦闘時間の和の最小値を求める問題.勝てないならそれを指摘する.
主人公の最初のパワーはpである.(100以下)
各戦闘に対して,p1, p2, t1, t2, w1, w2 が与えられる.(p1, p2, t1, t2は100以下,w1, w2は10以下)
戦闘時間は,
 主人公のパワーがp1より小さければ勝てない
 主人公のパワーがp2より大きければt2
 そうれなければ,主人公のパワーがp1の時,戦闘時間t1,パワーがp2の時,戦闘時間がt2になるように線形に補間する.
戦闘に勝ったら,ドーピング剤1がw1個,ドーピング剤2がw2個もらえる.ドーピング剤はいつ使っても良い.
ドーピング剤1は使うと主人公のパワーが永続的に1増える.
ドーピング剤2は使うと主人公のパワーが永続的に2倍になる.

解法

ドーピング剤1は手に入れたらすぐ使うのが最適.
あとは,どこまで敵を倒したか,現在のパワー,ドーピング剤2の所持個数を状態にDPする.
現在のパワーが100を超えても意味ないので,100を超えたら100として処理する.
ドーピング剤2の個数が7を超えても意味ないので,同様の処理を行う.

UVa 12293 - Box Game (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12293

問題概要

2人でゲームを行う.
順番に行動して,行動できなくなったら負け.
先手必勝か後手必勝かを判定する問題.
最初は(N,1)と書かれている.(Nは2以上10^9以下)
各ターンでは,書かれている整数のうち大きい方の数字を2つの正整数A, Bに分割し,書かれている整数を(A, B)に変更する.

解法

Nは2のべき乗-1のときのみ先手必敗になることがちょっと考えるとわかる.

UVa 12291 - Polyomino Composer (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12291

問題概要

サイズ10*10以下の2つのpolyomino A, Bが与えられる.
Aが,Bをちょうどずらして2つ並べた形になっているかどうかを判定する問題.
2つのBは重なっていてはいけないし,回転などしてもいけない.

解法

全パターン試す.

UVa 12290 - Counting Game (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12290

問題概要

n人 (100以下) の人が1列に並んでいる.
ターンは,右端の人から順番に回ってき,左端まで行くと折り返していく.
(n=4なら12343212343212…という感じにターンが回る.)
各ターン,最初の人は1,そうでなければ,最後の数字+1を言う.
ただし,その数字が7の倍数か,10進数で7という文字を含むなら代わりに手を叩く.
m番目の人はk回目 (100以下) に手を叩くとき,それは何という数字だったかを答える問題.

解法

シミュレーションする.

UVa 12289 - One-Two-Three (この記事を編集する[管理者用])

Source

The Seventh Hunan Collegiate Programming Contest Semilive (2011-09-17)
UVa 12289

問題概要

oneまたはtwoまたはthreeのどれかの単語を,たかだか1文字間違えたものが与えられる.(文字数は間違えない)
間違える前がoneなら1を,twoなら2を,threeなら3を出力する問題.

解法

やるだけ.3つ単語に対して条件を満たすか判定する.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。