Yak!の日記： Google Code Jam 2011 Round2
ooo-o--- で 39pts 594 位。Round 2 は通過ならず。仕方ないというか大健闘と言っていい感じかと。初の T シャツゲットです、多分。とりあえず small 専業と割り切ったのはレベル相応で悪くない判断だったと思っています。B-large、C-large、D-small は解けても良かったかもと思わないでもないですが、バグ無しで思ったコードをさくっと書けないというコーディング力や、練習が足りないという点も含めてやっぱり実力がちょっと足りなかったと思います。なお、以下は Contest Analysis を読まない状態で書いています。
A. Airport Walkways
速度が遅いところから greedy に t 秒とっていけばいいだけ。
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI x, s, r, t, n; cin >> x >> s >> r >> t >> n;
vector<UI> len(n), speed(n);
UI len0 = x;
REP(i, n) {
UI b, e, w; cin >> b >> e >> w;
len[i] = e - b;
speed[i] = s + w;
len0 -= len[i];
}
if(len0) {
len.push_back(len0);
speed.push_back(s);
}
vector<UI> index(len.size()); iota(RNG(index), 0);
sort(RNG(index), [&](UI i1, UI i2) { return speed[i1] < speed[i2]; });
double tt = t, result = 0;
REP(i, index.size()) {
UI ii = index[i];
UI leni = len[ii], speedi = speed[ii];
//cerr << i << ':' << result << ':' << leni << ':' << speedi << endl;
if(tt > 0) {
double speed_ = speedi + (r - s);
if(leni / speed_ >= tt) {
result += tt + (leni - tt * speed_) / speedi;
tt = 0;
} else {
result += leni / speed_;
tt -= leni / speed_;
}
} else {
result += double(leni)/speedi;
}
}
cout << "Case #" << casenum+1 << ": " << fixed << setprecision(12) << result << endl;
}
return 0;
}
B. Spinning Blade
small 専用で割り切ってループでぶん回しています。large は和の取り方を工夫するんだろうなぁと思いつつスキップ。ちゃんと復習しておきたい問題です。
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI r, c, d; cin >> r >> c >> d;
vector<vector<UI>> table(r, vector<UI>(c, d));
for(auto &v1 : table) {
string s; cin >> s;
REP(i, c) {
v1[i] += (s[i] - '0');
}
}
UI k = min(r,c); bool flag = false;
while(k >= 3) {
REP(i, r-k+1) {
REP(j, c-k+1) {
ULL sx = 0;
ULL sy = 0;
ULL sum = 0;
REP(ii, k) {
REP(jj, k) {
if((ii == 0 || ii == k - 1) && (jj == 0 || jj == k - 1)) continue;
sx += ii * table[i+ii][j+jj];
sy += jj * table[i+ii][j+jj];
sum += table[i+ii][j+jj];
}
}
//cerr << k << ':' << sx << ':' << sy << ':' << sum << endl;
if(2 * sx == (k-1)*sum && 2*sy == (k-1)*sum) {
flag = true;
break;
}
}
if(flag) break;
}
if(flag) break;
--k;
}
if(k >= 3) {
cout << "Case #" << casenum+1 << ": " << k << endl;
} else {
cout << "Case #" << casenum+1 << ": IMPOSSIBLE" << endl;
}
}
return 0;
}
C. Expensive Dinner
small だけとはいえ、これが解けたのは嬉しかったですね。題意から費用そのものは単調非減少、その約数(通せる番号)の数も単調非減少になります。また最終的な費用は N 以下の全ての数字の最小公倍数になることが分かります。ということで最小回数の時はできるだけ早く最小公倍数までに増加(＝約数の数を増やす)させ最大回数の時はできるだけ遅く最小公倍数までに増加させればいいわけです。こう考えると最小回数の場合は、2^l、3^m、5^n、7^o、…(l、m、n、o、… は N 以下になる最大値)という順に通していけばいいことになります。つまり N 以下の素数の個数が回数になります。一方最大回数の場合は 1、2、2^2、…、2^l、3、3^2、…、3^m、… と通していけば 1 個ずつ素因数が増えるので最も遅い場合になります。以下のコードでは 1 ～ N まで愚直に回して指数の最大値を求めていますが、素数についてループを回して N 以下になる最大指数を求めるべきですね。
large については 10^12 が厳しい条件なわけですが、sqrt(N) より大きな素数の場合、指数が 1 となり最大回数の場合でも最小回数の場合でも 1 回としか数えられないので最大回数-最小回数を求める今回の場合は完全に無視できる、つまり sqrt(10^12) = 10^6 まで調べるだけで OK ということになります。@uwitenpen さんの tweet を見て初めて気付いたので時間中には思いつけなかったと思います。
template<typename T, typename OutputIterator>
inline T pshieve(T n, OutputIterator out) // type should be changable
{
T count = 0;
if(n<2) return count;
*out++=2;
++count;
std::vector<bool> v(n/2);
const T nn1 = static_cast<T>(std::sqrt(n));
const T nn = max(nn1, n/nn1);
T i;
for(i=3;i<=nn;i+=2) {
if(v[i/2-1]==false) {
*out++=i;
++count;
}
for(T j=i+i+i;j<=n;j+=i+i) {
v[j/2-1]=true;
}
}
for(;i<=n;i+=2) {
if(v[i/2-1]==false) {
*out++=i;
++count;
}
}
return count;
}
int main(void)
{
ios_base::sync_with_stdio(false);
vector<ULL> primes;
pshieve(1000ULL, back_inserter(primes));
UI cases; cin >> cases;
REP(casenum, cases) {
ULL n; cin >> n;
vector<ULL> counts(primes.size());
REPV(ULL, i, n) {
ULL ii = i+1;
REPV(ULL, j, primes.size()) {
ULL count = 0;
while(ii % primes[j] == 0ULL) {
ii /= primes[j];
++count;
}
if(counts[j] < count) counts[j] = count;
}
}
ULL minimum = count_if(RNG(counts), [&](ULL v) { return v > 0; });
ULL maximum = (n>1ULL?1ULL:0ULL) + accumulate(RNG(counts), 0ULL);
cout << "Case #" << casenum+1 << ": " << maximum - minimum << endl;
}
return 0;
}
D. A.I. War
時間中に書いていたコードは BFS ですがデバッグしている途中で終わりました。色々と無駄が多く直したところで結局 TLE します(上のコード)。s.c[0] = true; の代わりに s.c[0] == true; と書いていたのがバグだったのですが、これ、警告が出ません。こういう場合、大抵は式の値を使っていないとかいう警告が出るのですが、vector<bool> のため値を参照するだけで色々と処理が発生しているので警告が出ないのだと思われます。vector<bool> さんはマジ鬼門。当初 bitset 使おうかとも思ったのですが使い慣れてないので逃げました。というか、36 だから 32 ビット超えてるし、と思ってしまったのですが unsigned long long は 64 ビットなので普通にビットフラグで持てるんですよね。さらに threaten な範囲は毎回調べる必要はない、というのを修正したのが下のコードでこれで small は通ります。
struct St
{
vector<bool> c;
vector<bool> t;
};
bool operator<(const St& s1, const St &s2)
{
return s1.c < s2.c || s1.c == s2.c && s1.t < s2.t;
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI p, w; cin >> p >> w;
vector<vector<char> > mat(p, vector<char>(p, 0));
REP(i, w) {
int x, y; char c; cin >> x >> c >> y;
mat[x][y] = mat[y][x] = 1;
}
set<St> st, st_;
St s;
s.c = vector<bool>(p, false);
s.t = vector<bool>(p, false);
s.c[0] = true;
REP(i, p) {
if(mat[0][i]) s.t[i] = true;
}
auto check = [&](const St& ss)->bool { return ss.t[1]; };
st.insert(s);
UI c = p, t = 0; bool flag = false; UI cur = 1;
while(1) {
if(cur > p) break;
//cerr << st.size() << endl;
for(auto &v : st) {
if(check(v)) {
flag = true;
if(c > cur || c == cur && count(RNG(v.t), true) > t) {
c = cur;
t = count(RNG(v.t), true);
}
} else {
//cerr << "TH1" << endl;
REP(i, p) {
if(v.c[i] == false) continue;
//cerr << "TH2" << endl;
REP(j, p) {
if(mat[i][j] && v.c[j] == false) {
//cerr << "TH3" << endl;
St temp = { v.c, vector<bool>(p, false) };
temp.c[j] = true;
REP(ii, p) {
if(temp.c[ii]) {
REP(jj, p) {
if(mat[ii][jj] && temp.c[jj] == false) {
temp.t[jj] = true;
}
}
}
}
st_.insert(temp);
}
}
}
}
}
if(flag) break;
swap(st, st_);
++cur;
}
cout << "Case #" << casenum+1 << ": " << c-1 << ' ' << t << endl;
}
return 0;
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI p, w; cin >> p >> w;
vector<vector<char> > mat(p, vector<char>(p, 0));
REP(i, w) {
int x, y; char c; cin >> x >> c >> y;
mat[x][y] = mat[y][x] = 1;
}
ULL checker = 0;
REP(i, p) {
if(mat[1][i]) checker |= (1ULL << i);
}
set<ULL> st, st_;
ULL s = 1ULL;
auto check = [&](ULL ss)->bool { return ss & checker; };
auto th = [&](ULL ss)->UI {
ULL t = 0; int count = 0;
REP(i, p) {
if(((ss >> i) & 1ULL) == 0) continue;
REP(j, p) {
if(mat[i][j] && ((ss >> j) & 1ULL) == 0 && ((t >> j) & 1ULL) == 0) {
t |= (1ULL << j);
++count;
}
}
}
return count;
};
st.insert(s);
UI c = p, t = 0; bool flag = false; UI cur = 1;
while(1) {
if(cur > p) break;
//cerr << st.size() << endl;
for(auto &v : st) {
if(check(v)) {
flag = true;
if(c > cur || c == cur && th(v) > t) {
c = cur;
t = th(v);
}
} else {
//cerr << "TH1" << endl;
REP(i, p) {
if(((v >> i) & 1ULL) == 0) continue;
//cerr << "TH2" << endl;
REP(j, p) {
if(mat[i][j] && ((v >> j) & 1ULL) == 0) {
//cerr << "TH3" << endl;
ULL temp = v;
temp |= (1ULL << j);
st_.insert(temp);
}
}
}
}
}
if(flag) break;
swap(st, st_);
++cur;
}
cout << "Case #" << casenum+1 << ": " << c-1 << ' ' << t << endl;
}
return 0;
}
まとめ
2008 は Round2 661 位で通過、Round3 885 位、2009 は Round1 で落ち、2010 は Round2 1005 位と評価に困る所ではありますが 2008 はまぐれとするとちょっとずつ向上という言い方もできるかもしれません。反省的には、毎回コーディング力と練習が足りない、ばっかり言っている気がしますが、事実だからしょうがないというか。
テンプレ
// Using C++0x mode in g++ 4.6.0
#include <iostream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <tuple>
#include <initializer_list>
#include <cmath>
// Boost library can be retrieved from http://www.boost.org/
// I used 1.46.1
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;
#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)
using namespace std;
template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer last)
{ return boost::irange(first, last); }
Google Code Jam 2011 Round2 More ログイン