500
http://community.topcoder.com/stat?c=problem_statement&pm=12534&rd=15498
memo[前の前に配置した地点][前に配置した地点]
ある２点間が、ある1つの区間に含まれるかどうかを前もって作っておく。
あとは、今現在着目している地点をこれまで配置した2点と同様の区間にならない様に選んでいく。
6/23/2013
6/22/2013
SRM575 Div1 Medium
500
http://community.topcoder.com/stat?c=problem_statement&pm=12498&rd=15495
ある位置が部分列に選ばれる確率を計算する。
ある位置の数字が"最終的に"その場所にある確率を計算する。
こういう列の要素のスワップの問題って、"その位置"と"他の位置"に分けて考えるのが定番なの？
http://community.topcoder.com/stat?c=problem_statement&pm=12498&rd=15495
ある位置が部分列に選ばれる確率を計算する。
ある位置の数字が"最終的に"その場所にある確率を計算する。
こういう列の要素のスワップの問題って、"その位置"と"他の位置"に分けて考えるのが定番なの？
ラベル: SRM
6/19/2013
SRM583 Div1 Medium
500
グラフ中の最長パスを求める。もし両端を切り替える必要があるなら、そのパスで切り替える。
パスの両端の片方あるいは両方を木から取り除いて同様の操作を繰り返す。
もっと簡単にDFSやループだけで解けるらしい。
グラフ中の最長パスを求める。もし両端を切り替える必要があるなら、そのパスで切り替える。
パスの両端の片方あるいは両方を木から取り除いて同様の操作を繰り返す。
もっと簡単にDFSやループだけで解けるらしい。
ラベル: SRM
6/16/2013
SRM543 Div1 Medium
500
http://community.topcoder.com/stat?c=problem_statement&pm=11912&rd=14735
DP[どの島][どの港]
普通にループを回すと当然のがら間に合わない。
何分探索かして今注目している位置より左から適切な場所を探すのかと思ったけど、そんなことはなかった。
最小値あたりのインデックスを持っておいて、距離の近い方へと見ていく。
http://community.topcoder.com/stat?c=problem_statement&pm=11912&rd=14735
DP[どの島][どの港]
普通にループを回すと当然のがら間に合わない。
何分探索かして今注目している位置より左から適切な場所を探すのかと思ったけど、そんなことはなかった。
最小値あたりのインデックスを持っておいて、距離の近い方へと見ていく。
ラベル: SRM
6/14/2013
6/09/2013
SRM536 Div1 Medium
500
http://community.topcoder.com/stat?c=problem_statement&pm=11797&rd=14728
(総和の半分) or (総和 - 最大値)
(総和の半分)はすぐに思いつく。
(総和 - 最大値)は分からなかったので小さいケースをいくつか手で試した。
http://community.topcoder.com/stat?c=problem_statement&pm=11797&rd=14728
(総和の半分) or (総和 - 最大値)
(総和の半分)はすぐに思いつく。
(総和 - 最大値)は分からなかったので小さいケースをいくつか手で試した。
ラベル: SRM
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する。
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する。
ラベル: SRM
6/01/2013
SRM522 Div1 Medium
450
http://community.topcoder.com/stat?c=problem_statement&pm=11604&rd=14547
いつも通りどれかを決め打ちして計算する。AとBを決めて、近い値を探す。
よく見たら解くの２度目だった。
http://community.topcoder.com/stat?c=problem_statement&pm=11604&rd=14547
いつも通りどれかを決め打ちして計算する。AとBを決めて、近い値を探す。
よく見たら解くの２度目だった。
ラベル: SRM
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])で計算できる。
難しかった。
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])で計算できる。
難しかった。
ラベル: SRM
登録:
投稿
(
Atom
)