トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ARC-043-B 難易度

■■■問題■■■

高橋君はプログラミングコンテストを開く仕事をしている。
高橋君はストックしているN個の問題から4問を選んでコンテストに出題する。
各問題には「難易度」という正の整数が決められており、i番目の問題の難易度はDiである。
選ぶ問題は以下の3つの条件を満たしていなければならない。

●2問目の難易度は1問目の難易度の2倍以上である。
●3問目の難易度は2問目の難易度の2倍以上である。
●4問目の難易度は3問目の難易度の2倍以上である。

上の条件のもとでN個の問題から4問選ぶとき、何通りの選び方があるか求めよ。
この値は非常に大きくなり得るので1000000007 (=10の9乗+7)で割った余りを求めよ。

■■■入力■■■

N
D1
D2
・
・
・
DN

1行目には高橋君がストックしている問題の個数 N(4 <= N <= 10万) が与えられる。
2行目からのN行のうちi行目にはi番目の問題の難易度を表す整数 Di(1 <= Di <= 10万)が与えられる。

■■■出力■■■

高橋君の問題の選び方の通り数を1000000007 (=10の9乗+7)で割った余りを1行で出力せよ。
出力の末尾に改行を入れること。


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static IEnumerable<string> GetInputEnum()
    {
        if (InputPattern == "Input1") {
            foreach (string EachStr in new string[] { "5", "1", "2", "4", "5", "10" })
                yield return EachStr;
            //2
            //1,2,3,5 問目もしくは 1,2,4,5 問目を選ぶことができます
        }
        else if (InputPattern == "Input2") {
            for (int I = 10; I <= 20; I++) yield return I.ToString();
            //0
            //1つも条件に合う選び方がないこともあります
        }
        else if (InputPattern == "Input3") {
            yield return "20";
            for (int I = 1; I <= 20; I++) yield return I.ToString();
            //94
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) yield return wkStr;
        }
    }

    static void Main()
    {
        IEnumerable<string> InputEnum = GetInputEnum();
        int[] DArr = InputEnum.Skip(1).Select(X => int.Parse(X)).ToArray();

        Array.Sort(DArr);
        int UB = DArr.GetUpperBound(0);

        //尺取法で、STLのUpper_Boundもどき
        //その難易度の半分以下で最大の難易度の添字
        int[] STL_UB_Arr = new int[DArr.Length];
        int L = -1;
        for (int R = 0; R <= UB; R++) {
            while (L + 1 <= UB && DArr[L + 1] <= DArr[R] / 2) L++;
            STL_UB_Arr[R] = L;
            Console.WriteLine("STL_UB_Arr[{0}] = {1}", R, STL_UB_Arr[R]);
        }

        //場合の数[DArrでの添字]なDP表
        int[] PrevDP = new int[DArr.Length];
        int[] RuikeiArr = new int[DArr.Length];

        //初期化
        for (int X = 0; X <= UB; X++) {
            PrevDP[X] = 1;
        }

        for (int N = 2; N <= 4; N++) {
            int[] CurrDP = new int[DArr.Length];

            for (int X = 0; X <= UB; X++) {
                RuikeiArr[X] = PrevDP[X];
                if (X > 0) RuikeiArr[X] += RuikeiArr[X - 1];
                RuikeiArr[X] %= 1000000007;

                //和の法則でDP表を更新
                int KasanUB = STL_UB_Arr[X];
                if (KasanUB > -1) {
                    CurrDP[X] = RuikeiArr[KasanUB]; //貰うDP
                }
            }
            Console.WriteLine(new string('■', 15));
            Console.WriteLine("{0}問目までの場合の数", N);
            PrintDP(CurrDP);

            PrevDP = CurrDP;
        }

        int Answer = 0;
        foreach (int EachInt in PrevDP) {
            Answer = (Answer + EachInt) % 1000000007;
        }
        Console.WriteLine(Answer);
    }

    static void PrintDP(int[] pCurrDP)
    {
        var sb1 = new System.Text.StringBuilder();
        var sb2 = new System.Text.StringBuilder();

        for (int I = 0; I <= pCurrDP.GetUpperBound(0); I++) {
            sb1.AppendFormat("[{0,2}]", I);
            sb2.AppendFormat(" {0,2} ", pCurrDP[I]);
        }
        Console.WriteLine(sb1.ToString());
        Console.WriteLine(sb2.ToString());
    }
}


C#でのデバッグ情報付の実行結果

STL_UB_Arr[0] = -1
STL_UB_Arr[1] = 0
STL_UB_Arr[2] = 1
STL_UB_Arr[3] = 1
STL_UB_Arr[4] = 3
■■■■■■■■■■■■■■■
2問目までの場合の数
[ 0][ 1][ 2][ 3][ 4]
  0   1   2   2   4
■■■■■■■■■■■■■■■
3問目までの場合の数
[ 0][ 1][ 2][ 3][ 4]
  0   0   1   1   5
■■■■■■■■■■■■■■■
4問目までの場合の数
[ 0][ 1][ 2][ 3][ 4]
  0   0   0   0   2
2


C++のソース

#include <algorithm>
#include <stdio.h>
#include <string>
#include <valarray>
#include <vector>

std::string InputPattern = "Input1";

int Dummy;
void PrintDP(std::valarray<int> pCurrDP);

std::vector<int> GetInputVect()
{
    std::vector<int> WillReturn;

    if (InputPattern == "Input1") {
        int wkArr[] = {1,2,4,5,10};
        for(int I=0;I<=sizeof(wkArr)/sizeof(wkArr[0])-1;I++)
            WillReturn.push_back(wkArr[I]);
        //2
        //1,2,3,5 問目もしくは 1,2,4,5 問目を選ぶことができます
    }
    else if (InputPattern == "Input2") {
        for(int I=11;I<=20;I++) WillReturn.push_back(I);
        //0
        //1つも条件に合う選び方がないこともあります
    }
    else if (InputPattern == "Input3") {
        for(int I=1;I<=20;I++) WillReturn.push_back(I);
        //94
    }
    else {
        int ScanCnt;
        Dummy = scanf_s("%d",&ScanCnt);
        for(int I=1;I<=ScanCnt;I++){
            int wkInt;
            Dummy = scanf_s("%d",&wkInt);
            WillReturn.push_back(wkInt);
        }
    }
    return WillReturn;
}

int main()
{
    std::vector<int> DVect = GetInputVect();
    std::sort(DVect.begin(),DVect.end());
    int UB = (int)DVect.size()-1;

    //尺取法で、STLのUpper_Boundもどき
    //その難易度の半分以下で最大の難易度の添字
    std::valarray<int> STL_UB_Arr(0,UB+1);
    int L = -1;
    for (int R = 0; R <= UB; R++) {
        while (L + 1 <= UB && DVect.at(L + 1) <= DVect.at(R) / 2) L++;
        STL_UB_Arr[R] = L;
        printf("STL_UB_Arr[%d] = %d\n",R,STL_UB_Arr[R]);
    }

    //場合の数[DArrでの添字]なDP表
    std::valarray<int> PrevDP(1,UB+1);
    std::valarray<int> RuikeiArr(0,UB+1);

    for (int N = 2; N <= 4; N++) {
        std::valarray<int> CurrDP(0,UB+1);

        for (int X = 0; X <= UB; X++) {
            RuikeiArr[X] = PrevDP[X];
            if (X > 0) RuikeiArr[X] += RuikeiArr[X - 1];
            RuikeiArr[X] %= 1000000007;

            //和の法則でDP表を更新
            int KasanUB = STL_UB_Arr[X];
            if (KasanUB > -1) {
                CurrDP[X] = RuikeiArr[KasanUB]; //貰うDP
            }
        }

        printf("%d問目までの場合の数\n",N);
        PrintDP(CurrDP);

        PrevDP = CurrDP;
    }

    int Answer = 0;
    for (int X = 0; X <= UB; X++) {
        Answer = (Answer + PrevDP[X]) % 1000000007;
    }
    printf("%d\n",Answer);

    return 0;
}

void PrintDP(std::valarray<int> pCurrDP)
{
    std::string str1,str2;

    for (int X = 0; X <= (int)pCurrDP.size()-1; X++) {
        char wkChar[200];
        Dummy = sprintf_s(wkChar,"[%2d]",X); str1+=wkChar;
        Dummy = sprintf_s(wkChar," %2d ",pCurrDP[X]); str2+=wkChar;
    }
    puts(str1.c_str());
    puts(str2.c_str());
}


解説

動的計画法で、その添字までの、問題の選び方の場合の数を、順番に更新してます。