Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2012-05-06

GCJ12 Round1B A

11:50 | はてなブックマーク - GCJ12 Round1B A - 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();
   }
}

GCJ12 Round1B B

11:50 | はてなブックマーク - GCJ12 Round1B B - 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));
   }
}

GCJ12 Round1B C Small

11:50 | はてなブックマーク - GCJ12 Round1B C Small - cafelier@SRM

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..$]);
   }
}
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20120506
 | 

presented by cafelier/k.inaba under CC0