Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-03-31

TopCoder SRM 501 writer

| 22:45 | TopCoder SRM 501 writer - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - TopCoder SRM 501 writer - Wrong Answer -- japlj TopCoder SRM 501 writer - Wrong Answer -- japlj のブックマークコメント

2度目のwriterをやりました。今回は1セット分全て、4問書きました。

今回の問題をよく見ると Div2 Easy 以外は全て DP (Div1 Easyは greedy 解もありますが) なので DP回でした。

とりあえず簡単な解説。括弧内は問題のジャンルです。解答例は Practice room へどうぞ。

Div2 Easy FoxProgression (Straightforward)

22:32 | Div2 Easy FoxProgression (Straightforward) - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Div2 Easy FoxProgression (Straightforward) - Wrong Answer -- japlj Div2 Easy FoxProgression (Straightforward) - Wrong Answer -- japlj のブックマークコメント


やるだけですがDiv2 250にしては実装がきついです。サンプルを充実させてしっかりとした annotation をつけましたが、それでも難しすぎるようでした。300ぐらいにすべきだったかもしれません。

Div2 Medium = Div1 Easy FoxPlayingGame (Dynamic Programming / Greedy)

22:32 | Div2 Medium = Div1 Easy FoxPlayingGame (Dynamic Programming / Greedy) - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Div2 Medium = Div1 Easy FoxPlayingGame (Dynamic Programming / Greedy) - Wrong Answer -- japlj Div2 Medium = Div1 Easy FoxPlayingGame (Dynamic Programming / Greedy) - Wrong Answer -- japlj のブックマークコメント


DPとGreedyの2種類の解法があります。まずはDPから。

たぶんある程度実力のある人ならGreedyできるなーと思いつつ安全策をとってDPすることが多いと思います。このDPはよくある感じで dp[足し算の回数][掛け算の回数] こういう状態をとればいいですが、2種類の値を保存しておく必要があるので注意が必要です。

最終的に求めるのが最大値なのでそれを保存しておくのは当然ですが、負の値を掛ける場合は直前の値が小さい方がいいので最小値も保存しておく必要があります。

次にGreedy。

最終的に答は次のような形になります。

a*be1 + a*be2 + ... + a*bek

ただし nB >= e1 >= e2 >= ... >= ek >= 0 です。

このとき足し算の各項を最大化することを考えるとGreedy解が得られます。実際に考えてみると足し算の途中で掛け算を挟むことはないので、その分け方を全通り試すコードが比較的安全なGreedyだと思います。

aの正負やbの絶対値を使って場合分けしてもいいですが、nB = 0 の場合などに注意が必要です。

Div2 Hard = Div1 Medium FoxAverageSequence (Dynamic Programming)

22:32 | Div2 Hard = Div1 Medium FoxAverageSequence (Dynamic Programming) - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Div2 Hard = Div1 Medium FoxAverageSequence (Dynamic Programming) - Wrong Answer -- japlj Div2 Hard = Div1 Medium FoxAverageSequence (Dynamic Programming) - Wrong Answer -- japlj のブックマークコメント


典型的なDPです。

dp[pos][sum][last][flag] := A[0..pos] まで埋めていて、 A[0..pos] の総和が sum、A[pos] = last であり、A[pos-1]>A[pos] という条件式の値が flag であるような場合の数

で素直にDPしましょう。

もともとDiv1のほうには seq.size() <= 50, seq[i] <= 100 で出すつもりでした。この制約だと O(NM4) は TLE するので一工夫必要です。そこまで難しい工夫というわけではないですが、すこしひねったDPの練習にはうってつけだと思います。Practice roomの模範解はこの制約でも解けるようになっています。

Div1 Hard FoxSearchingRuins (Dynamic Programming, Data Structure)

22:32 | Div1 Hard FoxSearchingRuins (Dynamic Programming, Data Structure) - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Div1 Hard FoxSearchingRuins (Dynamic Programming, Data Structure) - Wrong Answer -- japlj Div1 Hard FoxSearchingRuins (Dynamic Programming, Data Structure) - Wrong Answer -- japlj のブックマークコメント


まず最初に基本的なDPから作っていきます。簡単のために、ひとつの行には1つ以下の宝石しかないものとします(この制約はあとで外します)。

まず最初に、宝石の場所は y の順にソートされているとします(ひとつの行に2つ以上の宝石がある場合を考えるときは y が同じなら x の順にソートします)。

今いる場所と、そこに来るまでに使った横移動の回数から経過時間は一意に定まるので

dp[今いる場所][横移動の回数] := この状態になるとき集められる宝石の価値の最大値

というDPを考えます。今いる場所は W*H 通りありますが、宝石のある場所だけ考えればいいので 1000 通りだけで問題ありません。横移動も最大 1000 回までなので状態数は約100万です。宝石 i の場所に横移動 d 回を使って居るときのDPの値の計算は

dp[i][d] = v[i] + max(dp[i-1][d-|x[i]-x[i-1]|], dp[i-2][d-|x[i]-x[i-2]|], ..., dp[0][d-|x[i]-x[0]|])

で行えます。この計算を宝石0から順番に行っていきます。これだと1回の計算に最大 1000 個の値の max をとる必要があるため、合計で 100万 * 1000 = 109 回計算が必要になって TLE します。

これを改善するには、まず「今いる場所」の表し方を変えます。宝石0から順番に考えていって、いま宝石 i について考えているとき

dp[p][d] := (p, y[i]) に d 回の横移動を使って来たときに集められる宝石の価値の最大値

とします。こうすると DP の値の計算が

dp[p][d] = v[i] + max(dp[p][d], dp[p-1][d-1], ... , dp[0][d-p],
                      dp[p][d], dp[p+1][d+1], ... , dp[W-1][d+W-p-1])

になります。これをそのまま計算しても結局 109 には変わりないのでまだ TLE します。

これを高速化するために、まず max 内の値たちについて考えます。max 内の1行目と2行目を別に考えると、これらは2次元の表の斜め向きの線上に乗っかっていることがわかります。つまり、2次元の表において斜め向きに連続する要素の最大値を計算しているわけです。これを線形よりもよい時間で計算してやりたいということになります。

そのための道具として用いるのが segment tree や 平方分割です。これらのデータ構造については iwiwiさんの解説スライド がとても分かりやすいので是非読んでみてください。以降ではこれらの構造をまとめて RMQ と呼んでおきます。

ひとつの RMQ にひとつの斜め線を対応させることにすると、縦の大きさが Y で横の大きさが X であるような2次元表にありうる斜め線を網羅するためには 約2*(X+Y) 個の RMQ が必要になります。そしてこれらの RMQ を DPの配列の代わりに使うことで先の計算を高速化することができます。

要素数 N の配列に対して「任意の範囲の最大値を求める」という操作と「任意の要素を任意に変更する」という操作を考えると、segment tree はこれを O(log N) と O(log N)、平方分割はこれを O(√N) と O(1) で実現します。

よって、宝石の数を J, 許される横移動の回数を D とすると、この解は O(J D log W) または O(J D √W) で動きます。平方分割は若干厳しいように見えますが、定数が小さいので間に合います。

最後に1つの行に宝石が2つ以上ある場合を考えましょう。もし IOI 2009 の Salesman という課題を知っているなら、この部分は Salesman と同じ方法で解決することができます。

1つの行に複数の宝石がある場合、どのように宝石をとったとしてもとられる宝石は横に連続した範囲になります。つまり1つの行に K 個の宝石がある場合、 O(K2) 通りの取り方が考えられるわけですが、宝石の数の2乗オーダーがかかってしまうと時間制限に間に合わなくなります。

そこでまず、1行にある K 個の宝石それぞれについて、その宝石以外の K-1 個が無いものと仮定してとりあえずその宝石をとるとした場合の DPの値を計算します。あとはそのDPの値をもとに、左からと右からそれぞれどこからどこまで取るのが最適かを簡単に計算することができます。

この方法だと1行に宝石が K 個ある場合、それらすべてを処理するのに O(K D log W) または O(K D √W) 時間がかかりますが、全体で見るとオーダーは O(J D log W) または O(J D √W) で不変なので時間制限に間に合ってようやく AC を貰えます。

 |