cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
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)); } }
presented by cafelier/k.inaba under