読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

CodeIQ「ホリエモンからの挑戦状」を解いて賞金1246円を手に入れた

競技プログラミング

codeiq.jp
100万円を正解者数で割った金額が賞金としてもらえるというルール
6月20日ぐらいに挑戦した時は挑戦済みは2,3百人ぐらいだったけど、最終的には986人が挑戦したらしい

問題の内容は、数値の配列と目標値が与えられるので、数値3つの合計が目標値になる組み合わせの数を答える、というものです

「これ蟻本でやったところだ!」というわけで、わりと簡単に解けました

2つ選ぶのを総当りして、残りの数が配列に含まれているかを判定すれば\(O(N^2)\)ぐらいで解けます(配列の長さを\(N\)とする)
この問題とだいたい同じ問題には3SUMという名前がついていてWikipediaにも記事があります

Pythonだと何故か間に合わなかったので、C++で書きなおしました
↓解説によるとPythonRubyでもがんばれば通せたみたいですcodeiq.jp

C++のコード

#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>

using namespace std;

int main(void) {
	int L, N;
	cin >> L >> N;
	int t;
	vector<int> A;
	unordered_set<int> S;
	while(cin >> t) {
		A.emplace_back(t);
		S.emplace(t);
	}
	sort(A.begin(), A.end());
	
	int count = 0;
	
	for(int i = 0; i < N; ++i) {
		int d = L - A[i];
		for(int j = i + 1; j < N; ++j) {
			int d2 = d - A[j];
			if(d2 <= A[j]) {
				break;
			}
			if(S.find(d2) != S.end()) {
				count += 1;
			}
		}
	}
	cout << count << endl;
	
	return 0;
}

手元だと0.85秒ぐらいで終わるPythonのコード

import bisect
import sys
I = map(int, sys.stdin.read().split())

L = I[0]
N = I[1]
A = I[2:]

s = set()
for i in xrange(N):
    s.add(A[i])

A.sort()

count = 0

for i in xrange(N):
    d = L - A[i]
    n = bisect.bisect_left(A, d - A[-1], i + 1)
    for j in xrange(n, N):
        d2 = d - A[j]
        if d2 <= A[j]:
            break
        if d2 in s:
            count += 1
print count
-->