cafelier@SRM

SRM436

SRM | 22:18 |

SRM436 の成績・ソース (要ログイン) : AC/AC/- : グーグルパワーで解けなかった

500開く

• 『500×500の2次元マップに通れないマス(壁)が何個かある。できるだけ曲がる回数を少なく左上から右下まで行くには』

• 左上から幅優先探索するだけじゃなかろうか
  • あいだに壁がなくてxかy座標が同じマスどうしは1ステップで行けるというグラフ
  • 行って戻る手を2ステップでも行けると数えてしまうのは厳密には間違いだけど、これは元々1ステップで行けるはずなのでそれより多いところで変なのが出ても構わない
  • 500×500マスそれぞれで最悪4方向計1000マス試すO(N^3)。
    • 2億5000万くらい軽いから行けるよたぶん… O(4*N^2) でも書けそうだけど面倒い。だるい

• 書いた
  • サンプル通った
  • 500×500で壁が一個もない奴（自分の探索ルーチンだとこれが最悪のはず）で手元のマシンで2.5秒。これは経験的にTopCoderなら問題ないレベル。OkOk。

250開く

• Division Summary 見るかんじ瞬殺してる人数少ないので手間かかっていい系だ
• 『x軸上に建物が並んでて、heights[i]はx座標iに高さheights[i]の建物があることを意味する。他の建物が(隠されずに)見える数が一番大きい建物から見える数は何個』

• 建物は50個までなので、50^3 で見える数普通に数えれば十分。
  • 建物Cが建物Aから建物Bを隠してるかどうかの判定が…
  • AとCを結ぶ線分の上にCの頭が出ているかどうかだから…
  • 線分の式たてて不等式。適当に係数書ければ全部整数の範囲だ

• できた。サンプル通った。OK

1000開く

• 『60000要素のベクトルXとYがあります。Xを適当にrotateして内積を最大にしてください。ベクトルの要素は0～99の整数』

• 60000通りしかずらしかたはないけど、毎回内積を求めると60000^2。しんどい

• 1個rotateしたときの内積の変化を定数とかlog nで求められたりしない？
  • 差分の式は…全然だめだ。

• 0～99というのが怪しい。実は要素の値でグループ化すると…
  • グループ化しても結局rotateするときに元の位置情報まで必要になるから意味ないよね

• 要は内積とかrotateって行列乗算の一種だな。
• なんかべき乗早くする的テクニックで速くは…
  • ならない

• いや待て
  • 行列乗算という考えは行けそうだ。
  • 要は、xのrotateのしかたを全部並べた行列とyの内積でできるベクトルの、要素の最大値を求めればいい
  • xのrotateを全部並べた行列って、かなり特殊な形をしている
  • この前、連立方程式が速く解ける テプリッツ行列 というのを聞いたけど、これになってる！
  • Wikipediaにベクトルとの乗算O(n log n)って書いてある！キタコレ！

• ぐぐった
  • テプリッツ行列のさらに特殊例になってるらしい。
  • xとyをFFTして、要素毎に積を取って、逆FFTするとあら不思議、欲しい積がでるらしい。
    • すげー
  • でもFFTってライブラリ化してない。うわー書けるかな。自信ない。
    • 長さが 2^n じゃなければ考えればなんとかなるか…
    • でもそうとは限らんよな…
  • まあとりあえず、いつもお世話になっている こちら にFFTがあったので拝借して2^nの場合で実験…

• あれー微妙に値が合わない
  • そりゃそうだ 2^n じゃない場合が
  • xの方に0増やして、yの方はcircularに増やして2^nに長さを揃えればいいような気がする
• あれーやっぱり値が合わない
  • というか元々4個の時でもあってない
  • なぜだ
  • わからん
  • 時間切れ

感想

• やっぱりFFTであってるみたいだなあ。
• 応用力がなさすぎです。
• 特殊な形の行列の演算はひととおりチェックしといたら便利かも
• Psyhoさんのソース(要ログイン) かっこよすぎる。さらっとこれが書けるプログラマになりたい

SRM436 1000

あとで | 12:28 |

通った。そうかどっちか逆転しないと

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <complex>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

CMP tmp[65536*2];

template<int F>
void fft_impl( CMP a[], int n, int stride = 1 )
{
  if( n > 1 )
  {
    CMP *ev=a, *od=a+stride;
    int s2=stride*2, n2=n/2;

    fft_impl<F>( ev, n2, s2 );
    fft_impl<F>( od, n2, s2 );

    for(int i=0; i<n; ++i) tmp[i] = ev[i%n2*s2] + od[i%n2*s2]*polar(1.0, F*2*M_PI*i/n);
    for(int i=0; i<n; ++i) a[i*stride] = tmp[i];
  }
}

void fft( vector<CMP>& a )
{
  fft_impl<+1>(&a[0], a.size());
}

void ifft( vector<CMP>& a )
{
  fft_impl<-1>(&a[0], a.size());
  for(int i=0; i<a.size(); ++i)
    a[i] /= a.size();
}

class CircularShifts {
public:
  int maxScore(int N, int Z0, int A, int B, int M) 
  {
    // input
    LL X[60000], Y[60000], Z=Z0%M;
    for(int i=0; i<N+N; ++i)
    {
      (i<N ? X[i] : Y[i-N]) = Z % 100;
      Z = (Z*A+B) % M;
    }

    // solve
    int NN = 1;
    while( NN < N*2 ) NN*=2;

    vector<CMP> CX(NN), CY(NN), CZ(NN);
    for(int i=0; i<N; ++i)
      CX[i]=CX[i+N]=X[N-i-1], CY[i]=Y[i];

    fft(CX);
    fft(CY);
    transform( CX.begin(), CX.end(), CY.begin(), CZ.begin(), multiplies<CMP>() );
    ifft(CZ);

    double m = 0;
    for(int i=0; i<NN; ++i)
      m = max(m, CZ[i].real());
    return int(m+0.5);
  }
};