Entries

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

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

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

Source

TopCoder SRM530 DIV1 HARD (900pt)
Problem Statement

問題概要

相異なる0以上50以下の整数からなる配列Sを考える.(要素数Nは50以下,与えられるわけではない)
ある要素を1増やして,ある要素を1減らす,という操作を繰り返すことで,配列Sを昇順にソートした.
操作の回数は最小回数でソートし,ソートした後の配列Tとなった.
操作の回数とTが与えられた時,考えうるSの数をmod 1000000009で求める問題.
操作の回数は650以下.

解法

S[i]がT[i]より大きければ,S[i] - T[i]回だけS[i]を減らす操作を行わないといけないので,操作の最小回数は
 max(0, S[i] - T[i])の和
となる.同様に増やす操作の数を考えると,これは
 max(0, T[i] - S[i])の和
にも等しく,更に
 |S[i] - T[i]| / 2 の和
とも等しい.この問題を考えるときは最後のを用いる.
S[i]はT[i]の置換なので,各iに対して,T[i]とどのT[k]を対応付けるか,を探すことになる.
わかりにくいので,T1[i] = T2[i] = T[i]とすると,T1[i]とT2[k]を対応付けると,
 kがiより大きい時,T[k]回プラス,T[i]回マイナス
 kがiより小さい時,T[k]回マイナス,T[i]回プラス
していって,合計回数がmoves*2になるものの対応の数を求める問題になる.
このとき,kがiより大きいか小さいかだけによって,プラスマイナスが反転する,つまり,kは具体的に決める必要はないことに注意する.
また,T1[i]と対応付けるT2[k]を考えるのと同時に,T2[i]と対応付けるT1[m]も考える.
この時,iとkの大小関係,iとmの大小関係で,4パターンある.
kやmの方が小さいときは,今まで自分より大きいものと対応させたのと対応させなければならない.
ので,
 i

 今まで大きいものと対応させた数 - 今まで小さいものと対応させた数

 現在の回数
を状態としてDPする.
今まで大きいものと対応させた数 - 今まで小さいものと対応させた数はT1とT2で別々に所持しなくても,同じになる.
重複してカウントしないために,大きいものと対応させる時か,小さいものと対応させる時かのどちらかしか,残ってる大きいもの,小さいものの数をかけてはいけない.

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

続きを読む

SRM530 DIV1 MEDIUM - GogoXMarisaKirisima/DIV2 HARD - GogoXReimuHakurai (この記事を編集する[管理者用])

Source

TopCoder SRM530 DIV1 MEDIUM (500pt)
TopCoder SRM530 DIV2 HARD (1000pt)
Problem Statement (DIV1)
Problem Statement (DIV2)

問題概要

ノード数N (50以下) の有向グラフが与えられる.
自分に枝が張られていたり,同じノード間に2本枝があったりはしない.
ノード0からノードN-1に移動するのを,以下の方法で繰り返すとき,最大で何回ノード0からノードN-1に移動できるかを求める問題.
 ノード0からノードN-1に行くのに,今まで使ったことのない枝を少なくても1個通らなければいけない.
 (そのパスの途中にノードN-1を含んでも良い)
 ノードN-1についたら,枝を使わず,ノード0にジャンプできる.
DIV2の場合のみ,グラフはDAGで,ノードiからノードjに枝があるならi < jでなければならない.

解法

使えるノードをノード0,N-1以外で,ノード0からノードN-1に移動する際に通ることのできるものとする.
同様に使える枝を,ノード0からノードN-1に移動する際に通ることのできるものとする.
すると答えは,
 使える枝数 - 使えるノード数
になる.
なぜなら,ノード0,N-1以外で新しいノードにたどり着いたときは,そのノードに来るとき使った枝,出ていくときに使った枝,2本消費してしまう.
そうでなければ,すでにたどり着いてるノードからは,今まで使った枝のみで0から来れ,N-1にいけるので,枝の消費1本で1回だけN-1まで移動できるから.
(DIV1もDIV2も解答はこの方針は同じ)

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

続きを読む

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

Source

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

問題概要

50*50以下のグリッドと,そのサイズ以下のスタンプが与えられる.
グリッドはすでにいくらか黒くて,スタンプは押すと黒くなる場所が与えられる.
スタンプは回転することができず,はみ出して押すことも,すでに黒くなってる場所が,さらに黒くなるようにも押せない.
グリッドを全部黒くすることが出来るかどうかを判定する問題.

解法

greedyにスタンプを左上から押せるだけ押していけば良い.
そして,全部黒くなるかどうかを判定する.
これで良い理由は,グリッドの一番左上の白い場所は,スタンプの一番左上の黒くする場所に対応しなければいけないから.

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

続きを読む

SRM526.5 DIV2 HARD - MagicNaming (この記事を編集する[管理者用])

Source

TopCoder SRM526.5 DIV2 EASY (1000pt)
Problem Statement

問題概要

アルファベット小文字のみからなる50文字以下の文字列が与えられる.
それは,n個の単語を,繋げたもので,繋げ方n!通りある中の,繋げたあとの文字列が辞書順で最小になるように繋げたものである.
考えうるnの最大値を求める問題.

解法

例えば,文字列A, B, C, Dを繋げた時,ABCDが辞書順最小になるための必要十分条件は
 AB ≤ BA, BC ≤ CB, CD ≤ DC
と2つの隣り合う文字列をひっくり返しても,辞書順で早くならないことである.
ということで,最後に使った単語の場所を状態として,それ以降の文字列を最大で何個に分割できるかというDPをすれば良い.

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

続きを読む

SRM526.5 DIV2 EASY - MagicStonesStore (この記事を編集する[管理者用])

Source

TopCoder SRM526.5 DIV2 EASY (250pt)
Problem Statement

問題概要

1以上1000以下の整数nが与えられる.
 p + q = 2n
となる素数が存在するかどうかを判定する問題.

解法

すべてのp, qを試しても良いが,
 4以上の偶数は2つの素数の和で書ける
というゴールドバッハの予想がある.(証明はされていないが,反例も見つかっておらず,当然小さい範囲では反例はない)
ので,n=1の時以外は存在する.

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

続きを読む

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

Source

TopCoder SRM526.5 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

雪の結晶が1個ずつ降る.その後の各マス目の綺麗さの和を求める問題.
N要素 (50以下) の整数配列Rとamountが与えられる.Rの各要素は10000以下,amountの各要素は10000以下.
雪の結晶の振り方は,各iに対して,amount[i]回だけ以下の様に降らす.
 x座標,y座標の絶対値がR[i]以下の格子点をランダムに1つ選び,そこに降る.
各マス目の綺麗さは,そのマス目に降った雪の結晶の数の2乗.

解法

Rが小さい方から処理する.
各雪の結晶が降った時,どれだけ綺麗さが増加するかというのは,そのマスにすでに降ってる雪の数に対して線形なので,期待値の線形性が使える.
ので,増加量は単純に計算できるので,O(降る雪の結晶の数)でシミュレーションすれば良い.(和をまとめて計算するとO(N)でできる)
本番の解答(以下のコード2)は,Rが大きい方から処理して,雪の結晶がk個ある点の個数の期待値を状態とするDPをした.
O(古雪の結晶の数^2)だが,十分に小さい確率は無視するぐらいの枝刈りを行った..
もちろんTLEするのだが,ジャッジデータが弱くて通ってしまった.

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

続きを読む

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

Source

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

問題概要

最初,1~Nまでの整数が順番に書いてある.(Nは1000000000以下)
以下の操作を繰り返すとき,一番最後に削除される整数を求める問題.
 平方数番目を同時に消す.つまり,1番目,4番目,9番目,…,を消す.
 消されて空白になった場所を詰める.

解法

色々解法はある.
以下のコードの方法は,
 N - 一番最後が削除される回数
が答えで,一番最後が消されるかどうかだけチェックしながらシミュレーションした.
証明は可能だけど自明じゃない.
他には,答えには規則性があるので,Nが小さい時に愚直にシミュレーションして規則を探す,とか,
時間的に最後の削除から順番にgreedyにシミュレーションする方法などがある.

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

続きを読む

Facebook Hacker Cup 2012 Qualification Round 3問目 - Alphabet Soup (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Qualification Round 3問目

問題概要

アルファベット大文字,半角スペースのみからなる文字列が与えられる.文字列の長さは1000以下.
その中に含まれる文字を自由に切り取って使って,HACKERCUPという文字列は最大で何個できるかを求める問題.

解法

 文字列に含まれるHの数,文字列に含まれるAの数,文字列に含まれるCの数/2,文字列に含まれるKの数,…,文字列に含まれるPの数
の最小値が答え.
HACKERCUPにはCが2回出てくるので,Cに関してだけ2で割るのを忘れないように.

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

続きを読む

Facebook Hacker Cup 2012 Qualification Round 1問目 - Billboards (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Qualification Round 1問目

問題概要

幅W,高さHの板に文字を書く.幅と高さはそれぞれ1000以下.
書く文字は与えられて,単語と単語の間は,スペースを入れるか改行する.文字数はスペースも入れて1000以下.
フォントサイズ(整数)を決めたら,全ての文字とスペースは,それぞれ高さと幅が両方共そのフォントサイズになる.
その板に書ききれる最大のフォントサイズを求める問題.
フォントサイズが1でもダメなら0を返す.
幅12の板にフォントサイズ4の文字を3文字書くことはできるが,幅11には無理.

解法

愚直にフォントサイズを1から順番に,書ききれるかどうか調べれば良い.(もちろん二分探索しても良い)
どこで改行するかはgreedyに,次にくる単語がこの行に書き切れないときに改行すれば良い.
一行に収まらない単語があるときなどはダメなことに注意.

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

続きを読む

Round #102 DIV1 D問題 - Help Shrek and Donkey 2 (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 D問題 (2000pt)
Problem description

問題概要

2人でゲームを行う.validな行動ができなくなった方の負け.
先手必勝か,後手必勝か,永遠にゲームが終わらないかを判定する問題.
n行m列 (100*100以下) のグリッド上に,駒がいくらかある.先手の駒は緑 (G) ,後手の駒は赤 (R).
各行には,駒は2駒以下しかない.
各ターンでは,1駒以上,k駒以下,自分の駒を選んで1マス以上,左右 (同じ行にとどまるよう) に動かす.
ただし,駒を飛び越えたり,盤面の外に出たり,駒をクロスさせるようなことはできない.
また,各ターンの行動は,attackかretreatかを選ばなくてはならなくて,
 attackを選べば,動かす駒は全て,同じ行の敵駒に近づくように動かさなければならなく,
 retreatを選べば,動かす駒は全て,同じ行の敵駒から離れるように動かさなければならない.
同じ行に敵駒がいなければ,その駒はどちらの方向に動かしても良い.

解法

まず,自駒があって,敵駒がいない行があって,しかもそれを1マス以上動かせるなら,そのプレイヤーは負けない.
両方負けないなら,引き分けで,永遠にゲームが終わらない.
勝つ方法は,相手に近づけて,端に追い込んで動けなくすれば良い.
離れることには意味はない(得にならない).離れた分だけ,相手が近づけば同じ状況になるから.
なので,間を近づけることを考えると,n個のNimを考えているのと同じ事になる.
片方だけ,負けない(自由に動かせる駒がある)なら,手番をパスできることに相当するので,必ず勝てる.
Nimのgrundy numberは,石の数,この場合は,自駒と敵駒の間のマスの数.
k個までNimを同時に進行できるので,n個のgrundy numberを2進数表示して,2^iの桁の和 (n個の数字の和) が全てk+1で割り切れるならば,先手の負けとなる.

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

続きを読む

Round #102 DIV1 C問題/DIV2 E問題 - Help Caretaker (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 C問題 (1500pt)
Codeforces Round #102 DIV2 E問題 (2500pt)
Problem description

問題概要

n*m (9*9以下) のグリッドに,Tの字のピース (問題文の図を参照,90度単位で回転しても良い) を最大で何個置くことが出来るか.
置ける数と,置き方を1つ求める問題.

解法

枝刈り全探索.
既においた数 + まだ見ていないセルのうち空きセルの数/5 が現在見つかってる答え以下なら枝刈り,で十分間に合った.
また,多少間に合わない程度なら答えを埋め込めば良い.
DPでも解けるっぽいのだけど,DPの方が計算時間も長くなるし,実装も複雑.(2行分だけ覚えておけば良いのでO(n*m*2^(2m))程度の状態数)

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

続きを読む

Round #102 DIV1 B問題/DIV2 D問題 - Help General (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 B問題 (1000pt)
Codeforces Round #102 DIV2 D問題 (2000pt)
Problem description

問題概要

n*m (1000*1000以下) のチェス盤を考える.
その上で,互いに攻撃できないようにナイトの駒を置くと,最大で何個置くことが出来るかを求める問題.

解法

対称性より,n ≤ mとする.
n=1の時は,全てに置けば良い.
n=2の時は,詰めておくことで,2*2において,次に2*2は置かない,とそれを繰り返すのが最適.
その他の時は,市松模様のように,行番号+列番号が2で割り切れる場所に置くと,ceil(n*m/2)個置ける.

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

続きを読む

Round #102 DIV1 A問題/DIV2 C問題 - Help Farmer (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 A問題 (500pt)
Codeforces Round #102 DIV2 C問題 (1500pt)
Problem description

問題概要

1以上10^9以下の整数nが与えられるので,
 n = (A-1) * (B-2) * (C-2)
を満たす正整数A, B, Cに対して
 A*B*C - n
の最小値と最大値を求める問題.
ストーリーは,最初,高さA,幅B,奥行きCの場所に1*1*1のレンガがABC個あった.
(地面に接する面は除き)表面のレンガが焼きただれて,n個残った.
焼きただれたレンガの個数の最小値と最大値を求める.

解法

A, B, Cの全組合せを試せば良い.
それは,n=xyzみたいに分解すればよくて,x ≤ y ≤ zと仮定すれば,xはn^(1/3)まで探す,yは(n/x)^(1/2)まで探す,とすれば良い.

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

続きを読む

UVa 12400 - 3, 2, 1, 0 (この記事を編集する[管理者用])

Source

7th Contest of Newbies (2011-12-31)
UVa 12400

問題概要

整数N, M, Kが与えられる.(N, Mは0以上999以下,Kは1以上999以下)
10進数表示でちょうどK桁で,2と3しか含まず,3の数がN個以下,2の数がM個以下のもののうちで,2進数表示で下K桁が全部0のものを求める問題.
複数存在するなら最小のものを求め,1つも存在しないならそれを指摘する.

解法

実は,NとMを無限と思うと,各Kに対して答えが一意に定まる.(小さいケースで全探索するなどすると確かめられる)
そして,その答えは,K-1の答えの頭に2か3のどちらかをつけたものになる.
K=999のときの答えを予め計算しておいて埋め込んだ.
後は,2の数,3の数が足りているかどうかチェックするだけ.

UVa 12401 - Metal Powers (この記事を編集する[管理者用])

Source

7th Contest of Newbies (2011-12-31)
UVa 12401

問題概要

a = (1+sqrt(5))/2, b = (2+sqrt(8))/2, c = (3+sqrt(13))/2 とする.
a^n, b^n, c^n を最も近い整数に丸めたものを答える問題.nは10^8以下.
ただし,答えが10桁以上になるなら,最初の3桁と最後の3桁と桁数を求める.
問題文に書かれているヒントは,a^n + (1-a)^nは任意のnについて整数になる.
a^n, b^n, c^nはそれぞれ,nが大きくなると,整数に近づく,など.

解法

b^n + (2-b)^n,c^n + (3-c)^nも常に整数で,
例えば,b^n = x + y sqrt(8)と書くと,(2-b)^n = x - y sqrt(8)となるので,
nが大きいときは,b^nに最も近い整数は2xになる.
nが小さい時は,doubleで計算して,そのまま出力する.
桁数と上3桁を求めるのは,doubleで対数を計算すればなんとかなる.
下3桁は,上の事実から,x, yに対する漸化式を立てて行列べき乗に落として,mod 1000で計算する.
ただし,行列の各要素は,半整数 (1/2の倍数) になるが,その行列をいくつ掛けても半整数でかけるという性質がある.
ので,行列を2倍しておいて,掛け算するたびに,1/2倍しておくなどして,うまく計算する.

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

Source

7th Contest of Newbies (2011-12-31)
UVa 12399

問題概要

同じコンテストのB問題の逆バージョン.
最終状態が与えられるので,それを達成するボタンの押し方のうち,最も少ない手順で達成するものを1つ求める問題.
答えが存在しないならそれを指摘する.

解法

同じマスを10回以上押す必要はない.
上の6マスの押す回数を決めると,下3マスは一意に定まる.
ので,10^6パターン全部試せば良い.

UVa 12398 - NumPuzz I (この記事を編集する[管理者用])

Source

7th Contest of Newbies (2011-12-31)
UVa 12398

問題概要

3*3のマスに最初全部数字の0が書いてある.
あるマスのスイッチを押すと,そのマスと,その上下左右のマス (があれば) そのマスの数字を1増やす.
ただし,9の場合1増やすと0になる.
200回以下押したとして,押したマスの列が与えられるので,最終状態を求める問題.

解法

シミュレーション.やるだけ.

UVa 12397 - Roman Numerals (この記事を編集する[管理者用])

Source

7th Contest of Newbies (2011-12-31)
UVa 12397

問題概要

問題文の図のようにマッチを使ってアルファベットを作る.
与えられた整数N (1以上3999以下) を標準的なローマ数字で表すときにマッチ棒が何本必要かを求める問題.

解法

やるだけ.
図から使っているマッチ棒の数を数える時は,黒い部分の数を数えるとわかりやすい.

Appendix

Recent Articles

ブログ内検索

Ads


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