naoya_t@topcoder

SRM431 祝☆YellowCoder

12.23+.2008 (今年最終)

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	LaserShooting	◎				235.94点
1	500	MegaCoolNumbers	間に合わず
1	1000

250点問題: LaserShooting

数分でできた。（自己最速？）

システムテストも通って235.94点。

#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++)

class LaserShooting {
public:
  double numberOfHits(vector <int> x, vector <int> y1, vector <int> y2) {
    int n=x.size();
    double rate=0;
    for(int i=0;i<n;i++){
      double r1=atan2((double)y1[i],(double)x[i]),
        r2=atan2((double)y2[i],(double)x[i]);
      if (r1>r2) { double tmp=r1;r1=r2;r2=tmp;}
      rate += (r2-r1)/3.141592653589793238462643383279;
    }
    return rate;
  }
};

円周率手打ちです。acos(-1)とかM_PIとか使った方が打鍵数少なくて良いのですが思いつかなくて。すみませんすみません。

500点問題: MegaCoolNumbers

たっぷり（１時間超）時間が使えたけど解けなかった。

あとで続きを考えよう。

部屋で１人もsubmitしていなかった。チャレンジすらできないとは。

［追記］Div1全体でも19人しか通ってない！

1000点問題

開いてない

もしかしたら1000点問題に挑戦してもよかったのかも・・・解けそうかどうか開いてみるだけでも・・・

235.94点で119/526位。

レーティング：1456→1577 祝☆Yellow Coder昇格

これは素敵なクリスマスプレゼント（≒自分へのご褒美）。

次回SRM（来年）ではとりあえず黄色防衛したいので、確実に２問解ける実力（特にスピード）を身につけないと。

来年はRedを目指す！！

SRM410 Div1 Easy: AddElectricalWires

過去問, 練習 | 18:07 |

これ250点問題だけどちょっと難しい。サンプルケースが通った程度では安心できない。通過率も53.71%でMediumより低い。

• gridに繋がっているノードをまとめる
  • いちばん多く繋がっているgridはどれか
• gridに繋がっていないノードは全て、いちばん多く繋がっているgridに繋げる
• 各gridについて、同じgridに繋がるノードは全て繋ぐ
• 最初からあるコネクションの数を引く

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#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++)

class AddElectricalWires {
  vector<vector<bool> > w;
  vector<int> gC;
  int nw, ngc;

  void turn(int orig,int dest) {
    rep(i,nw) if (gC[i]==orig) gC[i]=dest;
  }

public:
  int all_connections(int n) { return (n>=2) ? n*(n-1)/2 : 0; }
    
  int maxNewWires(vector<string> wires, vector<int> gridConnections) {
    nw = wires.size(); // 1-50
    ngc = gC.size(); // 1-50

    gC.resize(nw); rep(i,nw) gC[i]=-i-1;
    tr(gridConnections,it) gC[*it]=*it;

    int conn = 0;
    w.resize(nw); tr(w,it) it->resize(nw);
    rep(i,nw) rep(j,nw) {
      w[i][j] = (wires[i][j]=='1');
      if (i<j && w[i][j]) {
        conn++;
        turn(min(gC[i],gC[j]), max(gC[i],gC[j]));
      }
    }
    rep(i,nw) if (gC[i]<0) gC[i] = -1;

    vector<int> count(nw+1,0);
    rep(i,nw) count[1+gC[i]]++;

    int maxc = 0, maxc_at = -1;
    for (int i=1;i<=nw;i++)
      if (count[i] > maxc) {
        maxc = count[i]; maxc_at = i;
      }
    if (maxc_at < 0) {
      return all_connections(nw) - conn;
    } else {
      count[maxc_at] += count[0];
      int ans = 0;
      for (int i=1;i<=nw;i++) ans += all_connections(count[i]);
      return ans - conn;
    }
  }
};

SRM409 Div1 Easy: OrderedSuperString

過去問, 練習 | 18:07 |

酩酊状態で解いたら１時間かかった。バグっててシステムテスト１つ通らず。（→直った）

class OrderedSuperString {
public:
  int getLength(vector<string> words) {
    int n=words.size();

    string w0=words[0];
    int l0=w0.length();
    if(n==1) return l0;
    int a0=0;

    for (int i=1;i<n;i++) {
      string wi=words[i];
      int li=wi.length();
      if (l0>=li) {
        for(int a=a0;a<=l0-li;a++) {
          if(w0.substr(a,li)==wi) {a0=a; goto next;}
        }
      }
      for(int w=min(l0,li-1);w>0;w--){
        if(l0-w<a0)continue;
        if (w0.substr(l0-w,w)==wi.substr(0,w)) {w0+=wi.substr(w,li-w);a0=l0-w;l0+=li-w;goto next;}
      }
      a0 = l0; w0 += wi; l0 += li;
    next:
      ; 
    }
    return l0;
  }
};