Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-09-24

SRM449

02:10 | SRM449 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM449 - naoya_t@topcoder SRM449 - naoya_t@topcoder のブックマークコメント

09.23+.2009

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 MaxTriangle o - - 174.22pts
1 550 HexagonalBattleField 間に合わず - - -
1 950 StairsColoring 開いてちょっと考えた -

250点問題: MaxTriangle

  • 2辺の長さの可能な全組合せについて、向き全パターンを試しても大丈夫
  • 辺の長さが1の場合が抜けてて焦った
  • 174.22points (20'43'')
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class MaxTriangle {
  double s(int v1x, int v1y, int v2x, int v2y) {
    return 0.5 * abs(v1x * v2y - v1y * v2x);
  }
 public:
  double calculateArea(int A, int B) {
    int i;
    map<int,int> sq;
    sq.clear();
    for(i=0;i<=44721;i++) { sq[i*i]=i; }

    set<pair<int,int> > ai, bi;
    ai.clear(); bi.clear();
    
    for(i=0;i<=A;i++) {
      int i2=i*i; if (i2 > A) break;
      int j2=A-i2; if (!found(sq,j2)) continue;
      int j=sq[j2];
      ai.insert(make_pair(i,j));
    }
    if (sz(ai)==0) return -1;
    for(i=0;i<=B;i++) {
      int i2=i*i; if (i2 > B) break;
      int j2=B-i2; if (!found(sq,j2)) continue;
      int j=sq[j2];
      bi.insert(make_pair(i,j));
    }
    if (sz(bi)==0) return -1;

    double smax=0, s_;
    tr(ai,at){
      int ax=at->first, ay=at->second;
      tr(bi,bt){
        int bx=bt->first, by=bt->second;
        for(int a0=-1;a0<=1;a0+=2)
          for(int a1=-1;a1<=1;a1+=2)
            for(int b0=-1;b0<=1;b0+=2)
              for(int b1=-1;b1<=1;b1+=2) {
                s_ = s(a0*ax,a1*ay,b0*bx,b1*by);
                if (s_ > smax) smax = s_;
              }
      }
    }
    
    return smax;
  }
};

550点問題: HexagonalBattleField

  • ネットワークのどの辺を取ってどの辺を捨てて・・・とか考えててDPっぽい無理コード書いてて訳分からん

950点問題: TheCardLineDivOne

  • 550が訳分からないので開いてみた。どっちを解くか考えたけど色の塗り分けに尻込みした。ProjectEulerならありがちな問題だと思うんだけど

Challenge Time

  • 落としも落とされもせず

174.22点。部屋で5位, Div1では 261/846

1419→1503 (+84) 4度目の青→黄色。そろそろ黄色で安定したい

http://gyazo.com/2bea53d91ccf482a90f27091117abdf1.png


追記。yeharaさんから激励のメッセージを頂きました。とりあえず1600を目指したいです。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090924