解いた問題

6/23/2013

SRM578 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12534&rd=15498

memo[前の前に配置した地点][前に配置した地点]
ある2点間が、ある1つの区間に含まれるかどうかを前もって作っておく。
あとは、今現在着目している地点をこれまで配置した2点と同様の区間にならない様に選んでいく。

6/22/2013

SRM575 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12498&rd=15495

ある位置が部分列に選ばれる確率を計算する。
ある位置の数字が"最終的に"その場所にある確率を計算する。

こういう列の要素のスワップの問題って、"その位置"と"他の位置"に分けて考えるのが定番なの?

6/19/2013

SRM583 Div1 Medium

500

グラフ中の最長パスを求める。もし両端を切り替える必要があるなら、そのパスで切り替える。
パスの両端の片方あるいは両方を木から取り除いて同様の操作を繰り返す。

もっと簡単にDFSやループだけで解けるらしい。

SRM583 Div1 Easy

250

WFとか。
range[i]が頂点の数より大きくなる場合がある。
(i - range[i] + V) % Vだと負になったりする。

6/16/2013

SRM543 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11912&rd=14735

DP[どの島][どの港]
普通にループを回すと当然のがら間に合わない。

何分探索かして今注目している位置より左から適切な場所を探すのかと思ったけど、そんなことはなかった。
最小値あたりのインデックスを持っておいて、距離の近い方へと見ていく。

6/09/2013

SRM536 Div1 Medium

500

http://community.topcoder.com/stat?c=problem_statement&pm=11797&rd=14728

(総和の半分) or (総和 - 最大値)

(総和の半分)はすぐに思いつく。
(総和 - 最大値)は分からなかったので小さいケースをいくつか手で試した。

6/04/2013

SRM528 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11634&rd=14553

memo[一方をどこまで作った][もう一方をどこまで作った]

s[x[k]] = s[y[k]] の条件を満たしうる長さN/2の文字列を全て生成して数え上げる。
候補の文字列をtとして、memo[i][j]に注目している時、t[i]かt[j]のどちらかに文字を割り当てる。
割り当てられる文字はs[i + j]。

(2^20)*(20^2)は無理だろうと思ってひたすら別解法を考えたけど、結局はこれだった。
あまり手を抜くとTLEする。

6/01/2013

SRM522 Div1 Medium

450
http://community.topcoder.com/stat?c=problem_statement&pm=11604&rd=14547

いつも通りどれかを決め打ちして計算する。AとBを決めて、近い値を探す。

よく見たら解くの2度目だった。

SRM520 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=11496&rd=14545

DP1[どれを解いた][ポイント] = あるポイント以下を取るパターン数
DP2[何人目まで見た][ポイント] = パターン数

まず、幾らかの問題を解いてあるポイントを取るパターン数を数え上げる。
問題 i のポイントのとり方は、(1, points[i]) の区間。
注目しているポイントを p とすると、テーブルの更新にはそれまでの (p - 1, p - points[i]) の区間の総和が必要。
BITで挑戦するも、意外と遅くて方針転換。

ある区間の総和は、累積和で計算する。
DP1[bit | (1 << i)][p] = (DP1[bit][p - 1] - DP1[bit][p - 1 - points[i]]) + DP1[bit | (1 << i)][p - 1]
加算の左辺値が区間の和で、右辺値が累積
※この累積和の区間はinclusive

次に、全体のパターン数を数える。
n番目の参加者は(n - 1)番目の参加者よりも大きいポイントを取っているはず。
n番目の参加者がポイントを p だけ取得しているとすると、(n - 1)番目の参加者が p 未満のポイントを取った場合のパターン数の総和が必要。
また総和が必要なので累積和をまた使う。 
DP2[c][p] = DP2[c][p - 1] + DP2[c - 1][p - 1] * (ポイント p の作り方)
加算の左辺値が累積で、右辺値がポイント p を取るパターン数
ポイント p の作り方は最初の累積和から、 (DP1[bit][p] - DP1[bit][p - 1])で計算できる。



難しかった。