Entries

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

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

SRM528 DIV1 HARD - ColorfulCookie (この記事を編集する[管理者用])

Source

TopCoder SRM528 DIV1 HARD (1000pt)
Problem Statement

問題概要

N個 (50以下) の正整数が与えられる.各整数は2000以下.
整数P1, P2が与えられる.これらは50以上2000以下.
以下の操作を好きなだけやって,得られる得点の最大値を求める問題.
N個の中から異なる2つの整数を選んで,片方からP1だけ減らし,片方からP2だけ減らし,P1+P2点を得る.ただし,整数が負になってはいけない.

解法

1回の操作で得られる得点は一定なので,何回操作できるか,P1減らす,P2減らすをどのように振り分けるかを考えれば良い.
まず,操作の回数の最大値は1000.
P1減らす操作と,P2減らす操作を,別々にできるとするならば,DPで,P1をk回減らす操作を行った時,残りからP2減らす操作を行うことのできる最大値を求めることができる.
このDPはO(50*1000*2000/50)程度.
残りの制約は,P1とP2は同じ回数でなければいけないのと,同じ要素からいっぺんにP1とP2を同時に減らせないこと.
前者は簡単で,後者は,全体の操作回数がMとして,一つの要素から合計でM回以下しか減らしてないなら,適当に振り分ければ可能.
Mの値を決めつければ,DPによってそれが達成できるか判定可能なので,二分探索すれば良い.
自分の解答では,基本的に小さいケース以外は振り分けれてしまうので,Mの最大値を求めて,少しずつ減らしながら調べた.

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

続きを読む

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

Source

TopCoder SRM528 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

長さN (40以下) のoかxからなる文字列が与えられる.文字列の長さNは偶数.
互いに共通部分のない長さN/2の部分列を2つ選んで,それを一致させる方法は何通りあるかを求める問題.
つまり,N/2文字選んで,それだけ取り出して順番を変えずにくっつけた文字列と,残った文字をそのままくっつけた文字列が一致するようなN/2文字の選び方の数を求める問題.

解法

解法を何通りかある.
部分列に含まれるoの数とxの数は簡単に計算可能で,それから考えうる部分列は最大でもC(20,10)通り.
後は,O(N^2)のDPでそれぞれに対して選び方のパターン数をカウントする.(自分の解答はこれ)
他の方法は,文字列を半分に分けて,それぞれ全列挙で2^(N/2)パターン作って,くっつける.
後は,どこまで文字を処理したか,まだ一致していない部分の文字列を状態としてDPしたとしても,一致してない部分の文字列は長さ20までしか考えなくてよいので,状態数は最大で40*2^20でなんとかなる.

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

続きを読む

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

Source

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

問題概要

うなぎを切って,ちょうど長さ10の破片をできるだけたくさん作る問題.
要素数N (50以下) の整数列が与えられる.(各要素は0以上1000以下)
maxCut回以下だけ,次の操作ができる.(maxCutは1000以下)
ある要素xを取り除いて,0より大きくxより小さい整数yを選び,2つの要素x-yとyを加える.
最終的に,10の数の最大値を求める問題.

解法

greedy.
yとしては10以外を選ぶ必要はない.
x-yとして10になると1回得するので,できるだけその回数を増やしたい.
10の倍数で,小さいものから切っていく,10の倍数がなければ何でもいいから切っていく.
どのうなぎまで処理したか,切れる残り回数を状態としてDPしても良い.O(50*1000^2)程度.

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

続きを読む

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

Source

TopCoder SRM526 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

2人でゲームを行う.打つ手がなくなったら負け.
それぞれ,勝てるなら最短ターンで勝つ,負けるなら最長ターンで負けようと動く.
ゲームは,何ターンでどちらの勝利で終わるかを求める問題.
最初数字 N (474747以下) が書かれている.
その数字を1以上K以下引いた数字に書き換える.(KはN以下)
ただし,書き換える数字は,先手は素数,後手は合成数になるように書き換えなければいけない.

解法

Mをとても大きい数字として,Kターンで勝てる状態をM-K,Kターンで負ける状態をKとする.
すると,状態遷移先の最小値を見つければ良い.
seg treeやヒープなどを使えばlog Nかlog Kで見つけることができる.(seg tree使うと結構時間ぎりぎりになる)
greedy解もあるが,難しい.(勝つ側は出来るだけ多く減らし,負ける側は少なく減らす.向かう場所は3か合成数がたくさん連続している場所.細かい部分で色々注意)
素数の最大の幅は120程度で,それを超えるときgreedyで,それ以下の時,愚直なO(NK)のDPという方法もあるらしい.

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

続きを読む

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

Source

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

問題概要

50*50以下の盤面に,何匹かアヒルがいる.
各行には高々1匹のアヒルしかおらず,各列にも高々1匹のアヒルしかいない.
1回の手順で,1匹のアヒルを上下左右に1マス動かすことができる.
縦か横に,すべてのアヒルを連続するように並べるための最小手数を求める問題.

解法

縦に並べるか,横に並べるか,両方試せばよいが,実は各行各列に1匹しかいないことから,片方だけでいいことがわかる.
x座標y座標別々に考えて,一致させるには中央値に移動すればよく,連続させるには,中央値を中心になるように連続させれば良い.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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