CODE FESTIVAL 2016 予選B : B - Qualification simulator

問題リンク :
B: Qualification simulator - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 略

解法 :
既に通過した国内の学生と海外の学生の数を変数に保持しながらループを回します。

コード :

#include<iostream>

using namespace std;

const string YES = "Yes";
const string NO  = "No";

int main() {
  int N,A,B;
  string S;
  cin >> N >> A >> B >> S;
  int a = 0,b = 0;
  for(int i=0;i<N;++i) {
    if( S[i] == 'a' ) {
      if( a+b < A+B ) cout << YES << endl,++a;
      else            cout << NO << endl;
    } else if( S[i] == 'b' ) {
      if( a+b < A+B && b < B ) cout << YES << endl, ++b;
      else                     cout << NO << endl;
    } else {
      cout << NO << endl;
    }
  }
  return 0;
}

CODE FESTIVAL 2016 予選B : A - Signboard

問題リンク :
A: Signboard - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 略

解法 :
ループを回します。

コード :

#include<iostream>

using namespace std;

int main() {
  string s = "CODEFESTIVAL2016",t;
  getline(cin,t);
  int mini = 0;
  for(int i=0;i<(int)s.size();++i) if( s[i] != t[i] ) ++mini;
  cout << mini << endl;
  return 0;
}

LiveArchive 6503 : Golf Field

問題文 : https://icpcarchive.ecs.baylor.edu/external/65/6503.pdf

問題概要 :
２次元平面上にn個の点がある. ( 4 <= n <= 30,000 )
この中から異なる４点を選び凸包を作る.
得られる凸包の面積の最大値を求めよ.

解法 :
凸包 + キャリパー法 + 三分探索

以下の問題の完全上位互換
ncastar.hatenablog.com

解法は基本的に同じだが、
上記の問題よりも頂点数が多くなっているため愚直に２重ループを回せない
そのため２重ループの代わりにキャリパー法を使う

コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
 
using namespace std;
 
// Geo --->
 
class Point{
public:
  double x,y;
 
  Point(double x = 0,double y = 0): x(x),y(y){}
 
  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }
 
  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }
 
  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }
 
};
 
struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator <  (const Segment& s) const { return ( p2 == s.p2 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ) || ( s.p1 == p2 && s.p2 == p1 ); }
 
};
 
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
 
ostream& operator << (ostream& os,const Point& a){ return os << "(" << a.x << "," << a.y << ")"; }
 
ostream& operator << (ostream& os,const Segment& a){ return os << "( " << a.p1 << " , " << a.p2 << " )"; }
 
double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
 
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
 
double norm(Point a){ return a.x*a.x+a.y*a.y; }
 
double abs(Point a){ return sqrt(norm(a)); }
 
//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }
 
// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }
 
// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}
 
int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}
 
bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}
 
Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}
 
double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}
 
double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}
 
Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]); //同じセグメントかもよ
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}
 
Polygon andrewScan(Polygon s)
{
  Polygon u,l;
  if(s.size() < 3)return s;
 
  sort(s.begin(),s.end());
 
  u.push_back(s[0]);
  u.push_back(s[1]);
  l.push_back(s[s.size()-1]);
  l.push_back(s[s.size()-2]);
 
  for(int i=2;i<s.size();i++)
    {
      for(int n=u.size();n >= 2 && ccw(u[n-2],u[n-1],s[i]) != CLOCKWISE; n--)
    u.pop_back();
      u.push_back(s[i]);
    }
 
  for(int i=s.size()-3; i>=0 ; i--)
    {
      for(int n=l.size(); n >= 2 && ccw(l[n-2],l[n-1],s[i]) != CLOCKWISE; n--)
    l.pop_back();
      l.push_back(s[i]);
    }
 
  reverse(l.begin(),l.end());
 
  for(int i = u.size()-2; i >= 1; i--) l.push_back(u[i]);
 
  return l;
}
 
double heron(Point pa,Point pb,Point pc) {
  double a = abs(pa-pb);
  double b = abs(pb-pc);
  double c = abs(pc-pa);
  double s = ( a + b + c ) / 2.0;
  return sqrt( s * ( s - a ) * ( s - b ) * ( s - c ) );
}
 
double LT(double a,double b) { return !equals(a,b) && a < b; }
double LTE(double a,double b) { return equals(a,b) || a < b; }
// Geo <---
 
int n;
 
 
double ternarySearch(int a,int b,vector<Point> &ps){
  int nV = (int)ps.size();
  int L = 1, R = ( a > b ) ? ( ( a - b - 1 + nV ) % nV ) : ( ( ( a + nV ) - b - 1  ) % nV );
  int sp = b;
  int pL = L, pR = R;
 
  rep(_,120){
    if( LT(heron(ps[((L+R*2)/3+sp)%nV],ps[a],ps[b]),heron(ps[((L*2+R)/3+sp)%nV],ps[a],ps[b])) ) {
      R = ( L + R * 2 ) / 3;
    } else {
      L = ( L * 2 + R ) / 3;
    }
    if( R == pR && L == pL ) break;
    pR = R, pL = L;
  }
  return heron(ps[(int)(((L+R)*0.5)+sp)%nV],ps[a],ps[b]);
}
 
bool cmp_x(const Point &p,const Point &q) {
  if( p.x != q.x ) return p.x < q.x;
  return p.y < q.y;
}
 
void compute(vector<Point> &ps) {
  ps = andrewScan(ps);
  double maxi = 0.0;
  n = ps.size();
  if( n == 2 ) assert(false);
  int i = 0, j = 0;
  rep(k,n) {
    if( !cmp_x(ps[i],ps[k]) ) i = k;
    if(  cmp_x(ps[j],ps[k]) ) j = k;
  }
 
  int si = i, sj = j;
  while( i != sj || j != si ) {
    maxi = max(maxi,ternarySearch(i,j,ps)+ternarySearch(j,i,ps));
    if( cross(( ps[(i+1)%n] - ps[i] ),( ps[(j+1)%n]-ps[j])) < 0 ) {
      i = ( i + 1 ) % n;
    } else {
      j = ( j + 1 ) % n;
    }
  }
  printf("%.1f\n",maxi);
}
 
int main() {
  int T;
  while( cin >> T ) {
    while( T-- ) {
      cin >> n;
      vector<Point> ps(n);
      rep(i,n) cin >> ps[i].x >> ps[i].y;
      compute(ps);
    }
  }
  return 0;
}

SRM 694 Div1 medium : DistinguishableSetDiv1

問題概要 :
n人にm回質問をする.
人と質問にはそれぞれ0からn-1,0からm-1まで番号が割り振られている.
人iの質問jに対する回答は英大文字('A'~'Z')として表現される.
各人の各質問への回答が入力として与えられる.
全ての人を区別するためにしなければならない質問の集合は何通りあるか.

解法 :
動的計画法

区別するためにしなければならない質問の集合を数え上げるのではなく、
区別できない質問の集合を数え上げる.

異なる2人を選び、その人らを区別できない最大の質問の集合を求める.
この集合は2人が同じ回答をした質問の集合である.
このような集合から1つ要素を取り除いた集合もまた区別できない質問の集合なので、
要素を取り除くことでそこから得られる区別できない質問の集合を全て列挙する.

あとはこれを全ての異なる2人に対して行えば良い.

本番は解けてないのでwriter解を見て解いた.
本番中は「Twenty Questionsっぽい問題だな〜」と考えていたけど、全く違った残念

コード :

bool dp[1<<20];

class DistinguishableSetDiv1 {
public:
  int count(vector <string> answer) {
    int n = answer.size();
    int m = answer[0].size();
    rep(i,n) REP(j,i+1,n) {
      int state = 0;
      rep(k,m) if( answer[i][k] == answer[j][k] ) state |= (1<<k);
      dp[state] = true;
    }
    int cnt = 0;
    for(int state=((1<<m)-1);state>=0;--state) if( dp[state] ) {
	rep(i,m) if( (state>>i) & 1 ) dp[state&~(1<<i)] = true;
      }
    rep(i,(1<<m)) cnt += dp[i];
    return (1<<m)-cnt;
  }
};

SRM 694 Div1 easy : TrySail

問題概要 :
n人の生徒からなるクラスがある.
各生徒には強さがあり、それらは0以上255以下の整数として表される.

n人の生徒を3つのグループに分ける.
ただし、グループ分けを行う際に、だれも生徒が属さないようなグループが出来てはいけない.
グループの強さはそのグループに属する生徒の強さのbitwise xorをとった値とする.
このとき、3つのグループの強さの総和を最大化し、その値を返せ.

制約 :
3 <= n <= 50
0 <= 生徒の強さ <= 255

解法 :
制約を見てみると強さも生徒数も少ないので、そのまま配列を確保してDPする.

3つのグループには1から順に3まで番号が割り振られているものとする.

dp[i][j][k][l] := グループ3の最大値
i : 各グループに生徒を1人以上割り当てたかどうかをビットで表す ( 0 <= i < (1<<3) )
j : グループ1の現在の強さ ( 0 <= j < (1<<8) )
k : グループ2の現在の強さ ( 0 <= k < (1<<8) )
l : curとnext ( 0 <= l < 2 )

他の人のコードを見てみると2次元配列で解いていた人もいたでのメモリ節約できるらしい

コード :

#define MAX (1<<8)
  int dp[10][MAX][MAX][2];
  
  class TrySail {
  public:
    int get(vector <int> vec) {
      memset(dp,-1,sizeof dp);
      int n = (int)vec.size();
      dp[0][0][0][0] = 0;

      rep(i,n) {
	int cur  = i & 1;
	int next = (i+1) & 1;
	{
	  rep(j,(1<<3)) rep(k,MAX) rep(l,MAX) dp[j][k][l][next] = -1;
	}
	rep(bit,(1<<3)) {
	  rep(p1,MAX) {
	    rep(p2,MAX) {
	      if( dp[bit][p1][p2][cur] == -1 ) continue;
	      rep(sel,3) {
		int nbit = bit | (1<<sel);
		int np1 = p1;
		int np2 = p2;
		int np3 = dp[bit][p1][p2][cur];
		if( sel == 0 ) np1 = np1 ^ vec[i];
		if( sel == 1 ) np2 = np2 ^ vec[i];
		if( sel == 2 ) np3 = np3 ^ vec[i];
		dp[nbit][np1][np2][next] = max(dp[nbit][np1][np2][next],
					       np3);
	      }
	    }
	  }
	}
      }
      int maxi = 0;
      rep(j,MAX) rep(k,MAX) if( dp[(1<<3)-1][j][k][n&1] != -1 ) {
	maxi = max(maxi,dp[(1<<3)-1][j][k][n&1]+j+k);
      }
      return maxi;
    }
  };

AOJ 1314 : Matrix Calculator

問題概要 :
問題文で定義されている Matrix Calculator を実装せよ
シンタックスはBNFで与えられる

Matrix Calculator : 行列計算を行うプログラム
Matrix Calculator の機能等を適当に列挙
1. +, -, * : 行列の加算、減算、乗算
2. - : 単項演算子のマイナス
3. 行列の各要素の値は2^15(=32768)でmodをとった値であり、0以上32767以下 (負の場合は正になるまで2^15を加算し続ける)
4. 行列 * 定数 もしくは 定数 * 行列 の場合、行列内の各要素に定数を掛ける
5. 行列(1行k列の行列,1行l列の行列)はk行l列の行列を返す (行列の各要素v(i,j)は元の行列の要素w(k[i],l[j]) )
6. 行列' は転置行列

解法：
BNFに従って実装する

基本的にBNFが書いてあるときはそれに従って再帰下降型構文解析を行う
ただ、そのまま実装できない場合があるので注意
具体的には、
1. 左再帰が存在する
- 例 : program ::= assignment | program assignment
2. 何文字か先読みしないと曖昧な場合がある
- 例 : primary ::= inum | var | matrix | "(" expr ")" | indexed-primary | transposed-primary
indexed-primary ::= primary "(" expr "," expr ")"
"(" が来たときに "(" expr ")" なのか indexed-primary の "(" expr "," expr ")" なのか先読みしないとわからない

これらの対処は次の通り
1. 文法を等価で左再帰を持たない文法に変換する
- program ::= assignment | program assignment => program ::= assignment | assignment program
( その他についての具体的な変換方法は、残念ながら書けない ( 直感でやってしまった ( 左再帰　除去　あたりでぐぐるとでてくると思う それかコンパイラの本（ドラゴンブックとか　を読むとあるはず
2. 先読みする
- "(" がきたら、それが"("...")"なのか"("...","...")"なのかを判定して場合分けする
- 括弧の対応関係をもとめる方法( int cnt=0 を "(" なら +1, ")" なら -1 )をやって cnt == 1 であれば今見ている括弧の直下にある要素なので、そこに","があるようであれば "("...","...")"

あとはバグにすぐ気付けるようにassertかけまくって(※重要)実装を頑張る

コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef VVI matrix;
 
ostream& operator << (ostream &os,const matrix &mat) {
  rep(i,(int)mat.size()) {
    rep(j,(int)mat[i].size()) {
      if( j ) os << " ";
      os << mat[i][j];
    } if( i+1 != (int)mat.size() ) os << endl;
  }
  return os;
}
 
 
 
const int MOD = 32768;
 
matrix identity(int n) {
  matrix A(n,vector<int>(n,0));
  for(int i=0;i<n;i++) A[i][i] = 1;
  return A;
}
 
matrix multi(const matrix& A,const matrix& B){
  if( (int)A.size() == 1 && (int)A[0].size() == 1 ) {
    matrix C(B.size(),VI(B[0].size()));
    int coef = A[0][0];
    rep(i,(int)B.size()) {
      rep(j,(int)B[0].size()) {
        C[i][j] = B[i][j] * coef;
        C[i][j] %= MOD;
      }
    }
    return C;
  }
  if( (int)B.size() == 1 && (int)B[0].size() == 1 ) {
    matrix C(A.size(),VI(A[0].size()));
    int coef = B[0][0];
    rep(i,(int)A.size()) {
      rep(j,(int)A[0].size()) {
        C[i][j] = A[i][j] * coef;
        C[i][j] %= MOD;
      }
    }
    return C;
  }
  matrix C(A.size(),vector<int>(B[0].size()));
  for(int i=0;i<C.size();++i)
    for(int j=0;j<C[i].size();++j)
      for(int k=0;k<A[i].size();++k) {
        C[i][j] += ( A[i][k] * B[k][j] );
        while( C[i][j] < 0 ) C[i][j] += MOD;
        C[i][j] %= MOD;
      }
  return C;
}
 
matrix add(const matrix& A,const matrix& B){
  assert( A.size() == B.size() );
  matrix C(A.size(),vector<int>(A[0].size(),0));
  rep(i,(int)A.size()) {
    assert( A[i].size() == B[i].size() );
    rep(j,(int)A[0].size()) {
      C[i][j] = ( A[i][j] + B[i][j] ) % MOD;
      while( C[i][j] < 0 ) C[i][j] += MOD;
      C[i][j] %= MOD;
    }
  }
  return C;
}
 
matrix sub(const matrix& A,const matrix& B){
  assert( A.size() == B.size() );
  matrix C(A.size(),vector<int>(A[0].size(),0));
  rep(i,(int)A.size()) {
    assert( A[i].size() == B[i].size() );
    rep(j,(int)A[0].size()) {
      C[i][j] = ( A[i][j] - B[i][j] ) % MOD;
      while( C[i][j] < 0 ) C[i][j] += MOD;
      C[i][j] %= MOD;
    }
  }
  return C;
}
 
matrix neg(const matrix& A) {
  matrix B(A.size(),vector<int>(A[0].size(),0));
  rep(i,(int)A.size()) {
    rep(j,(int)A[i].size()) {
      B[i][j] = -A[i][j];
      while( B[i][j] < 0 ) B[i][j] += MOD;
      B[i][j] %= MOD;
    }
  }
  return B;
}
 
matrix transpose(const matrix& A) {
  matrix B(A[0].size(),vector<int>(A.size(),0));
  rep(i,(int)A[0].size()) {
    rep(j,(int)A.size()) {
      B[i][j] = A[j][i];
    }
  }
  return B;
}
 
matrix factor();
matrix term();
matrix expr();
matrix transposed_primary(matrix);
matrix indexed_primary(matrix);
matrix indexed_primary_and_transposed_primary(matrix);
 
map<char,matrix> buffer;
 
string context;
int ptr;
 
matrix row() {
  matrix p = expr();
  while( ptr < (int)context.size() && context[ptr] == ' ' ) {
    ++ptr;
    matrix q = expr();
    assert( p.size() == q.size() );
    rep(i,(int)p.size()) {
      rep(j,(int)q[i].size()) {
        p[i].push_back(q[i][j]);
      }
    }
  }
  return p;
}
 
matrix row_seq() {
  matrix p = row();
  while( ptr < (int)context.size() && context[ptr] == ';' ) {
    ++ptr;
    matrix q = row();
    rep(i,(int)q.size()) p.push_back(q[i]);
  }
  return p;
}
 
matrix c_matrix() {
  assert( context[ptr] == '[' );
  ++ptr;
  matrix p = row_seq();
  assert( context[ptr] == ']' );
  ++ptr;
  return p;
}
 
bool next_is_indexed_primary() {
  assert( ptr < (int)context.size() && context[ptr] == '(' );
  int i=ptr+1,cnt = 1;
  for(;i<(int)context.size();++i){
    if( context[i] == '(' ) ++cnt;
    else if( context[i] == ')' ) --cnt;
    if( cnt == 0 ) {
      ++i;
      break;
    }
  }
  if( context[i] != '(' ) return false;
  ++i,cnt = 1;
  for(;i<(int)context.size();++i) {
    if( context[i] == '(' ) ++cnt;
    else if( context[i] == ')' ) --cnt;
    if( cnt == 0 ) break;
    if( cnt == 1 && context[i] == ',' ) return true;
  }
  return false;
}
 
bool next_is_indexed_primary2() {
  int i=ptr+1,cnt = 1;
  while( i < (int)context.size() && context[i] != '(' ) ++i;
  if( i >= (int)context.size() ) return false;
  assert( context[i] == '(' );
  ++i,cnt = 1;
  for(;i<(int)context.size();++i) {
    if( context[i] == '(' ) ++cnt;
    else if( context[i] == ')' ) --cnt;
    if( cnt == 0 ) break;
    if( cnt == 1 && context[i] == ',' ) return true;
  }
  return false;
}
 
bool is_indexed_primary() {
  assert( ptr < (int)context.size() && context[ptr] == '(' );
  int i=ptr+1,cnt = 1;
  for(;i<(int)context.size();++i) {
    if( context[i] == '(' ) ++cnt;
    else if( context[i] == ')' ) --cnt;
    if( cnt == 0 ) break;
    if( cnt == 1 && context[i] == ',' ) return true;
  }
  return false;
}
 
matrix primary() {
  if( context[ptr] == '(' && !next_is_indexed_primary() ) {
    ++ptr;
    matrix p = expr();
    assert( ptr < (int)context.size() );
    assert( context[ptr] == ')' );
    ++ptr;
    return indexed_primary_and_transposed_primary(p);
  } else if( context[ptr] == '(' ) {
    ++ptr;
    matrix p = expr();
    assert( context[ptr] == ')' );
    ++ptr;
    return indexed_primary_and_transposed_primary(indexed_primary(p));
  }
 
  if( context[ptr] == '[' ) {
    return indexed_primary_and_transposed_primary(c_matrix());
  }
  if( 'A' <= context[ptr] && context[ptr] <= 'Z' ) {
    char var = context[ptr++];
    assert( buffer.count(var) );
    return indexed_primary_and_transposed_primary(buffer[var]);
  }
  if( '0' <= context[ptr] && context[ptr] <= '9' ) {
    int v = 0;
    while( ptr < (int)context.size() && '0' <= context[ptr] && context[ptr] <= '9' ) {
      v *= 10;
      v += ( context[ptr++] - '0' );
    }
    return indexed_primary_and_transposed_primary(matrix(1,vector<int>(1,v)));
  }
  assert(false);
}
 
matrix indexed_primary_and_transposed_primary(matrix p) {
  while( ptr < (int)context.size() && ( context[ptr] == '\'' || ( context[ptr] == '(' && is_indexed_primary() ) ) ) {
    char opr = context[ptr];
    if( opr == '\'' ) {
      p = transposed_primary(p);
    } else {
      p = indexed_primary(p);
    }
  }
  return p;
}
 
matrix indexed_primary(matrix p) {
  if( ptr < (int)context.size() && context[ptr] == '(' ) {
    if( is_indexed_primary() ) {
      ++ptr;
      matrix k = expr();
      assert( ptr < (int)context.size() && context[ptr] == ',' );
      ++ptr;
      matrix l = expr();
      assert( ptr < (int)context.size() && context[ptr] == ')' );
      ++ptr;
      assert( (int)k.size() == 1 );
      assert( (int)l.size() == 1 );
      matrix np = matrix((int)k[0].size(),VI((int)l[0].size()));
      rep(i,(int)k[0].size()) {
        int y = k[0][i]-1;
        rep(j,(int)l[0].size()) {
          int x = l[0][j]-1;
          np[i][j] = p[y][x];
        }
      }
      p = np;
    }
  }
  return p;
}
 
matrix transposed_primary(matrix p) {
  if( ptr < (int)context.size() && context[ptr] == '\'' ) {
    int cnt = 0;
    while( ptr < (int)context.size() && context[ptr] == '\'' ) {
      ++ptr, ++cnt;
    }
    if( cnt & 1 ) {
      p = transpose(p);
    }
  }
  return p;
}
 
matrix factor() {
  assert( ptr < (int)context.size() );
  if( context[ptr] == '-' ) {
    int cnt = 0;
    while( context[ptr] == '-' ) {
      ++cnt, ++ptr;
    }
    matrix p = factor();
    if( cnt & 1 ) {
      p = neg(p);
    }
    return p;
  }
  return primary();
}
 
matrix term() {
  matrix p = factor();
  while( ptr < (int)context.size() && context[ptr] == '*' ) {
    ++ptr;
    matrix q = factor();
    p = multi(p,q);
  }
  return p;
}
 
matrix expr(){
  matrix p = term();
  while( ptr < (int)context.size() && ( context[ptr] == '+' || context[ptr] == '-' ) ) {
    char opr = context[ptr++];
    matrix q = term();
    if( opr == '+' ) {
      p = add(p,q);
    } else if( opr == '-' ) {
      p = sub(p,q);
    }
  }
  return p;
}
 
void assignment() {
  assert( 0 <= ptr && ptr < (int)context.size() );
  char var = context[ptr++];
  assert( 0 <= ptr && ptr < (int)context.size() );
  assert( context[ptr] == '=' );
  ++ptr;
  matrix mat = expr();
  assert( 0 <= ptr && ptr < (int)context.size() );
  assert( context[ptr] == '.' );
  ++ptr;
  buffer[var] = mat;
  cout << mat << endl;
}
 
 
void exec() {
  ptr = 0;
  assignment();
}
 
int main() {
  int n;
  while( cin >> n, n ) {
    cin.ignore();
    buffer.clear();
    rep(_,n) {
      getline(cin,context);
      exec();
    }
    puts("-----");
  }
  return 0;
}

Graphviz でノード名にプライムをつけたかった

Graphvizでノード名にプライムをつけようとしたらエラーが出た

ググっても解決策がでてこなかったのでメモ

解決策 : ノード名を"で囲む

ダメな例 :

digraph g {

node0' [color="#ffffff", fontcolor="#ffffff"];
node1', node2->;

}

良い例 :

digraph g {

"node0'" [color="#ffffff", fontcolor="#ffffff"];
"node1'", "node2->";

}