| 
縦か横か、どの列/行に揃えるか決めて、
揃えるコスト＋「ダックを並べ始めるとこからダックの数だけ、想定する場所に動かすためのコストの最小値」を計算する。
その最小値が答え。
説明しづらい。
方針を考えるのが遅い。実装もバグがいくつか。むむむむむ
practice で system test pass
class DucksAlignment { public: int minimumTime(vector <string> grid) { int N=0; int H=grid.size(); int W=grid[0].size(); VI v0, v1; REP(y, H) { REP(x, W) { if(grid[y][x]=='o') { v0.push_back(x); v1.push_back(y); N++; } } } sort(ALL(v0)); int ans = 100000000; REP(ii, 2) { int L=ii==0?H:W; FOR(ai, v0) { int lans = 0; FOR(v, v0) { lans += abs(*ai-*v); } int lans2=1000000; REP(be, L-N+1) { int llans2=0; REP(i, N) { llans2 += abs(be+i - v1[i]); } lans2 = min(lans2, llans2); } ans = min(ans, lans+lans2); } swap(v0, v1); } return ans; }
| 
とりあえず解くことはできたが時間がかかりすぎである。
思い込みで進めないでもっと考えるべきである。
class DropCoins { public: int getMinimum(vector <string> board, int K) { int W = board[0].size(); int H = board.size(); //cout<<W<<" "<<H<<endl; VVI v(H); REP(i, H) REP(j, W) v[i].push_back(0); REP(y, H) REP(x, W) { REP(yy, y+1) REP(xx, x+1) { v[y][x] += board[yy][xx]=='o' ? 1:0; } } VI ans; for(int sy=H;sy>0;sy--) { for(int sx=W;sx>0;sx--) { REP(by, H-sy+1) { REP(bx, W-sx+1) { int ax=bx-1; int ay=by-1; int ex=bx+sx-1; int ey=by+sy-1; int co=v[ey][ex]; if(ay>=0) co-=v[ay][ex]; if(ax>=0) co-=v[ey][ax]; if(ax>=0 && ay>=0) co+=v[ay][ax]; //cout<<" try "<<co<<" "<<bx<<" "<<by<<" "<<ex<<" "<<ey<<" area "<<sx<<" "<<sy<<endl; if(co==K) { int lans = 2*(bx+W-ex-1)-max(bx, W-ex-1) + 2*(by + H-ey-1) - max(by, H-ey-1); //cout<<"found "<<lans<<" "<<bx<<" "<<by<<" "<<ex<<" "<<ey<<" area "<<sx<<" "<<sy<<endl; ans.push_back(lans); } } } } } if(ans.size()==0) return -1; sort(ALL(ans)); return ans[0]; }
| 
本番では全然できなかったが、他の方の解説やヒントを参考に後から書いてみた。(system test pass)
S[i] = sum(A[0]..A[i]) とすると、sum(A[i-k]..A[i]) > 0 <==> S[i]-S[i-k-1] > 0 と、(i, i-k-1) の間に制約ができる。
これを有向グラフとして表し、閉路がなければ無矛盾なので解ありとする。
これを 0 ～充分大きな長さの範囲で二分探索すると答えが出るという流れ。
閉路検出に帰着するのか！こんな発想ができるようになりたいものである...
あと max_element 知らなかった。STL の勉強になるので人のソース読むのはいいなぁ。
今回は使わなかったけど累積を計算する partial_sum もあるんすね。
閉路検出のルーチンで帰りがけにノードを記録するようにして最後に逆順にすると、トポロジカルソートになるようである。
#include <cassert> #include <iostream> #include <vector> #include <cstdlib> using namespace std; #define REP(i,n) for(int i=0;i<(int)n;++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() typedef vector<int> Edge; typedef vector<Edge> Graph; bool tsort(Graph& g, int i, vector<int>& status, vector<int>& topo) { //cout<<"visit "<<i<<endl; status[i]=1; for(int j=0;j<g[i].size();j++) { if(status[g[i][j]]==1) return false; if(!status[g[i][j]] && !tsort(g, g[i][j], status, topo)) return false; } topo.push_back(i); status[i]=2; return true; } bool tsort(Graph& g) { int vn = g.size(); vector<int> status(vn, 0), topo; for(int i=0;i<vn;i++) { if(!status[i] && !tsort(g, i, status, topo)) return false; } //reverse(topo.begin(), topo.end()); //for(int i=0;i<topo.size();i++) { // cout<<topo[i]<<" "; //} //cout<<endl; return true; } int solve(vector<int>& cst) { int cn = cst.size(); if(*max_element(ALL(cst))<0 || *min_element(ALL(cst))>0) { return -1; } // S[i] = sum(A[0]..A[i]) // sum(A[i-k+1]..A[i]) > 0 <==> S[i]-S[i-k] > 0 // make edge i->j | S[i]>S[j] int low=0, high=10000; while(high-low>1) { int mid = (high+low)/2; Graph g(mid+1); // graph node 0..mid (mid+1) FOR(c, cst) { REP(i, mid+1-abs(*c)) { if(*c>0) g[i+abs(*c)].push_back(i); else g[i].push_back(i+abs(*c)); } } bool ret = tsort(g); //cout<<mid<<" "<<ret<<endl; if(ret) low=mid; else high=mid; } return low; } #define CHECK(cst, ref) check((cst), sizeof(cst)/sizeof(cst[0]), ref) int check(int cst[], int n, int ref) { vector<int> tmp(cst, &cst[n]); int ret = solve(tmp); if(ret!=ref) { FOR(v, tmp) cout<<*v<<endl; cout<<ref<<" but ret "<<ret<<endl; } return 0; } int main() { CHECK(((int[]){-2, 3}), 3 ); CHECK(((int[]){524}), -1 ); CHECK(((int[]){1, -1}), 0 ); CHECK(((int[]){11, -7}), 16 ); CHECK(((int[]){-227, 690, 590, -524}), 713 ); CHECK(((int[]){514, -514}), 513 ); CHECK(((int[]){524, -524}), 523 ); CHECK(((int[]){1}), -1 ); CHECK(((int[]){-1}), -1 ); CHECK(((int[]){1, 2, 3, -1, -2, -3}), 0 ); CHECK(((int[]){1000, -1000}), 999 ); CHECK(((int[]){1000, -999}), 1997 ); CHECK(((int[]){999, -1000}), 1997 ); : :
| 
"()" を""に置換して、残った文字数が答え。std::stringのreplaceを初めて使ったらちょっとハマって20分かかってしまい166点。(同じ部屋の人はみなさん220-249)
| 
点の個数が40個までなので個数に関してなんかループをまわすんだろうと思ったが、どうやって正方形の位置を決めるのかなど、その後良いアイデアが出ず。
名前忘れたけど赤コーダーのひとの解答が分かりやすかった。
点のx座標とy座標それぞれでソートしてユニークにして、そこから四重ループでx1 y1 x2 y2と決めていくと、すべての点の囲み方が列挙できる。さらに、x1-1 y1-1 x2+1 y2+1は正方形に入る予定の点群を含み、かつ入らない予定の点群を(線上を除いて)含まない最大の長方形を表すので、
あとは、含まれる点群とnlowから決まる正方形サイズと含まれない点群とnhighから決まる正方形サイズを求めて、前者の方が小さければそのパターンをsetに追加する。で最後にsetのサイズが答え。
パターンは2**40が表せればいいのでlong longで。
ポイントは、実際に解となる集合のサイズが2**40より大幅に小さいのと、正方形の具体的な場所が決まらなくてもサイズの条件からあり得るかどうか決まる、の二点のようだ。
ふむぅ..
| 
a(small/large) だけ 15点 349位 ズタボロ。
A smallを（初めて使うときがキタコレ！のnext_permutationを使って）16分で通したまでは良かった....
が、そこからB Cと各1時間強やってだめで、このまま5点で終わるとかヤバいショボすぎると焦りつつ、終了10分前にそういえばA smallの解の傾向を見てみよう→あー山作るだけか→つうかBの前にこれやっとけよ→で急いで山を作るコードを書いてlarge提出したのが終了124秒前。
それからA smallの結果と比較して合ってることを確認して大丈夫だろうと一安心するものの相変わらずTシャツ圏外でがっくし感はまったく変わらず。
B smallはpythonでやり始めてbinary冪乗を実装したけど1回目の時点でmodをとってしまっていてだめだった。そりゃそうだ。1回目は普通にA**Aでいけるんすね。
ちなみにpython 2.7以降は三引数powがあって、三番目の数でmodを取った結果を高速に計算してくれるようだ。これを使うだけでB smallは通るみたい。へーへーへー。
Cは最初の文字列のすべての部分文字列についてパターンを作って他方に含まれてなかったらokという方針でためしたけどbm bmm みたいに他方が全部分文字列を含む場合がだめとわかってあーだこーだやってたら時間が経ったので諦めた。
ということで全体的に焦っていて最悪だった。ハマったら深呼吸して落ち着くべしですね。
最悪だったけど、コンテスト自体は恒例のお祭りみたいで楽しかったです。定期的に腕試しができて良いことです。
