ARC 043 - B: 難易度

・問題
B: 難易度 - AtCoder Regular Contest 043 | AtCoder

・感想
これはDPだなーとコンテスト中に問題見て思った。しかも私でもすぐ気づく感じなので、割と典型な感じの。ただ、DPを実装するにあたって、私はメモ化再起でしか書けなくて、dpの配列をforループで回して求めるあのスマートなやつがどうしてもまだすらすら書けないので、メモ化再起に頼ったら詰んだ(http://arc043.contest.atcoder.jp/submissions/470543)。やっぱめっちゃ関数呼び出しがあるから遅いんだなあと実感。
考え方は何も間違っていなかったが、メモ化再起とループでの実装は考え方が逆流するので、時間内に正しいのをつくるのはムリだった。この形に慣れるようにしないといけないなあというのを今回のコンテストで感じた。

・実装(C++)

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

int n, d[100000];
const int mod=1e9+7;

int dp[100001][4]={0}; //問題xをy問目に選ぶ組み合わせ
int sum[4]={0}; //今までの累積

int main(){
	//input
	scanf(" %d", &n);
	for(int i=0; i<n; ++i) scanf(" %d", &d[i]);
	
	sort(d, d+n);
	
	int pre=0;
	
	for(int i=0; i<n; ++i){
		dp[i][0]=1; //それぞれの問題を1問目として選ぶ方法は1通り	
		
		while(d[i] >= d[pre]*2){ //この問題を次の問題の候補にできる
			for(int j=1; j<4; ++j){
				sum[j]+=dp[pre][j-1];
				sum[j]%=mod;	
			}
			++pre;
		}
		
		//そこまでの合計が問題iをj問目として選ぶことができる合計の組み合わせになる。
		for(int j=1; j<4; ++j) dp[i][j]=sum[j];
	}
	
	int ans=0;
	for(int i=0; i<n; ++i){
		ans+=dp[i][3];
		ans%=mod;
	}
	printf("%d\n", ans);	
}

今回は76位でした。ABCでは全完、ARCでは2完が最近の目標になってきている。もう少し知識増やす必要があるなとは感じるので、ある程度夏休みで身につけたい。