TopCoder 裏Onsiteに行ってきた

TopCoder 裏Onsite in Japan (@ベローチェ 新橋四丁目店 )

同じSRMに参加する学生向けのイベントがヒカリエで開催されていて、それを表Onsiteとしたらこちらは裏Onsiteということで。

今回のSRMは第555回。というかSRMに参加するのは久しぶり。
最近Pythonコードの読み書きが多いのでC++での競技は良い気分転換*1。

SRM555 registered (at ベローチェ新橋四丁目店) atnd.org/events/31173 twitter.com/naoya_t/status…

— naoya tさん (@naoya_t) 9月 7, 2012

↑今回はDeNAさんがスポンサーになっていて、登録時にこんな質問をされる。
オンサイトイベントを学生限定で開催してる事から推測して社会人は対象外だと思うよ

レーティングが青方偏移しそうな位に久しぶり #srm555

— naoya tさん (@naoya_t) 9月 7, 2012

Easy (255): CuttingBitString

• 5^n を2進表現した文字列を予め用意

$ gosh -usrfi-1
gosh> (map string-length (map (cut format "~b" <>) (map (^x (expt 5 x)) (iota 30))))
(1 3 5 7 10 12 14 17 19 21 24 26 28 31 33 35 38 40 42 45 47 49 52 54 56 59 61 63 66 68)
gosh> (map (cut format "~b" <>) (map (^x (expt 5 x)) (iota 22)))
("1" "101" "11001" "1111101" "1001110001" "110000110101" "11110100001001" "10011000100101101" "1011111010111100001" "111011100110101100101" "100101010000001011111001" "10111010010000111011011101" "1110100011010100101001010001" "1001000110000100111001110010101" "101101011110011000100000111101001" "11100011010111111010100100110001101" "10001110000110111100100110111111000001" "1011000110100010101111000010111011000101" "110111100000101101101011001110100111011001" "100010101100011100100011000001001000100111101" "10101101011110001110101111000101101011000110001" "1101100011010111001001101011011100010111011110101")

• submitしようとしたら30%ルールに引っかかるけど良いかと何度も聞かれた。要らないコード入れてないはずだけど最近ルール変わったのかなとか悩んだ
  • 2進表現の文字列配列をクラスの外に（グローバルで）置いてたのが原因＞＜
  • 甚だしい時間ロス
• でもまあpassed; 153.52points

#include <iostream>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define sz(a)  int((a).size())
#define found(s,e)  ((s).find(e)!=(s).end())

class CuttingBitString {
 public:
  char s[51];
  int ls;

  map<int,int> mm;

  int sub(int b, int j) {
    static const char* bs[22] = {
  "1",
  "101", "11001", "1111101", "1001110001", "110000110101",
  "11110100001001", "10011000100101101", "1011111010111100001",
  "111011100110101100101", "100101010000001011111001",
  "10111010010000111011011101", "1110100011010100101001010001",//13
  "1001000110000100111001110010101", "101101011110011000100000111101001",
  "11100011010111111010100100110001101", "10001110000110111100100110111111000001",
  "1011000110100010101111000010111011000101",
  "110111100000101101101011001110100111011001",
  "100010101100011100100011000001001000100111101",//20
  "10101101011110001110101111000101101011000110001",
  "1101100011010111001001101011011100010111011110101" };

    
    if (b==ls) return 0;
    int k=(b<<5)+j;
    if (found(mm,k)) return mm[k];
    int v = 999999;
    for (int i=j; i<22; i++) {
      int li = strlen(bs[i]);
      if (ls - b < li) break;
      if (strncmp(s+b, bs[i], li) == 0) {
        v = min(v, 1+sub(b+li, j));
      }
      v = min(v, sub(b, j+1));
    }
    return mm[k] = v;
  }
  
  int getmin(string S) {
    mm.clear();
    
    ls = S.size();
    strcpy(s, S.c_str());
    int a = sub(0, 0);
    if (a == 999999) return -1;
    return a;
  }
};

Medium (555): XorBoard

• トグル動作（というかxor）なのでx+2nかけるのはx回かけるのと同じ。
• 残った回数（偶数であること）でon/offを繰り返せばよい。
• どの行（列）にon/offするかの組み合わせは(w+x)Cxみたいな。
• 何行・何列かけるとSになるのか調べて、どの列にかけるかの組み合わせの数はnCrで計算。
• 327.58points → 撃墜
  • 1人目のコードを開いた瞬間に自分のが落とされる事に気づいた＞＜
  • nCr のパスカルの三角形をテーブルに用意しておこうと思ったのは良かったんだけど足りなかった。c[1600][1600] とかないわー
• 2400x2400まで取ってPractice Roomに投げたら通った＞＜
  • ちなみにメモリ制限があるのでlong longで3000x3000とかは取れないよ

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

#define MOD 555555555LL

ll c[1600][1600]; ///OOPS.. このコードの1600を2400に置き換えれば通る

class XorBoard {
 public:
  ll sep(ll m, ll k) {
    return c[m+k-1][k-1];
  }
  int count(int H, int W, int Rcount, int Ccount, int S) {
    rep(i,1600) rep(j,1600) c[i][j] = 1LL;
    for (int i=2; i<1600; ++i) {
      for (int j=1; j<i; ++j) {
        c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
      }
    }

    ll tot = 0LL;

    int iH=H, iW=W;
    if (iH>Rcount) iH=Rcount;
    if (iW>Ccount) iW=Ccount;
    rep(h,iH+1) rep(w,iW+1) {
      int ah = Rcount-h, aw = Ccount-w;
      if ((ah&1) || (aw&1)) continue;
      ah/=2; aw/=2;

      int rh = H-h, rw = W-w;
      int s = h*rw + w*rh;
      if (s == S) {
        ll u = (c[H][h] * sep(ah,H)) % MOD;
        ll v = (c[W][w] * sep(aw,W)) % MOD;
        u = (u * v) % MOD;
        tot = (tot + u) % MOD;
      }
    }
    return tot;
  }
};

Hard (1055): MapGuessing

• 開いた。題意把握。
• イカ娘とかないわー

Challenge phase

• 部屋(Room 9)に赤が1人だけ、あとは黄色と青。
• 不活溌なChallenge phase。落とされたのは自分のMediumだけ。

終了

ox- 1586→1557 ;; Medium解けた!!と思ったのにc[1600][1600]までしか用意してないという初歩的な死因。（2400x2400ぐらいあれば足りる。3000x3000とかはメモリ制限に引っかかる）#srm555

— naoya tさん (@naoya_t) 9月 7, 2012

• [Easy] 2進50ビットなら（文字列じゃなくて）long longでやれるよね（今日は文字列しか考えてなかった＞＜）
• [Medium] combination回りで足下を掬われる人は少なくない？
• 夕食会（懇親会？）には参加せず帰宅。
• またonsiteがあれば行きます
  • オンサイトとかあると割と参加しようかなと思うので、学生限定とかなしでちょくちょくやってほしい

*1:CourseraのAlgorithmsのクラスでJavaコードを書いてる時も同じ事を考えているので単に言ってみたいだけ