トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
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());
}
解説
動的計画法で、その添字までの、問題の選び方の場合の数を、順番に更新してます。