Entries

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

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

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

Source

TopCoder SRM558 DIV1 EASY (275pt)
TopCoder SRM558 DIV2 MEDIUM (600pt)
Problem Statement

問題概要

Nマス (50以下) のグリッドにスタンプで色を塗りたい.
各マス最初は何も色が塗られていなくて,全てのマスについてRかGかBにしたい.
各マスについて,Rにしなければいけない,Gにしなければいけない,Bにしなければいけない,どれでもいい,が与えられる.
スタンプは1種類だけ買うことができて,長さLのスタンプはL*aだけコストが必要.
そのスタンプを押すには1回につきコストb必要で,グリッドからはみ出す場所に押してはいけない.
スタンプは1回押すと,長さLの区間が全部指定した色にできるが,別の色で塗られているグリッドの上はインクが混ざるので上書きしてはいけない.
最小コストを求める問題.
a, bは100000以下ぐらい.

解法

買うスタンプの長さLは全部試す.
DPで,どこまで塗ったかを状態に,次どこまで塗るかを全部試せば良い.

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

続きを読む

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

Source

TopCoder SRM557 DIV1 HARD (1000pt)
Problem Statement

問題概要

n要素の非負整数からなる数列が与えられる.nは50以下で,各要素は10^15以下.
好きなだけ以下の操作を行う.
 数列の要素A[i]とA[j]を取ってきて,A[i]をA[i] XOR A[j]に変える.(A[j]はそのまま,iとjは異なってなければならない)
最終的に得られる数列の各要素の和の最大値求める問題.

解法

Ad-hocかつgreedyにやる.色々やりかたはあるみたいだけど,以下は自分の解法.
まず最上位ビットが1な要素を1つだけにする.
その要素を取り除いた時に,最上位ビットが1なのを1つだけにする.
と繰り返していき,基底を作る.幾つかの要素は0になるが,それは最後に最大値とXOR取れば良いので除外して考える.
最上位ビットを保ったまま,それぞれの数字を最小化する.
それは,自分の最上位ビットより下位ビットしかないものとXORを取って減るならgreedyにXORを取るというのを繰り返せば良い.
次に最も大きい要素だけ最大値にする.それも,greedyにXOR取る.
後は,最大値以外の全ての要素は最大値とXORを取って終わり.
これで和が最大になる証明は難しくないと思う.

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

続きを読む

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

Source

TopCoder SRM557 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

n人の少女がいる.(50以下)
また,各少女が,各少女が愛しているかどうかが与えられる.
好きな少女を魔法少女にすることができる.
魔法少女になると,魔法少女が愛している少女を守ることができて,また,守られている少女が好きな少女も守られる.
守られていない魔法少女の数の最大値を求める問題.

解法

各少女について,その少女が魔法少女になれば結果的に守られる少女を調べるために,ワーシャルフロイドやら何やらしておく.
魔法少女になったら,自分を守ることになる少女は,魔法少女にするだけ損なので除外して考える.
するとグラフはDAGになって,最小パス被覆を求める問題になって,二部マッチングで解ける.

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

続きを読む

SRM557 DIV1 EASY - FoxAndMountainEasy (この記事を編集する[管理者用])

Source

TopCoder SRM557 DIV1 EASY (250pt)
Problem Statement

問題概要

n+1要素の数列を考える.(nは100000以下)
その数列は非負整数のみからなり,その階差数列 (D[i] = A[i+1] - A[i]) はすべて1か-1.
階差数列の連続する部分がmin(n,50)要素以下与えられる.
また,数列の初項A[0]と末項A[n]が与えられる.
そのような数列が存在しうるかどうかを判定する問題.

解法

階差数列で与えられない部分で,1の要素の数,-1の要素の数は計算可能. 後は0を下回らないように,1を全部使って,与えられた部分を使って,-1を全部使えば良い. 本番では,1を使う数は,0を下回らないぐらい使って,後はgreedyに0に近づくようにシミュレーションした.

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

続きを読む

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

Source

TopCoder SRM552 DIV1 HARD (900pt)
Problem Statement

問題概要

N以下の正整数で,以下の条件をみたすものがいくつあるかを求める問題.
 Nを素因数分解した時,出てくる素因数は全てM以下.
 素因数pを持つならば,素因数分解した時に,素数pは偶数回出てくる.(詳細は問題文参照)
Nは10^10以下,Mは10^6以下.

解法

基本的には枝刈り全探索すれば良い.
小さい素数から順番に,それが何回素因数分解した時に登場するかを決定していく.
ただし,(N / 現在の数) が (現在の素数の2乗) を上回ったら,後は2個以上の素数をかけることができないから,
何も書けない,1個素数をかける,しか選択肢がなく,かけることができる素数の数は簡単に求めれるから端折る.
計算量は謎いけど,最悪ケースで0.4秒以下ぐらいで終わった.

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

続きを読む

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

Source

TopCoder SRM552 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

N*M (30*30以下) のグリッドが与えられる.
各マスは,空白か,PかLが書かれている.
2つの核軸に平行な長方形型の領域を選ぶ.この時,共通領域があってはいけない.
長方形に含まれているPの数とLの数の差はmaxDiff (900以下) 以下でなくてはいけない.
長方形に含まれているPの数とLの数の最大値を求める問題.
条件をみたすように長方形を選べないときはそれを指摘する.

解法

まず,重ならないように長方形を選ぶというのは,少なくてもx座標か,y座標が共通部分を持っていない.
つまり,2つの長方形を分断するように縦か横に線を引ける.
線の場所で全探索する.(横に線を引くとして,グリッドを回転して2回処理した)

まず,そのマスより左上の長方形領域に含まれるPの数,Lの数を前計算しておく.
すると,包除原理より,ある長方形領域に含まれるPの数,Lの数はO(1)で計算できる.

ある長方形領域を選ぶとき,Pの数 - Lの数が等しいなら,Pの数 + Lの数が大きいほうが良いから,Pの数 - Lの数をキーとして,Pの数 + Lの数の最大値をメモする.
長方形領域の最初の行と最後の行を固定した時でDPした後,最初からある行までの範囲でDPしたりした.

実装方法によるけど,だいたいO(30^4)~O(30^6)程度になる.(6乗は下手に書くとTLEかも)
以下のコードはO(30^5).

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

続きを読む

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

Source

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

問題概要

問題文の図のようにボールを並べてN段の三角形を作りたい.
触れているボール通しは違う色でなければならない.
色は3色で,赤のボールの数がR個,緑がG個,青がB個使える.
最大で何個の三角形を作れるかを求める問題.
Nは10^9以下,R, G, Bは10^18以下.

解法

最初の2段は全部違う色でなくてはいけないし,後はボールの色は一意に定まってしまう.
結局は,全部だいたい同じ数だけボールが必要となる.
もうちょっと正確に言うなら,
 N mod 3 = 1の時,必要なボールの数はN(N+1)/3 = 3M+1となって,ある一色はM+1個,他の2色はM個必要
 その他の時,N(N+1)/3 = 3Mとなっと,全てのボールがM個必要
となる.

・解法1 (本番に書いたもの)
R >= G >= Bとする.(ソートする)
1個の三角形を作るのに必要なボールの数をそれぞれ a, b, c (a ≥ b ≥ c) とする.
答えは,
 min( floor(B/c), floor( (G+B)/(b+c) ), floor( (R+G+B)/(a+b+c) ) )
となる.(ボトルネックになる場所を全部調べる)
この問題では,実は,
 min( floor(B/c), floor( (R+G+B)/(a+b+c) ) )
で良い.(b=cであるから)

・解法2
N mod 3が1でないとき,答えは min(R,G,B) / Mとなる.(M = N(N+1)/6は三角形1個作るのに,それぞれの色の必要なボールの数)
N mod 3 = 1のとき,二分探索する.
K個作れるかためには,R-KM, G-KM, B-KMが負にならず,和 (R+G+B-3KM) がK以上でなければいけない.

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++によるスパゲッティなソースコード

続きを読む

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

Source

TopCoder SRM533 DIV1 HARD (1000pt)
Problem Statement

問題概要

N個 (30以下) の単語にピカチュー語を割り振る問題.
k番目の単語の出現頻度freq[k] (1以上1000以下) が与えられる.
k番目の単語に割りふるピカチュー語code[k]は以下を満たさなければいけない.
 code[k] は "pi", "ka", "chu" を何個か繋げてできる単語.(同じのを繋げても良い,pikapi, pikachuなどが可能)
 code[i] は code[j] のprefixになっていない.(i != j)
length(code[k]) * freq[k]の和の最小値と,最小値を達成できる割り当て方が何パターンあるかを mod 1000000009 で求める問題.

解法

メモ付き探索.freqの値はソートしておく.
最初使えるcodeは長さ0のコード1つのみとして,長さkのコードは,単語に割り振るか,長さk+2, k+2, k+3のコードを生成できると考える.
状態を,まだ割り振ってない単語の数,今使えるコードの種類として,以下のように探索していく.
 今使えるコードの種類のうち,最も長さの短いものの数をxとして,その内の何個を単語に割り振るかで場合分けする.(他はコード生成に使う)
 割り振る単語はfreqの高い方から割り振れば良い.割り振る単語の選び方のパターン数,freqが同率の場合はどれに割り振るかのパターン数を計算しながら探索する.
新しくコードを作るときは,残り単語数より多くのコードを生成しても意味無いので,作り過ぎないように適当に処理する.
以下のコードで最悪ケース0.072 sec.

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

続きを読む

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

Source

TopCoder SRM533 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

n*m (50*50以下) のグリッドが与えられる.各セルは#か.のどちらか.
好きな#のセルから初めて良いので,以下のような方法で,すべての#を削除できるかどうかを判定する問題.
 今いる場所の#を消し,
  現在の処理の回数が偶数回目なら,今と同じ行の#のセルに移動する.
  現在の処理の回数が奇数回目なら,今と同じ列の#のセルに移動する.
 最初に動くのは,0回目とする.(最初は同じ行内で動く)

解法

2つセットで考えると,X = #が奇数個ある行の数,Y = #が奇数個ある列の数とすると,
 Xは0以上1以下,Yは0以上2以下
を満たさなければいけないことがわかる.
また,自由に同じ行,同じ列にある#まで動くことができるとすると,すべての#のセルは連結でなければいけない.
逆に,以上の条件を満たせば,必ずすべての#を通るパスが存在することを示すことができる.

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

続きを読む

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

Source

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

問題概要

要素数Nの整数列が与えられる.各整数は1以上1000以下.
要素数が3以上なら,ある要素を消して,その両隣の数字の積を得点として得ることができる.
両端の要素は消せない.
最高得点を求める問題.
DIV1ではNは50以下.
DIV2ではNは10以下.

解法

逆から考える.
最初,両端の要素しかなく,まだ挿入してない要素を挿入すると,その両端の要素の積が得点として得られるとする.
すると,要素を挿入すると,それより左と右の区間は独立に考えることができるので,区間を状態としてDPすれば良い.
DIV2では全探索も可能.

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

続きを読む

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

Source

TopCoder SRM527 DIV1 MEDIUM (450pt)
Problem Statement

問題概要

n*m (30*30以下) のグリッド (rows) が与えられる.
また,m個だけ,長さnの文字列 (cols) が与えられる.
それぞれは,グリッド,文字は,0か1か?からなる.
?を0か1に変えて,以下の条件を満たすようにしたい.
 各グリッドを縦に読んで,得られるm個の長さnの文字列は,(順番を入れ替えると)colsに一致する.
条件を満たすグリッドのうち,辞書順最小のものを求める問題.条件を満たすグリッドは少なくても1つは存在することは保証されている.

解法

つまりは,各列をどの文字列に対応させれば良いのか,マッチング問題になる.
なので,条件を満たす?の変え方が存在するかどうかは判定することができる.
グリッドの?を最初の方から,1文字ずつ0に置き換えて,条件をみたすことができなくなったらそれは1に置き換える,とgreedyに置き換えていく.

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

続きを読む

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

Source

TopCoder SRM527 DIV1 EASY (300pt)
TopCoder SRM527 DIV2 MEDIUM (550pt)
Problem Statement

問題概要

0以上,10000以下の整数列a[1], a[2], ..., a[N]が与えられる.
N+1個のノードからなる全域木に対して,点数を以下のように定める.
 次数がkのノードに対して,a[k]点を与える.
 木の点数は,ノードの点数の合計.
全ての全域木の中で,最高点を求める問題.

解法

全域木であるので,ノード数はN+1,次数の合計は2N,次数の最低は1,最大はNを満たさなければいけない.
逆に,それを満たせば,そのような全域木を作ることはできる.
なので,現在使ったのノード数,使った次数を状態にしてDPすれば良い.

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

続きを読む

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

Source

TopCoder SRM529 DIV1 MEDIUM (600pt)
Problem Statement

問題概要

バッグ0~4のが5個あり,最初バッグ0にN個の石が入っている.(Nは10^12以下)
問題文に書かれている通りの動作を行った時,バッグに石を1個入れるという操作を何回することになるか mod 1000000009 で求める問題.
処理が終わらないならそれを指摘する.

解法

問題文の処理を噛み砕いて書くと,

  答え = 1;
  for(i=2;;i++){
    答え += 1;
    if(Nは正で,Nはiで割り切れる){
      答え += 3*N;
      答え += ceil(N/i)
      exit(0);
    } else {
      答え += 4*N;
      答え += ceil(N/i)
    }
  }

みたいな感じ.
ここで,iがどこで終了するかはO(sqrt(N))で計算でき,非自明な部分はceil(N/i)の和だけ.
これは,ceil(N/i)が一定になるiの範囲を計算して端折りつつ計算すればO(sqrt(N))でできる.
Nが0か1のときは終わらない.

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

続きを読む

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

Source

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

問題概要

N人 (50以下) の王様の名前が与えられる.
王様の名前は,
 アルファベット大文字1文字+アルファベット小文字で何文字か+半角スペース1文字+50未満のローマ数字
というフォーマットになっている.
半角スペースより前のアルファベットの早い順,アルファベット部分が同じなら,ローマ数字の小さい順にソートする問題.

解法

やるだけ.

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

続きを読む

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

Source

TopCoder SRM532 DIV1 HARD (1000pt)
Problem Statement

問題概要

N行M列のグリッドがある.
各セルに1以上K以下の数字を1つ書くのだけど,以下の条件を満たす書き方は何通りあるかをmod 1000000007で求める問題.
 任意の2つの行A, Bに対して,少なくても1つの数字が存在して,行Aに含まれるその数字の数と行Bに含まれるその数字の数は異なる
Nは10以下,Mは50以下,Kは100以下.

解法

他にも方法があるみたいだけど自分が解いた方法.
まず,Mの分割数を列挙する.
 M = A + B + C + ... (A ≥ B ≥ C ≥ ...)
として,ある行に対して,最も多い数字がA個,次に多い数字がB個,…,となる
数字の選び方と,数字を選んだとき1行に並べるパターン数を計算する.
後は,今何行埋めたか,を状態として,その数字の選び方のうち何個使うかで場合分けするDPする.
素直にやって,組み合わせの数とかを事前計算したり漸化式でうまく計算するとO(N^2 * Mの分割数)となるが微妙にタイムリミットが厳しい.
分割数を列挙して組み合わせの数を計算した時,「数字を選んだとき1行に並べるパターン数」が一致するものを全部まとめておくと最悪ケースで4倍ぐらい早くなって間に合うと思う.

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

続きを読む

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

Source

TopCoder SRM532 DIV1 MEDIUM (450pt)
Problem Statement

問題概要

N, M, Kが与えられた時,以下の条件を満たす無向グラフの数をmod 1000000007で求める問題.
 ノード数N (30以下) で,枝数M (30以下)
 各ノードの次数は偶数 (0でも良い,同じノード間にたくさん枝があっても良い)
 ノードAとノードBの間に枝があるならば,|A-B|はK以下.ただしノード番号は1からNまでとする.Kは8以下.

解法

DPする.
少なくても状態は,今見ているノード番号(N),すでに使った枝の本数(M),自分とK個先までの次数の偶奇(2^(K+1))が必要.
ノード番号が小さい方から見て行って,枝を追加していく.
枝を追加していく順番に依存させないために,最後に枝を追加した相手のノード番号(K)も覚えておくと良い.
すると,状態数はN*M*K*2^(K+1)ぐらいになる.

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

続きを読む

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

Source

TopCoder SRM532 DIV1 EASY (300pt)
TopCoder SRM532 DIV2 MEDIUM (600pt)
Problem Statement

問題概要

N個 (50以下) の文字列が与えられる.
各文字列は三文字からなり,各文字は数字か.のどちらか.
文字列のスコアとは,数字のみからなる部分文字列のうち,数字の和が最大のもの.
好きな順番で文字列を連結した時,その文字列のスコアの最大値を求める問題.

解法

ad-hoc.
数字のみからなる部分文字列が,複数の文字列から作られるのならば,全部数字の文字列は間に自由に入れれる.
なので,全てが数字の文字列の数字の和を最初に求めておいて,その左右につける文字列を全探索すれば良い.
1つの文字列からなるものが最大になる場合もあるので気をつける.(.9. ..1 111 1..など)

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

続きを読む

SRM531 DIV2 EASY - UnsortedSequence (この記事を編集する[管理者用])

Source

TopCoder SRM531 DIV2 EASY (250pt)
Problem Statement

問題概要

50要素以下の整数の配列が与えられる.(各要素は1以上1000以下)
順番を自由に入れ替えて,昇順ソートされていないような,辞書順最小のものを求める問題.
存在しないならそれを指摘する.

解法

sortしてから1回next_permutationする.
next_permutationしないなら,最後から見て,隣り合う値が違う最初の場所をスワップしてあげれば良い.
存在しないのは,すべての要素が同じ値の時.

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

続きを読む

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

Source

TopCoder SRM531 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

この世の中にはN種類 (50以下) のモンスターがいる.
最初は,種類1のモンスターが1匹だけいる.
各種類のモンスターはちょうど1日で死に,死んだ時に,新しくモンスターを生み出し,そのとき,新しく生み出されるモンスターの種類の番号が与えられる.
各種類が死んだ時に生み出されるモンスターの数は1以上24以下ぐらい.
総モンスター数は,無限に増えるかどうかを判定し,有限に収束するなら,最終的なモンスター数 mod 1000000007で求める問題.

解法

増え続けるなら,N日に1日は必ず増える.有限にとどまるなら,N日以内に収束する.
なので,2N日以上ぐらいシミュレーションしてあげれば良い.
ただし,modを取りながらシミュレーションすると,増え続けているのに,見かけ上収束する可能性があるので,そこだけ注意する.
回避法は,複数のランダムなmodを試して,本当に収束してるか確認する方法(以下のコードはこれ)や,
グラフの形を見て,発散するかどうかを最初に判定して上げる方法がある.
グラフの形が,種類Kは,種類1からいつか作られるモンスターで,種類Kから種類Kはいつか作られ,種類Kから一度に作られるモンスターが2匹以上,
みたいなKが存在すれば無限に増える.

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

続きを読む

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

Source

TopCoder SRM531 DIV1 EASY (300pt)
TopCoder SRM531 DIV2 MEDIUM (600pt)
Problem Statement

問題概要

以下の条件をみたすように,1~N (Nは100以下) までの数字をP個 (N以上100以下) 並べる方法の数をmod 1000000007で求める問題.
 同じ数字は,間に少なくてもM個 (0以上N以下) の違う数字を挟まなければいけない.
 すべての数字は少なくても1回は登場しないといけない.

解法

2個目の条件,全ての数字は少なくても1回は登場しないといけない,を忘れると,簡単に計算できるので,包除原理する.(以下のコードはこっち)
もしくは,今何番目か,1回以上使った数字の種類数,を状態にしてDPしても良い.

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

続きを読む

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++によるスパゲッティなソースコード

続きを読む

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++によるスパゲッティなソースコード

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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