cafelier@SRM

CodeCraft 2010

その他 | 02:16 |

CodeCraft 2010 : ooo-oo-o, 7位。Username は catbat

Temperature

• Small: A～Nの全ての温度を定義どおりに変換してみるだけ
• Large: 行きはCで割って帰りはBで割るので、元に戻る戻らない分布は長くともlcm(C,B)でループしているはず。ということでNをlcm(C,B)で割って計算…したらそれでもTLE。ダメ元でlcm(C,B)ではなくCで割って計算したら通った。いいのかそれで。なんでだろう。

#include <iostream>
using namespace std;
typedef long long LL;

int naiveCount(LL A, LL B, LL C, LL from, LL to)
{
   int cnt = 0;
   for(LL D=from; D<=to; ++D)
   {
      LL G  = ((D-A)*B + C/2)/C;
      LL D2 = (G*C + B/2)/B + A;
      if( D2 == D )
         ++cnt;
   }
   return cnt;
}

int main()
{
   for(LL A,B,C,N; cin>>A>>B>>C>>N; )
   {
      LL LOOP = C; //lcm(C,B);

      LL Z = (N+1-A) % LOOP;
      LL X = (N+1-A) / LOOP;
      LL a = naiveCount(A,B,C, A, A+Z-1);
      LL b = naiveCount(A,B,C, A+Z, A+Z+LOOP-1);
      cout << a+b*X << endl;
   }
}

Lucky Draw

• ありうるパターンは
  • AをN回
  • Aを(i=0～N-1)回 + Bを(1～N-i)回
  • Aを(i=0～N-1)回 + C
• しかない。
• Small: 計算するだけ。A^N + Σ(A^i B (N-i)) + Σ(A^i C)
• Large: Nが大きいので高速化が必要
  • A^N は定番の、A^1, A^2, A^4, A^8, ... を計算していってNのバイナリ表記でビットが立っているところを掛けていく奴
  • Σ_{i=0}^{N-1} A^i は、

(A 0)^i (1)
(0 1)   (0)

• この行列積の結果は (A^i 0) になるので、ちょっと変えて

(A 0)^i (1)
(1 1)   (0)

• とすると、結果が (A^N ΣA^i) になる。
• というわけで、この (A 0-1 1) 行列のN乗を同じように高速ベキ乗で求めれば終わり。
• Σ(A^i (N-i)) は、
  • (Σ_{i=0}^0 A^i)+(Σ_{i=0}^1 A^i)+...+(Σ_{i=0}^{N-1} A^i)
  • に等しいので、要するに、(ΣA^i)の更に総和をとった感じ。
• というわけで、行列の次元をさらに一つ増やして

(A 0 0)^N (1)
(1 1 0)   (0)
(0 1 1)   (0)

• を高速ベキ乗で求めれば求まる。

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;

static const LL MODVAL = 10000;

LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
LL POW(LL x, LL e) {
   LL v = 1;
   for(;e;x=MUL(x,x),e>>=1)
      if(e&1)
         v = MUL(v, x);
   return v;
}

vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b)
{
   int N = a.size();
   vector< vector<LL> > c(N, vector<LL>(N));
   for(int i=0; i<N; ++i)
   for(int j=0; j<N; ++j)
   for(int k=0; k<N; ++k)
      c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j]));
   return c;
}

LL GEO(LL x_, LL e) {
   // x^0 + x^1 + ... x^e-1

   // (x 0)e (1)
   // (1 1)  (0)
   vector< vector<LL> > v(2, vector<LL>(2));
   vector< vector<LL> > x(2, vector<LL>(2));
   v[0][0] = v[1][1] = 1;
   x[0][0] = x_; x[0][1] = 0;
   x[1][0] = 1 ; x[1][1] = 1;
   for(;e;x=MATMUL(x,x),e>>=1)
      if(e&1)
         v = MATMUL(v, x);
   return v[1][0];
}

LL HYP(LL x_, LL e) {
   // e x^0 + (e-1) x^1 + ... + 1 x^e-1
   //=
   // GEO(x,1) + GEO(x,2) + ... + GEO(x,e)

   // (x 0 0)e (1)
   // (1 1 0)  (0)
   // (0 1 1)  (0)

   vector< vector<LL> > v(3, vector<LL>(3));
   vector< vector<LL> > x(3, vector<LL>(3));
   v[0][0] = v[1][1] = v[2][2] = 1;
   x[0][0] = x_; x[0][1] = 0; x[0][2] = 0;
   x[1][0] = 1 ; x[1][1] = 1; x[1][2] = 0;
   x[2][0] = 0 ; x[2][1] = 1; x[2][2] = 1;
   e++;
   for(;e;x=MATMUL(x,x),e>>=1)
      if(e&1)
         v = MATMUL(v, x);
   return v[2][0];
}

int main()
{
   int nCase; cin>>nCase;
   while( nCase-- )
   {
      LL A, B, C, N;
      cin >> A >> B >> C >> N;

      LL total =
         ADD( POW(A, N),
              ADD( MUL(C, GEO(A,N)),
                   MUL(B, HYP(A,N)) )
         );

      cerr << total << endl;
   }
}

A Simple Math Problem

• ３次方程式の解と係数の関係から、
  • x1+x2+x3 = 0
  • x1^2 + x2^2 + x3^2 = -2a
• になっている。3乗以上は x^3 = -ax-b なので、
• 次数を2ずつ落とせるから2次以下になるまで落とせばよい。

import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
   public static void main(String[] arg) throws Exception
   {
      StreamTokenizer tok =
         new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

      while( tok.nextToken() != StreamTokenizer.TT_EOF )
      {
         int a = (int)tok.nval; tok.nextToken();
         int b = (int)tok.nval; tok.nextToken();
         int n = (int)tok.nval;

         int last = 2>n ? 2 : n;
         BigInteger[] poly = new BigInteger[last+1];
         for(int i=0; i<=last; ++i)
            poly[i] = BigInteger.ZERO;
         poly[n] = BigInteger.ONE;

         while( last >= 3 )
         {
            poly[last-3] = poly[last-3].subtract( poly[last].multiply(BigInteger.valueOf(b)) );
            poly[last-2] = poly[last-2].subtract( poly[last].multiply(BigInteger.valueOf(a)) );
            --last;
         }

         BigInteger v = poly[0].multiply(BigInteger.valueOf(3)).subtract(
            poly[2].multiply( BigInteger.valueOf(2) ).multiply( BigInteger.valueOf(a) )
         );
         System.out.println(v);
      }
   }
}

• long long で大丈夫かな → WA → ダメか。ここはJavaでBigIntegerだ
• → やっぱりWA → あれ？あ、凡ミスしてた → 修正。通った
• ということをやっていたので、BigInteger必要なのかlong longでいいのかは不明

Concatenated Integers

• 和を取っている途中で桁が変わると面倒くさいので、
• どうせ最高で19桁しかないのだから
• 1桁の部分、2桁の部分、... と分割して計算する

• 桁数が同じk桁の部分は、a @ a+1 @ a+2 @ ... @ a+n という結合で、
• これは数式で書くと Σ (a+i)*10^(k(n-i))
• この問題、Lucky Draw でやったところだ！

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;

LL MODVAL;

LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
LL POW(LL x, LL e) {
   LL v = 1;
   for(;e;x=MUL(x,x),e>>=1)
      if(e&1)
         v = MUL(v, x);
   return v;
}

vector< vector<LL> > MATMUL(vector< vector<LL> >& a, vector< vector<LL> >& b)
{
   int N = a.size();
   vector< vector<LL> > c(N, vector<LL>(N));
   for(int i=0; i<N; ++i)
   for(int j=0; j<N; ++j)
   for(int k=0; k<N; ++k)
      c[i][j] = ADD(c[i][j], MUL(a[i][k],b[k][j]));
   return c;
}

LL GEO(LL x_, LL e) {
   vector< vector<LL> > v(2, vector<LL>(2));
   vector< vector<LL> > x(2, vector<LL>(2));
   v[0][0] = v[1][1] = 1;
   x[0][0] = x_; x[0][1] = 0;
   x[1][0] = 1 ; x[1][1] = 1;
   for(;e;x=MATMUL(x,x),e>>=1)
      if(e&1)
         v = MATMUL(v, x);
   return v[1][0];
}

LL HYP(LL x_, LL e) {
   vector< vector<LL> > v(3, vector<LL>(3));
   vector< vector<LL> > x(3, vector<LL>(3));
   v[0][0] = v[1][1] = v[2][2] = 1;
   x[0][0] = x_; x[0][1] = 0; x[0][2] = 0;
   x[1][0] = 1 ; x[1][1] = 1; x[1][2] = 0;
   x[2][0] = 0 ; x[2][1] = 1; x[2][2] = 1;
   e++;
   for(;e;x=MATMUL(x,x),e>>=1)
      if(e&1)
         v = MATMUL(v, x);
   return v[2][0];
}

LL countSame( LL a, LL b, LL k, LL v )
{
   LL tk = POW(10,k);

   return ADD(
      MUL(v, POW(tk, b-a+1)),
      ADD(
         MUL(a%MODVAL, GEO(tk, b-a+1)),
         SUB(HYP(tk, b-a+1), GEO(tk,b-a+1))
      )
   );
}

int main()
{
   for(LL a,b,p; cin>>a>>b>>p; )
   {
      MODVAL = p;

      LL v = 0;

      LL k  = 1;
      LL lo = 1;
      unsigned long long hi = 10;
      while( k <= 19 )
      {
         if( a<hi && lo<=b )
            v = countSame( max(a,lo), min<unsigned long long>(b,hi-1), k, v ); 

         k  += 1;
         lo *= 10;
         hi *= 10;
      }

      cerr << v << endl;
   }
}

Points on Circle

• Temperature-small の次に解法まで思いついて取りかかったのがこれだったんですが、全然バグが取れずひたすら苦戦してしまいました。
  • 主に3点に外接する円の中心を求める式を全然出せなくて死んでいたorz

• 3点選ぶ → その3点全部通る円が一意に定まる → それに乗ってる点の個数を数える
• というナイーブな方法だと、O(N^4) になってしまうので無理。

• 2点(i,j)選ぶ
• → その他の各点(k)に対し、i,j,kを通る円の中心c[k]を求める - → 例えばc[k1]=c[k2]=c[k3]になったらi,j,k1,k2,k3を通る円があるということなので、5点通る。
• という感じで、c[k] が何個重なってるかを数えればよい
• sortして順に見ていくとかすれば、全体で O(N^3 log N)

• N=200 はこれで通る
• N=400 は通らなかった。絶妙なバランスだ…
  • c[k] として円の中心座標(x,y)を持つのではなく、xだけを持つように変更
    • どうせi,jの二等分線の上にあるので、どっちか片方だけでもう片方は決まる
    • 二等分線がx軸に垂直なときは、yだけを持つ
  • これでも答え合わない…
  • 精度の問題っぽい
  • 二等分線の傾きが45度を超えているかいないかで、xとyのどちらを持つか決めてみる
  • 通った

#include <iostream>
#include <cmath>
#include <complex>
#include <algorithm>
using namespace std;
typedef complex<double> CMP;

int solve( const vector<CMP>& p )
{
   const int N = p.size();

   int best = 2;
   for(int i=0; i<N; ++i)
      for(int j=i+1; j<N; ++j)
      {
         CMP A = p[i];
         CMP B = p[j];
         double na = norm(A);
         double nb = norm(B);
         bool hor = (abs(sin(arg(B-A))) < 0.5);

         double Xs[401];
         int XsN = 0;
         for(int k=j+1; k<N; ++k)
         {
            CMP C = p[k];

            double D =
               2 * (A.real()*(B.imag()-C.imag()) +B.real()*(C.imag()-A.imag())
                   +C.real()*(A.imag()-B.imag()));
            if( abs(D)<1e-20 )
               continue;

            double nc = norm(C);

            double Xx =
               na*(B.imag()-C.imag()) + nb*(C.imag()-A.imag()) + nc*(A.imag()-B.imag());
            double Xy =
               na*(C.real()-B.real()) + nb*(A.real()-C.real()) + nc*(B.real()-A.real());
            Xs[XsN++] = (hor ? Xy : Xx)/D;
         }

         sort(Xs+0, Xs+XsN);

         int runLength=0;
         for(int x=0; x<XsN; ++x) {
            if( x>0 && Xs[x]-Xs[x-1]<1e-9 )
               ++runLength;
            else
               runLength = 1;
            best = max(best, 2+runLength);
         }
      }
   return best;
}

int main()
{
   int nCase; cin>>nCase;
   while( nCase-- )
   {
      vector<CMP> v;

      int N; cin >> N;
      while( N-- )
      {
         double x, y; cin >> x >> y;
         v.push_back( CMP(x,y) );
      }
      cout << solve(v) << endl;
   }
}

Triangular Fields

• これも最初から最後まで長々と苦戦
• キャンディー10万個、三角形10万個なので、全体全で計算するのは当然無理

• キャンディーの凸包を計算する
• 凸包の原点側に出っ張っているところの頂点だけを包含判定すれば十分。他の点を含む三角形なら必ずこいつらのどれかを含んでいるから。
  • さらに、三角形の斜辺の角度が a 度なら、
  • 凸包の辺の傾きがa度をちょうどまたぐ所にある頂点だけ包含判定すれば十分。

• まとめると、象限毎に凸包む計算 → 三角形が来るたびに角度で二分探索して判定対象頂点１つを取得 → 包含判定

#include <iostream>
#include <cmath>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
typedef complex<double> CMP;

double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }

int ccw(const CMP& a, CMP b, CMP c) {
   b -= a; c -= a;
   if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
   if( outer_prod(b,c) < 0 ) return -1; // clockwise
   if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line
   if( norm(b) < norm(c) )   return -2; // a--b--c on line
   return 0;
}

bool byX( const CMP& a, const CMP& b ) {
   if( a.real() != b.real() )
      return a.real() < b.real();
   return a.imag() < b.imag();
}

vector<CMP> convex_hull( vector<CMP> p )
{
   #define IS_RIGHT <0   // skip on-line verts
   //#define IS_RIGHT ==-1 // take all

   sort(p.begin(), p.end(), &byX);

   vector<CMP> ans;
   for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right
      while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
         ans.pop_back();
   if( ans.size() == p.size() )
      return ans;
   for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left
      while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
         ans.pop_back();
   ans.pop_back();
   return ans;
}

inline bool is_in( const CMP& p, const CMP& q0, const CMP& q1 )
{
   return arg(p-q0) > arg(q1-q0);
}

int main()
{
   int nCase; cin>>nCase;
   while( nCase-- )
   {
      int N, M; cin >> N >> M;

      vector<CMP> v[5];
      for(int i=0; i<N; ++i)
      {
         double x, y; cin >> x >> y;
         if(x>0&&y>0) v[1].push_back( CMP(x,y) );
         if(x<0&&y>0) v[2].push_back( CMP(-x,y) );
         if(x<0&&y<0) v[3].push_back( CMP(-x,-y) );
         if(x>0&&y<0) v[4].push_back( CMP(x,-y) );
      }

      vector<double> a[5];
      vector<CMP>    r[5];
      for(int k=1; k<=4; ++k)
         if( v[k].size() >= 3 )
         {
            v[k] = convex_hull( v[k] );
            v[k].push_back( v[k][0] );
            a[k].assign(1, 0);
            r[k].assign(1, v[k][0]);

            for(int i=0; v[k][i].imag()>v[k][i+1].imag(); ++i) {
               double a0 = arg( v[k][i] - v[k][i+1] );
               a[k].push_back(a0);
               r[k].push_back(v[k][i+1]);

               if( v[k][i+1].imag() <= v[k][i+2].imag() ) {
                  a[k].push_back( 1e+300 );
                  r[k].push_back( v[k][i+1] );
               }
            }
         }

      while( M-- )
      {
         double x0,y0,x1,y1;
         cin >> x0 >> y0 >> x1 >> y1;
         double x = x0==0 ? x1 : x0;
         double y = y0==0 ? y1 : y0;

         if( x==0 || y==0 ) {
            cout << "N" << endl;
            continue;
         }

         int k = -999999;
         if(x>0&&y>0) k=1;
         if(x<0&&y>0) k=2;
         if(x<0&&y<0) k=3;
         if(x>0&&y<0) k=4;

         x = abs(x);
         y = abs(y);

         CMP q0(x,0);
         CMP q1(0,y);

         if( v[k].size() <= 2 )
         {
            bool in = false;
            for(int i=0; i!=v[k].size(); ++i)
               if( is_in(v[k][i], q0, q1) )
                  in = true;
            cout << (in ? "Y" : "N") << endl;
         }
         else
         {
            double ag = arg(q1-q0);

            vector<double>::iterator it = lower_bound( a[k].begin(), a[k].end(), ag );
            --it;
            CMP p = r[k][it - a[k].begin()];
            cout << (is_in(p, q0, q1) ? "Y" : "N") << endl;
         }
      }
   }
}

Simple Subsequences

• 解けてない
• そんなに難しくは見えないのだけど問題文の出来が良くなくて意味が取りづらい
• たぶんわりと普通にDP

Weighing Scale

• 解けてない
• まったくわからないのだけど、かなり面白い設定の問題。
• 腕に覚えのある方は是非解いてみて下さい！