Entries

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

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

UVa 12460 - Careful teacher (この記事を編集する[管理者用])

Source

X Programming Olympiads in Murcia (Spain) (2012-05-05)
UVa 12460

問題概要

辞書として,20000個未満の単語が与えられる.
ある単語からある単語に直接的に遷移可能とは,文字列の長さが同じで,高々1文字しか違わないこと.
いくつかクエリが与えられて,ある単語からある単語に(間接的でも良いので)遷移可能かどうかを判定する問題.

解法

最初にどの単語間が直接遷移可能かグラフを作っておく.制限時間が長いこともあって愚直に作って間に合う.
あとはクエリごとにDFSなどをしてチェックする.

UVa 12459 - Bees' ancestors (この記事を編集する[管理者用])

Source

X Programming Olympiads in Murcia (Spain) (2012-05-05)
UVa 12459

問題概要

女の蜂は,母親と父親を持つ.
男の蜂は,母親のみを持つ.
今,男の蜂が1匹いて,そのn世代前 (80以下) の祖先は何匹かを求める問題.

解法

フィボナッチ数になる.
答えは符号付き64ビット整数に収まる.

UVa 12458 - Oh, my trees! (この記事を編集する[管理者用])

Source

X Programming Olympiads in Murcia (Spain) (2012-05-05)
UVa 12458

問題概要

二分探索木において,各ノードのキーの値と,深さのみ与えられる.
二分探索木を復元する問題.
キーはユニークで,復元可能なことは保証されている.

解法

各ノードについて,自分が担当する数字の範囲を覚えながら,その範囲内にある自分より深さが1つ深いノードを子供にしていく.

UVa 12457 - Tennis contest (この記事を編集する[管理者用])

Source

X Programming Olympiads in Murcia (Spain) (2012-05-05)
UVa 12457

問題概要

1以上25以下の整数nと,0以上1以下の実数pが与えられる.
誰かとテニスの試合を行う.
1試合した時,勝てる確率はp.
2n-1試合行なって,n勝以上した方が最終的な勝者となる.
n勝以上する確率を小数点以下2ケタまで求める問題.

解法

今何試合したか,今何試合勝ってるかを状態にしてDP.O(n^2).
もしくは,コンビネーションを用いて,n勝する確率,n+1勝する確率を全部求めて足しても良い.
もしくは,要求精度が低いので,モンテカルロしても通るらしい.

UVa 12456 - Mirror codes (この記事を編集する[管理者用])

Source

X Programming Olympiads in Murcia (Spain) (2012-05-05)
UVa 12456

問題概要

d要素の整数列Xを考える.
i番目の要素は0 ≤ X[i] < b[i]でなければならない.(b[i]は与えられる)
また,b[1] = b[d], b[2] = b[d-1], b[3] = b[d-2], ... が成り立つ.
正数列Xで,前後反転させて後ろから読んでも同じになるようなものでないのは何通り考えられるか,を求める問題.
答えは符号付き32bit整数に収まる.

解法

全部の組み合わせの数から,回文の組み合わせの数を引く.

UVa 12455 - Bars (この記事を編集する[管理者用])

Source

X Programming Olympiads in Murcia (Spain) (2012-05-05)
UVa 12455

問題概要

p個 (20以下) の正整数が与えられる.
その中からいくつか (0個でも良い,同じのを2回以上選べない) 選んで,和をn (1000以下) にできるかどうかを判定する問題.

解法

O(pn)のDP.
もしくは2^p個の組み合わせを全部確かめても良い.

Croc Champ 2012 Round 2 D問題 - Playing with Superglue (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 C問題 (2000pt)
Problem description

問題概要

n個 (2000以下) の文字列が与えられる.長さの合計は10^6以下.
その文字列をm個 (mは2000以下,同じのが複数回つながっている可能性がある) つなげた文字列をtとする.つなぎ方は与えられる.
また,2000文字以下の文字列sが与えられる.
tとsの最大部分列 (部分文字列ではない) の文字数を求める問題.
文字列は全てアルファベット小文字のみから成る.

解法

DP.
sを1文字ずつ見ていって,それまでの部分列の長さそれぞれに対して,その部分列のtの終点の最小値を覚えておく.
tの各場所に対して,次に文字cが現れる場所,というのを前計算しておいてすぐ求めれるようにしておく必要が有る.

C言語のスパゲッティなコード

続きを読む

Croc Champ 2012 Round 2 C問題 - Playing with Superglue (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 C問題 (1500pt)
Problem description

問題概要

2人でゲームを行う.先手必勝か後手必勝かを判定する問題.
n*m (100*100以下) の盤面の上に2つの駒がある.
2つの駒の初期座標が与えられる.最初駒の位置は異なり,盤面は糊が付着していない.
各ターン,以下のことを行う.
 先手は,糊付けされていない駒を1つ選び,上下左右のどこかに1マスだけ動かす.
 後手は,まだ糊が塗られていない,かつ,駒が存在しないマスを1マス選び,糊を塗る.
糊が塗られているマスに駒が移動すると,糊付けされて動けなくなる.
2つの駒が同じマスに存在する状況になったらその時点で先手の勝ち.
そうでなく,2つの駒が両方糊付けされて動けなくなったら後手の負け.
勝敗が決る前に両者ともvalidな行動ができなくなることはないことは少し考えればわかる.

解法

初期の駒のx座標の差と,y座標の差のみによってかわる.
後手は,厚さ2の壁を作れれば必勝で,それは,x座標の差とy座標の差のうち,どちらかか5以上ならできる.
そうでないときは,難しいが,パターンが少ないので,それぞれ実際に色々考えてみると,x座標差とy座標差の和が6以下なら先手が勝てることがわかる.

C言語のスパゲッティなコード

続きを読む

Croc Champ 2012 Round 2 B問題 - Word Cut (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 B問題 (1000pt)
Problem description

問題概要

長さNの文字列sとtが与えられる.(Nは1000以下) sを以下の操作をちょうどk回 (100000以下) 行なって,最終的にtに一致するのは何パターンあるかをmod 1000000007で求める問題.  s = xyと空でない文字列x,yに分解して,s=yxと置き直す.

解法

この操作1回分は,sの右から1文字以上N-1文字以下選び,それをsの左に移動させるというシフトを表す.
更にいうと,sの最も右の文字を左に移動させるという操作を1回~N-1回やったことに相当する.
なので,最終的に何文字分シフトされたかだけが重要で,更に,シフトされた文字数はmod Nで考えれば良い.
操作回数と何文字分シフトされたかmod Nを状態としてDPしてカウントすれば良く,愚直になるとO(Nk)だが早い言語で軽い処理をちゃんとかければ通るらしい.
実際には,何文字分シフトされたかmod Nは,1~N-1までは対称性より同じと見なせるので,O(k)でDPできる.

C言語のスパゲッティなコード

続きを読む

Croc Champ 2012 Round 2 A問題 - Trading Business (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 A問題 (500pt)
Problem description

問題概要

n個 (10以下) の惑星がある.
m個 (100以下) のアイテムがある.
それぞれの惑星で,それぞれのアイテムが,
 幾らで売られているか
 幾らで売れるか
 そのアイテム買うことのできる上限数(在庫数)
が与えられる.
宇宙船の容量kも与えられ,合計でk個のアイテムしか運べない.
初期資金は大量にあるとして,惑星をちょうど2個(1回ずつ)訪れるとき,儲けれる額の最大値を求める問題.

解法

訪れる惑星とその順番は全探索する.
どのアイテムを買うかは,売値と買値の差が大きい方からgreedyに買えば良い.
損をするものは買わない.

C言語のスパゲッティなコード

続きを読む

Round #115 E問題 - Power Defence (この記事を編集する[管理者用])

Source

RazMERiq 2012 E問題
Codeforces Round #115 E問題
Problem description

問題概要

タワーディフェンス系ゲーム.
敵が1匹,x軸を移動するので,与えることのできるダメージの最大値を求める問題.
タワーを建てれる場所は,y = -1, 1上の格子点のみで,同じ場所には2つ以上建てられない.
建てれるタワーの種類は以下3種類.
 タワー1,2 : 射程範囲内の敵に,毎秒いくらかのダメージを与える
 タワー3 : 射程範囲内の敵の移動スピードを遅くする
それぞれのタワーの種類に対して,射程範囲が与えられ,タワー1, 2に関しては攻撃力も与えられる.
敵の移動スピードは,1 / (1 + 影響を受けているタワー3の数).
それぞれの種類のタワーを何個まで建てることができるかが与えられる.建てられる合計数は20以下.

解法

本番では,以下で解いた.(おそらく想定解法ではない)
まず,タワーは一箇所に集中させた方が良い.
つまり,2m個置くなら (0, 1), (0, -1), (1, 1), (1, -1), ..., (m, 1), (m, -1) に置けばよいし,
2m+1個置くなら,追加で(m+1, 1)に置けば良い.
置き方は最悪で,20!/6!/7!/7!あるが,対称性を考えるとそんなに多くない.
つまり,(0, 1), (0, -1)を入れ替えても同じ置き方を満たせるし,左右反転しただけでも同じ置き方とみなせる.
対称なのを除去して,置き方を全部試すと,タイムリミットぎりぎりではあるけど通った.
その他の枝刈りとかは何も行なっていないので,枝刈ったりすると余裕を持って通るかもしれない.

おそらく想定解法は,タワー3の配置のみ全探索する.
これなら最大で20!/10!/10! = C(20, 10) < 2^20しかパターンはない.
タワー3の配置が決まれば,敵の移動スピードがわかるので,それぞれ空きマスにタワー1,2を置いたときのダメージ量が計算でき,DPにより最大ダメージが求められる.

C言語のスパゲッティなコード

続きを読む

Round #115 D問題 - Plane of Tanks: Duel (この記事を編集する[管理者用])

Source

RazMERiq 2012 D問題
Codeforces Round #115 D問題
Problem description

問題概要

2人でFPSゲームで銃の撃ち合い対戦する.
相手を倒せる確率を求める問題.
時間0では両者とも同時に攻撃する.
自分と敵のステータスとして,それぞれ
 HP : これが0になると倒され,以降攻撃できない
 DT : 攻撃間隔.このプレイヤーは時間0, DT, 2DT, 3DT, ... に攻撃する
 L, R : 最小攻撃力と最大攻撃力.攻撃が命中したら,敵のHPがL以上R以下のランダムの整数だけ減る.
 P : 攻撃を避けられる率.この確率で相手に全くダメージを与えられない.(整数%で与えられる)
が与えられる.
HPは200以下,DTは1以上30以下,攻撃力は10以上100以下.

解法

おそらく想定解法は以下の通り.
それぞれ何回攻撃を食らったら死ぬかという確率を十分大きな回数までDPで求めておく.
DPにおいて,R-L+1個の和を計算するとき,累積和を用いて高速化する.
後は,シミュレーションする.
避けられる率が100%の時は例外処理するのも良い.

本番では,以下で解いた.(おそらく想定解法ではない)
時間は周期LCM(DT1, DT2)で考えればよく,その間の攻撃回数はたかだか60回程度.
時間,自分のHP,相手のHPを状態にして,DPした.
DPする時,次に攻撃が命中する攻撃で場合分けし,ずっと当たらず時間が一周したら同じ状態に戻ってくるので,適当に処理する.
O((DT1+DT2)^2 * HP^2)ぐらい.

C言語のスパゲッティなコード

続きを読む

Round #115 C問題 - Geometry Horse (この記事を編集する[管理者用])

Source

RazMERiq 2012 C問題
Codeforces Round #115 C問題
Problem description

問題概要

コンボのあるシューティングゲーム的な何か.
N種類 (100以下) だけ敵の種類がある.
種類iはK[i]匹 (10^9以下) おり,倒した時にもらえる基本スコアはC[i] (1000以下) である.
好きな順番で倒して良い.
T個 (100以下) の整数P[i] (10^12以下) が与えられる.P[i] < P[i+1].
敵を既にP[i]匹以上倒している (かつP[i+1]匹倒していない) なら,敵を倒した時にもらえるスコアがi+1倍になる.
最終的に獲得可能な最大スコアを求める問題.

解法

Greedy.
だんだん倍率が高くなるので,スコアの小さい敵から倒していけば良い.
1匹ずつ処理するのではなく,同じ種類の敵がいなくなるか,倍率が変わるまで一気に処理する.

C言語のスパゲッティなコード

続きを読む

Round #115 B問題 - Plane of Tanks: Pro (この記事を編集する[管理者用])

Source

RazMERiq 2012 B問題
Codeforces Round #115 B問題
Problem description

問題概要

N回分 (1000以下) のゲームの結果が与えられる.
それぞれのゲームの結果は,プレイヤーの名前と点数が与えられる.
プレイヤーの名前はユニークであるとし,同じプレイヤーが何回もプレイしているかもしれない.
それぞれプレイヤーの最終得点は,プレイした中で最も高い得点とする.
総プレイヤー人数をMとして,各プレイヤーに対して,
 自分より点数が高いプレイヤーが50%*M以上いるなら noob
 そうでなく,自分より点数が高いプレイヤーが20%*M以上いるなら random
 そうでなく,自分より点数が高いプレイヤーが10%*M以上いるなら average
 そうでなく,自分より点数が高いプレイヤーが1%*M以上いるなら hardcore
 そうでなければ pro
と出力する問題.

解法

やるだけ.

C++言語のスパゲッティなコード

続きを読む

Round #115 A問題 - Robot Bicorn Attack (この記事を編集する[管理者用])

Source

RazMERiq 2012 A問題
Codeforces Round #115 A問題
Problem description

問題概要

N文字 (30以下) の数字から成る文字列が与えられる.
それは,0以上1000000以下の整数A, B, Cを繋げて書いたものである.
leading zerosは許されない.(0は良い)
A+B+Cの最大値を求める問題.
もしくは,そのようなA, B, Cの3つ組が存在しないならそれを指摘する.

解法

2ヶ所,何処で区切るか全探索する.区切り方はO(N^2)しかない.

C言語のスパゲッティなコード

続きを読む

SRM541 DIV1 MEDIUM - AkariDaisukiDiv1 (この記事を編集する[管理者用])

Source

TopCoder SRM541 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

長さ1以上50以下の文字列A, B, C, S, Fが与えられる.
10^7以下の正整数kが与えられる.
文字列から文字列の写像fを
 f(X) = A + X + B + X + C
で定める.ただし,ここで+記号は連結を表す.
 f^2(X) = f(f(X)), f^3(X) = f(f(f(X)))
とf^k(X)はfをk回作用させるとして,f^k(S)に部分文字列としてFは何箇所に含まれているかをmod 1000000007で求める問題.
含まれいる箇所はオーバーラップしていても良い.(その分重複して数える)

解法

XがFより長いとして,XにFが部分文字列としてn個含まれているとすると,
f(X)の中にFが何個あるかというと,
 2n + (AX の繋がってる部分でで新しく増えた分) + (XB の部分で増えた分) + (BXの分) + (XCの分)
となる.
XがFより短い間は,適当にfを作用させて,Fより長くなってから考える.
ところで,Xの最初と最後は,最終的に,AAA…,…CCCになるので,増分は一定に落ち着く.
なので,増分が一定になるまで計算して,一定になったら適当に計算を端折れば良い,

C++によるスパゲッティなソースコード

続きを読む

SRM541 DIV1 EASY/DIV2 MEDIUM - AntsMeet (この記事を編集する[管理者用])

Source

TopCoder SRM541 DIV1 EASY (250pt)
TopCoder SRM541 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

蟻が50匹以下,2次元平面上を歩く.
蟻の初期位置と,歩いている方角が与えられる.
初期位置は,座標の絶対値1000以下の格子点の何処かで,方角は上下左右のどれか.
歩く速度はすべての蟻が1で一定.
2匹以上の蟻が衝突すると,その瞬間,衝突した蟻が全部消える.
最終的に残る蟻の匹数を求める問題.

解法

衝突する可能性のある時間は0.5の倍数のみ.
また,衝突する可能性のある時間は2000以下だけ.
なので,時間を0.5ずつ進めながらシミュレーションすれば良い.
(座標が大きくなると,衝突する可能性のある時間を列挙してからシミュレーション)

C++によるスパゲッティなソースコード

続きを読む

2012 Qualification Round C問題 - Recycled Numbers (この記事を編集する[管理者用])

Source

Google Code Jam 2012 Qualification Round C問題
Problem Statement

問題概要

AとBは同じ桁の正整数.
整数xの下何桁かを,そのまま,xの左に移動させて,整数yが得られるとき,(x, y)の組を良いという.
A ≤ x < y ≤ Bで,良い組(x, y)はいくつあるかを求める問題.
A, Bはsmallは1000以下,lergeは2000000以下.

解法

xは全部試す.
実際に,右の何桁かを移動させて,それが条件を満たしているか調べれば良い.
1212みたいなときに,1桁移動と3桁移動で同じ組が得られるのを重複して数えてはいけない.
数えたものを記録しておいても良いし,何桁か移動してxに戻ったらそれで打ち切るなどとすれば良い.

Cによるスパゲッティなソースコード

続きを読む

2012 Qualification Round B問題 - Dancing With the Googlers (この記事を編集する[管理者用])

Source

Google Code Jam 2012 Qualification Round B問題
Problem Statement

問題概要

ダンスコンテスト.参加者はN人.
審査員が3人いて,それぞれの審査員は0点~10点 (整数) をつける.
参加者の点数は,その合計で決まり,30点が満点.
ただし,ある参加者に対して審査員の点数がばらけることは珍しく,
 審査員の点数の最大 - 最小が2を超えることはない
 審査員の点数の最大 - 最小が2となった参加者はちょうどS人いる.
N人の参加者の点数(それぞれ合計点のみ)が与えられる.
参加者の中で,少なくても1人の審査員からp点以上の評価を得た人数の最大値を求める問題.
Nはsmallは3以下,largeは100以下.
Sは可能な値.

解法

点数をtとして,
 (t+2)/3がp以上ならp点以上の評価が無条件に得られる
 最大 - 最小が2を超えても良いなら,(t+4)/3がp以上ならp点以上の評価が得られる (tが1以上なら)
S人は上に該当せず,下に該当する人にgreedyに振り分ければ良い.
ただし,t=0の時は,例外処理が必要で,この場合は絶対に全審査員の点数は0.

Cによるスパゲッティなソースコード

続きを読む

2012 Round 1A B問題 - Kingdom Rush (この記事を編集する[管理者用])

Source

Google code jam 2012 Round 1A B問題
Problem Statement

問題概要

Nステージからなるゲームがある.
ステージiは,
 すでにa[i]個の☆を獲得していれば,簡易クリア可能
 すでにb[i]個の☆を獲得していれば,完全クリア可能.
最初は☆を持っていない.
ステージを簡易クリアすると☆が1個もらえる.
ステージを完全クリアすると☆が2個もらえる.ただし簡易クリアしているステージに対しては追加で☆1個のみもらえる.
ステージは好きな順番にプレイできる.
☆を2N個集めるまでにステージをプレイしなければいけない回数の最小値を求める問題.
smallはNは10以下,largeはNは1000以下.

解法

Greedy.
完全クリア可能なステージに対しては,すぐクリアすれば良い.
そのうちクリアしなければならないし,クリアすることで不利になることもないから.
簡易クリアのみ可能なステージだけになったら,完全クリア可能な閾値の高いものから簡易クリアしていく.
完全クリア可能な閾値が低いものは,それによって,完クリか可能になり,プレイ回数が節減できるかもしれないから.

Cによるスパゲッティなソースコード

続きを読む

2012 Round 1A A問題 - Password Problem (この記事を編集する[管理者用])

Source

Google code jam 2012 Round 1A A問題
Problem Statement

問題概要

B文字のパスワードのうち,すでにA文字を打ち込んだ.打った文字は見えない.
ただし,打ち込んだ文字は間違えているかもしれない.
i文字目が間違えていない確率p[i]が与えられる.
バックスペースk回押すと,最後に入力したk文字を消すことができる.
Enterを1回押すと,間違えていたら,全てが消える.合っていればそれで終了.
パスワードを全部打ち込み終わるまでに押す平均キー数の最小値にする戦略をとった時,その平均キー数求める問題.
smallはAが3以下, Bが100以下.
largeはA, Bは100000以下.

解法

戦略は,  Enterを押して,もう1回全部打ち直す.(この場合B+2回必要)
 バックスペースをk回押して,打ち直す.間違えていたら全部もう1回打つ必要がある.
の2通りだけ考えれば良い.
最初のk文字が全部正しい確率とかは最初に求めておけば良い.

Cによるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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