naoya_t@topcoder

SRM449

02:10 |

09.23+.2009

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

250点問題: MaxTriangle

• ２辺の長さの可能な全組合せについて、向き全パターンを試しても大丈夫
• 辺の長さが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) ４度目の青→黄色。そろそろ黄色で安定したい

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