AOJ 1283 Most Distant Point from the Sea
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1283
多角形の内部の点で、辺との距離の最小値が最大になる点を求めよ。
解法
初めは他の人と同じように想定解の二分探索でやっていたが、謎のWAが解決できなかったから次のような山登り法?のような探索に変えた。
適当な内点を初期値として、最も距離が小さい辺と逆側に少しずつ動かしていった。
このアイデアは http://d.hatena.ne.jp/y_mazun/20121218/1355851934 を参考にした。
適当な3点を選び、その内心を最初の点としている。そこから最も距離が近い辺を探し、その方向とは逆向きのベクトルを足す。足すことによって点が円の外に出てしまうならその長さを足すことを諦めて、足す長さを短くする。これを答えに求められる精度が出る回数だけ繰り返す。
SpaghettiSourceのライブラリを使えば多角形の内外判定がlogの時間でできるのでだいたい となるが、これにかかる定数で精度が決まるのでそこを調節する必要がある。
最初の点の選び方によって失敗することがあるようで、少しランダム要素を加えて3回に2回以上はACされるように調整した。
ソースコード
double const eps=1e-8; double const inf = 1e10; double const pi = acos(-1); typedef complex<double> P; inline double cross(P const&a, P const&b){return imag(conj(a)*b);} inline double dot(P const&a, P const&b){return real(conj(a)*b);} struct L : public vector<P> { L(const P &a, const P &b){push_back(a); push_back(b);} L(){} }; P projection(L const&l, P const&p){double t = dot(p-l[0],l[0]-l[1])/norm(l[0]-l[1]);return l[0]+t*(l[0]-l[1]);} inline double distanceLP(L const&l, P const&p){return abs(p-projection(l, p));} P innerCenter(P const&a, P const&b, P const&c){ double la=abs(b-c), lb=abs(c-a), lc=abs(a-b); return (la*a+lb*b+lc*c)/(la+lb+lc); } int n; P ps[128]; L es[128]; enum { OUT, ON, IN }; int convex_contains(P const&p) { P g=(ps[0]+ps[n/3]+ps[2*n/3])/3.0; int a=0,b=n; while (a+1 < b) { int c=(a+b)/2; if (cross(ps[a]-g, ps[c]-g) > 0) { if (cross(ps[a]-g, p-g) > 0 && cross(ps[c]-g, p-g) < 0) b = c; else a = c; } else { if (cross(ps[a]-g, p-g) < 0 && cross(ps[c]-g, p-g) > 0) a = c; else b = c; } } b %= n; if (cross(ps[a] - p, ps[b] - p) < 0) return 0; if (cross(ps[a] - p, ps[b] - p) > 0) return 2; return 1; } double solve(){ rotate(ps,ps+rand()%n,ps+n); ps[n]=ps[0]; rep(i,n){ es[i]={ps[i],ps[i+1]}; } P p=innerCenter(ps[0],ps[n/3],ps[n/3*2]); if(n==3)return distanceLP(es[0],p); double const r[]={100,10,1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8}; double static d[128]; int near=0; rep(t,11){ rep(u,3000){ rep(i,n)d[i]=distanceLP(es[i],p); near=0; rep(i,n) if(d[i]<d[near]){near=i; } P h=projection(es[near],p); P np=p-(h-p)/d[near]*r[t]; if(convex_contains(np)==IN){ swap(p,np); } else { break; } } } return d[near]; } int main(){ srand(time(0)); while(cin>>n && n){ rep(i,n){ double x,y; scanf("%lf%lf",&x,&y); ps[i]=P(x,y); } printf("%lf\n",solve()); } }
幾何の問題は完全にSpagettiSourceに頼り切っているので自力でライブラリ書かないといけないと思った。
POJ 2676 Sudoku
正月に帰省したとき暇だったので数独Solverを書いてたんだけど、最近POJやってみようかなーと思って眺めていたらこの問題を見つけ、通してみた。
問題
数独を解け!
解法
枝刈り探索。
ソースコード
#include <iostream> #include <string> #include <cstring> #include <vector> using std::vector; int const n=9; int const m=3; typedef vector<int> vi; typedef vector<vi> vvi; namespace solver { bool column[n+1][n+1]; bool raw[n+1][n+1]; bool block[n+1][n+1]; vector<vvi> ans; vvi g(n,vi(n)); void rec(int x,int y){ while(y!=n && g[y][x]){ x++; if(x>=n){ x=0;y++; } } if(y==n){ ans.push_back(g); return; } for(int i=1;i<=n;i++){ if(column[x][i]||raw[y][i]||block[x/m*m+y/m][i]){ continue; } column[x][i]=raw[y][i]=block[x/m*m+y/m][i]=true; g[y][x]=i; rec(x,y); if(ans.size())return; column[x][i]=raw[y][i]=block[x/m*m+y/m][i]=false; g[y][x]=0; } } vector<vvi> solve(vvi const& g_){ g.assign(n,vi(n,0)); memset(column,0,sizeof(column)); memset(raw,0,sizeof(raw)); memset(block,0,sizeof(block)); ans.clear(); for(int y=0;y<n;y++){ for(int x=0;x<n;x++){ int t=g_[y][x]; g[y][x]=t; column[x][t]=raw[y][t]=block[x/m*m+y/m][t]=true; } } rec(0,0); return ans; } } int main(){ using std::cin; using std::cout; using std::endl; int _;cin>>_; while(_--){ vvi g(n,vi(n)); for(int y=0;y<n;y++){ std::string s;cin>>s; for(int x=0;x<n;x++){ g[y][x]=s[x]-'0'; } } vector<vvi> ans=solver::solve(g); for(int y=0;y<n;y++){ for(int x=0;x<n;x++){ cout<<ans[0][y][x]; if(x+1==n)cout<<endl; } } } }
Codeforces Round #257 (Div. 2)
http://codeforces.com/contest/450
oo--- =1540 (-99), expert Rank: 1085 とダメダメでした。
最近バグ取りもアルゴリズムを考えるのも遅くなってきてる気がする
A
待ち行列なのでQueueに入れ空になるまでループを回した。
int main(){ int n; while(cin>>n){ int m; cin>>m; typedef pair<int,int> P; queue<P> s; rep(i,n){ int x;cin>>x; s.push(P(i+1,x)); } while(s.size()){ P t=s.front(); s.pop(); if(t.second>m){ t.second-=m; s.push(t); }else{ ; } if(s.size()==0){ cout << t.first << endl; break; } } } }
B
何も考えずに行列ライブラリ(蟻本)に突っ込んだ。が、負の数のを正に直すときにwhile(y<0)x+=M;
などして無駄に時間を使う。こんなこと考えなくても少し手計算すると周期性が見えたらしい。
mat mul(mat &A, mat&B) { mat C(A.size(), vec(B[0].size())); rep(i,A.size()){ rep(k,B.size()){ rep(j,B[0].size()){ C[i][j] = (C[i][j] + A[i][k] * B[k][j]); } } } rep(i,C.size())rep(j,C[0].size()){ while(C[i][j]<0) C[i][j]+=M; C[i][j]%=M; } return C; } mat pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); i++) { B[i][i] = 1; } while (n > 0) { if (n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } ll solve(ll x,ll y,ll n) { n--; ll res; if(n==0) res= x; else if(n==1) res= y; else{ while(x<0)x+=M; while(y<0)y+=M; mat A(2, vec(2)); A[0][0] = 1; A[0][1] = -1+M; A[1][0] = 1; A[1][1] = 0; A = pow(A, n); res=A[1][0]*y + A[1][1]*x; } while(res<0) res+=M; res%=M; return res; } int main(){ ll x,y,n; while(cin>>x>>y>>n){ cout << solve(x,y,n) << endl; } }
C
切り方で全探索するとTLEする。
回水平に切ると垂直には 回切らなければならない。小さな長方形の高さの最小値は に、幅の最小値は となる。
が大きくなるほど が大きくとれる。 が の約数でなければ より大きい最小の約数で切るのと同じになるので、 は の約数の中だけで考えれば良い。 の約数を全列挙し、 の最大値をとる。同様に、垂直に切る回数 を の約数の中で考えた場合の最大値と比較して大きい方を返す。
これなら くらいなので間に合う。
他の人のソースによると全部垂直に切るか全部水平に切るかのどっちかだけで良いらしい。(どうしてかはよく分からない。)結局間に合わず解けなかったけどこういう問題好きだなー
ll a[1<<10]; template<typename T> ll divider(T n, T* a){ ll c=0; for(ll i=1;i*i<=n;i++){ if(n%i==0){ a[c++]=i; if(i*i!=n)a[c++]=n/i; } } sort(a,a+c); return c; } ll solve(ll n,ll m, ll k){ int const c=divider(n,a); if(n-1+m-1<k) return -1; ll ans=-1; rep(i,c){ ll w=a[i]; ll k1=n/w-1; ll k2=k-k1; if(0<=k1&&k1<=k&&0<=k2&&k2<=k){ ll h=m/(k2+1); ans=max(ans,h*w); } } return ans; } int main(){ ll n,m,k; while(cin>>n>>m>>k){ ll a1=solve(n,m,k); ll a2=solve(m,n,k); cout<<max(a1,a2)<<endl; } }
Codeforces Round #256 (Div. 2)
翌日早起きする必要があったのでリアルタイムでは不参加でした。
A
x = gets.chomp.split.map{|i| i.to_i}.inject(:+) y = gets.chomp.split.map{|i| i.to_i}.inject(:+) if (x+4)/5 + (y+9)/10 <= gets.to_i puts "YES" else puts "NO" end
B
if( に含まれる文字と に含まれる文字が順不同で等しい) -> array
else if ( が の部分文字列) ->automaton
else if ( に含まれる文字で を作れる) -> both
else need tree
// aとbの最長共通部分列(lcs)を求める template<typename T> T lcs(T const& a, T const& b) { const int n = a.size(), m = b.size(); vvi X(n+1, vi(m+1)); vvi Y(n+1, vi(m+1)); rep(i,n)rep(j,m){ if (a[i] == b[j]) { X[i+1][j+1] = X[i][j] + 1; Y[i+1][j+1] = 0; } else if (X[i+1][j] < X[i][j+1]) { X[i+1][j+1] = X[i][j+1]; Y[i+1][j+1] = +1; } else { X[i+1][j+1] = X[i+1][j]; Y[i+1][j+1] = -1; } } T c; for (int i = n, j = m; i > 0 && j > 0; ) { if (Y[i][j] > 0) --i; else if (Y[i][j] < 0) --j; else { c.push_back(a[i-1]); --i; --j; } } reverse(all(c)); return c; } string solve(string a, string b){ string ta=a; string tb=b; sort(all(ta)); sort(all(tb)); if(ta==tb){ return "array"; } if(lcs(a,b)==b){ return "automaton"; } bool both=true; map<char,int> ca; map<char,int> cb; each(i,a)ca[i]++; each(i,b)cb[i]++; each(p,cb){ if(ca[p.first]<p.second){ both=false; break; } } if(both){ return "both"; } return "need tree"; } int main(){ string a,b; while(cin>>a>>b) cout << solve(a,b) << endl; }
C
3 3 3 3 3
のように長方形になっているときは縦の長さと横の長さのうち短い方を返す。
そうでないときは
- 全部縦に塗る
- 数列の最小値の回数だけ下の方を塗ったあと、残った部分をどう塗るか再帰的に考えて足す。
の2通りのうち小さい方を返す。
例えば2 2 3 3 2 2
なら
- 縦に5回塗る
- 横に2回塗って
0 0 1 1 0 0
にしたあと残った1 1
どう塗るか考える
のどちらがいいか?となる。
こういう貪欲法の他にもDPで解くこともできるらしい。
int a[6000]; int solve(int l, int r){ if(l==r) return 0; int m=a[l]; bool rect=true; loop(i,l,r){ if(a[l]!=a[i])rect=false; m=min(a[i],m); } loop(i,l,r)a[i]-=m; int res; if(rect){ res = min(m,r-l); }else{ res=r-l; int x=0; int tl=0; while(1){ while(tl<r && a[tl]==0){ tl++; } int tr=tl; while(tr<r && a[tr]!=0){ tr++; } x+=solve(tl,tr); tl=tr; if(tl==r) break; } res=min(res, x+m); } // cout << l << " " << r << " " << res << endl; return res; } int main(){ int n; while(cin>>n){ rep(i,n)cin>>a[i]; cout << solve(0,n) << endl; } }
D
段目の行 の中で 以下の数の個数は (が割り切れるときは1引く)となる。これを まで足していけば表全体で より小さいものの個数がわかる。
の値で二分探索する。
ll solve(ll w,ll h,ll k){ if(w<h) swap(h,w); ll l=1; ll r=inf; // [l,r) while(l+1<r){ ll mid=(l+r)>>1; ll c=0; loop(y,1,h+1){ c+=min(w,(mid-1)/y); } // cout << mid << " " << c << endl; if(c<k)l=mid; else r=mid; } return l; } int main(){ ll n,m,k; while(cin>>n>>m>>k){ cout<<solve(n,m,k)<<endl; } }
Codeforces Round #FF (Div. 2)
0xFF = 255
ooo-- 296th rating: 1639(+69)
AB早解きでCはアドホックでした.CがバグりやすかったようでDiv1Aとして解いた人も結構落としてた.
アルゴリズムの勝負はDからだったと思うのでその段階で勝負できるようになりたいな…
A
テストのためにwhile (cin >> p >> n)
と書いているのにcontinue
のところをbreak
にしていたせいで3回WAする.なかなかこのミスに気づけず諦めて最後に回した.結局ACできたのは開始110分後になってしまった.
国内予選のC問題といいくだらないミスで数十分潰す案件が続いてる.
int main(){ ll n, p; while (cin >> p >> n){ set<ll> s; int ans = -1; rep(i, n){ ll x; cin >> x; ll h = x%p; auto t = s.insert(h); if (t.second) continue; else if (ans == -1) ans = i+1; } cout << ans << endl; } }
B
最も価値が大きいアルファベットを求め,それをの後ろに個付け足したものが答えとなる.
int main(){ string s; cin >> s; int k; cin >> k; char c = 'a'; int score = 0; map<char, int> m; loop(i, 'a', 'z' + 1){ int t; cin >> t; m[i] = t; if (t > score){ score = t; c = i; } } s += string(k, c); int ans = 0; rep(i, s.size()){ ans += m[s[i]] * (i + 1); } cout << ans << endl; }
C
番目以降で連続して増加する列の長さと以前で連続して増加する列の長さを予め求め, 最後にの最大値を求める.数列の長さが2以下の場合,先頭か末尾を変更する場合,差が1しかない場合など 結構引っかかった.
int main(){ int n; while (cin >> n){ if (n == 1 || n == 2){ cout << n << endl; return 0; } vll a(n); vll before(n, 1); vll after(n, 1); rep(i, n){ cin >> a[i]; } for (int i = 1; i < n; i++){ if (a[i - 1] < a[i]){ before[i] = before[i - 1] + 1; } } for (int i = n - 2; i >= 0; i--){ if (a[i] < a[i + 1]){ after[i] = after[i + 1] + 1; } } ll ans = after[1] + 1; // change a[0] ans = max(ans, before[n - 2] + 1); // change a.back() for (int i = 1; i + 1 < n; i++){ if (a[i - 1] + 1 < a[i + 1]){ ans = max(ans, before[i - 1] + after[i + 1] + 1); } else { ans = max(ans, before[i - 1] + 1); ans = max(ans, after[i + 1] + 1); } } //cout << a << endl; //cout << before << endl; //cout << after << endl; cout << ans << endl; } }
D
今取れる最大の行or列を取る貪欲を書いていたけど,手で解いたのと合わないケースが出てきたので諦めた.
ICPC2014 国内予選
だめでした
チームC++2zとして参加しました。結果は2問だけ解いて75位でした。
http://icpc.iisf.or.jp/2014-waseda/domestic/results/
先輩の研究室チームがおそらく予選通過する様で何よりです。
また来年がんばります。
過程
@LazyMiiに突っ込みをもらいながら僕(@tubo28)が実装し、その間に@menphimに他の問題を読んでもらうという作戦でした。
開始前
チームメイト3人共14:30に授業が終わる。ディスプレイや本番中に食べるお菓子を会場に運ぶ。 院生チーム(Undefind Iketeru Methods)の先輩から差し入れのドーナツをもらう。
練習セッションのJ問題を終了30秒前にACする。
会場の準備は大方後輩がやっていてくれたが、プリンタの準備をしていたら開始時間ギリギリになった。
開始
@LazyMiiとAを読む。商品がたくさんあると勘違いしてA問題からDP???と焦ったが@LazyMiiに2つしか無いと訂正される。
制約が小さいので2つの商品の税抜き価格で全探索する。
A AC(12分)
Bの説明を聞く。消す操作と落とす操作を別々に実装し、消せなくなるまで無限ループを回す方針で解く。落とすときにqueueかstackを使うと楽そうだねという話をする。
2次元配列のインデックス[i][j]
が逆になっていたりして詰まるけど無事AC。
B AC(38分)
@menphimにCの説明を聞く。二分探索するのが良さそう(思考停止)と初見で思い、幾何ライブラリも持ち込んでいたのでその方針で取り掛かる
具体的には、建物のてっぺんを下底として、高さが十分に大きい長方形で空の部分を敷き詰める。 円がその全ての長方形と共通部分を持たないような円の中心のy座標の最大値を二分探索する。
@LazyMiiにライブラリを読み上げてもらいながら円と長方形の当たり判定を実装する。が、自分の勘違いで写し間違えていたり、trueとfalseを逆にしていたりで盛大にバグる。
@LazyMiiといっしょにデバッグするも細かいバグが次々見つかり、更に初めに考えた方針自体が少し間違っていることに気づき、訳が分からなくなり、終了時間になってしまう。
デバックしている最中に@menphimがDが15分で解けるかもしれないし解けないかもしれない(?)と言ってくれたけど、苦手な文字列の問題だったので断ってしまった。
Eもグラフだから見てと言われて目を通したけど、1回しか通らない経路をどうにかして決めた後何かするんだろうなーと思いつつも大事な部分は分からなかったので、Cに集中したほうがいい気がして放置してしまった。
反省
コンテスト後のタイムラインで、Cの頭いい解き方を自称頭がついていないclimpetさんに教えてもらいほえーっとなる。(上位チームはみんなこれらしい)さらに、Dはよく考えたら正しくエンコードできたのをvectorに突っ込みながらbitで全探索して最後にソートする愚直な方法で十分だし、Eも初めだけ合ってたのでアイデアを説明して@menphimに詳しく考えてもらえばよかったなと思ったり、後悔ばかりだった。
変な解法に嵌って抜け出せなくなる負のスキルが発動して、それでもどうにか出来る実装力もなかった。精進します。
ソースコード
A
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; #define loop(i,a,b) for(int i=(a); i<int(b); i++) #define rep(i,b) loop(i,0,b) int main(){ int x,y,s; while(cin >> x>>y>>s && x|y|s){ int ans=-1; for(int i=1;i<=1000; i++){ for(int j=1;j<=1000; j++){ if(i*(x+100)/100 + j*(x+100)/100 > s) break; if(i*(x+100)/100 + j*(x+100)/100 != s) continue; ans = max(ans, i*(y+100)/100 + j*(y+100)/100); } } cout << ans << endl; } }
B
#include <iostream> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; #define loop(i,a,b) for(int i=(a); i<int(b); i++) #define rep(i,b) loop(i,0,b) typedef vector<int> vi; typedef vector<vi> vvi; int erase(vvi& g){ int h=g.size(); int res=0; rep(y,h){ for(int x=0; x<5; x++){ int t=g[y][x]; if(t==0) continue; int xx=x; for(;xx<5;xx++){ if(g[y][xx]==t) continue; else break; } int w=xx-x; if(w>=3){ for(int ix=x;ix<xx; ix++){ g[y][ix]=0; } res+=w*t; } } } return res; } void fall(vvi &g){ int h=g.size(); queue<int> gg[5]; for(int i=h-1; i>=0; i--){ for(int j=0; j<5; j++){ if(g[i][j]==0) continue; gg[j].push(g[i][j]); } } vvi ng(h,vi(5)); rep(j,5){ int i=h-1; while(gg[j].size()){ ng[i--][j]=gg[j].front(); gg[j].pop(); } } g=ng; } int main(){ int h; while(cin>>h && h){ vvi g(h,vi(5)); rep(i,h)rep(j,5)cin>>g[i][j]; int ans=0; while(1){ int t = erase(g); ans += t; if(t==0) break; fall(g); } cout << ans << endl; } }
はーーー…
平方分割のバケット法で区間の和を効率的に求める (UVa 12086 Potentiometers)
問題
個の可変抵抗が直列に繋がれている。
- 番目の抵抗を に変更
- 区間 の合成抵抗を出力(直列だから足すだけ)
という指示が来るので順番に処理せよ。
平方分割
抵抗もクエリも多いので普通に足すだけだとTLEする。
以前にあり本のFenwick Treeをコピペして解いたけど、平方分割のバケット法というテクニックを知ったので、その練習のためにやり直した。
このスライドが参考になった。 http://www.slideshare.net/iwiwi/ss-3578491
FenwickTreeは更新が ,出力も 、平方分割による 分木だと更新に ,出力に かかる。実際に掛かった時間はFenwickTreeは約0.21sec、平方分割は約0.43secくらいだった。更新が なのが優秀。
実装していてこれは賢いなーと思った。
バケット内の各要素に二分探索木を生やしたり、一般に 次元でやったりもするらしい。(だからtemplate<typename T>
にしてある。) そういえば弾幕STGの本で、当たり判定の部分で16分割くらいにして別々に処理していた気がする。
template<typename T> struct sqrt_tree{ vector<T> data, baqet; T sq; sqrt_tree(vector<T> const& v) :data(v){ sq = sqrt(data.size()); baqet.assign((data.size() + sq - 1) / sq, 0); rep(i, data.size()) baqet[i / sq] += data[i]; } T sum(int l, int r){ T res = 0; // 同じバケット内にある if (l / sq == r / sq){ loop(i, l, r) res += data[i]; } else { int e = r / sq; // 完全に被っているバケット loop(i, (l + sq - 1) / sq, e) res += baqet[i]; // 中途半端な左側のバケット if (l%sq){ int e = sq*(l / sq + 1); loop(i, l, e)res += data[i]; } // 中途半端な右側のバケット if (r%sq){ loop(i, r - r%sq, r)res += data[i]; } } return res; } void update(int i, T x){ baqet[i / sq] -= data[i]; data[i] = x; baqet[i / sq] += x; } }; int main(){ int t = 1; int n; while (scanf("%d", &n), n){ if (t != 1) puts(""); printf("Case %d:\n", t); t++; vl v(n); rep(i, n) scanf("%lld", &v[i]); sqrt_tree<ll> s(v); while (1){ char op[8]; scanf("%s", op); if (op[0] == 'M'){ int l, r; scanf("%d %d", &l, &r); l--; printf("%lld\n", s.sum(l, r)); } else if (op[0] == 'S'){ int i; ll x; scanf("%d %lld", &i, &x); s.update(i - 1, x); } else{ goto end; } } end:; /*cout << "DEBUG" << endl; rep(i, v.size())loop(j, i + 1, v.size() + 1){ cout << i << " " << j << " " << s.sum(i, j) << endl; }*/ } }