ICFPC2019
職場の同僚に誘われて初参加。"Gon the Fox"の一員でした。面白かったので覚えてるうちに自分がやったことの記録や感想を書きなぐっておく次第。
day1
職場のエンジニアメインのチームなので、終業後のオフィスを占領して参加。問題が公開されてとりあえず読む。ソルバー班とインフラ班に分かれようという事になり、インフラ系の知識が皆無な自分はソルバー班に。
問題は「2次元グリッドで表される地形をロボットで巡って全部塗ってね。アイテム使って塗る面積を広げたり、ロボットの数を増やしたりもできるよ」という感じだった。
最初のお仕事はInputの構文解析。探索領域が (0,0),(1,0),(1,1),(0,1) みたいな文字列として渡されてたり、使えるアイテムも B(2,3) という感じで文字列で与えられるので、これを慣れ親しんだ競プロっぽい形式(W×Hの文字でフィールドを表したりする)に直すコンバータを書くことに。
とりあえず皆でやって最初に動いたやつを使おうという事になり、とりあえず書いたらなんか動いたのでそれを使ってもらえることになった。この辺で周囲の飲食店が閉まりそうな時間になってきたので夕食(夜食?)へ。
その後はしばらくソルバーを書いていた。まずはアイテムを使わずにという事で適当な貪欲を書いたりしていた。Lightning Sectionの終了ちょっと前に用事で抜けなければならなかったので、始発で一時帰宅。ついでに仮眠を取った。Slackの通知で目を覚ますとロボットを増やすアイテムが追加されたとか激ヤバな事が書いてあったので急いでオフィスへと戻った。80/300ケースという事だったので、自分はひたすら1人用の最適化に勤しんでいたが、用事で抜けるちょっと前に微妙にステップ数を減らすのに成功しただけだった。つらい…。
day2
用事を終えて戻れたのは、まもなく日付が変わって日曜になろうかという頃。Ful Contestの仕様はとっくに発表された後で、Slackがざわざわしていたので早く戻らねば…と思っていたが電車を間違える痛恨のミスにより帰還が30分くらい遅れた。ちなみに帰還は最初に設定されていた締切である23時よりも後だった。ビッグウェーブに乗り遅れた感が悲しい。
19時に「23時から15分おきにマイニング用の問題だすで。出された問題の解と、別に与えた仕様を満たす問題をセットで送るんやで」という仕様が発表され、デスマ不可避だったらしい。問題解くのは既存のソルバーの中で一番良い解を返しておけば当面良さそうで、パズルジェネレータの用意が急務のようだった。自分が手をつけようかという頃にはマイニング開始が翌9時からに延期されていたので、電車間違う程度の疲労度を加味して一度仮眠を取る事にした。
自分のジェネレータの方針はこんな感じ
- 含むべき点にフィールド周囲4辺の中点らへんを足しておく(サイズ制約用)
- 含むべき点をSelf-Intersectionが出来ないよう注意しながらプリム法っぽく結ぶ
- 今の領域に隣接するマスについて削った時の外周の頂点数の差分を計算しておき、(最低頂点数)と(最大頂点数)の中間値を目指すようにマスを選んで、最低の面積を満たすまで領域を広げていく
納期の9時を過ぎること1時間(申し訳ねぇ…)、こんな感じのマップが作れるように
多少制約でいじわるされても良いように頑張るぞ(๑•̀ㅂ•́)و✧ という気持ちで書いたが、他のチームのマップを見ていたら頑張り過ぎた感も否めない。完成が遅れてマイニングを3回くらい落としたのが激痛だったが、完成後は一度もマップ生成に失敗する事はなかったし、3回くらい問題が採用もされたのでまぁ良いかということに。
day3
複製はマラソンガチ勢のチームメンバーが対応済でレッドオーシャンだったので、テレポートの対応を試みていた。が、4時間くらいかけて全く良くならず最終的にはテレポート対応のコードを全部消した。実装力が足りなかったのか、見切りをつけるのがおそかったのか、どちらにしても対応が悔やまれる部分だった。
day3あたりにしてついにマイニングで稼いだお金はアイテムに換金した方がお得っぽい、という話になった(しばらくアイテム購入に関しては懐疑的な空気だった)。となるとやはり複製には対応した方が良さそうで、自分も複製をやるクライアントを書き始めたが、その頃には既存のソルバーがかなりのクオリティで、最終的にも太刀打ちできるケースはほとんどなかった。一応、300ケース中7ケースで自分の出力を使ってもらえたらしいが、無念…。
どのマップでどのアイテムを買うかの購入計画については、自分がナップサック的にやれば行けるでしょみたいな事を言いだした手前実装した。
チームではサーバで各問題への回答を集計していて、各提出のステップ数と購入したアイテムを記録していた。この提出群を用いると各提出の相対スコア 1000*log(areaSize) * Tbest / Tself を計算できて、その提出の価値を(相対スコア - 使った金額)、使った金額を容積として、各問題から1提出えらべるという制約の元、稼いだ金額を上限にナップサックする感じ。
貧乏だったので、クローンを2個買う解とか調べなくて良くない…？という意見もあったが、富豪はやる可能性があるし仮想敵としていれておくべき、と主張して調べてもらった。結局クローンを2個使った提出も採用されていたらしいので良かった。
ふりかえり
目に見える貢献は、入力コンバータ、問題ジェネレータ、提出セレクタくらいで、要となるソルバーは微小な貢献に終わってしまった。ちょっとしたものを書くのは早かったっぽいけど、マラソン的な部分がやはり弱いらしい。
チーム内ランキングページやサーバ提出スクリプトを次々仕上げていくインフラ班も見事で、初参加の身としてはみんなしゅごい…という感じであった。
チーム戦は機会が少なくICPC以来では…くらいの感じだったが、なかなか業務だけでは見られにくい同僚の凄さなんかも見られて刺激になり、面白かった。次があれば、もうちょっとマラソン的なところで貢献したいなというのと、重要そうな局面は予定を空けておくようにしたい。
国内予選2015 G. 複雑な折り紙
くるくるドア(模擬国内予選G)の担当者であるnotさんとMi_Sawaさんが揃ってGを解いておられたので，
ライブラリをぺたぺたして解いてみた次第．
方針は，外周の候補を列挙後に折り線基準で偏角ソートして，
どっちかの多角形に内包(strictly)されているものを除くという感じ．
とりあえずサンプルは通った．
// ACM-ICPC国内予選2015 G. 複雑な折り紙 #include <iostream> #include <vector> #include <complex> #include <algorithm> #include <cstdio> using namespace std; typedef complex<double> P; typedef vector<P> G; const double EPS = 1e-8; struct L { P p, q; L(P p, P q) : p(p), q(q) {} }; double dot(const P& a, const P& b) { return real(conj(a)*b); } double cross(const P& a, const P& b) { return imag(conj(a)*b); } double angle(const P& a, const P& b) { return arg(conj(a)*b); } bool ssIntersect(const L& a, const L& b){ if(abs(imag((a.q-a.p)/(b.q-b.p))) < EPS) return false; return cross(a.q-a.p, b.p-a.p)*cross(a.q-a.p, b.q-a.p) < 0 && cross(b.q-b.p, a.p-b.p)*cross(b.q-b.p, a.q-b.p) < 0; } P ssCrosspoint(const L& a, const L& b){ double A = cross(a.q-a.p, b.q-b.p); double B = cross(a.q-a.p, a.q-b.p); return b.p + B/A * (b.q-b.p); } G convexCut(const G& g, const P& p, const P& q){ G res; int n = g.size(); for(int i=0;i<n;i++){ P A(g[i]), B(g[(i+1)%n]); double p1 = cross(q-p, A-p); double p2 = cross(q-p, B-p); if(p1 > -EPS) res.push_back(A); if(p1*p2 < -EPS) res.push_back(A+cross(q-p, q-A)/cross(q-p, B-A)*(B-A)); } return res; } bool contains(const G& g, const P& p){ bool in = false; for(int i=0;i<g.size();i++){ P a(g[i]-p), b(g[(i+1)%g.size()]-p); if(imag(a) > imag(b)) swap(a,b); if(imag(a)<=0&&0<imag(b)) if(cross(a,b)<0) in = !in; if(abs(cross(a,b))<EPS&&dot(a,b)<EPS) return false; } return in; } P footPerp(const L& l, const P& p) { return l.p + (l.q-l.p)*(dot(l.q-l.p, p-l.p) / norm(l.q-l.p)); } P lineShadow(const L& l, const P& p){ return 2.0*footPerp(l, p)-p; } pair<int, double> solve(const G& poly, const L& cut){ G g1 = convexCut(poly, cut.p, cut.q); G g2 = convexCut(poly, cut.q, cut.p); P p0(0, 0); int addNum = 0; for(const P& p : g1){ if(abs(cross(p-cut.p, cut.q-cut.p)) < EPS){ p0 = p0 + p; addNum++; } } for(P& p : g2){ p = lineShadow(cut, p); } p0 = p0/(double)addNum; vector<pair<double, P>> vp; for(const P& p : g1){ double agl = angle(cut.q-cut.p, p-p0); vp.push_back(make_pair(agl, p)); } for(const P& p : g2){ double agl = angle(cut.q-cut.p, p-p0); vp.push_back(make_pair(agl, p)); } for(int i=0;i<g1.size();i++){ L l1(g1[i], g1[(i+1)%g1.size()]); for(int j=0;j<g2.size();j++){ L l2(g2[j], g2[(j+1)%g2.size()]); if(ssIntersect(l1, l2)){ P cp = ssCrosspoint(l1, l2); double agl = angle(cut.q-cut.p, cp-p0); vp.push_back(make_pair(agl, cp)); } } } sort(vp.begin(), vp.end(), [](const pair<double, P>& a, const pair<double, P>& b){ return a.first < b.first; } ); G out; for(const pair<double, P>& pr : vp){ const P& p = pr.second; if(!contains(g1, p) && !contains(g2, p)){ int n = out.size(); if(n >= 1){ if(norm(out.back() - p) < EPS) continue; } if(n >= 2){ if(abs(cross(out[n-1]-out[n-2], p-out[n-2])) < EPS){ out.back() = p; continue; } } out.push_back(p); } } if(norm(out[0] - out.back()) < EPS) out.pop_back(); pair<int, double> res(out.size(), 0); for(int i=0;i<out.size();i++){ res.second += abs(out[i] - out[(i+1)%out.size()]); } return res; } int main(){ int n; while(cin >> n && n){ G g(n); for(int i=0;i<n;i++){ int x, y; cin >> x >> y; g[i] = P(x,y); } pair<int, double> res(0, 0); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ P mid = 0.5*(g[i]+g[j]); P dir = (g[j]-g[i])*P(0, 1) + mid; L l(mid, dir); res = max(res, solve(g, l)); } } printf("%.8lf\n", res.second); } }
SRM639
すごく久しぶりに出てみた。
- -
250. AliceGame
問題：{1, 3, ..., 2*n-1} の和がx+yになるようなnを選び、その部分和でxが作れるならそのときの要素数の最小値を求める問題。できなかったら-1を返す。
- とりあえず Σ(2*i-1) を求めるぜ！って思ってたら n^2 だった。
- x+y≦2*10^12 だったので、適当にループ回してもnは求まりそう。
- まぁ、easyだしxから大きい要素を貪欲に引いておけば良いのでは、と思うも自信ない。
- とりあえず小さいケースで全探索してみる。
- まず、x=2 や y=2 だとさすがに作れないことが判明。
- x=9, y=7 みたいなケースだと貪欲に引くと x=2 ができてやばい事が判明。
- 2に気をつけておけば良さそう、と思って書いたらサンプル通ったので提出した。
class AliceGame { public: long long findMinimumValue(long long x, long long y) { if(x+y == 0) return 0; for(long long turn=1;turn*turn<=x+y;turn++){ if(turn*turn != x+y) continue; long long res = 0; for(int i=turn;i>=1;i--){ if(x >= 2*i-1 && x-(2*i-1) != 2){ x -= 2*i-1; res++; } } return x==0 ? res : -1; } return -1; } };
500. BoardFolding
問題：白黒に塗られたN×Mのグリッド用紙を、同じ模様のところが重なるように折っていく。出来上がりの図形は何通り？的な問題。
- easy通るか怖かったので現実に帰ってくる。
- こういう問題は1次元の問題に分解できる場合があった気がした。
- 横にこう折ったら新たに縦のここが折れるようになったぜ！とか無いので独立っぽい。
- ので、各方向について問題を解いて結果を乗算してみたらサンプル通った。
- 念のため最大ケースを投げてみたら0.6secくらいだったので提出した。
int mem[251][251]; int same[250][250]; int toNumber(char c){ if(isdigit(c)) return c-'0'; if(islower(c)) return c-'a'+10; if(isupper(c)) return c-'A'+36; if(c == '#') return 62; return 63; } class BoardFolding { int solve(const vector< vector<int> >& v){ int n = v.size(), m = v[0].size(); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ same[i][j] = 1; for(int k=0;k<m;k++){ if(v[i][k] != v[j][k]) same[i][j] = 0; } } } memset(mem, 0, sizeof(mem)); mem[0][n] = 1; int res = 1; queue< pair<int, int> > qu; qu.push(make_pair(0, n)); while(!qu.empty()){ pair<int, int> pr = qu.front(); qu.pop(); int a = pr.first, b = pr.second; for(int c=a+1;c<b;c++){ bool ok = true; int d = c-1, e=c; while(a <= d && e < b){ if(!same[d][e]) ok = false; d--; e++; } if(!ok) continue; if(c-a >= b-c && !mem[a][c]){ mem[a][c] = 1; res++; qu.push(make_pair(a, c)); } if(b-c >= c-a && !mem[c][b]){ mem[c][b] = 1; res++; qu.push(make_pair(c, b)); } } } return res; } public: int howMany(int N, int M, vector <string> compressedPaper) { vector< vector<int> > paper(N, vector<int>(M, 0)); vector< vector<int> > paper2(M, vector<int>(N, 0)); for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ paper[i][j] = (toNumber(compressedPaper[i][j/6])>>(j%6))%2; paper2[j][i] = paper[i][j]; } } return solve(paper)*solve(paper2); } };
1100. ElectronicPet
- 観賞用だった。
- -
結果：AC / AC / -- ，-25, 473.03pt, 24位
レーティング：2442 -> 2484
easyがあんな撃墜祭りになると思ってなくて完全にビッグウェーブに乗り遅れたし、これは貪欲に引いたら落ちるやつだぜ！と思ってチャレンジしたら普通に-1が答えのケースを投げてしまってしょんぼりしてました。うーむ。
ABC015
rubyのお勉強をしてました。
- -
B : 高橋くんの集計
- 本番で出したコードそのまま。
- 0を除くのにselectを使ってみたけど、配列の引き算でもいけるらしくてこわい。
N = gets a = gets.chomp.split.map(&:to_i).select { |i| i > 0 } puts (a.reduce(:+)+a.size-1)/a.size
C : 高橋くんのバグ探し
- 本番で書いたものをtimesとか3項演算子とか使って整理した。
N, K = gets.chomp.split.map(&:to_i) dp = Array.new(N+1){Array.new(128){0}} dp[0][0] = 1 N.times { |i| gets.chomp.split.map(&:to_i).each { |val| 128.times { |j| dp[i+1][j^val] |= dp[i][j] } } } puts dp[N][0] == 0 ? "Nothing" : "Found"
D : 高橋くんの苦悩
- 本番ではTLE不可避だったのでカッとなってC++を使って通した。82ms。
- sune2さんが優先度をキーにすると良いと仰ってたので従ったらrubyでも通った。761ms。
- aとbの最小値を取るのは [a,b].min より a
W = gets.chomp.to_i N, K = gets.chomp.split.map(&:to_i) dp = Array.new(K+1){Array.new(5001){W+1}} dp[0][0] = 0 res = 0 sum = 0 N.times { |k| A, B = gets.chomp.split.map(&:to_i) [K-1, k].min.downto(0) { |i| sum.downto(0) { |j| dp[i+1][j+B] = dp[i+1][j+B] < dp[i][j] + A ? dp[i+1][j+B] : dp[i][j]+A } } sum += B } 5001.times { |j| (K+1).times { |i| res = j if dp[i][j] <= W } } puts res
- -
記事が短く済んで良いですね(白目)
模擬国内予選2014
いつものチラシ裏。
- -
C : 壊れた暗号生成器
- writerでした。国内予選レベルの構文解析の練習にと考えてみた問題。
- ?数制限はかなり迷った結果、謎の組織の会議によって3個制限を付けることに。
- 上位層は置換でサクッと通すだろうと思っていたら、意外と全探索してバグらせるチームがちらほら。
- でも一番仕事したのは、"++(たくさん)++R"と"--(いっぱい)--U"だった。剰余計算は闇ですね。
- 最後のサンプルがLOLだったり、1個目の出力に"GOODLUCKANDHAVEAFUN"が入ってたり、2個めの出力に"AZUNYAN"が入ってたりしますが、暗号生成器こわれてるから仕方ないね。
- 以下のコードは解説に従って書きなおしたもの。
#include <iostream> #include <string> #include <algorithm> using namespace std; string readCipher(const string& str, int& idx); string readString(const string& str, int& idx); char readLetter(const string& str, int& idx); string readCipher(const string& str, int& idx){ string res = ""; while(idx < str.size() && str[idx]!=']') res += readString(str, idx); return res; } string readString(const string& str, int& idx){ string res; if(str[idx]=='['){ ++idx; res = readCipher(str, idx); reverse(res.begin(), res.end()); ++idx; } else { res = readLetter(str, idx); } return res; } char readLetter(const string& str, int& idx){ char c = str[idx++]; char res; if(c == '+'){ res = readLetter(str, idx); if(res != '?') res = (res-'A'+1)%26+'A'; } else if(c == '-'){ res = readLetter(str, idx); if(res != '?') res = (res-'A'+25)%26+'A'; } else { res = c; } return res; } int main(){ string str; while(cin >> str){ if(str == ".") break; int idx = 0; string res = readCipher(str, idx); for(int i=0;i<res.size();i++) if(res[i] == '?') res[i] = 'A'; cout << res << endl; } }
E : 流れ星に願いを
- writerでした。昨年の夏くらいに、男3人で花火大会を見た思い出から作った問題。
- 考えたのが昨年なので、国内予選のために的な気持ちは入ってなかった。
- 最初はお姫様の願い事を叶えてあげよう的な問題文を書いたものの、他の問題を見て空気読んだ。
- 誤差まわりはそんなに気にしなくて良いはずだけど、「t<10^{-8}では接触しない」をスルーすると場合によっては引っかかる。
- 3分探索は想定してなかった。
#include <iostream> #include <vector> #include <valarray> #include <algorithm> #include <cstdio> using namespace std; double EPS = 1e-12; class P3{ public: double x, y, z; P3(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {} P3 operator + (const P3 &p) const { return P3(x+p.x,y+p.y,z+p.z); } P3 operator - (const P3 &p) const { return P3(x-p.x,y-p.y,z-p.z); } P3 operator * (const P3 &p) const { return P3(x*p.x,y*p.y,z*p.z); } P3 operator * (const double &p) const { return P3(x*p,y*p,z*p); } P3 operator / (const double &p) const { return P3(x/p,y/p,z/p); } double sum() const { return x+y+z; } double squareSum() const { return x*x+y*y+z*z; } }; struct Star { P3 p; P3 v; double r, d; }; int main(){ int n; while(cin >> n && n){ vector<Star> vs(n); for(int i=0;i<n;i++){ cin >> vs[i].p.x >> vs[i].p.y >> vs[i].p.z; cin >> vs[i].v.x >> vs[i].v.y >> vs[i].v.z; cin >> vs[i].r >> vs[i].d; } vector< pair<double, pair<int, int> > > vp; for(int i=0;i<n;i++){ vp.push_back(make_pair(vs[i].r/vs[i].d, make_pair(i, -1))); } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ double a = (vs[i].v-vs[j].v).squareSum() - (vs[i].d+vs[j].d)*(vs[i].d+vs[j].d); double b = ((vs[i].v-vs[j].v)*(vs[i].p-vs[j].p)).sum() + (vs[i].r+vs[j].r)*(vs[i].d+vs[j].d); double c = (vs[i].p-vs[j].p).squareSum() - (vs[i].r+vs[j].r)*(vs[i].r+vs[j].r); if(abs(a) < EPS){ if(abs(b) < EPS) continue; double t = -c/b; if(t > 0) vp.push_back(make_pair(t, make_pair(i,j))); } else { if(b*b-a*c < 0) continue; double t1 = (-b-sqrt(b*b-a*c))/a; double t2 = (-b+sqrt(b*b-a*c))/a; if(t1 > t2) swap(t1, t2); if(t1 > 0){ vp.push_back(make_pair(t1, make_pair(i, j))); } else if(t2 > 0){ vp.push_back(make_pair(t2, make_pair(i, j))); } } } } sort(vp.begin(), vp.end()); vector<double> res(n, 1e12); vector<int> hit(n, 0); for(int i=0;i<vp.size();i++){ int idxA = vp[i].second.first; int idxB = vp[i].second.second; if(hit[idxA] || (idxB!=-1 && hit[idxB])) continue; res[idxA] = vp[i].first; hit[idxA] = 1; if(idxB != -1){ res[idxB] = vp[i].first; hit[idxB] = 1; } } for(int i=0;i<n;i++) printf("%.12lf\n", res[i]); } }
G : ゴルフ
- 担当じゃなかったけど撃墜祭りに乗ってみた
- 解説が素晴らしいのでご一読いただければと
- 非実在問題にならないかドキドキしてたけど、提出あって良かった
- a/x=bを満たすxを求める方法を知らず、2分探索したアカウントがこちらになります
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <cmath> using namespace std; const long long MAX_VALUE = 1LL<<36; const long long MAX_DIGIT = 11; vector< pair<int, long long> > power; map<long long, int> term; int getLength(long long t){ int res = 1; for(long long i=t;i>=10;i/=10){ res++; } return res; } int getTermLen(long long t){ if(term.count(t)) return term[t]; return getLength(t); } bool checkUpdate(long long value, int length){ if(length < getLength(value)){ if(term.count(value)){ int curBest = term[value]; if(length < curBest){ term[value] = length; return true; } } else { term[value] = length; return true; } } return false; } void makePower(){ for(long long i=2;i*i<MAX_VALUE;i++){ long long value = i*i; int p = 2; int baseLen = getLength(i); while(value < MAX_VALUE){ int length = baseLen + getLength(p) + 1; checkUpdate(value, length); value *= i; p++; } } for(map<long long, int>::iterator it=term.begin(), end=term.end();it!=end;++it){ power.push_back(make_pair(it->second, it->first)); } sort(power.begin(), power.end()); } void termSearch(long long curValue, int curLength, bool mul){ if(curLength >= getLength(curValue)-1) return ; for(long long i=2;;++i){ long long nextValue = mul ? curValue*i : curValue/i; long long nextLen = curLength + getLength(i) + 1; if(nextValue >= MAX_VALUE) break; if(nextLen > MAX_DIGIT-3) break; if(nextLen >= getLength(nextValue)){ if(!mul) break; continue; } if(checkUpdate(nextValue, nextLen) && nextLen <= MAX_DIGIT-5){ termSearch(nextValue, nextLen, !mul); } } } void makeTerm(){ for(int i=0;i<power.size();i++){ termSearch(power[i].second, power[i].first, true); termSearch(power[i].second, power[i].first, false); } } void precalc(){ power.clear(); term.clear(); makePower(); makeTerm(); } int getDivNum(long long a, long long b){ // a/x = b if(a < b) return -1; int L = 1, R = 1000; while(R-L > 1){ int mid = (L+R)/2; if(a/mid > b) L = mid; else R = mid; } if(a/R == b) return R; return -1; } int solve(const long long s){ int res = getLength(s); if(term.count(s)) res = term[s]; for(map<long long, int>::iterator it=term.begin(), end=term.end();it!=end;++it){ long long baseValue = it->first; int baseLen = it->second; if(baseLen+2 >= res) continue; // baseValue +- v = s long long v = abs(s - baseValue); if(v < MAX_VALUE){ res = min(res, baseLen + getTermLen(v) + 1); } // baseValue * v = s if(s%baseValue == 0){ v = s/baseValue; res = min(res, baseLen + getTermLen(v) + 1); } // baseValue / v = s v = getDivNum(baseValue, s); if(v != -1){ res = min(res, baseLen + getLength(v) + 1); } } for(int i=0;i<power.size();i++){ // (power[i].second-v)*t for(int v=1;;v++){ int lenV = getLength(v); if(power[i].first+lenV+3 > res-2) break; long long baseValue = power[i].second - v; if(baseValue < 0) break; if(s%baseValue == 0){ long long t = s/baseValue; res = min(res, power[i].first+lenV+4+getLength(t)); } } for(int j=0;j<i;++j){ if(power[i].first + power[j].first > res-2) break; // pow2つ long long valA = power[i].second; long long valB = power[j].second; // valA + valB if(valA + valB == s){ res = min(res, power[i].first + power[j].first + 1); } // valA + valB +- v long long v = abs(s - (valA+valB)); res = min(res, power[i].first + power[j].first + getLength(v) + 2); // valA - valB if(abs(valA - valB) == s){ res = min(res, power[i].first + power[j].first + 1); } // valA - valB +- v v = abs(s - abs(valA-valB)); res = min(res, power[i].first + power[j].first + getLength(v) + 2); // valA * valB if((double)valA*valB < 1e15 && valA*valB < MAX_VALUE){ // valA * valB if(valA*valB == s){ res = min(res, power[i].first + power[j].first + 1); } // valA * valB +- v v = abs(s - valA*valB); res = min(res, power[i].first + power[j].first + getLength(v) + 2); // valA * valB / v v = getDivNum(valA*valB, s); if(v != -1){ res = min(res, power[i].first + power[j].first + getLength(v) + 2); } } } } return res; } int main(){ precalc(); long long s; while(cin >> s && ~s){ cout << solve(s) << endl; } }
Google Code Jam 2014 Round3
友人の結婚式でワインをたらふく飲んだため、
死にそうになりながらエンジョイ参加しました。
- -
A : Magical, Marvelous Tour
- i番目のデバイスが持つコンデンサ数をc[i]とする
- 要はmax(c[0]+...+c[a-1], c[a]+...+c[b], c[b+1]+...+c[N-1])を最小化する問題
- aを決めれば、bは後ろ2つの値が近くなるように決めれば良くて、2分探索できる
- N≦10^6なので、O(NlogN)で間に合う
#include <iostream> #include <cstdio> using namespace std; int a[1000000]; long long sum[1000001]; double solveLarge(int N){ long long get = sum[N]; for(int i=0;i<N;i++){ long long chooseA = sum[i]; if(sum[i+1]-sum[i] > sum[N]-sum[i+1]){ get = min(get, max(chooseA, sum[i+1]-sum[i])); } else { int L = i, R = N; while(R-L > 1){ int mid = (L+R)/2; if(sum[mid+1]-sum[i] <= sum[N]-sum[mid+1]){ L = mid; } else { R = mid; } } get = min(get, max(chooseA, max(sum[L+1]-sum[i], sum[N]-sum[L+1]))); if(L+2 <= N){ get = min(get, max(chooseA, max(sum[L+2]-sum[i], sum[N]-sum[L+2]))); } } } return (sum[N]-get)/(double)sum[N]; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N, p, q, r, s; cin >> N >> p >> q >> r >> s; sum[0] = 0; for(int i=0;i<N;i++){ a[i] = (i*(long long)p + q)%r + s; sum[i+1] = sum[i] + a[i]; } printf("Case #%d: %.10lf\n", test, solveLarge(N)); } }
B : Last Hit
- 各敵についてタワーに何回攻撃させるか決めると、自分が何回攻撃すれば良いか決まる
- 自分の攻撃回数が少なければ余った分は後に取っておくと考えられる
- 逆に多ければ、取っておいた攻撃を使うことになる
- どっちのターンで始まるか、攻撃の保存回数をキーにDPしてみた
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int N; int G[100]; int H[100]; int P; int Q; int solveLarge(){ int dp[2][2][2001]; memset(dp, -1, sizeof(dp)); dp[0][1][0] = 0; for(int i=0;i<N;i++){ int cur = i%2, next = 1-cur; memset(dp[next], -1, sizeof(dp[next])); for(int j=0;j<2;j++){ for(int k=0;k<=2000;k++){ if(dp[cur][j][k] == -1) continue; { int add = (H[i]+Q-1)/Q+j-1; dp[next][1][k+add] = max(dp[next][1][k+add], dp[cur][j][k]); } for(int enemyAttack=0; ;enemyAttack++){ if(enemyAttack*Q >= H[i]) break; int myAttack = (H[i]-enemyAttack*Q+P-1)/P; int chance = enemyAttack + j; if(myAttack > chance){ if(k < myAttack-chance) continue; dp[next][0][k-(myAttack-chance)] = max(dp[next][0][k-(myAttack-chance)], dp[cur][j][k]+G[i]); } else { dp[next][0][k+chance-myAttack] = max(dp[next][0][k+chance-myAttack], dp[cur][j][k]+G[i]); } } } } } int res = 0; for(int i=0;i<2;i++){ for(int j=0;j<=2000;j++){ res = max(res, dp[N%2][i][j]); } } return res; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ cin >> P >> Q >> N; for(int i=0;i<N;i++) cin >> H[i] >> G[i]; printf("Case #%d: %d\n", test, solveLarge()); } }
C : Crime House
- smallはとりあえず全探索しておいた。
- largeは0を貪欲に使うのはダメそうで悩んだ。
- フローっぽさを感じたけど結局分からなかった。
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; int bitCount(int t){ int res = 0; for(int i=t;i;i&=i-1) res++; return res; } int solveSmall(const vector< pair<int,int> >& ev){ vector<int> id; for(int i=0;i<ev.size();i++){ if(ev[i].second != 0) id.push_back(ev[i].second); } sort(id.begin(), id.end()); id.erase(unique(id.begin(), id.end()), id.end()); static int dp[2][1<<15]; for(int i=0;i<(1<<15);i++) dp[0][i] = 1; for(int e=0;e<ev.size();e++){ int cur = e%2, next = 1-cur; memset(dp[next], 0, sizeof(dp[next])); int checkID = -1; for(int i=0;i<id.size();i++){ if(id[i] == ev[e].second) checkID = i; } for(int i=0;i<(1<<15);i++){ if(!dp[cur][i]) continue; if(checkID == -1){ for(int j=0;j<15;j++){ if(ev[e].first == 0){ if(!(i&(1<<j))) dp[next][i|(1<<j)] = 1; } else { if(i&(1<<j)) dp[next][i^(1<<j)] = 1; } } } else { if(ev[e].first == 0){ if(!(i&(1<<checkID))) dp[next][i|(1<<checkID)] = 1; } else { if(i&(1<<checkID)) dp[next][i^(1<<checkID)] = 1; } } } } int res = 100; for(int i=0;i<(1<<15);i++){ if(dp[ev.size()%2][i]) res = min(bitCount(i), res); } return res; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N; cin >> N; vector< pair<int,int> > ev(N); for(int i=0;i<N;i++){ char c; int id; cin >> c >> id; if(c == 'E') ev[i] = make_pair(0, id); else ev[i] = make_pair(1, id); } int res = solveSmall(ev); if(res == 100) printf("Case #%d: CRIME TIME\n", test); else printf("Case #%d: %d\n", test, res); } }
D : Willow
- 読んだだけで終わった。
- -
Rank 104: /oo/oo/o-/--/ Score 49, Penalty 2:03:07
C-large解きたかったなと思いましたが、順位的には無難な出来だったと思います。
Google Code Jam 2014 Round2
巨人-オリックス戦を観戦しに行っていたのですが、
息詰まる投手戦のまま延長に突入したため泣く泣く撤退しての参加でした。
野球の方は12回までやって1-0とかアツい展開だったらしいです。ぐぬぬ…。
- -
A : Data Packing
- 最初「1個のディスクにデータは高々2個」という制約を読み落としてた
- NP困難的な空気を感じたので、流石に無いわと思って問題文を読み返して気付いた
- サイズ大きいのから貪欲に2個ずつ詰めたら良さそうだったので詰めた
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N, X; cin >> N >> X; vector<int> S(N); for(int i=0;i<N;i++) cin >> S[i]; sort(S.rbegin(), S.rend()); vector<int> used(N, 0); int res = 0; for(int i=0;i<N;i++){ if(used[i]) continue; used[i] = 1; for(int j=i+1;j<N;j++){ if(used[j]) continue; if(S[i]+S[j] <= X){ used[j] = 1; break; } } res++; } printf("Case #%d: %d\n", test, res); } }
B : Up and Down
- 反転数をアレするアレだな！って思ってたら2WAしたので頭冷やしてsmall書いた。
- largeがガチで分からなくて一旦D(small)に逃避
- smallのコードで、swap回数が最小になる時の並び順を出力してみた
- これ小さい方から左右の近い方に寄せてるだけだ…。
- 一応smallの解と比較してみたら合ってたので投げた。
- 記念にsmallのコードも晒しておく
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; int solveSmall(const vector<int>& vi){ vector<int> v = vi; vector<int> a(v.size()); sort(v.begin(), v.end()); int res = 10000000; vector<int> minV; do{ bool valid = true; int maxPos = 0; for(int i=1;i<v.size();i++){ if(v[maxPos] < v[i]) maxPos = i; } for(int i=0;i+1<=maxPos;i++){ if(v[i] > v[i+1]) valid = false; } for(int i=maxPos;i+1<v.size();i++){ if(v[i] < v[i+1]) valid = false; } if(!valid) continue; for(int i=0;i<v.size();i++){ for(int j=0;j<vi.size();j++){ if(v[i]==vi[j]) a[j] = i; } } int cnt = 0; for(int i=0;i<v.size();i++){ for(int j=i+1;j<v.size();j++) if(a[i] > a[j]) cnt++; } if(cnt < res) minV = v; res = min(res, cnt); }while(next_permutation(v.begin(), v.end())); return res; } int solveLarge(const vector<int>& vi){ vector<int> v = vi; vector<int> vp; for(int i=0;i<v.size();i++) vp.push_back(v[i]); sort(vp.begin(), vp.end()); int l = 0, r = vi.size()-1; int res = 0; for(int i=0;i<vi.size();i++){ int pos = -1; for(int j=l;j<=r;j++){ if(v[j] == vp[i]){ pos = j; break; } } if(pos-l < r-pos){ res += pos-l; for(int j=pos;j-1>=l;j--) swap(v[j], v[j-1]); l++; } else { res += r-pos; for(int j=pos;j+1<=r;j++) swap(v[j], v[j+1]); r--; } } return res; } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N; cin >> N; vector<int> vi(N); for(int i=0;i<N;i++) cin >> vi[i]; printf("Case #%d: %d\n", test, solveLarge(vi)); } }
C : Don't Break The Nile
- WindPassageに激似だなとは思った。コンテスト中は思っただけだった。
- smallは適当に流したら通るんじゃねと思って左手法で流していった。
- largeも座標圧縮したら通るんじゃねと思ったけど嘘しか書けなかった(´・ω・｀)
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; int river[1000][4000]; int mem[1000][4000]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int W, H, B; cin >> W >> H >> B; memset(river, -1, sizeof(river)); memset(mem, 0, sizeof(mem)); for(int i=0;i<B;i++){ int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; for(int j=x1;j<=x2;j++){ for(int k=y1;k<=y2;k++){ river[j][k] = -2; } } } int res = 0; for(int i=0;i<W;i++){ if(river[i][0]!=-1) continue; int x = i, y = 0, dir = 1; while(true){ if(mem[x][y]&(1<<dir)) break; mem[x][y] |= 1<<dir; river[x][y] = i; if(y == H-1){ res++; break; } for(int j=0;j<4;j++){ int ndir = (dir+5-j)%4; int nx = x+dx[ndir]; int ny = y+dy[ndir]; if(nx < 0 || W <= nx || ny < 0 || H <= ny || (river[nx][ny]!=-1&&river[nx][ny]!=i)) continue; x = nx, y = ny, dir = ndir; break; } } } printf("Case #%d: %d\n", test, res); } }
- ちなみに終了後にlarge通したコード。
- WindPassageでした。
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> #include <queue> using namespace std; class Node{ public: int pos, cost; Node(int pos, int cost) : pos(pos), cost(cost) {} bool operator < (const Node& nd) const { return cost > nd.cost; } }; int main(){ int T; cin >> T; int x1[1000], y1[1000], x2[1000], y2[1000]; for(int test=1;test<=T;test++){ int W, H, B; cin >> W >> H >> B; if(B == 0){ } for(int i=0;i<B;i++){ cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]; } int res = 0; vector< vector<Node> > g(B+2, vector<Node>()); g[B].push_back(Node(B+1, W)); for(int i=0;i<B;i++){ g[B].push_back(Node(i, x1[i])); g[i].push_back(Node(B+1, W-1-x2[i])); for(int j=i+1;j<B;j++){ int c = max(0, max(max(x1[i], x1[j])-min(x2[i], x2[j])-1, max(y1[i], y1[j])-min(y2[i], y2[j])-1)); g[i].push_back(Node(j, c)); g[j].push_back(Node(i, c)); } } vector<int> dist(B+2, 1000000007); priority_queue<Node> qu; qu.push(Node(B, 0)); dist[B] = 0; while(!qu.empty()){ Node nd = qu.top(); qu.pop(); if(nd.cost > dist[nd.pos]) continue; for(int i=0;i<g[nd.pos].size();i++){ int npos = g[nd.pos][i].pos; int ncost = nd.cost+g[nd.pos][i].cost; if(dist[npos] > ncost){ dist[npos] = ncost; qu.push(Node(npos, ncost)); } } } printf("Case #%d: %d\n", test, dist[B+1]); } }
D : Trie Sharding
- smallはどれだけ適当にやっても通りそうだったので通しておいた。
- largeは全く分からなかった。
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <set> using namespace std; int getNodeNum(const vector<string>& vs){ set<string> S; for(int i=0;i<vs.size();i++){ for(int j=1;j<=vs[i].size();j++){ S.insert(vs[i].substr(0, j)); } } return S.size(); } int main(){ int T; cin >> T; for(int test=1;test<=T;test++){ int N, M; cin >> N >> M; int maxNode = 0; int cnt = 0; vector<string> vs(N); for(int i=0;i<N;i++) cin >> vs[i]; for(int i=0;i<(1<<(2*N));i++){ vector< vector<string> > v(4); for(int j=0;j<N;j++){ v[(i>>(2*j))%4].push_back(vs[j]); } bool valid = true; int sum = 0; for(int j=0;j<4;j++){ if(j < M){ if(v[j].empty()) valid = false; else sum += getNodeNum(v[j]); } else { if(!v[j].empty()) valid = false; } } if(!valid) continue; if(sum == maxNode){ cnt++; } else if(sum > maxNode){ maxNode = sum; cnt = 1; } } printf("Case #%d: %d %d\n", test, maxNode+M, cnt); } }
- -
Rank 323 : /oo/oo/o-/o-/ Score 50, Penalty 1:49:55
通過ですが点数的には500位と一緒。時間勝負勢でした。
C-largeも通したかったですが、それよりBでハマりすぎたのが悲しかったです。
