srm429
全っ然分からなかった。今でも何が起きたのか謎。もっと勉強します。。。
div1:250
dpと思ってやってたので全然思いつかないのも当たり前。
あるマスに着目するとそのマスを含むような四角形の作り方の数が定数時間で求められる。
全てのアルファベットの出現回数の和は当然その四角形の作り方の数の和と等しくなる。
opened
div1:500
ウォーシャルフロイドでLCMっぽい物を計算。
opened
div1:1000
unopened
0点だったのでまた青か〜寂しいな〜
ICPC 2008 アジア地区予選 参加記
本番で書いたコードが送られて来たら思い出しながらしみじみ書こうかと思ったんですが、一向にその気配が無いので今更ながら書きます。とりあえず当日だけ。僕たちはトップチームとかでは全然ないので参加者が読んでも新たな知見を得られたりするわけではありませんが、これを読んだ人が興味を持って来年参加してくれたりしたら良いかなぁと。時間は覚えてないのでかなり適当です！
-75分
戦いは朝食から始まってました。スケジュールが全く同じ参加者全員が一つのホテルに詰め込まれているため朝食バイキングに長蛇の列が。30分以上並ぶ人もいたような。僕たちのチームは並ぶのに20分位かかって、食べ終わって出た時には40分位経ってたと思う。でも美味しかったから良いです。アホほど食った。
バスに乗って会場に到着すると既に開始10分前。余裕持って起きたはずなのになぁ。机の上に筆記用具等を並べて準備をし始める。
-5分
他のチームの人がなかなか集まらない。おそらく朝食のせい。ざわざわ。開始1分前になっても会場に入る人の流れは止まらない。こんな状態で始めるのかなぁ、えー始まった。
0分
心臓ばくばくになりながら封筒を開けると、なんと、問題セットが1部しか入ってない！これはひでー。去年はちゃんと3部あったような気がする。メモ用紙はどうしろって言うんだろ。とりあえずAとBの読解をお願いして自分はテンプレートや.emacsを書き始める。
5分
テンプレート書き終わる。Aを読んでた人に問題の説明をお願いするも、全然分からない。ただ大変分かりにくい問題だと言う事はわかった。他のチームも風船上がってないし、とりあえず焦らず、分かったらまた教えてーと言ってBを聞く事にする。
10分
Bも分からないｗこれは俺に問題があるのか。でもBは疑似コードを紙に書いてくれると言うので、書き終わるまでAに取り組む事にする。
25分
Aの説明にまだ曖昧な所があるけど、とりあえず書かなければ始まらないので書く。でも書いてて分からない所を聞いても返事が曖昧だ。うーむ。書き終わってもサンプルと一致しない。ちょっとこの流れはまずい。するとBの疑似コードが出来たというので再びBにスイッチ。
35分
Bの疑似コードを打ち込んだらサンプルと一致した。おーー！Submit & Accepted。結局Bを一番最初に通してしまった。終わった後で他のチームの人に「今年のA分かりづらかったですよねー」と言ったらみんな同意してくれたけど、「B先に通しましたよー」っていったら同意してくれなかった。
50分
Aの問題解釈が何度も変わってコードがぐちゃぐちゃになりながらも、ようやくサンプルと一致するコードが出来たので送信。Accepted。うーむちらほら4問通すチームも出始めた。まずいまずい。
60分
Cを聞いたらなんだか簡単そう。シミュレートして探索するだけか。探索部分が気になるけどとりあえずシミュレート部を書こう。三つの針の位置から時間を逆引きするためにvector
80分
シミュレート部が完成したので探索部分を書く。針の割当はnext_permutationした後で0~59を足して60でmod取ってやれば良くて、後は単なる探索を書くだけ。おっけー楽勝ーと思って書き始める。とりあえず全探索を書いてサンプルと一致したので、送信。TLE。げーやっぱ深さ12で全探索は辛いか…。考えるのが面倒だったので適当に枝刈りを入れる（現在までの最小の時間差を保持して、超えるなら枝刈り）。速くなったので送信。が、WA！サンプルと完璧に一致してるのでどうしようもない。枝刈りも間違ってない。うーん。PCの前で悩んでも仕方ないのでコードを印刷して紙デバッグをお願いする。
100分
まぁ目標6問だから1問50分で解けば良いわけで…と鼓舞。たださすがに2問しか解けてないのはまずかろう、と思ってstandingsを見ると、意外とみんな解けてなくて、10~12位くらいだった気がする。
問題解説をしてもらってFが見るからに探索なので次に取り組む事に決める。
120分
今度はじっくり解説してもらう。6色に塗り分けられた6面体をxy平面上で転がしていって目的地に辿り着くまでの最短ターンを求める問題。ただしマス目の色と6面体の上の面の色が一致するようにしか転がせない。なるほどねーサイコロと幅優先探索ね。状態数を計算するに、幅(30)*高さ(30)*サイコロの状態(24)*どこまで色を踏んだか(6) = 13万。楽勝でメモリに乗る。やるだけじゃん。うまい。spaghetti sourceのサイコロを写経して、dice
160分
Fをやっている間にstandingsを見て次に解くべきだろうと決めていたGに取りかかる。チームメイトに解説してもらうと、要するに長さ5000の文字列が与えられるので12個の単語のpermutationと一致する箇所を求めろとの事。箇所なので、文字列がaaで単語がa,aの時は2ではなく1になる。naiveには5000*12!だけどこれは終わらないな、と思っていると本文にも終わらないと書いてあったらしい。親切すぎる。こんなの誰もひっかからないだろー。疑似コード（深さ優先探索）まで書いてもらっていたので書き写し、サンプルと一致したので送信。TLE。はい。
180分
定数倍の最適化を何度か施し（てTLEをもらっ）ている間にチームメイトが最悪ケースを考えてくれていた。文字列がa...(5000)で、単語がa,a,..,bの場合。5000回単語に関して深さ優先探索するコードだったので、全てのpermutationが一致しない場合に結局5000*12!かかってた。はい。流石にnext_permutationは回避したものの見事にひっかかってました。しかしこれは別のアプローチが必要そうだ。
200分
CのバグをつぶすかGを考えるかで迷う。Cは全く糸口が掴めない。一方Gは計算量的にDPしか無いような気がする（文字列の長さが既に5000なのでせいぜいその10000倍位の計算しか必要でないはず）。チームメイトに了解を取ってGを進める事にして、Cのデバッグと問題読解を引き続きお願いする。
210分
PCの前に誰も座らず紙に向かう時間が始まる。GがDPだとするとまず計算途中の状態というのをはっきりさせないといけない。どのような情報があれば、ある箇所に全ての単語を使用したマッチが可能か分かるのかを考える。単語全体の集合をSとしてpermutationの最後で使う単語をs1とすると、s1以外の単語の集合S'を使って直前までマッチ出来た時にそこでs1がマッチ出来れば良い。もっと言うと単語の順序は必要なくて、どの単語を使用した時にどの箇所でマッチできるかが分かれば良い。使った単語の集合は単語の数が12個までなので12ビットあれば表せる。ビットDPか…ICPCではゆるいDPしか見た事ないし自信無いなぁ。と思いながら計算量を見積もると5000 * 2 ^ 12 = 2000万。dp[5000][1 << 12]はboolで取れば20MB。ぴったりだ、間違い無い。コード自体はシンプルになるので簡単なコードを書いてサンプルで試してみると、出力は少し間違っているものの計算自体は一瞬で終わる。おーー来た来た！
230分
Gを手直しすると出力が合うようになったのでSubmit。どきどきしながら結果を待っていると、なんとTLE。えーー。とここでチームメイトが紙でバッグでCのバグを発見してくれた。0~59までの値を足して60でmodを取る部分で、for文の終了条件がなんと「0 < 59」になっている。うわ！！これだこれ！59を意識しすぎていたのか何なのか。「0 <= 59」に書き換えて送信。これでWrong Answerだったらどうしようもないなーとか思って待っていると、今度はAccepted。よしこれで4問目。
250分
Gは計算量的にTLEはあり得ないので遅い原因を探す。と、単語が文字列とマッチするかを判断している部分が、あらかじめ5000箇所 * 12単語だけ計算すれば良いはずの所ループの中で繰り返し呼ばれている。これを外に追い出してみると数倍速くなったので送信…Accepted！浮かれてチームメイトと抱き合う。
260分
残り40分。解法さえ分かればもう一問いける時間。standingsを見るにDとEのどちらかを解く事になりそう。Dが強実装でEが空間幾何、どちらかと言えばEの方が解いたチームが多い。けれどもうちのチームに幾何要員は居ないのでDに行くしかない。直線が沢山与えられるので、それらをデジタル表示の数字（0~9)として見なした時に、それぞれの数字がいくつ出現したかを数える問題。直線はそれほど多くないので全対全で交差判定をしてUnionFindで分類して、それぞれの数字を構成するらしき直線の集合ごとに処理してやれば良さそう。チームメイトによると、直線が一本だけだったら1しかあり得ないし、四本で交点が四つだったら0しかあり得ない、みたいな調子で直線の数、交点の数、交点の種類（端点を共有するのか直線上に端点が乗るのか）を用いれば、2と5を除いて分類できる。2と5だけはccwで角度を調べないといけなくて少し面倒。との事。素晴らしい。ここまで来ればあとは実装を頑張るだけ。書いて書いて書いて書いて書く。
299分
書いて書いて書いて書いて、250行を超えようかという所で残念ながら時間切れ。書き始める前にもう少し整理するべきだった。。。
300分
疲れたー。結局試合中に席を離れたのは一度だけで軽食を食べる時間がなかったのがちょっと残念だった。その後選手の所まで来てくれたコーチと感想戦。GはDPだったとかDが面倒過ぎたとかFは実は簡単だったらしいとかそういう話をした。
srm427
とってもひどかった時のsrm日記。
div1:250
今回もなかなか読めなくて、要するに(yearLength % dayLength) * x = dayLength *
yとなるような最小のxを求めれば良いんだろーと思ってlcm(yearLength % dayLength, dayLength) / (yearLength % dayLength)って書いて提出したらyearLength == dayLengthの時の0割りエラーとlcm内部でのオーバーフローで死亡してた。
failed system test
div1:600
digの値を調べてみるとなんとなくdig(x * a) = dig(dig(x) * dig(a))っぽい事が分かった（気がした）ので、dig(multi ^ n)をanと置くとan+1 = dig(an * dig(multi))になってごにょごにょするのかな〜Kがでかい数列だからlogn累乗か〜と思ってやってたけど全然違ったという。こういうアドホックな問題はパニックになっちゃうな〜
opened
div1:900
今回も見ず。
challenge
600のfor(int i = 0; i < K; ++i)を見て特攻して-25ｗ内部でループを検出して抜けるというロジックが入っていたらしい。他にも同じ部屋の人が何人か釣られてた。
トータル-25で200近くレーティングが下がってとても悲しいです。色が変わらなかったのだけが救い。探索どこ〜DPどこ〜
（11/28追記）今更ながら600をやってみたけど、ループ長Lを最初に求めてlcm(L, 4)回シミュレートしてから最後にK % lcm(L, 4)回シミュレートするだけだった。ループするという仮定があればの話だけど、これは解かないとまずいな〜
Binary Indexed Tree
FloatingMedianとProductOfPricesとUVa 10909で動くのを確認。
template<class T> class BIT{ public: BIT(int n) : n(n), tree(n) {} T read(int idx) { // returns 0 if idx is smaller than 0 T ret = 0; for (; idx >= 0; ret += tree[idx], idx = (idx & (idx + 1)) - 1); return ret; } T read(int idxl, int idxr) { // both are inclusive return read(idxr) - read(idxl - 1); } void update(int idx, T val){ for (; idx < n; tree[idx] += val, idx |= idx + 1); } int getk(T k) { if (read(n - 1) < k) return -1; int lo = 0, hi = n - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (read(mid) >= k) hi = mid; else lo = mid + 1; } return lo; } private: vector<T> tree; int n; };
srm426
黄色くなって初めてのsrm!
div1:250
読んでも読んでも問題の意味する所が分からなかったが、こんだけ分かりづらかったらみんなもスコア低くなるだろ。。。と思って特に焦らず読む。10分ほど読んでようやく手計算と結果が一致したので注意深く組んで提出。部屋で3番手だったからやっぱりな〜と思ってちょっと安心。
passed system test 186.16
div1:500
ネズミを囲う事の出来る最小の範囲Lを求めれば良くて、Lが最小となるのは（きっと）あるネズミのペアの距離が最も近くなった時で、ネズミ同士の距離は下に凸な二次方程式で表せるので、微分または平方完成して時刻を全列挙して調べれば良い。と思って式を打ち込んだんだけど微妙に合わない。数パーセントの誤差がどうしても出てしまう。今考えるとこれが罠で、どっかでdoubleをintにキャストしてるのかな〜とか式写し間違えたかな〜とか思って調べてる間に時間切れになってしまった。で、今考えるに「きっと」の部分がおかしくて、範囲は円ではなく四角形なので距離が最小の時にLが最小になるとは限らない。うぁぁぁ。。。。そらそーだ！
opened
div1:1000
読まず。いや開かず。
500は三分探索だったかー。距離で考えてたから時間に関するLのグラフが奇麗に下に凸にならず凸凹になる気がして、局所解で止まる可能性を考えて止めてしまった。三分探索にしても初期条件の最大値をどれくらいで押さえれば良いのかとかそれほど自明でないのでちょっと難しい。
結局250をなんとも微妙な点数で通せただけだったので絶対レーティング下がるーと思って凹んでたら微増して嬉しい。1691から1728に37up。次回は実装ゲーな500を…お願いします…さいころダンジョンBFSとか…
（追記）
500はどう考えても三分探索がベストだ。
vector<int> xp, yp, xv, yv; double getl(double t) { double maxx = -1e50, minx = 1e50, maxy = -1e50, miny = 1e50; for (int i = 0; i < xp.size(); ++i) { double x = xp[i] + xv[i] * t, y = yp[i] + yv[i] * t; maxx >?= x, minx <?= x, maxy >?= y, miny <?= y; } return (maxx - minx) >? (maxy - miny); } class CatchTheMice { public: double largestCage(vector <int> xp, vector <int> yp, vector <int> xv, vector <int> yv) { ::xp = xp, ::yp = yp, ::xv = xv, ::yv = yv; double minT = 0, maxT = 10000; for (int i = 0; i < 200; ++i) { double d = (maxT - minT) / 3, aT = minT + d, bT = maxT - d; if (getl(aT) < getl(bT)) maxT = bT; else minT = aT; } return getl(minT); }
UVa 11544 Recruiter's Problem
二部マッチングの練習をしようと思ったら丸一日かかった…
グラフはこんな感じ。
SRC --1-- CANDIDATE(i) --1-- PROJECT(j) --r-- SINK
まず最初にここと同じで、一人目の一つ目の仕事からgreedyに割り振り、流量が減らないなら採用する事を繰り返す、という方針でやる。手元だと正しい答えが出ているように思えるが残念ながらTLE。定数倍の最適化を繰り返して何とか２倍くらい速くなったり、dinicを止めてford-fulkersonにしたらさらに２倍くらい速くなったりしたがTLEは変わらず。少し考えると
1 5 5 1 1 1 1 1 5 1 2 3 4 5 4 1 2 3 4 3 1 2 3 2 1 2 1 1
のようなケースの時にN^2回（最悪50^2=2500回！）（追記：正しくはN*(N+1)/2回ですね）の最大流が回るのでTLEなのも分からなくもない。どうしたもんかな〜〜〜〜と思ってforumを覗くとbinary-search出来るんじゃん？とある。うぉ！これだと最大流がNlogN回になって最悪ケースでも350回程度に押さえられる。素晴らしい〜（逆に50回で済むのが350回になって7倍程度遅くなるケースもあるけども）。と思って実装に取りかかるも、言うは易しで、どうやんだこれ？状態になり、全員使えるケースでは上手く行くが余るケースで上手く行かなかったり、そもそも「ある人が、自分の希望する仕事のうちx番目がらy番目の候補のどれかに必ず割り振られるような状態で最大流を求める」とかややこしすぎるだろ〜どうすんだ〜ってなったり、binary-searchなんて出来るのかと疑ったりしたけども最終的に上手くいってACもらった。嬉しす。
しかしdinicよりford-fulkersonが２倍速かったりまさかのbinary-searchで通ったりグラフを操作して「ある条件を満たすフロー」を流す事を勉強したり色々と良かった。
DinicとEdmondsKarp
どれが最新か分からなくなりそうなのでここにメモ。
// UVA 10989 AC:0.990sec // PKU 3469 AC:5938MS // (時間はdinicの方) class Graph { private: struct Edge { int to, back, flow, cap; Edge(int to, int cap, int back) : to(to), back(back), flow(0), cap(cap) {} int residue() { return cap - flow; } }; int n; vector<vector<Edge> > g; public: Graph(int n) : n(n), g(n) {} void insert(int i, int j, int c) { g[i].push_back(Edge(j, c, g[j].size())); //g[j].push_back(Edge(i, 0, g[i].size() - 1)); // 1) directed graph g[j].push_back(Edge(i, c, g[i].size() - 1)); // 2) undirected graph } int dinic(int s, int t) { for (int flow = 0, P[n], Q[n];;) { memset(P, -1, sizeof(P)); int QF = 0, QB = 0; P[Q[QB++] = s] = -2; while (QB > QF && P[t] == -1) for (int u = Q[QF++], v, i = 0; i < g[u].size(); ++i) if (P[v = g[u][i].to] == -1 && g[u][i].residue() > 0) P[Q[QB++] = v] = g[u][i].back; if (P[t] == -1) return flow; for (int i = 0, z; i < g[t].size(); ++i) if (g[z = g[t][i].to][g[t][i].back].residue() > 0 && P[z] != -1) { int inc = g[z][g[t][i].back].residue(); for (int e = z; P[e] >= 0; e = g[e][P[e]].to) inc = min(inc, g[g[e][P[e]].to][g[e][P[e]].back].residue()); if (!inc) continue; g[t][i].flow -= inc, g[z][g[t][i].back].flow += inc; for (int e = z; P[e] >= 0; e = g[e][P[e]].to) g[e][P[e]].flow -= inc, g[g[e][P[e]].to][g[e][P[e]].back].flow += inc; flow += inc; } } } int edmondsKarp(int s, int t) { for (int flow = 0, P[n], Q[n];;) { memset(P, -1, sizeof(P)); int QF = 0, QB = 0; P[Q[QB++] = s] = -2; while (QB > QF && P[t] == -1) for (int u = Q[QF++], v, i = 0; i < g[u].size(); ++i) if (P[v = g[u][i].to] == -1 && g[u][i].residue() > 0) P[Q[QB++] = v] = g[u][i].back; if (P[t] == -1) return flow; int inc = INT_MAX; for (int e = t; P[e] != -2; e = g[e][P[e]].to) inc = min(inc, g[g[e][P[e]].to][g[e][P[e]].back].residue()); for (int e = t; P[e] != -2; e = g[e][P[e]].to) g[e][P[e]].flow -= inc, g[g[e][P[e]].to][g[e][P[e]].back].flow += inc; flow += inc; } } };
2009/7/10追記。Dinic書き直し。
// SPOJ 4110 AC: 2.6sec // UVA 10989 AC: 0.692sec #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) template<typename T> struct Graph { struct Edge { int to, back; T flow, cap; Edge(int to, T cap, int back) : to(to), back(back), flow(0), cap(cap) {} T Residue() { return cap - flow; } }; int n; vector<vector<Edge> > edges; Graph(int n) : n(n), edges(n) {} void Connect(int i, int j, T c) { edges[i].push_back(Edge(j, c, edges[j].size())); //edges[j].push_back(Edge(i, 0, edges[i].size() - 1)); // 1) directed graph edges[j].push_back(Edge(i, c, edges[i].size() - 1)); // 2) undirected graph } Edge& Back(Edge& e) { return edges[e.to][e.back]; } T Dinic(int s, int t) { int P[n], Q[n], QF, QB; for (T flow = 0;;) { memset(P, -1, sizeof(P)); for (QF = QB = 0, P[Q[QB++] = s] = -2; QB > QF && P[t] == -1;) { int u = Q[QF++]; FOR(e, edges[u]) if (P[e->to] == -1 && e->Residue() > 0) P[e->to] = e->back, Q[QB++] = e->to; } if (P[t] == -1) return flow; FOR(e, edges[t]) if (Back(*e).Residue() > 0 && P[e->to] != -1) { T inc = Back(*e).Residue(); for (int u = e->to; P[u] >= 0; u = edges[u][P[u]].to) inc = min(inc, Back(edges[u][P[u]]).Residue()); if (inc == 0) continue; e->flow -= inc, Back(*e).flow += inc; for (int u = e->to; P[u] >= 0; u = edges[u][P[u]].to) edges[u][P[u]].flow -= inc, Back(edges[u][P[u]]).flow += inc; flow += inc; } } } };
