500
各行の最も右の 1 のところを移動する。
6/29/2012
6/26/2012
SRM547 Div1 Medium
500
式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?
サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S
式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?
サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S
ラベル: SRM
6/25/2012
6/21/2012
6/19/2012
6/18/2012
6/17/2012
SRM546 Div1 Easy
250
本番では解けなかった。
2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。
なぜ気が付かなかった・・・。
本番では解けなかった。
2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。
なぜ気が付かなかった・・・。
ラベル: SRM
6/13/2012
6/12/2012
6/11/2012
SRM545 Div1 Medium
500
ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。
原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。
K == 1 の時だけ別処理。
ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。
原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。
K == 1 の時だけ別処理。
ラベル: SRM
6/08/2012
SRM545 Div1 Easy
275
先頭から1文字ずつ作る。
ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。
あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。
先頭から1文字ずつ作る。
ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。
あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。
ラベル: SRM
6/01/2012
SRM410 Div2 Hard
1000
memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。
memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。
ラベル: SRM
登録:
投稿
(
Atom
)