C - Palindrome Concatenation

問題はこちらindeednow-finalb-open.contest.atcoder.jp

なぜこの問題かというと、コード祭り練習会の問題(AtCoder Problems)で一番なるほどなぁ、面白いなぁと思ったからです、はい。

どこが面白いかというと、一見めっちゃいかつそうな問題なのですが、解法を考えていくと思ったより素直な考え方で解けて、思ったより素直なコードに落とし込める、って感じなとこです、はい。

で、解法としては、まぁDPです。

dp[i] を「i番目までの文字を作るのにかかる最小コスト」とすると、

dp[i] = (0 < j < i)における (dp[j] + {j + 1番目からi番目までの文字を作るのにかかる最小コスト}) のmin

となります。

でも{j + 1番目からi番目までの文字を作るのにかかる最小コスト}ってが出なくない？ って話なんですが、これについては、実はj + 1番目からi番目までという連続部分文字列が回文のときだけ考えてあげればよいです。
回文でない場合はどこかに区切りがあって、そこで切られた場合については別のjでちゃんと考慮がなされているので、結局すべてのjにおいて残りの文字列が回文のときのみ、コストを計算して比較をしてあげればよいです。

ってことは、i を 1 ~ n で回してあげて、その中で j を 0 ~ i - 1 で回してあげて、その中で j + 1 から i の文字列が回文かどうかを判定し、回文だったらそのコストを足して比較、ってすればよいのですね！！！

って書いたコードがこちらindeednow-finalb-open.contest.atcoder.jp

はい。TLEです。このコードでは回文判定が なので、全体で , n = 5000 なので間に合うわけがありません。当然の結果です。

このコードでは回文か判定する関数 kaibun(l, r) が (l, r) = (0, 1), (0, 2), (1, 2), (0, 3), (1, 3)... ととても規則的に呼ばれているので、適当に今までの結果を使ってあげれば回文判定が でできます。うれしい。
私は kaibun(l, r) = kaibun(l + 1, r - 1) && s[l] == s[r] を用いました。
これをメモ化再帰っぽく（実際には再帰は1回で止まる）書けば完了です。

計算量は , n = 5000 なので2500万ですね、遅い言語で重い処理をしてると1000msを超えてきそうな数字ですかね。
私も最初640ms出て、用いる配列の大きさを半分にしたら380msになりました。納得いかねぇ。

てなわけで最終的なコードはこちら。関数呼び出しに時間かかってんのかなと思って関数捨てたがあんま速度変わらず逆に少しごちゃっとしてしまった。indeednow-finalb-open.contest.atcoder.jp

DPつよくなりたいしDPコンチャレンジを再開するかな……

SRM667 Div2 hard

初めてDiv2 hardを解きました。うれしい。
レートも爆上がり（1194 -> 1323 (+129) ）。とてもうれしい。
これでDiv1に5回くらい残留できるだろうか。
とりあえずmedは死んで、どうぞ。

TopCoder Statistics - Problem Archive
TopCoder Statistics - Problem Statement

問題を理解するのに10分、DPで行けんじゃないか、となるとこまで10分、途中で、これ一つ右の建物にいくつ店があるかも関係すんじゃん死んだ、ってなってから解法がひらめくまで3分、みたいな感じでした。
ぐちゃって書いたコードが一発でちゃんと動いたので助かった……。

n, m = 30なので全探索……はむりだわな、両隣しか関係しないからDPで行けるかな……。
となって、最初 dp[その建物の位置][その建物の店舗数] という配列で
dp[i][j] = (0 <= k <= m) における (dp[i - 1][k] + j * (価値関数))のmax
でいこうかと思い、これ価値関数が一つ右の建物の店舗数にも依存すんじゃん忘れてた、ってなった。
が、思いのほかすぐにひらめき、
dp[その建物の位置][その建物の店舗数][一つ右の建物の店舗数] で
dp[i][j][k] = (0 <= l <= m) における (dp[i - 1][l][j] + j * (価値関数))のmax
とした。O(n * m^3) なので 30^4 = 810000 で楽勝で間に合う。

using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
 
public class ShopPositions {
  public int maxProfit(int n, int m, int[] c) {
        var dp = new int[n][][];
        for (int i = 0; i < n; i++)
        {
            dp[i] = new int[m + 1][];
            for (int j = 0; j <= m; j++)
                dp[i][j] = new int[m + 1];
        }
        for (int i = 1; i <= m; i++)
            for (int j = 0; j <= m; j++)
                dp[0][i][j] = i * c[i + j - 1];

        for (int i = 1; i < n; i++)
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= m; k++)
                    for (int l = 0; l <= m; l++)
                        dp[i][j][k] = Math.Max(dp[i][j][k], dp[i - 1][l][j] + j * c[i * 3 * m + l + j + k - 1]);

        int max = 0;
        for (int i = 0; i <= m; i++)
            max = Math.Max(max, dp[n - 1][i][0]);

    return max;
  }
}
// Powered by Greed 2.0-RC