読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2016 - Round 1B

4/30(土) 25:00〜27:30
C-smallまで取れて70点596位。1000位以内に入れたのでRound 2(+ Distributed Code Jam) 進出決定!
(C-largeも諦めずに書き続けて27:39にpractice roomでAC出せたので、あと9分あれば全完でした)

続きを読む

Google Code Jam 2016 - Round 1A

4/16(土) 10:00〜12:30
Bで躓いて順当にRound 1B進出をキメました*1…orz
いずれにせよ、100点取ってないと(取ってても)上位1000人には入れなかったようなので、1Bでまた頑張ります…

*1:ここを読んでる方はご存知だと思いますが、1A,1B,1Cの3回のチャンスのどれかで上位1000人に入ればRound 2に進出できる仕組みです

続きを読む

Google Code Jam 2016 - Qualification Round

4/9 8am〜4/10 11am
hackercup以来のプロコン参加。

QRは27時間で、30点以上獲得すれば本選に進出。
QRに限っては、相談しながらやってもよくて、公開されていない謎言語で解いてもいい。
Project Eulerみたいに紙と鉛筆でもいいのかは分からない)

とりあえず(いつも通り)、予選通過確定のためにsmallから押さえる。
珍しくwrong tries無しでA (small 7pt) - A (large 8pt) - B (small 10pt) - C (small 10pt) - D (small 10pt) と進む。
smallはその場でAC/WA判定されるのだけれど、largeの判定は終了後なので、この時点で37点は確実なので予選通過確定。

その後、B (large 10pt) - C (large 20pt) - D (large 25pt) と解いて全完。
無事全問ACで100点通過しました

続きを読む

Facebook Hacker Cup 2016 : Round 1

Programming Contest

Qiitaにはいくつか記事を書いていますがはてなでは1年以上ぶりです。
普段はPythonばかり書いています。最近はtheanoが気に入っています。あとclickと。

かよちん生誕祭に開催されたFacebook Hacker CupのR1でなぜか全完できたので、たまには記事を書こうという気になりました。
f:id:n4_t:20160118074840p:plain

続きを読む

SRM638

金曜日にagwさんクラスタ(Marathon勢多め)とお好み焼に行ってきて刺激されて。
半年ぶりのSRM参戦。

300-600-800とな
いずれにしてもEasyから開く方針

Coding Phase

Easy (300) ShadowSculpture

開いた。

1x1x1キューブで出来た三次元物体のxy面・yz面・zx面それぞれへの射影が与えられ、それと辻褄の合うような、「1つに繋がった」物体が存在しうるかどうか。

まず、xy面の影に、yz面の影を掛けあわせていく感じ。(論理積
xy面の影からyz面の影が不可能だと分かる場合はその時点で"Impossible"。
さらにそこにzxの影を掛けあわせていく。ここで不可能なら"Impossible"。
出来上がった物体が1つに繋がっていれば(ここはUnionFindね)"Possible"。2つ以上の島になってれば”Impossible”。

→WA(30'57'', 167.69pts→0.0pts)
3つの影からの合成だと、内側に(というかどの軸からも見えない影に)孤立したキューブが残ってしまってImpossibleと誤判定してしまうケース(しかもそれを消しても影は変わらなくて本当はPossible,みたいな)などがあるらしい。

うちの部屋はyellowとblueしかいなくて撃墜少なめだったけど、ほとんどsystem testで落ちてた。
Div1でこれ通せた人数はMediumより少なかった。

using namespace std;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);++var)

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size);
  bool unionSet(int x, int y);
  bool findSet(int x, int y);
  int root(int x);
  int size(int x);
};

class ShadowSculpture {
 public:
  int n;
  int b[10][10][10];
  string possible(vector <string> XY, vector <string> YZ, vector <string> ZX) {
    n = sz(XY);

    int cc=0;
    UnionFind uf(n*n*n);

    rep(x,n)rep(y,n)rep(z,n) b[x][y][z]=0;
    rep(x,n)rep(y,n){
      int s = (XY[x][y]=='Y')?1:0;
      rep(z,n) b[x][y][z] = s;
    }
    rep(y,n)rep(z,n){
      int s = (YZ[y][z]=='Y')?1:0;
      int cnt = 0;
      rep(x,n) cnt += b[x][y][z];
      if (s>0 && cnt==0) goto impossible;
      rep(x,n) b[x][y][z] &= s;
    }
    rep(z,n)rep(x,n){
      int s = (ZX[z][x]=='Y')?1:0;
      int cnt = 0;
      rep(y,n) cnt += b[x][y][z];
      if (s>0 && cnt==0) goto impossible;
      rep(y,n) b[x][y][z] &= s;
    }

    rep(x,n)rep(y,n)rep(z,n){
      if (!b[x][y][z]) continue;
      ++cc;
      int id=z*n*n + y*n + x;
      if (x<n-1){
        if (b[x+1][y][z]) uf.unionSet(id,id+1);
      }
      if (y<n-1){
        if (b[x][y+1][z]) uf.unionSet(id,id+n);
      }
      if (z<n-1){
        if (b[x][y][z+1]) uf.unionSet(id,id+n*n);
      }
    }
    if (cc==0) goto possible;

    rep(x,n)rep(y,n)rep(z,n){
      if (!b[x][y][z]) continue;
      int id=z*n*n + y*n + x;
      if (uf.size(id) == cc) goto possible;
      else goto impossible;
    }
 possible:
    return "Possible";
 impossible:
    return "Impossible";
  }
};

Medium (600) NarrowPassage2

開いた
左からDP?違うね
大きい狼からtreeにぶら下げていく?ちょっと違う。
大きい狼から順に、可動域(左右の自分より大きい狼だけ見て行って、swapできなくなる所まで)を調べていく。
自分より大きな狼の並び順は、swapさえできるならどうでもいい。(というか単純に掛けあわせていけばいい)

→AC(39'41'', 290.52pts)
これ通してたの部屋で5人だけだった

using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
typedef pair<int,int> i_i;

class NarrowPassage2 {
 public:
  int n;
  int count(vector<int> size, int mss) {// maxSizeSum
    n = sz(size);
    ll ans = 1L;
    vector<i_i> pos(n);
    rep(i,n) pos[i] = i_i(size[i], i);
    sort(all(pos)); reverse(all(pos));
    vector<int> rev(n);
    rep(i,n){
      rev[pos[i].second] = i;
    }
    rep(i,n){
      int s=pos[i].first, a=pos[i].second;
      int x=mss-s, c=1;
      for(int j=a-1; j>=0; --j){
        if (rev[j]>=i) continue;
        if (size[j]>x) break;
        ++c;
      }
      for(int j=a+1; j<n; ++j){
        if (rev[j]>=i) continue;
        if (size[j]>x) break;
        ++c;
      }
      ans = (ans * c) % 1000000007LL;
    }

    return (int)(ans % 1000000007LL);
  }
};

Hard (800)

3分ぐらい残ってたけど
開いてない

Challenge Phase


600みんなに開かれた(が落とされず)
300落とされた
Div1の他所の部屋では300大虐殺らしい。

System Test

600通ってよかった。最高レーティング更新!


f:id:n4_t:20141103183041p:plain

Google Code Jam 2014 - Round 2

Programming Contest Google Code Jam


晩御飯たべて風邪薬のんで寝落ちして、気がつけば開始30分過ぎてました…orz

気を取り直して問題を開いて
...

A-small, A-large だけ通して、Bではまり。
「参加賞」Tシャツに手が届かず、今年の夏は終わりました。

来年またお会いしましょう。

続きを読む

GCCのビルトイン関数メモ

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html より

関数名末尾に l が付いてるのは long、ll なら long long、無印は unsigned int。
他にもいろいろあるけど、コンテストで使うかもしれないやつだけとりあえず。

__builtin_popcount, __builtin_popcountl, __builtin_popcountll

立ってるビット数を数えて返す
0x11 (2進で10001) なら2
0x57 (2進で1010111) なら5

__builtin_parity, __builtin_parityl, __builtin_parityll

立ってるビット数の偶奇を返す。(popcount % 2 に相当)
0x11 (2進で10001) なら0(偶数)
0x57 (2進で1010111) なら1(奇数)

__builtin_ffs, __builtin_ffsl, __builtin_ffsll

2進で表した場合に小さい方から何桁目に初めて1が現れるか。
0x07 (2進で111) なら1。0x08 (2進で1000) なら 4。
0の場合は0を返す。

__builtin_clz, __builtin_clzl, __builtin_clzll

2進で表した場合に左側にいくつ0を埋める必要があるか (the number of leading 0-bits in x)
(32bit unsigned intの場合)0x07 (2進で111) なら29。
0の場合は未定義。

__builtin_ctz, __builtin_ctzl, __builtin_ctzll

2進で表した場合に、1の位からいくつ0が連なっているか (the number of trailing 0-bits in x)
0x08 (2進で1000) なら3。
0の場合は未定義。