とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

人生初の競技プログラミング参加

POJ で問題を解いたことはあっても,制限時間ありの本格的な(?)競技プログラミングはしたことがありませんでした。
今回 Google Code Jam Japan 2011 に初参加。

結果

A-smallC-small だけ通しました。順位は上位80%以内。次回(あれば)は上位50%以内を目指してみたいです。

感想

初参加かつ競技が始まってからの参加であたふたしながら,また,途中抜けながら問題を解きました。
C-large で余計なことして不正解にしてたり,B-small で消費期限を考慮してなかったりと,ぐだぐだな感じでした。しかし,競技自体はわりと楽しかったです。

コード

A-small

iota を使ったほうがカッコイイと思うのですが,forとpush_backでカードを作りました。競技中はその方が速いと思ったのですが,今思えば vector::size 使っても zero-initialize されるわけじゃないから iota 使ってもよかったかも。
rotate が美しくきまってますよね?

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

using namespace std;

template<class T>
inline T get()
{
 T tmp;
 cin >> tmp;
 return tmp; 
}

typedef unsigned M_t;
typedef vector<M_t> cards_t;

int main()
{
 unsigned const T = get<unsigned>();
 for(unsigned i = 0; i < T; ++i)
 {
  M_t const M = get<M_t>();
  unsigned const C = get<unsigned>();
  M_t const W = get<M_t>();
  
  cards_t cards;
  cards.reserve(M);
  for(M_t j = 1; j <= M; ++j)
   cards.push_back(j);

  for(unsigned j = 0; j < C; ++j)
  {
   M_t const A = get<M_t>();
   M_t const B = get<M_t>();
   rotate(cards.begin(), cards.begin() + A - 1, cards.begin() + A - 1 + B);
  }
  cout << "Case #" << i + 1 << ": " << cards[W - 1] << '\n';
 }
}

C-small

最初に解きました。使われることのない残骸があります。スルーしましょう。

#include<vector>
#include<algorithm>
#include<iostream>
#include<utility>

using namespace std;

typedef pair<unsigned, unsigned> P;
typedef vector<P> V;

unsigned f(unsigned n)
{
 unsigned ret = 0;
 for(unsigned i = 0; i < 32; ++i)
 {
  if(n & (1 << i))
  {
   ++ret;
  }
 }
 return ret;
}

V make_p(unsigned n)
{
 V v;
 v.reserve(n - 1);
 return v;
}

int main()
{
 unsigned t;
 cin >> t;
 for(unsigned i = 0; i < t; ++i)
 {
  unsigned n;
  cin >> n;
  vector<unsigned> v;
  v.reserve(n - 1);
  unsigned mx = 0;
  for(unsigned j = 0; j < n; ++j)
  {
   unsigned tmp = f(j) + f(n - j);
   mx = max(tmp, mx);
  }
  cout << "Case #" << i + 1 << ": " << mx << '\n';
 }
}

C-large

時間内に提出したコードにはバグがあり,不正解でした。修正したものを貼ります。

#include<vector>
#include<algorithm>
#include<iostream>
#include<utility>

using namespace std;

unsigned f(unsigned long long n)
{
 unsigned ret = 0;
 for(unsigned long long i = 0; i < 64; ++i)
 {
  if(n & (1ULL << i))
  {
   ++ret;
  }
 }
 return ret;
}

int main()
{
 unsigned t;
 cin >> t;
 for(unsigned i = 0; i < t; ++i)
 {
  unsigned long long n;
  cin >> n;
  unsigned mx = f(0) + f(n);
  for(unsigned long long j = 1; j < n; j = (j + 1) * 2 - 1)
  {
   unsigned tmp = f(j) + f(n - j);
   mx = max(tmp, mx);
  }
  cout << "Case #" << i + 1 << ": " << mx << '\n';
 }
}

元のバグってるコードでは

  for(unsigned long long j = 1; j < n; j = (j + 1) * 2 - 1)

  for(unsigned long long j = 1; j < n / 2 + 1; j = (j + 1) * 2 - 1)

と書いていました。
元々総当りのコードを書いていた→半分だけ調べたらいいんじゃね→やっぱ (n^2)-1 だけ調べればいいんじゃね?
の流れで "/ 2 + 1" を残してしまったのです。これさえちゃんと消していれば…。ぐぬぬ…。