AtCoder Regular Contest #051
| ω・｀)ﾉ ﾔｧ |
最近TopCoderのレートが低迷気味のため、ちゃんと日記書こうと思いました。
もはや日記の書き方（？）すら忘れてるレベル。
A問題：塗り絵
考えたこと
円と四角だから完全に重複することないので、以下２つをチェックすれば良い。
円が四角を囲う条件：４隅全部が円の中にある判定すれば良い
四角が円を囲う条件：円の最上点・最下点・最右点・最左点が四角の範囲か判定
コード
int main(){ int x1,y1,r,x2,y2,x3,y3; cin >> x1>>y1>>r>>x2>>y2>>x3>>y3; if( x1+r <= x3 && x1-r>=x2 && y1+r <= y3 && y1-r >= y2 ){ cout << "NO"<<endl; } else{ cout << "YES"<<endl; } int dx[] = {x2-x1,x3-x1}; int dy[] = {y2-y1,y3-y1}; bool no=true; for( int xi=0;xi<2;xi++ ){ for( int yi=0; yi<2; yi++ ){ if( dx[xi]*dx[xi]+dy[yi]*dy[yi] > r*r ){ no=false; break; } } } if( no ){ cout <<"NO"<< endl; } else{ cout <<"YES"<<endl; } return 0; }
B問題：互除法
考えたこと
互除法の逆計算を行うだけ。
初期状態がa=0,b=1 (K=0の時) だと逆計算できないので、
a=1,b=2(K=1の状態)からスタートすることにする。
コード
int main(){ int K; cin >> K; int b=1; int a=2; for( int i = 1 ; i < K; i++ ){ b+=a; swap(a,b); } cout << a << " " << b << endl; return 0; }
C問題：掛け算
考えたこと
とりあえずリストの最大値を超えない範囲でAをかけ続けることを考える。
A=1だと無限ループに陥るが、
そもそもA=１の場合は計算しなくて良いので、例外処理。
リストの最大値を超えない範囲でAを掛け切ったリストをbとし、あとAを掛ける必要がある回数をB_remainとすると、それ以降はAの掛ける順番はbの小さい順である。
よって、すべての要素にAをB_remain/N回掛けて、（ここは大きな値になるのでダブリング処理する）残りのB_remain%N回を小さい順にかけて上げれば良い。
コード
突然のpython。
mod 1000000007の計算をするときにlong longとintをちゃんと使い分けるのが面倒くさいな、くらいの軽い気持ちで書いたけど、heapqの使い方など忘れてて時間を食った。
import heapq N,A,B=map(int,raw_input().split()) a=map(int,raw_input().split()) m=1000000007 def calc(A,ex,m): ret = 1 mul = A while ex!= 0: if ex%2 == 1: ret*=A ret%=m A*=A A%=m ex/=2 return ret if A==1: a.sort() for ans in a: print ans exit() MA=max(a) bi=0 for i in range(N): curA=a[i] while curA*A < MA: curA*=A bi+=1 if bi>B: heapq.heapify(a) for bi in xrange(B): n=a[0] heapq.heappop(a) heapq.heappush(a,n*A) for i in range(N): print a[0] heapq.heappop(a) else: for i in range(N): while a[i]*A < MA: a[i]*=A B-=1 a.sort() ex=B/N common=calc(A,ex,m) r=B%N for i in range(N): a[i]*=common a[i]%=m for i in range(r): a[i]*=A a[i]%=m for i in range(r,N): print a[i] for i in range(r): print a[i]
もっと早く出すために
時間かけすぎてしまった反省点メモ。
最大値を超えない範囲でAを掛けきってしまわずに計算終了するケースと、更にその先を計算するケースについて、ほぼ別ロジックで書かれている。
（しかも、Aを掛けきるかどうか？の処理として無駄に似たようなコードが２回書かれている。残念極まりないコードである)
この理由は、前者のケースでドヤってheapqを使おうとしたせいだった。
kmjpさんのコード(Submission #696154 - AtCoder Regular Contest 051 | AtCoder)を見て気付いたけれど、
今回の制約条件ではheapqなんぞ使わずとも毎回sortし直す実装にすれば無駄なケース分けや、heapqの使い方を調べる時間は削減できた。
（Aを掛けきるまでの掛け算回数はたかだか1500回、ソートにかける時間は 50 log 50……余裕ですね)
D：長方形
D: 長方形 - AtCoder Regular Contest 051 | AtCoder
考えたこと
BIT使う系かと思ったけど違うっぽいしDPでも解けそうにない。
つまり、僕には解けない。
復習
りんごさんのニコ生解説が神だった。
AtCoder Regular Contest 051 解説放送 - 2016/04/16 22:30開始 - ニコニコ生放送 48分くらいから。
前処理として、a_w,b_hそれぞれについてi番目の要素まででj個の連続する要素の和の最大値wMax(i,j),hMax(i,j)を計算しておく。
すると、クエリA、Bが来た時に返すべき値は
Z= wMax(A,p)*q+hMax(B,q)*pの最大値である。
qの値を固定して考える。
例えばq=3, hMax(B,q)=4だとする。
すると、この問題は 3wMax(A,p)+4pの最大値を返せば良い。
x=p,y=wMax(A,p)とすると、これはz=3y+4xを最大にする点(p,wMax(A,p))(1<=p<=A)を探す問題になる。
受験数学でお馴染みのy=4x/3-z/3の線を上から被せていって最初にぶつかる頂点を探す問題と同じである。
これはプログラム的には(p,wMax(A,p))の凸包を計算し、二分探索的に求めることが可能である。
まとめると、
Qクエリそれぞれについて、まず(p,wMax(A,p)) (1<=p<=A)の凸包を計算 (O(W))して後、
各 q について (O(H)) 二分探索的にwMax(A,p)*q+hMax(B,q)*pの最大値を計算(O(log W) )し、
最終的な最大値を返す。
これは O(Q* (W+ HlogW) ) だけの計算量となるため、2000*2000*log(2000) = 1.3*10^7
くらいで計算できる。
コード
凸包ライブラリが盛大にバグっていた（外積部分）のでつぎはぎで対処している。
通りはしたけどまだバグってるかも知れないし、ちゃんとメンテしないとな。
long long product( pair<int,int> p1, pair<int,int> p2, pair<int,int> p3 ){ pair<int,int> v1 = make_pair( p2.first-p1.first, p2.second-p1.second); pair<int,int> v2 = make_pair( p3.first-p2.first, p3.second-p2.second); return -(v2.first*(long long)v1.second-v2.second*(long long)v1.first); } vector< pair<int,int> > convex_hull( vector<pair<int,int> > &V){ if( V.size() <=2 ) return V; int size = V.size(); sort(V.begin(),V.end()); vector<pair<int,int> > ret(size*2); int retlen=0; for( int i = 0 ; i <size; i++ ){ while( retlen >= 2 && product( ret[retlen-2],ret[retlen-1],V[i] ) <= 0 ) retlen--; ret[retlen++]=V[i]; } int underlen=retlen; for( int i = size-2 ; i >= 0 ; i-- ){ while( retlen > underlen && product( ret[retlen-2],ret[retlen-1],V[i] ) <= 0 ) retlen--; ret[retlen++]=V[i]; } ret.resize(retlen); return ret; } int main(){ int W,H; cin >>W >> H; int a[W]; int b[H]; for( int i = 0 ; i <W; i++ ) cin >> a[i]; for( int j = 0 ; j <H; j++ ) cin >> b[j]; for( int i = 0 ; i < 2001; i++ ){ for( int j =0; j <2001; j++ ){ wMax[i][j]=hMax[i][j]=-(INT_MAX/2); } } for( int i = 1 ; i <=W; i++ ){ int cur=0; for( int j =0; j<i; j++ ){ cur+=a[j]; } wMax[i][i]=cur; for( int j=i+1; j<=W; j++ ){ cur -= a[j-1-i]; cur += a[j-1]; wMax[j][i] = max(wMax[j-1][i],cur); } } for( int i= 1 ; i <= H ; i++ ){ int cur = 0; for( int j=0; j <i; j++ ) cur+=b[j]; hMax[i][i]=cur; for( int j=i+1; j<=H ; j++ ){ cur -= b[j-1-i]; cur += b[j-1]; hMax[j][i] = max( hMax[j-1][i],cur); } } int Q; cin >> Q; for( int qi = 0; qi<Q; qi++ ){ int A,B; cin >> A>> B; int* w=wMax[A]; int* h=hMax[B]; vector<pair<int,int> > ps; for( int x=1; x<= A; x++ ){ ps.push_back( make_pair(x,w[x])); } vector<pair<int,int> > poly = convex_hull(ps); // maximize w[x]*y + h[y]*x /* for( int i = 0 ; i < (int) poly.size(); i++ ){ cout << poly[i].first << ", " << poly[i].second<<endl; }*/ long long ans = -2000000; for( int y = 1; y <= B ; y++ ){ int left=0; int right=(int)poly.size()-1; while( left < right ){ int mid = (left+right)/2; //cout <<left <<"- "<< mid <<"- "<<right << endl; long long midValue = poly[mid].first*(long long)h[y]+poly[mid].second*(long long)y; long long neighbourValue = poly[mid+1].first*(long long)h[y]+poly[mid+1].second*(long long)y; //cout << midValue <<"vs"<<neighbourValue<<endl; if( midValue > neighbourValue )right=mid; else left=mid+1; } //cout << y<<": "<< right<<": "<< poly[left].first <<", "<< poly[left].second<<endl; ans =max( ans, poly[right].first*(long long)h[y]+poly[right].second*(long long)y); } cout << ans << endl; } return 0; }
