Warm Up Contest

会津大学主催のプログラミングコンテストに参加してみた。
レジストしてからc,c++しか使えないことに気づいてどうしようかと思ったけど、勉強も兼ねて参加。
結果は６問中３問でした。

A：Traffic Analysis

経過時間をソートして最大の間隔のものをとるだけ

B：Cubes Without Holes

n*n*nの立方体(n <= 500)に何本かの線分を貫通させる。このとき穴の開いていない立方体が何個あるか答えよという問題。
500^3 = 1250万だから500*500*500の配列を用意して穴をあけるのをシミュレートしていけば大丈夫かと思ったけどTopCoderと違って1ケースにつき何秒ではなく、何個かのケースの合計で1秒のためTLEをもらった。
結局穴が空いた立方体の座標をsetにつっこんでn^3からsetのサイズを引くという方針で通した。

C：Simple GUI Application

入れ子構造になっているGUIのXMLっぽい設定ファイルが与えられるのでパースしなさいという問題。
パースとかよりもC++で部分文字列をどう取るんだっけみたいな文法的知識がないことに苦戦した。
C.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Panel{
  vector<Panel> children;
  string name;
  int x1,y1,x2,y2;
  Panel(string name , int x1, int y1 , int x2 , int y2):name(name),x1(x1),y1(y1),x2(x2),y2(y2)
  {}
  void add(Panel p){
    children.push_back(p);
  }
  int size(){
    return children.size();
  }
};

typedef pair<Panel , int> result;

result parse(const string &tags , int p){
  int ts = tags.find('<' , p);
  int te = tags.find('>' , p);
  string name = tags.substr(ts + 1 , te - ts - 1);
  ts = tags.find('<' , te);
  int x1,y1,x2,y2;
  string value = tags.substr(te + 1 , ts - te - 1);
  sscanf(value.c_str() , "%d,%d,%d,%d" , &x1 , &y1, &x2, &y2);
  Panel panel(name , x1 , y1 , x2 , y2);
  string endtag("</"); endtag += name; endtag += ">";
  int et = tags.find(endtag , ts);
  p = ts;
  while(p != et){
    result res = parse(tags , p);
    panel.add(res.first);
    p = res.second;
  }
  result r(panel , et + endtag.size());
  return r;
}

bool find(Panel p , int x , int y){
  if(p.x1 <= x && x <= p.x2 && 
      p.y1 <= y && y <= p.y2){
    if(p.size() == 0){
      cout << p.name << " " << p.size() << endl;
      return true;
    }
    for(int i = 0 ; i < p.size() ; i++){
      Panel child = p.children[i];
      if(find(child , x , y)){
        return true;
      }
    }
    cout << p.name << " " << p.size() << endl;
    return true;
  }
  return false;
}

int main(){
  int n;
  while(1){
    cin >> n;
    if(n == 0)break;
    string tags;
    cin >> tags;
    Panel root = parse(tags , 0).first;
    int x , y;
    for(int i = 0 ; i < n ; i++){
      cin >> x >> y;
      if(!find(root ,x , y)){
        cout << "OUT OF MAIN PANEL 1" << endl;
      }
    }
  }
  return 0;
}