Entries

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

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

February 2011 Challenge 6問目 - Rush Hour (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 6問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

箱入り娘パズル.
12*12以下の盤面に,1*2または1*3または2*1または3*1の車が26種類以下配置されている.車にはユニークなアルファベットが割り当てられている.
aの車は横2マス,縦1マスであることが保証されている.
aの車を右端に移動するまでに必要な最小ステップ数を求める問題.
横長の車は横にしか,縦長の車は縦にしか動かせない.1度に動かすマス数は任意だが,車を飛び越えたり,他の車と重なるように動けない.
答えは10以下であることが保証されており,テストケースはランダムに生成される.(意地の悪い人工的なテストケースはない)

解法

枝刈り全探索DFSで通った.(想定解法はIDA*らしい)

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

続きを読む

February 2011 Challenge 5問目 - Milestones (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 5問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

二次元平面上のN個 (10000以下) の点が与えられる.
最も多くの点がのっている直線の上には何個の点がのっているかを求める問題.
N個の点は,二次元平面上に7個の直線があって,そのどれかの直線上にあると仮定して良い.(7個の直線は与えられない)

解法

ある点を原点に平行移動して,各点までのx軸からの角度 mod πを求めて,それが等しいものが同じ直線上にのっているとみなせる.
最初に選ぶ点は全ての点を選ばなければいけないはずだが,少なくても答えはN/7以上であるので,適当にいくつか選ぶと十分に高い確率で正しい答えが見つかる.

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

続きを読む

February 2011 Challenge 4問目 - Glass Measurement (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 4問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

n個 (10以下) の正整数 x[k] が与えられる.
ある数字Zがx[k]の和で表せれるとは,
 Z = (x[1]+x[1]+…) + (x[2]+x[2]+…) + …
と書けること,つまり,非負整数y[k]が存在して
 Z = Σx[k]*y[k]
となること,である.
この問題でやるべきことは以下の2つ.
 x[k]の和でかけない最大の正整数を求めること.ただし存在しないならそれを指摘する.
 10^7個以下の整数が与えられ,それらの内,何個がx[k]の和で書けるか調べること.
x[k]はそれぞれ10^7以下で,x[k]の中に少なくても1つは10^5以下のものが存在する.

解法

最小のx[k]をXと書くことにする.
aがx[k]の和で表せるなら,a+Xも当然x[k]の和で表すことができる.
よって,a = 0, 1, ..., X-1 に対して,a+m*Xがx[k]の和で表すことのできる最小のmを求めることを考える.
 Z = a+m*X
が表せるなら,
 (Z+x[k]) mod X + floor( (Z+x[k])/X ) * X
も表せるので,ノードaからノード(Z+x[k]) mod Xにコストfloor( (X+z[k])/X ) - mの枝を張る.
こうしてできたグラフ上でダイクストラすることで,全てのaについて,a+m*Xが表すことのできる最小のmが求まる.
後は適当にやるだけだが,タイムリミットの設定が微妙に厳しめなので,できるだけ効率のよいコードを書くと良い.

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

続きを読む

February 2011 Challenge 3問目 - Counting Terms (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 3問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

 (x[1] + x[2] + … + x[k])^n mod p
を展開したときの項の数をmod 1000003で求める問題.
k, nは10^15以下,pは100以下.

解法

規則性を探して解いた.
実際に試してみると,nをp進数表示したとき,
 n = (… a[2] a[1] a[0])_p
となったとすれば,答えは
 Comb( k-1+a[0], a[0] ) * Comb( k-1+a[1], a[1] ) * Comb( k-1+a[2], a[2] ) * …
のmod 1000003になることがわかる.
後は,桁ごとに見てやってDPすれば解ける.

C言語のスパゲッティなコード (上が自分の解答コード,下が規則を探すのに用いたコード)

続きを読む

February 2011 Challenge 2問目 - Coloring Colorable Graphs (チャレンジ形式) (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 2問目 (チャレンジ形式)
Problem Statement
February 2011 Challengeの参加記録

問題概要

ノード数N (500以下),枝数M (10000以下) の3彩色可能な無向グラフが与えられる.
できるだけ使用色数の少ない彩色を求める問題.

解法

とりあえず,アルゴリズムに適当なランダム性を入れてTLEにならない程度に何回も繰り返して一番良いものを出力する.
今回使った方法は,ノードを1つずつ塗れる最小の色番号に塗っていった.
次に塗るノードの選び方は,
 既に塗ったノードで隣接しているものの色の種類数が多いものから選ぶ
 同じなら,できるだけ次数の大きいものから選ぶ
3彩色可能であることを利用したアルゴリズムがあるらしい.

C言語のスパゲッティなコード (149.4pt)

続きを読む

February 2011 Challenge 1問目 - Bogosort (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 1問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

長さNの配列で,最初1~Nの置換で,k番目の要素はkではないものが与えられる.
それを以下のアルゴリズムでソートする場合,必要ステップ数 (以下の2が実行される回数) の期待値を分数で厳密に求める問題.
 1. 考えている区間 (未ソートの部分) を[1, N]とする.
 2. 考えている区間の要素を全てランダムに並び替える
 3. 考えている区間の左端の要素が,考えている区間内の最小値である限り,考えている区間の左端を+1する
 4. 考えている区間の右端の要素が,考えている区間内の最大値である限り,考えている区間の右端を-1する
 5. 考えている区間が空なら終了.そうでなければ2~4を繰り返す.
テストケースの数は150以下,Nは2以上150以下.ソースコード制限は10000バイト以下.

解法

多倍長を使って適当にDPする.
DPで工夫するか,多倍長の計算で工夫するかしないとTLEになる.
以下は素朴なDPだが,多倍長の計算で約分をできるだけ排除し,さらに約分するときのあまり大きい約数で分子分母ともに割れることがないのを利用して高速化している.

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

続きを読む

February 2011 Challenge (この記事を編集する[管理者用])

2011年02月01日18時から10日間,6問.(1問はマラソン形式)
[LINK]

Codechefの10日間コンテストとしては簡単な問題セット.
おかげで,全部解いてまさかの2位.
以下問題別.

・1問目 Bogosort
多倍長の有理数.上手く計算しないとTLE.特に約分は重たいので上手く行う.
・2問目 Coloring Colorable Graphs (チャレンジ問題)
3彩色可能なグラフの彩色問題.3彩色可能ってのを上手く使えば良いらしいが,何も考えずにやってしまった.
・3問目 Counting Terms
規則性を見つけてDPした.
・4問目 Glass Measurement
以前類題をGCJで解けなかったので,今回は気づけた.それでも気づくまでに時間がかかったけど.
ダイクストラ.
・5問目 Milestones
7本しかないので,適当にランダムで行けると思ったらTLEだったので,サンプル数減らしたら通った.
・6問目 Rush Hour
枝刈り全探索DFSしたが普通に間に合った.むしろケアレスミスや,やってはいけない枝刈りでWAをたくさんもらった.
想定解法はIDA*らしい.

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

Source

TopCoder SRM499 DIV1 HARD (1000pt)
Problem Statement
SRM499 DIV1 自分の参加記録

問題概要

次のゲームを行うとき,プレイヤーが絶対勝てないようにするためには,ゲームマスターは最小で何色使えば良いかを求める問題.
ゲームマスターは最初に,ABCDのみからなる長さk (30以下) の文字列に対応する色をすべて決める.
プレイヤーは1つの文字列を選び,最初に選んだ文字列と違う文字列で最初と同じ色に出来れば勝ち.できる操作は以下の通り.
 1. 隣接する2文字を入れ替える
 2. 部分文字列としてbefore[k]を含んでいるなら,その部分をafter[k]に置き換える
before[k]とafter[k]の長さは同じで,この文字列は入力で与えられ,ゲームマスターが自由に決めることはできない.
beforeとafterの要素数は50以下.

解法

まず,文字は自由にswapできるので,ABCDの文字が何文字含まれているかのみを考えれば良い.
すると,状態数はO(k^3)程度しかない.
それをノードとして,状態遷移できるノードに枝をはってグラフを作る.
もし,それがDAG (閉路がない) なら,そこから移動できるノードに使われている色の最大値+1の色を各ノードに割り当てれば良い.
全てのノードが子供より大きい色が割り当てられていることから,自分の子孫までみる必要はなく,自分の子どもの色の最大値+1を割り当てれば良いので,DPでO(枝数)ぐらいで計算可能.
閉路があれば,強連結成分分解してDAGに落とせば良い.強連結成分は全部違う色に塗らないとダメになる.

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

続きを読む

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

Source

TopCoder SRM499 DIV1 MEDIUM (550pt)
Problem Statement
SRM499 DIV1 自分の参加記録

問題概要

半角スペースをSPと書き,改行をNLと書くことにする.
50行以下のテキストで,各行,s[k]個の半角スペースがあるものを作りたい.
この時,SPACEキーとDELETEキーとRETURNキーを押す回数の合計数を最小化したい.
カーソルの移動は自由で,
 SPACEキーを押すと,その行のスペースの数が1個増える
 DELETEキーを押すと,その行のスペースの数が1個減る
 RETURNキーを押すと,その行と同じ数だけのスペースを持つ行が,その次の行に付け加わる

解法

 dp[考えてる最初の行][考えている最後の行][元になった行] = 考えてる区間を,元になった行のSPと同じ数の行から作るための最小キー回数
でDPする.
実はgreedyでも出来るらしい.

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

続きを読む

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

Source

TopCoder SRM499 DIV1 EASY (250pt)
TopCoder SRM499 DIV2 MEDIUM (500pt)
Problem Statement
SRM499 DIV1 自分の参加記録

問題概要

N匹 (50以下) の同じ街に住むウサギに,
 あなたの街に,あなた以外に,あなたと同じ色のウサギは何人いますか?
と聞いた答えa[k]が (1000000以下) 与えられる.
答えが正しいと仮定したとき,その街に住むウサギの最小数を求める問題.

解法

同じ答えのウサギをまとめる.
そのグループから 答え+1 匹までは同じ色にできるので同じ色にしていく.
後は,同じ色の組それぞれに対して, 答え+1 匹のウサギがいるはずなので,それを足していく.

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

続きを読む

SRM498 DIV2 HARD - NinePuzzle (この記事を編集する[管理者用])

Source

TopCoder SRM498 DIV2 HARD (950pt)
Problem Statement

問題概要

問題の図のような10ピースのパズルを考える.1マス空いていて,そこに隣接するピースを移動できる.
各マスは4色 (赤,緑,青,黄) のどれかの色に塗られている.
初期状態と終了状態が与えられたとき,最小で何個のマスを塗り直せば終了状態に移動できるようになるか,を求める問題.

解法

実は全ての状態に遷移可能なので,同じ色を一致させて,残りを変換すれば良い.
状態数は高々10!で,色が4色しかないことからもっと少ないので,全状態を作って,何色違っているかのminを取るのも良い.(以下のコードはこれ)

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

続きを読む

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

Source

TopCoder SRM498 DIV2 EASY (250pt)
Problem Statement

問題概要

黒板に3つの整数A, B, C (それぞれ1以上50以下) が書かれている.
N回 (150以下) だけ以下の操作を行う.最高点を求める問題.
 1個の数字を選び,その数字が正だったら,その数字だけ点数として得,その数字を1減らす.

解法

毎回一番大きい数字を選べば良い.シミュレーションする.

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

続きを読む

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

Source

TopCoder SRM498 DIV1 HARD (1000pt)
Problem Statement
SRM498 DIV1 自分の参加記録

問題概要

最初(0,0)にいる狐が,ちょうどR回 (1600以下) のジャンプで (Tx,Ty) に移動するジャンプパターンの数をmod 10007で求める問題.
MxとMyが与えられて,1回のジャンプでは,x軸の正方向に0セル以上Mxセル以下移動,y軸の正方向に0セル以上Myセル以下移動しなければいけない.
現在のセルにとどまるジャンプは許されない.
また,要素数50以下,各要素10の倍数の配列badが与えられて,x軸方向にも,y軸方向にも両方ともbad[k]だけ移動するようなジャンプは許されない.
Tx, Tyは0以上800以下,Mx, Myも800以下.

解法

badに0を加えることで,現在位置に留まることができないという条件を考えないで良くなる.
まず,badが空の場合について考える.
これは,x座標とy座標独立に考えることができて,それはTxにたどり着くパターン数はDPで数えることができる.
 dp[現在までのジャンプ回数][現在のx座標] = ここに辿り着く経路の数
愚直に書けば,O(R*Tx*Mx)でTLEになるが,途中までの和を記録して,上手く計算することでO(R*Tx)で書ける.
badがある場合は,包除原理を利用すれば良い.
 すべての場合 - badを1回使って,残りは自由な場合 + badを2回使って,残りは自由の場合 - …
badをk回使って,斜め方向に何セル進む方法がいくつあるか,というのもDPで求める.

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

続きを読む

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

Source

TopCoder SRM498 DIV1 MEDIUM (450pt)
Problem Statement
SRM498 DIV1 自分の参加記録

問題概要

200*200以下の盤面の書くセルに,それぞれ違う色の石が1個ずつ置かれている.
50セル以下,指定されたセルがある.
セルAと指定されたセルとの距離が,全て,セルBと指定されたセルとの距離と等しければ,セルAの石とセルBの石を入れ替えることができる.
距離は,x座標の差とy座標の差の大きい方で定義される.(1-ノルム)
得られる盤面はいくらあるか,mod 1000000009で求める問題.

解法

AとBが入れ替え可能,BとCが入れ替え可能なら,AとCも入れ替え可能.
盤面は,いくつかの,それぞれ入れ替え可能なグループに分けることができる.
それぞれのグループ内では自由に入れ替えれるから,そのパターン数は,グループに属すセルの数の階乗.
それぞれのグループは,指定されたセルからの距離によって特徴付けられるので,それでグループ分けすれば良い.

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

続きを読む

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

Source

TopCoder SRM498 DIV1 EASY (250pt)
TopCoder SRM498 DIV2 MEDIUM (500pt)
Problem Statement
SRM498 DIV1 自分の参加記録

問題概要

与えられた数列 (要素数50以下) が,以下の4つの等差数列を繋げたものになっているかどうかを判定する問題.
 最初は単調増加の等差数列 (要素数2以上)
 次は単調減少の等差数列 (要素数2以上)
 次は定数数列 (要素数1以上,つまり空でも良い)
 次は単調増加の等差数列 (要素数2以上)
 次は単調減少の等差数列 (要素数2以上)

解法

今どのパートにいるか,交差は何かを覚えつつ,左からなぞれば良い.
以下のコードは,それぞれのパートがどこか全部試すO(50^5)のコード.
他の人のコードは,交差の変化点だけ抜き出して,それが正負0正負,または正負正負の場合のみOKとしてる人が結構いた.

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

続きを読む

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

Source

TopCoder SRM497 DIV2 MEDIUM (550pt)
Problem Statement
SRM497 DIV1 自分の参加記録

問題概要

問題文に定められた形式のXHTMLが与えられる.
それぞれのタグに,colorの指定があるが,それを全部CSSでやりたいとき,最小で何個のルールを作れば良いかを求める問題.
タグの名前は,bとuとiのみ.
カラーの名前は,black, blue, gray, green, red, white, yellowの7種類のみ.
タグは,タグの名前と,ユニークな任意文字列IDと,指定したい色で,構成される.
CSSのルールは以下の2種類が利用可能.
 IDを指定して,それの色を指定する
 IDとタグの名前Nを指定して,そのIDの中にある全てのタグの名前がNであるタグの色を指定する
ルールは好きな順番で与えることができて,複数のルールが適応される場所は,最後に適応した色になる.
与えられるXHTMLは50*50文字以下.(タグの数に直すと100未満程度)

解法

構文解析+DP.
現在どのタグにどの色が割り当てられているかを状態にして,そこからどのタグにどの色を割り当てるかを全部試す.
状態数が8^3 (8 = 7色+未割り当て) で,どの色を割り当てるかも8^3で,合計の計算時間は タグ数*8^6 程度.

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

続きを読む

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

Source

TopCoder SRM497 DIV1 EASY (250pt)
TopCoder SRM497 DIV2 MEDIUM (500pt)
Problem Statement
SRM497 DIV1 自分の参加記録

問題概要

1~N+1の数字の置換(a[0], a[1], ..., a[N])に対して,N文字の文字列Xを
 X[k] = I (a[k+1]がa[k]より大きい)
 X[k] = D (a[k+1]がa[k]より小さい)
にて定める.
文字列が与えられるので,それに対応する置換のうち,辞書順で最小のものを求める問題.
対応するものが存在しないならそれを指摘する.
Nは50以下.

解法

基本的にはGreedy.色々な解法が考えられるので,いくつか紹介しておく.

1つ目の解法は,規則性に着目する.
最終的な答えは,1~N+1までを順番に並べたものから,Dが連続してる部分をひっくり返したものになる.
計算時間はO(N).

2つ目の解法は,再帰処理.(以下のコードの1つ目)
再帰処理で,サイズの1つ小さい,X[1]~X[N-1]の条件を満たす,a[1]~a[N]までを1~Nまでの置換として辞書順最小なものを求める.
X[0]がIならば,a[0]を1にして,X[0]がDならば,a[0]はa[1]より1だけ大きくする.
a[1]~a[N]は上下関係を保ったまま,a[0]以上なら1だけ足すことで,同じ数字をなくす.
計算時間はO(N^2).

3つ目の解法.(以下のコードの2つ目)
a[0]~a[k-1]まで決めた後,a[k]をxに出来るかどうかを全部チェックして,可能な最小のxを採用する,というのを繰り返す.
a[k]をxに出来るかどうか,というのは,その直後に連続する D (I) の数だけ,xより 小さい (大きい) 数が未使用で残っているかどうかで判定できる.
連続する D (I) の次の I (D) で,いくらでも 大きい (小さい) のに直せるので,その後は上手く配置すれば絶対に配置可能.
計算時間はO(N^3).
実際には,直後に連続するのがDの場合だけ調べれば良くて,そうなれば,残ってる数字の中から,直後に連続するDの数+1番目の数字を選べば良いことになる.
これだと,O(N^2).

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

続きを読む

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

Source

TopCoder SRM496 DIV2 EASY (250pt)
Problem Statement

問題概要

50文字以下のアルファベット小文字のみからなる文字列がN個 (50以下) 与えられる.
それらから,いくつかの文字列を選び,選んだ文字列のどのペアもアナグラムの関係になっていないようにしたい.
最大で何個の文字列を選べるか求める問題.
2つの文字列がアナグラムの関係,とは,それぞれの文字を並び替えることで一致させることができること.

解法

要するに,それぞれの文字列の,それぞれの文字の文字数を全部数えて,それらが異なっているものが何種類あるかという問題.
以下のコードでは,それぞれの文字が何個あるかをvector<int>にいれて,それをsetに突っ込んで,最終的なsetの要素数を返した.
それぞれの文字数を数えずに,それぞれの文字列をソート (abdac→aabcd) して,setに突っ込むというのが一番楽かも.

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

続きを読む

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

Source

TopCoder SRM496 DIV1 MEDIUM (500pt)
Problem Statement
SRM496 DIV1 自分の参加記録

問題概要

1次元上を左右どちらにかわからないが速度1で動いている粒子がある.
最初N個 (50以下) の粒子の初期位置が与えられる.
その後,いくらか正の時間が経った後 (たった時間は未知) のM個 (N以上) の粒子の位置が与えられる.
それは,N個の粒子に加え,M-N個の粒子を加えている.
さて,最初のN個の粒子と,M個の粒子の対応関係としてvalidなものはいくつあるか,を求める問題.
最初,最後には,同じ位置には粒子はないとする.

解法

あるボールに着目して,それがどこに移動したか50通りしかないので,経過時間の候補は高々50通りしかないので全部調べる.
後は,2部グラフのマッチングの個数を求める問題に帰着される.
その2部グラフは,連結成分を取り出すと,/\/\のような形をしているので,そのマッチングの個数は解析的に簡単に求まるので,それをかければ良い.
例えば,/\/\だったら,上の2点をどっちに繋げるか,左左,左右,右右の3通り.
同様に,上の点がn個で,下の点がn+1個だと,左左…左,右左…左,右右…左,…,右右…右,のn+1通り.

以下のコードは,結局,グラフが特徴的な形をしているので,枝刈りが効くのと,答えの最大値はそんなに大きく無いので,全探索してみました,というコード.
(本番は,これで通してしまったが良い解法とは言えない)

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

続きを読む

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

Source

TopCoder SRM496 DIV1 EASY (250pt)
TopCoder SRM496 DIV2 MEDIUM (500pt)
Problem Statement
SRM496 DIV1 自分の参加記録

問題概要

50*50以下のグリッドが与えられる.各グリッドは赤,緑,青,白のどれか.
1回で,青は横幅1マスで縦にいくらでも長く塗れる.
1回で,赤は縦幅1マスで横にいくらでも長く塗れる.
緑は赤青両方で塗られたマス.
真っ白の盤面から,与えられたグリッドを作るための最小塗り回数を求める問題.

解法

赤と青は別々に考えれば良い.
それぞれ塗れるだけ長く塗れば良いので,縦か横の線分がいくつ存在するか数えるだけ.
他の人の解法で賢いなと思った実装方法は,横の線の数を数えるなら,横方向に塗る場所と塗らない場所が隣り合ってる部分の数を数えれば良い,という実装.

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

続きを読む

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

Source

TopCoder SRM495 DIV1 EASY (275pt)
TopCoder SRM495 DIV2 MEDIUM (525pt)
Problem Statement
SRM495 DIV1 自分の参加記録

問題概要

1~Nまで (Nは1000以下) の数字が書かれたカードが1枚ずつあり,素数だと背景が赤,そうでなければ背景が青.
今,K枚 (50以下) のカードが,裏向きに置いてある.そのカードは左から小さい順に置いてあることが保証されている.
カードの色だけが与えられたとき,各カードに対して,特定できるならその数字を,できないなら-1を返す問題.

解法

それぞれのカードの取りうる最小値を左から決めていく.
同様に,それぞれのカードの取りうる最大値を右から決めていく.
最小値と最大値が一致したカードのみ一意に定まる.

以下のコードは,それぞれのカードについて,それぞれの数字が取りうるかどうか全て判定している.
判定方法は,そのカードより左のカードの最大値をgreedyに決めていって,全てvalidな値が存在して,同様に右も最小値をgreedyに割り当てていってvalidな値が全部存在すれば良い.

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

続きを読む

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

Source

TopCoder SRM494 DIV1 MEDIUM (500pt)
TopCoder SRM494 DIV2 HARD (1000pt)
Problem Statement
SRM494 DIV1 自分の参加記録

問題概要

n本 (50以下) の木の高さの分布が与えられる.
それぞれの分布はa[k]以上b[k]以下 (a[k], b[k]は100000以下) の整数を等確率に取るような分布.
木の高さが与えられたとき,以下でスコアを定める.そのスコアの期待値を求める問題.
 Alternatingとは,木の高さAが順番に大きくなって小さくなって (または,小さくなって大きくなって) となること,つまり
  A[0] > A[1] < A[2] > A[3] < … または A[0] < A[1] > A[2] < A[3] > …
 Alternatingな木の高さに関しては,スコアは隣合う木の高さの差の絶対値を足した物,つまり
  |A[0]-A[1]| + |A[1]-A[2]| + |A[2]-A[3]| + …
 Alternatingじゃない木の高さに関しては,好きな数だけ木を無視して,Alternatingな木の高さにしたときのスコアの最大値

解法

木を取り除くとしたら,極値を取る木以外を取り除くのが最適で,それは取り除かなかったときのスコアと同じになる.
結局,期待値の線形性より,隣り合う2つの木に対して,その高さの差の期待値を別々に求めて全部足してやれば良い.
愚直にO(100000^2)は間に合わないので,等差数列の和の公式を使って上手く計算するとか,何か工夫が必要.
以下は,隣合う木の高さの差がiとなる場合の数を数え上げて計算している.

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

続きを読む

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

Source

TopCoder SRM494 DIV1 EASY (250pt)
TopCoder SRM494 DIV2 MEDIUM (500pt)
Problem Statement
SRM494 DIV1 自分の参加記録

問題概要

50*50ピクセル以下の白黒画像が与えられる.
最初真っ白な画像で,好きな回数だけn*nの正方形領域を黒くできる.その時,黒い場所は黒いまま.
与えられた白黒画像を作れるような最大のnを求める問題.

解法

nで作れるかどうか,全てのnに対して判定してやれば良い.(二分探索でも良いが,計算時間的には問題ない)
作れるかどうかの判定は,実際に,n*nの領域が全部が黒い場所を全部塗って,最初に与えられた画像と一致するかどうかを調べる.
頑張れば計算時間量を落とすことはできるが,愚直に実装してO(50^5)でも問題ない.
二分探索する,各長方形に含まれる黒マスの数をDPで記憶してすぐ求めれるようにする,などでO(50^2 log 50)とかにはすぐなるけど….

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

続きを読む

SRM499 DIV1 参加記録 (この記事を編集する[管理者用])

2011年03月09日01時02分から.

Assignment

250-550-1000の微変則セット.

EASY

N匹 (50以下) の同じ街に住むウサギに,
 あなたの街に,あなた以外に,あなたと同じ色のウサギは何人いますか?
と聞いた答えa[k]が (1000000以下) 与えられる.
答えが正しいと仮定したとき,その街に住むウサギの最小数を求める問題.

うさぎセットだ….なのにCat Pochi.
同じ答えのウサギを全部まとめてあげて,a[k]+1を足していくだけ.
あ,そうか,その答えのウサギはa[k]+2以上いたら,2グループに分けないといけないのか.
まぁ,a[k]って答えたウサギをa[k]+1匹消して,処理続行でいい.
書くだけ.書いた.サブミット.

MEDIUM

半角スペースをSPと書き,改行をNLと書くことにする.
50行以下のテキストで,各行,s[k]個の半角スペースがあるものを作りたい.
この時,SPACEキーとDELETEキーとRETURNキーを押す回数の合計数を最小化したい.
カーソルの移動は自由で,
 SPACEキーを押すと,その行のスペースの数が1個増える
 DELETEキーを押すと,その行のスペースの数が1個減る
 RETURNキーを押すと,その行と同じ数だけのスペースを持つ行が,その次の行に付け加わる

550だけあって,ちょっと面倒なDPっぽい.
しかも,サンプルが弱すぎる….これは慎重にやらないと.
多分,ある区間を作るとき,あるものから作った場合の最小コストを記録する形で行ける…よね.
 dp[a][b][c] = 区間[a,b]のものを作るとき,最初に使う行のスペースの数はs[k]個のときの最小コスト
一部ぐらいはgreedyが出来る部分があって,もうちょっと単純に行けるかと思ったけど,O(n^5)は間に合うだろうし,
下手に何か仮定したら間違えそうな問題だから,できるだけ間違えないようなアルゴリズムで書く!
では,書く.いろいろ混乱.
苦戦しながら書き上げた.サブミット.
最大ケース試す.TLE.えええええええーーー.
流石に無駄にループ回しすぎてる部分を削る.最大ケースで600msぐらい.リサブミット.
自明な小さいケースを入れる.答えがバグる.ローカルで試す.ローカルだとうまく動く.
なんでだ….
配列の範囲外にアクセスしてる!
修正.再度リサブミットorz
てか,この問題は自信ないなぁ…,とりあえず,HARD見て無理そうなら見直しするとして,HARDを見てみる.

HARD

次のゲームを行うとき,プレイヤーが絶対勝てないようにするためには,ゲームマスターは最小で何色使えば良いかを求める問題.
ゲームマスターは最初に,ABCDのみからなる長さk (30以下) の文字列に対応する色をすべて決める.
プレイヤーは1つの文字列を選び,最初に選んだ文字列と違う文字列で最初と同じ色に出来れば勝ち.できる操作は以下の通り.
 1. 隣接する2文字を入れ替える
 2. 部分文字列としてbefore[k]を含んでいるなら,その部分をafter[k]に置き換える
before[k]とafter[k]の長さは同じで,この文字列は入力で与えられ,ゲームマスターが自由に決めることはできない.
beforeとafterの要素数は50以下.

さて,問題文の意味が分かりにくいぞ.
なんとなく理解した.
隣接文字を入れ替えることができるのだから,何が何文字あるかだけを考えれば良い.
状態数は30^4ぐらい.
それをどれに移動できるか全部グラフを作る.
枝の数が30^4 * 30^4のサイズになる….
いや,状態数はそもそも30^3だよね.文字列の長さがちょうどkじゃないといけないから.もっと少ない.
なんとかなるのでは.
グラフ作ってどうするの?
とりあえず,強連結成分分解はしたいよね….
あれ,で,後DAGになれば,単なるDPなのでは….
いけるじゃん.
行ける…けど,結構実装重いし,MEDIUMで時間使いまくってあんまり時間ないぞ?
諦めずに,書けるところまで書く!
書く.
書く.
デバッグ.
書く.
書く.
デバッグ.
書く.
書く.
書けたー.残り5秒.サブミットーーー.

Challenge

550は簡単な訳ない.みんなできてないに違いない.サンプルも弱いし.
ランダムで爆撃準備OK.
開く! 何この簡単なコード.Greedyっぽい? こんなの通るわけ無いじゃん,攻撃! 失敗orz
なんだと….
てか,DPほとんどいないぞ? Greedyばっかだぞ?
え,Greedyでいけるのか….
結構上位陣もGreedyだし,いけるらしい…?
後は怖くなって何もできず.GreedyはGreedyで結構落ちてたけど落とし所がわからなかった.

System tests

自信なかったMEDIUM通る.
終了直前提出のHARD落ちる.
HARDはDPでメモ用の配列用意してたのに,メモしてなかった.
メモしたら通った.

SRM498 DIV1 参加記録 (この記事を編集する[管理者用])

2011年02月27日02時02分から.

Assignment

250-450-1000の微変則セット.
よく見かける強い日本人が何人かいる部屋.

EASY

与えられた数列 (要素数50以下) が,以下の4つの等差数列を繋げたものになっているかどうかを判定する問題.
 最初は単調増加の当差数列 (要素数2以上)
 次は単調減少の当差数列 (要素数2以上)
 次は定数数列 (要素数1以上,つまり空でも良い)
 次は単調増加の当差数列 (要素数2以上)
 次は単調減少の当差数列 (要素数2以上)

Foxもふもふ.
ループ回すとき,ちゃんとどこからどこまで回すか考えないと1間違えて落ちそう,慎重に組もう.
で,左からなぞるだけでO(n)でできそうではあるのだけど,サイズも大きくないし着実に組む方法で.
どこからどこまでがどのパートに対応するのが全探索して,validなものがあるかどうかを調べる.
あ,これだと,O(n^5)なのか…,まぁ多分大丈夫だろ.
書く.
書いた.50要素で試してみても余裕で間に合う.じゃ,いける…多分.
サブミット.
見直しして次へ.

MEDIUM

200*200以下の盤面の書くセルに,それぞれ違う色の石が1個ずつ置かれている.
50セル以下,指定されたセルがある.
セルAと指定されたセルとの距離が,全て,セルBと指定されたセルとの距離と等しければ,セルAの石とセルBの石を入れ替えることができる.
距離は,x座標の差とy座標の差の大きい方で定義される.(1-ノルム)
得られる盤面はいくらあるか,mod 1000000009で求める問題.

問題文の意味が分からない,どういうことだ…?
同じ距離の石は入れ替えることができる…のかな?
えっと,それぞれのセルの状態を,各指定されたセルまでの距離のベクトルとして,
同じ状態のセルは入れ替え可能だから,同じ状態のセルの数の階乗を掛けていくだけなのでは.
そんな気がする.書いてみよう.
書いた.サンプルあったのでサブミット.これはサンプル合えば大丈夫だと思うので次

HARD

最初(0,0)にいる狐が,ちょうどR回 (1600以下) のジャンプで (Tx,Ty) に移動するジャンプパターンの数をmod 10007で求める問題.
MxとMyが与えられて,1回のジャンプでは,x軸の正方向に0セル以上Mxセル以下移動,y軸の正方向に0セル以上Myセル以下移動しなければいけない.
現在のセルにとどまるジャンプは許されない.
また,要素数50以下,各要素10の倍数の配列badが与えられて,x軸方向にも,y軸方向にも両方ともbad[k]だけ移動するようなジャンプは許されない.
Tx, Tyは0以上800以下,Mx, Myも800以下.

単純にDPしてみたら…,流石にTLEなのか.
さてどうしたものか.
x軸とy軸を分けて1次元で考えたいよね.
留まるのもめんどいから,badに0を追加して,留まることができないってのも考えないことに使用.
badがなければ,1次元ごとに分けて考えれる.
あ,わかったかも.
badを何個使うかで,包除原理で計算すれば良いのじゃないの?
良さそうだ.
書いてみよう.
…,結構面倒.
コンビネーションとかも必要なのか.
書けた.
提出.

Challenge

EASYでループの範囲を間違えている人を探す.
いないなぁ….(後々サンプル見直すと,かなり親切だったことに気づく)
何もせず.

System tests

全部通る.簡単めだったとはいえHARD通るとか珍しすぎる.

SRM497 DIV1 参加記録 (この記事を編集する[管理者用])

2011年02月11日11時02分から.

Assignment

250-550-1000の少し変則セット.てか最近標準セットの方が珍しくないか?

EASY

1~N+1の数字の置換(a[0], a[1], ..., a[N])に対して,N文字の文字列Xを
 X[k] = I (a[k+1]がa[k]より大きい)
 X[k] = D (a[k+1]がa[k]より小さい)
にて定める.
文字列が与えられるので,それに対応する置換のうち,辞書順で最小のものを求める問題.
対応するものが存在しないならそれを指摘する.
Nは50以下.

とりあえず,対応しないものなんてない気がするが,多分ない.
うーんと,最初のIの場所を探して,そこを1にして,あとはIが続く限り1ずつ増やす.
後,次にIが見つかった場所からまた再開.
Dは逆順に同じようなことをやれば良い.
これで辞書順最小じゃないかな?
書いてみる.
全然違う.てか辞書順最小なわけじゃないじゃないか,サンプル1のDIで既に違うじゃねーか.
えっと,うーむ?
….
計算時間は余裕なはずだから….
k番目の数字がxに出来るかどうかを最初から全部調べても余裕だからそういう方針を立ててみよう.
それで,使わなきゃいけないのは…,自分の前は確定してるから,自分より後がずっと同じ文字だったら,
自分より大きい or 小さいものがその数だけないとダメ.
で,文字が変わったら,そこでいくらでも減らす or 増やせるから,その後はなんとでもなる.
よし,いける.
書く.サンプル合う.
サブミット.長かった….

MEDIUM

問題文に定められた形式のXHTMLが与えられる.
それぞれのタグに,colorの指定があるが,それを全部CSSでやりたいとき,最小で何個のルールを作れば良いかを求める問題.
タグの名前は,bとuとiのみ.
カラーの名前は,black, blue, gray, green, red, white, yellowの7種類のみ.
タグは,タグの名前と,ユニークな任意文字列IDと,指定したい色で,構成される.
CSSのルールは以下の2種類が利用可能.
 IDを指定して,それの色を指定する
 IDとタグの名前Nを指定して,そのIDの中にある全てのタグの名前がNであるタグの色を指定する
ルールは好きな順番で与えることができて,複数のルールが適応される場所は,最後に適応した色になる.
与えられるXHTMLは50*50文字以下.

最初に: 終始,複数のルールが適応される場所は最後に適応した色になるってのを読み落として,全てのタグに1つのルールしか適応してはいけないと勘違いした
問題文開いた瞬間嫌な感じががが.絶対めんどーなだけの問題.
問題文長いけど,思ったより問題文読みにくくない.結構簡単に読める.(これが罠だったか)
えっと,やっぱり,めんどーい.
まずは構文解析して木を作る.これをしないと始まらない.けどこれをしたら殆ど終わりか.
で,後は,自分の下のタグでそれぞれの名前について,全部同じ色だったら,一括で指定する.
そうでなければ,自分を塗って,部分木の処理を再帰でしてやる.
書く書く書く書く.苦戦しながら書く.
書いた.サブミット.
配列サイズが足りなくてリサブミットとかした気がするけど,よく覚えてない.

HARD

 X[0] = (K*A) mod N
 X[i] = (X[i-1]+K) mod N
で定めた長さB-A+1の数列の中に,lower以上upper以下の項がいくつあるかを求める問題.
A, B, K, Nは10^10以下.

まず,K*Aがlong longでオーバーフローするんですが….
で,これはどうするのだ….
あ,これ単に,K*nがupper以下になるようなnの数 (n = 0, 1, ..., N) を求めれればOKなんだなぁ.
時間ないし,MEDIUMの見直しでもしよう.

Challenge

見てるだけー.
550落とされたー,なんでじゃー.だいぶ見直ししたのに….

System tests

EASY通る.
とりあえず焦りすぎ.もうちょっと落ち着いて整理して考えないとダメ.
って,定期的に思い出してくれるのがTopCoderです.

SRM496 DIV1 参加記録 (この記事を編集する[管理者用])

2011年02月01日21時02分から.

Assignment

赤が自分しかいない部屋.
250-500-950の少し変則セット.

EASY

50*50以下のグリッドが与えられる.各グリッドは赤,緑,青,白のどれか.
1回で,青は横幅1マスで縦にいくらでも長く塗れる.
1回で,赤は縦幅1マスで横にいくらでも長く塗れる.
緑は赤青両方で塗られたマス.
真っ白の盤面から,与えられたグリッドを作るための最小塗り回数を求める問題.

これは実際に塗るだけ…,というか,線分がいくつあるか,赤青独立に数えるだけ.
書く.サンプル通る.提出.

MEDIUM

1次元上を左右どちらにかわからないが速度1で動いている粒子がある.
最初N個 (50以下) の粒子の初期位置が与えられる.
その後,いくらか正の時間が経った後 (たった時間は未知) のM個 (N以上) の粒子の位置が与えられる.
それは,N個の粒子に加え,M-N個の粒子を加えている.
さて,最初のN個の粒子と,M個の粒子の対応関係としてvalidなものはいくつあるか,を求める問題.
最初,最後には,同じ位置には粒子はないとする.

えっと.
たった時間が決まれば,2部マッチングの数.
たった時間は,それぞれの粒子の位置の差で,50*50通り試しても問題ない気がする.(実は50通りで十分なことに気づいてない)
2部マッチングの数って,簡単に求まるものだっけ? そうじゃない気がするな.
えっと…,N個の粒子それぞれに対応できるのは,正方向,負方向に動いた場所で,たかだか2個までしか対応しない.
だから,グラフの次数は最大で2.これはキーポイントっぽい.
うーん….
わからない.
….
……….
……………….
やばい,時間だいぶ経って,提出してる人が結構な数いるのに,全く方針すら浮かばないぞ.
てか,これって,実は全探索で間に合うんじゃね?
いや,あんまり下手な全探索だとダメだけど…,「賢い全探索」なら間に合う気がする.
 ・対応できる粒子がなくなったものが存在したら打ち切る
 ・1個しか対応できない粒子が1個しか対応できない粒子と対応できるなら即座に対応させる
 ・2個対応できるのがあって,対応先が両方その粒子としか対応できないなら,その粒子を対応済みにしてその後答えを2倍する
みたいな感じ.
最悪ケースでどれとどれを対応させるかで2^50ぐらいはできそうだが,そういうケースは一瞬で終わるはず.
書いた.最悪ケースを入れてみる.2^25が返ってくる.え?
何か間違えたか…,いや,違う,このケースだと2^25でいいんだ….
あれ? ちょっとまてよ….
これ,long longで返す問題だけど,long longになりそうにないぞ??
罠か!
最悪ケースが何かはわからないけど,賢くない全探索でも…,いや,それは微妙かなぁ….
とりあえず,サブミット.

HARD

50個以下の文字列が与えられる.始点文字列と終点文字列が与えられる.
ある文字列から別の文字列に移動するコストは,
 移動前の文字列の長さ^2 + 移動後の文字列の長さ^2 - 移動前,移動後の文字列の最長共通プレフィックスの長さ^2
となる.
全部のノードをちょうど1回ずつ通るような,始点文字列から終点文字列まで移動するコストの最小値を求める問題.

ハミルトンパスってなんじゃい? てか,どっちじゃい?
Wikipedia先生教えてー.ノードを全部1回ずつ通るやつか.
うーん…,最小ハミルトンパスって難しいよね? うん,調べた感じNP完全っぽい.
….
全くわからない.
……,はっ.
残り時間僅かで,はたと気づく.
これって基本的に,辞書順でソートして,順番に訪れればいいんだよね?
始点と終点の扱いが問題なのか….
ここまで辿りつくの遅っ.
始点と終点の前後1ノードは全部試して,後は全部順番に訪れることにする.
何も保証はないけど,取り敢えず出してみてもいいかな.
2分で書く.サブミット.
うおおお,ノード数2のとき,次に行くノードの候補がなくて,無限大が返ってくるー.
ノード数が6以下ならnext_permutationで全探索する!
リサブミット.

Challenge

500で賢くない全探索してる人がいるなぁ…,これ落ちるんじゃないかな?
いや,チャレンジ失敗したらでかい位置だぞ,成功してもでかいけど,ちゃんと考えろ.
うーむ,どうだろう,よくわからない.というかお腹痛い.
諦めてトイレ.
トイレで考えてると,2^25通り答えがあって,さらに,毎回50個なぞってたから,どう考えてもTLE.
落ちるじゃん!
と気づいたけど,何もできず.

System tests

HARDは落ちる.ちゃんと考えてないgreedyが通るほど甘くはない.

SRM495 DIV1 参加記録 (この記事を編集する[管理者用])

2011年01月28日01時02分から.

Assignment

275-500-975という何とも中途半端な配点のセット.

EASY

1~Nまで (Nは1000以下) の数字が書かれたカードが1枚ずつあり,素数だと背景が赤,そうでなければ背景が青.
今,K枚 (50以下) のカードが,裏向きに置いてある.そのカードは左から小さい順に置いてあることが保証されている.
カードの色だけが与えられたとき,各カードに対して,特定できるならその数字を,できないなら-1を返す問題.

rngセットだ.
どうやるんだろう.
えっと,結構サイズが小さいな.
各カードに対して,そのカードがxであることがあるかどうかを全部判定しても問題なさそう.
で,それはgreedyで良いのでは?
そのカードから左に眺めていって,使える数字のうち最も大きいのを割り当てて可能かどうか.
同様に,右に眺めていって,使える数字のうち最も小さいのを割り当てていって可能かどうか,それぞれ判定.
いけるな.
結構めんどい,275だからか.書く.
サンプル通った.提出.

MEDIUM

N個 (50以下) の箱の中に1つだけハズレがある.
N*Nの{0, 1}行列が与えられる.
箱iを開けたとき,行列のi,j成分が1なら,箱jがハズレかどうかがわかる.
最適戦略を取ったとき,ハズレの箱を開けずに,ハズレの箱を特定できる確率を求める問題.

ほう….どうするんだろう.
rngセットの問題は,大抵最初はどうするんだろう,から始まるなぁ.
サンプルを眺めてみる.
結局,どの箱はハズレかわからないから,答えは,1 - 開けるべき箱の数 / 全部の箱の数 でいいんだな.
自分の情報が他の箱に入ってない場合は開けなければいけない.
いや,最後に残すのもありか.
どれを最後に残すか全パターン試してもいいな,それは.
うーん,あれ?
サンプル4って,0.875じゃないんじゃない?
1個だけ開ければ良いってことだよね?
1個で他の箱の情報を1個を除いて全部持ってる箱なんてないじゃないか.
え???
どういうことだ…?
??
????
??????
あ,わかったかも.わかった.
そうだそうだ,ハズレじゃないとわかった箱はノーリスクで開けられるんだ.で,その中にある情報もゲット出来る.
最初にワーシャルフロイドしよう….
それだと,基本的に,強連結成分分解してDAGに落としたときの入次数0のノードの数を求めるような感じ.(ダメ予備軍)
だけど,自分から枝が張られているようなノードの次数は絶対自分より小さいから,普通にgreedyに選ばべば良いじゃん.(ダメ)
ってことで,次数の大きい方から順番に箱を開けていけば良い.(ダメ)
書く.サンプル通る.提出.

HARD

H階 (10^9以下) に N層 (H以下) のエレベーターは何通り考えうるか,mod 1000000007で求める問題.
N層のエレベーターとは,N-1個の整数A[1]~A[N]で特徴付けられ,一番下の層がa階に止まっているとき,それぞれの層は
 a, a+A[1], a+A[2], ..., a+A[N]
階に止まっている.
また,一番下の層の止まる階が,決められており,その階に止まることで,全ての階に厳密に1つのエレベーターの層が止まることにならなくてはいけない.

取っ付きやすそうに見えるので,少し考える.
いろいろ考えると,小さいサイズに帰着させて解けそうな気がしてきたが,最初の印象ほど単純じゃないことに気づく.
時間もないし,適当に書いてみる.
一番面倒そうなサンプル「だけ」通る.
記念サブミット.
サマリー見ると,上位でも500をリサブミットしてる人が多くて不安になる.え,ハメなんかない問題だよね…?

Challenge

何もできず.HARDは落とされた.

System tests

MEDIUMが落ちる.
greedyでいいかどうか,怪しいと思いつつ提出した人が多かったみたいだけど,自分はgreedyで良いと確信していた.
よくよく考えればgreedyで良いわけがないのだが,なんでこんな勘違いをしたのか今となっては誰もわからない.

SRM494 DIV1 参加記録 (この記事を編集する[管理者用])

2011年01月23日02時02分から.

Assignment

250-500-1000の標準的なセットで,標準的な部屋.

EASY

50*50ピクセル以下の白黒画像が与えられる.
最初真っ白な画像で,好きな回数だけn*nの正方形領域を黒くできる.その時,黒い場所は黒いまま.
与えられた白黒画像を作れるような最大のnを求める問題.

実際に塗るだけ…ではなかろうか.
全ての,n*nが黒い場所を実際に塗ってみて,もともとの画像が復元出来てるかで,nで可能かどうかは判定できる.
後は全てのnについて判定すれば良い.
書こう.
…,あれ,計算量全然大したことないと思ってたけど,これって実はO(50^5)じゃないか?
いや,まぁいい,間に合うはず.
書いた.
一応最悪ケースを試す.100ms未満.余裕すぎる…,こんなに速いのか.
サブミット.

MEDIUM

n本 (50以下) の木の高さの分布が与えられる.
それぞれの分布はa[k]以上b[k]以下 (a[k], b[k]は100000以下) の整数を等確率に取るような分布.
木の高さが与えられたとき,以下でスコアを定める.そのスコアの期待値を求める問題.
 Alternatingとは,木の高さAが順番に大きくなって小さくなって (または,小さくなって大きくなって) となること,つまり
  A[0] > A[1] < A[2] > A[3] < … または A[0] < A[1] > A[2] < A[3] > …
 Alternatingな木の高さに関しては,スコアは隣合う木の高さの差の絶対値を足した物,つまり
  |A[0]-A[1]| + |A[1]-A[2]| + |A[2]-A[3]| + …
 Alternatingじゃない木の高さに関しては,好きな数だけ木を無視して,Alternatingな木の高さにしたときのスコアの最大値

えっと….DPっぽいが….
うん,木の高さの上限も100000だし,前の木の高さを覚えてDPすれば良さそう.
工夫せずにDPすると,1回の更新で100000^2掛かるけど,途中までの和を計算してうまく使えば100000になるはず.
で,Alternatingじゃないとダメだから….
 dp[今何本目][今増えてるか減ってるか][前の木の高さ]
とかでやればOK.
いや,期待値だから…,それぞれの状態を達成する組み合わせの数も覚えて正規化が必要….
いや,一様分布だからいらないか.
ちょっと書き始める.
…,ってか,凄いめんどいぞ?
うがーー,書き書き.
いや,まてよ,ちょっと手を止めて冷静になれ.
木を切るのって,絶対に極値の木を残せば良いんだよね?
もうちょっと言えば,別に木を切らなくても,隣り合う木の高さの絶対値の差を足していくだけだよね?
…,そうっぽい.いや,絶対そう.
この罠はなんだ…,今増えてるか減ってるかの状態要らない.少し楽になる!
….
ちょっとじゃなくて,もっともっと待て.
それだったら…,期待値だから….
隣り合う木の高さの差の期待値を別々に求めて足すだけ….
なんだそれはー!
一旦ソースコードを全消し.書きなおす.
でも,愚直にやると100000^2で死ぬ.
でも,どうとでもなるよね.
和の公式使えばいい…,が場合分けがちょっと面倒じゃない? もっといい方法ない?
うまい方法思いつかないが,差がkになるパターン数を数え上げてみよう.
おっと,これ,long longにしないとオーバーフローするな…,チャレンジケースに覚えておこう.
サンプルあった.提出!

HARD

N*M (150*150以下) のグリッドの各マスにスイッチがある.最初はスイッチは全部オフ.
あるマスを選んでスイッチを反転させると,同時に,そのマスからチェスのナイトで1回で移動できるマスのスイッチが全部反転する.
たかだか各マスを選ぶ回数は1回までという制約を課したとき,全てのスイッチをオンにする方法は何通りあるかをmod 123456789で求める問題.
スイッチを選ぶ順番だけ入れ替えたものは同じものとみなす.

うーん,全くわからない.

サンプル見ると実は答えは2の冪じゃないかと予想.
77502052ってのが2^x mod 123456789かどうか確かめてみる.
2の冪だ!
だから…?
なにか法則でもないかな….
小さいケースで総当たりしてみよう.
….
nを固定したとき,フラクタルっぽい構造が見え隠れするがよくわからない….
時間切れ.

Challenge

500のオーバーフローする + 中盤以降ランダム最大のテストケースを作って待機してた.
500のオーバーフロー狙いと行く.
いきなり,100000^2っぽいコードを見つけたので,まあ,これは落としておく.
案の定,オーバーフロー1人いたー,落とす!

System tests

250,500通る.
500が遅めだったけど,2チャレンジ成功のおかげで良い順位だった.

UVa 11913 - Tape Recording (この記事を編集する[管理者用])

Source

Sixth Contest of Newbies (2011-01-29) (blog)
UVa 11913

問題概要

1日分,午前6時~午前5時59分までの見たいテレビ番組表が与えられる.(番組数は100以下)
テレビ番組にはそれぞれ「見たい度」 (1以上5以下) が設定されている.
自分で見るのと,ビデオに録画するのとで,同じ時間で2つの番組まで見ることができる.
番組の一部のみを見ることはできない.
見ることができるテレビ番組の見たい度の和の最大値を求める問題.

解法

最小費用流に帰着させて解いた.
想定解法はDPだと思う.

Appendix

Recent Articles

ブログ内検索

Ads


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