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

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

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

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

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

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

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

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

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

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勝する確率を全部求めて足しても良い．
もしくは，要求精度が低いので，モンテカルロしても通るらしい．

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整数に収まる．

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

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 C問題 (2000pt)
Problem description

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

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

続きを読む

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以下なら先手が勝てることがわかる．

続きを読む

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できる．

続きを読む

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

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

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

続きを読む

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により最大ダメージが求められる．

続きを読む

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)ぐらい．

続きを読む

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匹ずつ処理するのではなく，同じ種類の敵がいなくなるか，倍率が変わるまで一気に処理する．

続きを読む

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
と出力する問題．

やるだけ．

続きを読む

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)しかない．

続きを読む

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になるので，増分は一定に落ち着く．
なので，増分が一定になるまで計算して，一定になったら適当に計算を端折れば良い，

続きを読む

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

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

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

続きを読む

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に戻ったらそれで打ち切るなどとすれば良い．

続きを読む

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．

続きを読む

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

続きを読む

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文字が全部正しい確率とかは最初に求めておけば良い．

続きを読む

This is an unused problem for CodeChef March Cook-Off 2012.

Ciel has N dice. The i-th die is a fair A_i-sided die. For a single roll of fair k-sided dice, the number i is shown with probability 1/k for all 1 ≤ i ≤ k. (I don't know what 1-sided dice are like, but Ciel may have them!)

Ciel sometimes holds the game with her dice. In the game, Ciel rolls her N dice, and asks the challenger to answer the sum of the numbers which are shown. Of course, the result of the rolling is concealed, but Ciel gives one hint to the challenger. Ciel's hint is the sum S of X_k-th die over all 1 ≤ k ≤ M, where X_k are distinct. If the challenger's answer is correct, the challenger get any food menu in the restaurant for free.

Your task is to find the most probable sum for various her hints.

Input

The first line contains 2 integers N and Q, where Q is the number of hints. Then next line contains N integers A₁, A₂, ..., A_N. Then next Q lines contain M+2 integers M, S, X₁, X₂, ..., X_M.

Output

For each hint, if the hint must be wrong, print "Ciel lies" without quotes. Otherwise print the most probable sum. If there are multiple answers, print the minimal one.

Constraints

1 ≤ N ≤ 50000 (5 * 10⁴)
1 ≤ Q ≤ 1500
1 ≤ A_i ≤ 1000000000 (10⁹)
0 ≤ M ≤ 500
0 ≤ S ≤ 1000000000000000000 (10¹⁸)
1 ≤ X_i ≤ N
X_i ≠ X_j (i ≠ j)

Sample Input

2 1
6 6
0 0

Sample Output

7

Sample Input

4 2
1 2 3 4
2 3 1 2
2 6 2 3

Sample Output

7
Ciel lies

Output details

The first hint of the first sample input is totally useless. Ciel rolls two six-sided dice, the most probable sum is 7 which occurs with probability 6/36 = 1/6, because there are 6 patterns (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) whose sum is 7.

For the first hint of the second sample input, there are two most probable sums 7, 8.
Sum = 5: There is 1 pattern (1, 2, 1, 1).
Sum = 6: There are 2 patterns (1, 2, 1, 2), (1, 2, 2, 1).
Sum = 7: There are 3 patterns (1, 2, 1, 3), (1, 2, 2, 2), (1, 2, 3, 1).
Sum = 8: There are 3 patterns (1, 2, 1, 4), (1, 2, 2, 3), (1, 2, 3, 2).
Sum = 9: There are 2 patterns (1, 2, 2, 4), (1, 2, 3, 3).
Sum = 10: There is 1 pattern (1, 2, 3, 4).

The second hint of the second sample input is wrong, because the sum of two-sided and three-sided dice cannot be 6.

codechef February 2012 Cook-off 5問目
Problem Statement

0以上10^6以下の整数a, b, cが与えられた時，以下の等式を満たす正整数の組(x, y)の数を求める問題．
　x*y = a + b*lcm(x,y) + c*gcd(x,y)
無限に存在するならそれを指摘する．

まず，任意の素数pに対して，yがpを素因数にもつ は 数xがpを素因数にもつ数 以上とする．
（後で，素因数にもつ数が等しくないものは入れ替え可能なので，適当にパターン数2^kをかける）
すると，等式は，
　x*y = a + b*y + c*x
となり，yはxで書き下すことができる．
a mod x = 0でなければならないのと，yはx以上であることを考慮すると，xの取りうるパターンは多くなく，全部試せる．
コーナーケースとして，
　a = b = c = 0の時は答え0
　a = c = 0, b != 0の時は答え無限
であることに注意する．

続きを読む

codechef February 2012 Cook-off 4問目
Problem Statement

列車の席は6つの席ごとにグループになっていて，各車両の空席状況が与えられる．
x人分だけ，同じグループになっている席を買いたい．
パターン数を求める問題．

やるだけ．

続きを読む

codechef February 2012 Cook-off 3問目
Problem Statement

正整数Nが素因数分解した形
　N = p[1]^k[1] * p[2]^k[2] * ... * p[m]^k[m]　(p[i]は100000以下，k[i]は10^9以下)
で与えられる．
Nをphi(N)に置き換えるという操作を何回行うとNは1になるかを求める問題．

置き換える操作は，同時に，それぞれp[k]^xを(p[k]-1)*p[k]^(x-1)に置き換えることになる．
まず，100000以下のそれぞれの素数に対して，p[k]-1を素因数分解しておく．
それぞれの素数に対して，p[k]が最初に現れるのは，何回目の操作が終わってからか？というのも計算しつつ大きい素数からその素因数が消えるまでシミュレートする．

続きを読む

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．

続きを読む

TopCoder SRM533 DIV1 MEDIUM (500pt)
Problem Statement

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

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

続きを読む

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では全探索も可能．

続きを読む

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12432

長さL (10^9以下) の床があり，カーペットを重なりなく敷き詰める最小コストと，その最小コストを達成するような色の変化の最小数を求める問題．
色はM (50以下) 種類あり，それぞれのペンキの値段が与えられる．
また，既存のカーペットはN (1000以下) 種類あり，それぞれの情報は
　区間[st, ed]を覆うことができる (区間[st+1, ed+1]などには使えないし，一部分だけ使うこともできない)
　色
　価格
　値引き率（後述）
が与えられる．
敷き詰めるときは，必ず，区間の最初から敷き詰めなければいけない．
できることは，あるカーペットを買ってそのまま敷くか，長さ1の無色カーペット（無料）をインクで塗って敷くかのどちらか．
カーペットを買うとき，同じ色のカーペットを3回以上連続で買うと，3回目以降はmax(価格 - 値引き率, 0)だけの価格で買うことができる．
途中で無色カーペットを使うと，連続して買っていることにならない．

最後に買ったカーペットと，同じ色のカーペットを連続で買ったかどうかを状態としてDPする．
無色カーペットを使うときは，左右と同じ色か，最もインクの易い色しか考えなくて良い．(Mは微妙に小さいので全部考慮しても通る？)

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12431

Xはb進数で，dがn文字並んでいる数字とする．
X mod Mの値を（10進数で）出力する問題．
bは100以下，nとMは10^12以下

漸化式を立てて行列べき乗した．
modの値Mが大きいので，オーバーフローしないように注意する．