Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2009-06-24

SRM443

| 12:07 | はてなブックマーク -  SRM443 - cafelier@SRM

SRM443 の成績・ソース (要ログイン) : AC/TLE/- : おもしろい問題セットだった

300開く

  • 300, 600, 1000 だったので 600 難しそうと思ってヒヨりました…
  • 『ちょうど接したり交わったりはしてないけど重なってることはある円が2次元平面上にばらまかれてます。ある点からある点まで行くのに円周を最小で何回越えれば行けますか』
  • えーと最小と言えばダイクストラ、というか幅優先か。
    • 300点だから多少ハードなコード書くハメになるんだろうから、そのくらいのコードは書くべきかな。
    • あ、グラフじゃなくてツリーになるから共通の一番下の祖先(LCA)まで上って降りてくるのが最短パスに決まってる
    • それでいこう
  • 領域と領域が先祖関係は否かは円同士の包含関係で決まる
  • 50領域しかないから、直接の親かどうかは↑を二重ループで回せば求まる
  • …とやってツリーを作ったら、ループ回してそれぞれの祖先リスト作って重なってる部分を除いたら最短路!
  • できた。通った。
  • submit!
    • submitした瞬間に気づいたんだけど、ツリーとかLCAとか考えなくても、「始点を含んでる円の数 + 終点を含んでる円の数 - 両方含んでる円の数*2」でいいのでは…俺はアホか…

600開く

  • 問題文短い!すばらしい
  • 『A個の0とB個の1があります、1回の操作でちょうどK個の数字のビット反転できます。全部1にするのに必要な操作は何回』
    • A,B,Kは100000まで。
  • えーと単純に幅優先探索すると
    • A+B=200000状態あって、それぞれからK通りの反転の仕方があるから、200億。死亡。Kが大きすぎると逆に手が減るけど、それでも√K手くらいを20万にかけたら十分死ねるなあ
  • 0の個数がKの倍数だったらひたすら0を反転していけば終わるからA/K回だなあ。
  • それ以外の場合もなにか最寄りのKの倍数に行ってそっからKずつ減らすパターンに必ず落ちるはず。最寄りとは限らないか。
    • で、どうやって最寄り?のKの倍数に行く最短操作を求めるのか…
  • Aが奇数でKが偶数だったら絶対無理だよね。
    • AもBもKも偶数だったら全部2で割っても同じ答えになりそうな気がする
    • とかやって次々減らしてって互いに素に持ち込むとなんかGCDになったり
    • …わからん。
  • うーん
  • 残り25分

1000開く

  • 600より1000が簡単だったりするのでは
  • まとめると『9ノード以下のグラフに重さ9以下の有向edgeがたくさん張られてる時に、min以上max以下のパスの総数をmodなんか大きい数で数えてね』
    • minとmaxは10億くらい
  • modなんとかということは探索ではなくてDPとかで、minとmaxが10億ということは下から律儀に埋めるのは無理で行列乗算とかだ。
  • なんか9x9か81x81の遷移行列組んでどうにか…

  • うーんまとまらない
  • 残り15分。考えまとまってもちゃんとコーディングするの無理だなあ。600のコードなら10分あれば書けそう。

再度600

  • まあしかし思いつかないので、
    • 幅優先の遅いコード書いておいて時間のかかるケースをみつけておき、あとで撃墜用に使う
  • という戦略で行く。
  • まあ5分で書ける。100000,100000,19999 とかで盛大に時間がかかって終わらない。よしこれで撃墜する。
  • さっきの、Kの倍数ならA/K回で行ける、というのを下端にして枝刈り入れるとどうだろう。
  • 入れてみた。
    • …いろいろ試してみても、手元で最悪1.4secくらいで通る…
    • 出しちゃおっかなー。行けたりしないかなー
    • システムテストは通らなくても仕方ないけど、そうそう撃墜できないはずだから…
    • そうだ!他人にunsuccessfully challengedの山を築かせる嫌がらせを!
  • 出しちゃった
    • 撃墜タイムは突破、システムテストで死亡。そんな甘くはないよね、やっぱり

撃墜タイム

  • 100000,100000,19999 で2人撃墜。
    • 二人ともただのBFSだったんだけど、片方自分のスタイルと違うやり方だったので読むのに時間がかかった。

感想

  • 狙って撃墜できると満足してしまう
  • 満足してないでまずはLv2問題を確実に解けるようにしなさい自分

SRM443 300

| 12:22 | はてなブックマーク - SRM443 300 - cafelier@SRM

うむ

class CirclesCountry { public:
  int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) 
  {
    int d = 0;
    for(int i=0; i<X.size(); ++i)
      d += hypot(X[i]-x1, Y[i]-y1)<R[i] ^ hypot(X[i]-x2, Y[i]-y2)<R[i];
    return d;
  }
};

SRM443 600

| 14:14 | はてなブックマーク - SRM443 600 - cafelier@SRM

tanakhことhaskell_masterさんの解説を参考に。なるほどなあ。ほとんど普通のBFSのコードのまま綺麗に書ける。かっこいい。全く別のアプローチとしてLayCurseさんの(要ログイン)が更にかっこよすぎる。useがその式になる理由が理解できてないのでちゃんと考えなくては…。

class BinaryFlips { public:
  int minimalMoves(int A, int B, int K) 
  {
    vector<int> visitedUpto(A+B+1, -1);
    visitedUpto[B] = B;

    // Breadth-first search from the initial state (A,B)
    queue< pair<int,int> > q;
    q.push( make_pair(B, 0) );
    while( !q.empty() )
    {
      // pop state (a,b)
      int b=q.front().first, a=A+B-b, step=q.front().second; q.pop();

      // if (a,b) == (0,A+B), done
      if( b == A+B )
        return step;

      // for all possible next values (nb) of b...
      int nb_min = abs(b-K), nb_max = A+B-abs(a-K);
      for(int nb=nb_min; nb<=nb_max; nb+=2)
        if( visitedUpto[nb] == -1 )
        {
          // if not visited, push the new state to the queue
          q.push( make_pair(nb, step+1) );
          visitedUpto[nb] = nb_max;
        }
        else
        {
          // if visited, skip it
          int nb2 = visitedUpto[nb];
          visitedUpto[nb] = max(visitedUpto[nb], nb_max);
          nb = nb2;
        }
    }
    return -1;
  }
};

chenyukunchenyukun2009/06/28 03:36Hi:
I want to learn more about SRM 443, can you give me you email address?

cafeliercafelier2009/07/01 11:45Hi, you can send me a message from my topcoder profile page: http://www.topcoder.com/tc?module=MemberProfile&cr=22758647

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20090624
 | 

presented by cafelier/k.inaba under CC0