cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
Dで。普通。
#!/usr/bin/rdmd import std.algorithm; import std.array; import std.conv; import std.stdio; import std.string; void solve(real[] S) { const X = S.reduce!"a+b"; foreach(J; S) { real L = 0, R = 1; foreach(_; 0..1000) { real Y = (L+R)/2; real myScore = J + X*Y; real beatMe = 0.0; foreach(JJ; S) beatMe += max(0.0, (myScore-JJ)/X); (beatMe <= 1 ? L : R) = Y; } writef(" %.09f", L*100); } } void main() { const T = readln.chomp.to!int; foreach(t; 0..T) { writef("Case #%d:", t+1); solve(readln.split.map!(to!real).array[1..$]); writeln(); } }
Dで。std.containerの使ったつもりになって書いたはいいがコンパイルエラーとれず使い方わからず、自分で書いた方が速え、という展開に…
#!/usr/bin/rdmd import std.algorithm; import std.array; import std.conv; import std.stdio; import std.string; import std.typecons; class Heap(T) { T[] data; T front() { return data[0]; } void removeFront() { data[0] = data[$-1]; data.length --; for(int i=0;; ) { int l = i*2+1; int r = i*2+2; if(l>=data.length) break; int c = r>=data.length ? l : data[l]>data[r] ? r : l; if(data[i]>data[c]) { T t = data[i]; data[i]=data[c]; data[c]=t; i = c; } else { break; } } } void insert(T e) { data ~= e; for(int i=data.length-1; i>0; ) { int p = (i-1)/2; if(data[p] < data[i]) break; T t = data[i]; data[i]=data[p]; data[p]=t; i = p; } } } real solve(in int Water, in int H, in int W, in int[][] C, in int[][] F) { alias Tuple!(int, "w", int, "y", int, "x") State; bool[long] V; auto Q = new Heap!State(); Q.insert(State(-Water,0,0)); for(;;) { // Deque State s = Q.front; Q.removeFront; int w = -s.w; int y = s.y; int x = s.x; // Visit check long key = y*100L + x; if(key in V) continue; V[key] = true; // Goal if(y==H-1 && x==W-1) return (Water-w) / 10.0; // Next int[] dy = [-1,+1,0,0]; int[] dx = [0,0,-1,+1]; foreach(d; 0..4) { int yy = y + dy[d]; int xx = x + dx[d]; if(0<=xx && xx<W && 0<=yy && yy<H) { int meF = F[y][x]; int meC = C[y][x]; int yoF = F[yy][xx]; int yoC = C[yy][xx]; if( !(yoF+50 <= meC) ) continue; if( !(max(meF, yoF)+50<=yoC) ) continue; int wlevel = min(w, yoC-50); int t = (wlevel==Water ? 0 : wlevel-meF>=20 ? 1 : 10); State next = State(-(wlevel-t*10), yy, xx); long nextkey = next.y*100L + next.x; if(nextkey !in V) Q.insert(next); } } } assert(false); } void main() { const T = readln.chomp.to!int; foreach(t; 0..T) { auto header = readln.split.map!(to!int); int Water = header[0]; int H = header[1]; int W = header[2]; int[][] C, F; foreach(_; 0..H) C ~= readln.split.map!(to!int).array; foreach(_; 0..H) F ~= readln.split.map!(to!int).array; writefln("Case #%d: %.1f", t+1, solve(Water, H, W, C, F)); } }
Dで。3進数マスクすぐ作れるのはいい感じ。Largeわからなかった。
#!/usr/bin/rdmd import std.algorithm; import std.array; import std.conv; import std.stdio; import std.string; import std.range; void solve(in long[] S) { const N = S.length; for(int m=0; m<3^^N; ++m) { auto S1 = iota(N).filter!((i){return m/(3^^i)%3==1;}).map!((i){return S[i];}).array; auto S2 = iota(N).filter!((i){return m/(3^^i)%3==2;}).map!((i){return S[i];}).array; long S1_sum = reduce!"a+b"(0L, S1); long S2_sum = reduce!"a+b"(0L, S2); if(S1_sum>0 && S2_sum>0 && S1_sum==S2_sum) { writeln(S1.map!(to!string).join(" ")); writeln(S2.map!(to!string).join(" ")); return; } } writeln("Impossible"); } void main() { const T = readln.chomp.to!int; foreach(t; 0..T) { writefln("Case #%d:", t+1); solve(readln.split.map!(to!long).array[1..$]); } }
presented by cafelier/k.inaba under