ハーフパイプ(2) 解説？ - うにゅーん、って感じだ

今回、testerをさせていただきました。

問題はこちら
No.398 ハーフパイプ(2) - yukicoder

まずはwriterさんの解説をご覧ください
http://yukicoder.me/problems/no/398/editorial

この問題、想定解法は埋め込みです。testerで問題をもらった時 6*100*100*600*100 = 36億から落ちないよぉふぇぇ... ってなって解説をカンニングして、は〜〜〜、ってなった記憶があります。

ただ、ちゃんと定数倍改善を行えばこのオーダーでも C++ で 250ms, C# で 900ms で通る（かつ埋め込みのための列挙がほぼ同じ時間でできる！）ようになります。まずはその解説から。

まず dp[index][min][max][sum] というDPを考えます。これの更新式は以下のようになります。

for m in {0..100}:
dp[i + 1][min(j, m)][max(k, m)][l + m] += dp[i][j][k][l]

初期化については、一番左に置く数について埋め込み、

dp[0][i][i][i] = 1

としてしまうのが楽だと思います。

このdpの場合、
sum = x * 4とし、

for i in {0..100}:
for j in {i..100}:
ans += dp[5][i][j][sum + i + j]

とした ans が求めるものです。

このままやるともちろんTLEしますが、端的に言うと dp[i][j][k][l] == 0 の場合に m のループに入らないようにすれば良いです。

というのも、dp[i][j][k][l] == 0 となる場合が（定数倍の範囲内ですが）そこそこあり、その時に内側のループに入らないようにしてあげればループ回数がおよそ1億回ほどになり、C++等で通ります。C#でも1300msほどで通りましたが、Python等の言語では厳しいと思います。
(参考 : http://yukicoder.me/submissions/103388,
　　 : http://yukicoder.me/submissions/103389,
　　 : http://yukicoder.me/submissions/103496)
また、dp[i][j][k][l] > 0 となる l の範囲は連続なので、そこだけループを回すようにしてあげればもう少し早くなります。
(参考 : http://yukicoder.me/submissions/103467,
　　 : http://yukicoder.me/submissions/103495)

dp[i][min][max][sum] > 0 なる sum の範囲は、
最小値が min + max + max + ... + max = min + max * i,
最大値が min + ... + min + min + max = min * i + max となるので、そこだけ回すとC++で250ms, C#で900msほどになります。

まぁ詳しくはソースコードを読んでください。

さて、そして問題のなんか場合分けして速いの(http://yukicoder.me/submissions/103511)についてですが、オーダーとしては 100^3 です。

やってることとしては単純で、

a + b + c + d + sum && a <= b <= c <= d

なる (a,b,c,d) を全探索し、一つ一つに対して min <= a なる min と d <= max なる max を追加した時の並べ方の場合の数を数え上げています。

min と max については、
・min == a && d == max
・min < a && d == max
・min == a && d < max
・min < a && d < max

の 4通りだけ調べればOK。

並べ方の場合の数については、

{a,a,a,a,a,a} : 1
{a,a,a,a,a,b} : 6C1 = 6
{a,a,a,a,b,b} : 6C2 = 15
{a,a,a,b,b,b} : 6C3 = 20
{a,a,a,a,b,c} : 6P2 = 30
{a,a,a,b,b,c} : 6C1 * 5C2 = 60
{a,a,b,b,c,c} : 6C2 * 4C2 = 90
{a,a,a,b,c,d} : 6P3 = 120
{a,a,b,b,c,d} : 6P2 * 4C2 = 180
{a,a,b,c,d,e} : 6P4 = 360
{a,b,c,d,e,f} : 6P5 = 720

となります（実際に解いた時に用いたメモを紛失したので間違ってるかも...、変なとこあったら教えてください><）

あとはこれを落ち着いてコードに起こすと、以下のコードになります。

#include <iostream>
using namespace std;

int main() {
    int a, b;
    scanf("%d.%d", &a, &b);
    int sum = (a * 100 + b) / 25;
    long long ans = 0;
    
    for (int i = 0; i < 101; ++i) {
        for (int j = i; j < 101; ++j) {
            for (int k = j; k < 101; ++k) {
                int l = sum - i - j - k;
                if (l < k) break;
                if (l > 100) continue;
                
                int m = 100 - l;
                if      (i < j && j < k && k < l)
                    ans += 180 + (i + m) * 360 + i * m * 720;
                else if (i == j && j < k && k < l)
                    ans += 60 + i * 180 + m * 120 + i * m * 360;
                else if (i < j && j == k && k < l)
                    ans += 90 + (i + m) * 180 + i * m * 360;
                else if (i < j && j < k && k == l)
                    ans += 60 + i * 120 + m * 180 + i * m * 360;
                else if (i == j && j < k && k == l)
                    ans += 20 + (i + m) * 60 + i * m * 180;
                else if (i == j && j == k && k < l)
                    ans += 15 + i * 60 + m * 30 + i * m * 120;
                else if (i < j && j == k && k == l)
                    ans += 15 + i * 30 + m * 60 + i * m * 120;
                else if (i == j && j == k && k == l)
                    ans += 1 + (i + m) * 6 + i * m * 30;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

もしこれが想定解法として提示されたら窓からMacBookAirを投げ出すレベルの解法ですが...
まぁこんな面倒くさい場合分け、競プロerだとあんまりしないですけど、そこまで競プロになれてない人だと逆にこっちで頑張るのが自然かも、とも思いました。