Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@emattsan

第23回オフラインリアルタイムどう書く を C++のテンプレート で解く

More than 5 years have passed since last update.

久々にC++テンプレートプログラミングに挑戦してみました。

お題はこちらです。

C++で別解

まず鍋谷さんの解答を参考にC++でもう一度書いたもの。

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

int get_length(const std::string& values, int pos, int lengths[])
{
    if(std::isdigit(values[pos]) && (lengths[pos] == 0))
    {
        int l[] =
        {
            (values[pos] < values[pos - 6]) ? get_length(values, pos - 6, lengths) : 0,
            (values[pos] < values[pos + 6]) ? get_length(values, pos + 6, lengths) : 0,
            (values[pos] < values[pos - 1]) ? get_length(values, pos - 1, lengths) : 0,
            (values[pos] < values[pos + 1]) ? get_length(values, pos + 1, lengths) : 0
        };

        lengths[pos] = *std::max_element(std::begin(l), std::end(l)) + 1;
    }

    return lengths[pos];
}

std::string solve(const std::string& input)
{
    std::string source = std::string(6, '/') + input + std::string(6, '/');

    int lengths[36] = {};
    for(int pos = 0; pos < 36; ++pos)
    {
        get_length(source, pos, lengths);
    }

    std::ostringstream oss;
    oss << *std::max_element(std::begin(lengths), std::end(lengths));

    return oss.str();
}

void test(const std::string& input, const std::string& expected)
{
    std::string actual = solve(input);
    if(expected == actual)
    {
        std::cout << "." << std::flush;
    }
    else
    {
        std::cout << "\ninput: " << input << ", expected: " << expected << ", acutal: " << actual << std::endl;
    }
}

int main(int argc, char* argv[])
{
    /*0*/ test( "01224/82925/69076/32298/21065", "6" );
    /*1*/ test( "03478/12569/03478/12569/03478", "10" );
    /*2*/ test( "09900/28127/87036/76545/87650", "10" );
    /*3*/ test( "77777/77777/77777/77777/77777", "1" );
    /* ... */
    /*50*/ test( "02489/77571/84873/03879/84460", "7" );

    std::cout << std::endl;

    return 0;
}

C++のテンプレートで書く

これをふまえて。
C++のテンプレートで書き直してみます。
実行環境はC++コンパイラです。「コンパイルが通る」がすなわち「テストにパスした」ことになります。
久々のテンプレートプログラミングとはいえ、脇が甘い感じ。

template<bool F, typename T, typename U> struct If;
template<typename T, typename U> struct If<true,  T, U> { static const int value = T::value; };
template<typename T, typename U> struct If<false, T, U> { static const int value = U::value; };

template<typename T, typename U>
struct Max
{
    static const int value = If<(T::value > U::value), T, U>::value;
};

struct Zero { static const int value = 0; };

template<int N>
struct Table
{
    constexpr static char chr(int n);
};

template<int N, int POS, char C>
struct Length
{
    static const int value = Max<
        Max<
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS - 6),
                Length<N, POS - 6, Table<N>::chr(POS - 6)>,
                Zero
            >,
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS + 6),
                Length<N, POS + 6, Table<N>::chr(POS + 6)>,
                Zero
            >
        >,
        Max<
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS - 1),
                Length<N, POS - 1, Table<N>::chr(POS - 1)>,
                Zero
            >,
            If<
                Table<N>::chr(POS) < Table<N>::chr(POS + 1),
                Length<N, POS + 1, Table<N>::chr(POS + 1)>,
                Zero
            >
        >
    >::value + 1;
};

template<int N, int POS>
struct Length<N, POS, '/'>
{
    static const int value = 0;
};

template<int N, int POS = 35>
struct Solve
{
    static const int value = Max<
        Length<N, POS, Table<N>::chr(POS)>,
        Solve<N, POS - 1>
    >::value;
};

template<int N>
struct Solve<N, -1>
{
    static const int value = 0;
};

template<int M, int N> struct Assert;
template<int N> struct Assert<N, N> {};

#define TEST(N, S, E) \
template<> constexpr char Table<N>::chr(int n) { return ("//////" S "//////")[n]; } \
Assert<E, Solve<N>::value> assert##N

TEST(  0, "01224/82925/69076/32298/21065",  6 );
TEST(  1, "03478/12569/03478/12569/03478", 10 );
TEST(  2, "09900/28127/87036/76545/87650", 10 );
/* ... */
TEST( 50, "02489/77571/84873/03879/84460",  7 );
1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
emattsan
ソフトウェアエンジニア、言語オタク
esm
ソフトウェアで未来をつくる、人のチカラで未来をつくる。福井、東京、沖縄で活動するエンジニア集団。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?