codeiq.jp
100万円を正解者数で割った金額が賞金としてもらえるというルール
6月20日ぐらいに挑戦した時は挑戦済みは2,3百人ぐらいだったけど、最終的には986人が挑戦したらしい
問題の内容は、数値の配列と目標値が与えられるので、数値3つの合計が目標値になる組み合わせの数を答える、というものです
「これ蟻本でやったところだ!」というわけで、わりと簡単に解けました
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: Kindle版
- この商品を含むブログを見る
この問題とだいたい同じ問題には3SUMという名前がついていてWikipediaにも記事があります
Pythonだと何故か間に合わなかったので、C++で書きなおしました
↓解説によるとPythonやRubyでもがんばれば通せたみたいです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