解いた問題

6/26/2012

SRM547 Div1 Medium

500

式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?

サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S

SRM547 Div1 Easy

250

x と y の差のそれぞれが何パターン出現するかを計算して答えを出す。

6/21/2012

AOJ2403

AOJ2403

2012模擬国内予選E問題

単純な枝刈りで充分
軍事力順でソートして、残りを全て取って現状の最大値を超えられるか見る


以下、本番で提出したコード

UVa11206

UVa11206

普通に塗って試せばいい。

グラフは連結だし、頂点の数も充分に小さいっぽい。

6/19/2012

UVa11229

UVa11229

盤面の状態は 3^9 = 19683 程度。メモ化する。
引き分けの場合は後手番の勝利に含めてしまっていい。

memo[ 盤面の状態 ] = 先手の勝率
先手は勝率を最大化し、後手は勝率を最小化する。

6/18/2012

SRM546 Div1 Medium

500

m 桁目を n より大きくして残りは0で埋める。下の桁で digit1, digit2 の帳尻を合わせる。

6/17/2012

SRM546 Div1 Easy

250

本番では解けなかった。

2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。

なぜ気が付かなかった・・・。

6/13/2012

UVa548

UVa548

ポストオーダーの最後に登場する頂点でインオーダーを分割する。
このコードより簡単な実装or解法がある気がする。

UVa10128

UVa10128

dp [ 誰を使った ] [ これまでで最も高い身長 ] [ 前から見て何人見えるか ]

最も身長の高い人より後ろに並んでいる人は当然見えない。
つまり、その人の前と後ろで分けて考えることが出来る。

6/12/2012

UVa 12410

UVa12410

memo [ 何桁目まで作ったか ] [ 使った 1 の数 ] [ idealとの違い ] [ mod 3 ] [ mod 7 ] [ smaller or not ]

6/11/2012

SRM545 Div1 Medium

500

ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。

原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。

K == 1 の時だけ別処理。


6/08/2012

SRM545 Div1 Easy

275

先頭から1文字ずつ作る。

ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。

あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。


6/01/2012

SRM410 Div2 Hard

1000

memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。

SRM410 Div2 Medium

500

グリッドと連結でない頂点は、最も大きい連結成分との間に辺を作る。

SRM410 Div2 Easy

250

やるだけ