Google Code Jam Japan 2011 予選

公式

B-largeのみ不正解。196位。決勝もこれならTシャツギリギリラインだ。
公式ハッシュタグは #gcjjp (自分用メモ)

A. カードシャッフル

シャッフル回数がたかだか100回だから、ほとんどのカードが最後まで連番で並んでる。
なので、[ [最初のカード番号, 枚数], ... ] のように区間リストで持ってシミュレーションした。
カット範囲が複数の区間にまたがるので書きにくく、1時間くらいかかってAC。

模範解答は知りたいカードの位置だけ考えて、逆順にシャッフルして最初にどこにあるか求めればいいらしい。がっかり。

require 'pp'

# http://0xcc.net/ruby-bsearch/index.html.ja
# require './bsearch'

# https://github.com/kanwei/algorithms
# require 'rubygems'
# require 'algorithms'
# include Containers

def ppd(*arg)
  if $DEBUG
    pp(*arg)
  end
end

def putsd(*arg)
  if $DEBUG
    puts(*arg)
  end
end

def read_ints()
  readline().split.map{|e| e.to_i }
end

def read_floats()
  readline().split.map{|e| e.to_f }
end

def read_words(count)
  words = []
  for i in 1 .. count
    words << readline().chomp
  end
  words
end

# main
t_start = Time.now

# ここから問題に応じて
cases = readline().to_i

(1 .. cases).each do |case_index|
  m, c, w = read_ints
  
  cuts = Array.new
  for i in 1 .. c
    cuts << read_ints
  end

  cards = Array.new
  cards << [ 1, m ]

  cuts.each do |cut|
    cut_start = cut[0]
    cut_count = cut[1]

    index = 1

    new_cards = Array.new
    cutted = Array.new

    cards.each_with_index do |seq, cards_index|
      index_range_start = index
      index_range_end = index + seq[1]

      if cut_count > 0 && index_range_start <= cut_start && cut_start < index_range_end
        # この連番の一部をカットする
        start_in_seq = seq[0] + cut_start - index_range_start
        max_cut_count = seq[1] - (cut_start - index_range_start)
        count = [cut_count, max_cut_count].min

        cutted << [start_in_seq, count]

        new_seq_1 = [seq[0], start_in_seq - seq[0]]
        new_seq_2 = [start_in_seq + count, seq[1] - (cut_start - index_range_start) - count]

        new_cards << new_seq_1 if new_seq_1[1] > 0
        new_cards << new_seq_2 if new_seq_2[1] > 0

        cut_start += count
        cut_count -= count
        if cut_count < 0
          cut_count = 0
        end
      else
        new_cards << seq
      end

      index += seq[1]
    end

    cutted.reverse.each do |e|
      new_cards.unshift(e)
    end

    raise if cut_count != 0

    cards = new_cards
  end

  # W番目のカードを求める
  index = w
  answer = -1
  cards.each do |seq|
    if index <= seq[1] && answer == -1
      answer = seq[0] + (index - 1)
    end
    index -= seq[1]
  end

  puts "Case ##{case_index}: #{answer}"

  # progress
  trigger = 
    if cases >= 10
      case_index % (cases / 10) == 0
    else
      true
    end

  if trigger
    STDERR.puts("case #{case_index} / #{cases}, time: #{Time.now - t_start} s")
  end
end

B. 最高のコーヒー

全探索でSmallのみAC。Largeは思いつかず。
最終日から逆順にGreedyでいいらしい。言われてみればそうかも。
序盤の問題だからDPはないだろう、たぶんGreedyだよなー。と思いつつもたどり着けなかった。

#include <cstdio>
#include <cmath>
#include <ctime>
#include <memory.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <assert.h>
#include <string>
#include <limits.h>

using namespace std;

#define FOR(i, e) for(int i = 0; i < (e); i++)
#define FORS(i, s, e) for(int i = (s); i < (e); i++)
#define ALL(c) c.begin(), c.end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;

int ri(){ int value; scanf("%d", &value); return value; }
ll rl(){ ll value; scanf("%lld", &value); return value; }
double rd(){ double value; scanf("%lf", &value); return value; }
string rs(){ char buf[10000]; scanf("%s", buf); return buf; }
template<class T> void sort(T& c){ sort(c.begin(), c.end()); }
template<class T> void rsort(T& c){ sort(c.begin(), c.end()); reverse(c.begin(), c.end()); }

#ifdef LOCAL
	#define ppd(...) printf(__VA_ARGS__)
#else
	#define ppd(...)
#endif

int N, K;
int c[8];
int t[8];
int s[8];
int max_score = 0;

int select[8];

void solve(int day, int score)
{
	if(day > K)
		return;

	FOR(i, N)
	{
		if(t[i] >= day && c[i] >= 1)
		{
			select[day - 1] = i;
			int current_score = score + s[i];
			if(max_score < current_score)
			{
				max_score = current_score;
				
				printf("%d : ", max_score);
				FOR(j, day)
				{
					printf("%d ", select[j]);
				}
				printf("\n");
			}

			c[i]--;
			solve(day + 1, current_score);
			c[i]++;
		}
	}
}

int main()
{
#ifdef LOCAL
	time_t start;
	time(&start);
#endif
	// 本文 --------------------------------------
	int probs = ri();
	FOR(prob_index, probs)
	{
		N = ri();
		K = ri();
		FOR(i, N)
		{
			c[i] = ri();
			t[i] = ri();
			s[i] = ri();
			ppd("[%d] c, t, s = %d, %d, %d\n", i, c[i], t[i], s[i]);
		}

		max_score = 0;
		solve(1, 0);
		printf("Case #%d: %d\n", prob_index + 1, max_score);
	}

	// 本文終わり --------------------------------
#ifdef LOCAL
	time_t end;
	time(&end);
	printf("%ld sec.\n", end - start);
#endif
	return 0;
}

C. ビット数

N = 1から順に手で解いたら、a, bの片方は全ビットが立つみたい。
よくわかんないけどそれで書いてAC。

require 'pp'

# http://0xcc.net/ruby-bsearch/index.html.ja
# require './bsearch'

# https://github.com/kanwei/algorithms
# require 'rubygems'
# require 'algorithms'
# include Containers

def ppd(*arg)
  if $DEBUG
    pp(*arg)
  end
end

def putsd(*arg)
  if $DEBUG
    puts(*arg)
  end
end

def read_ints()
  readline().split.map{|e| e.to_i }
end

def read_floats()
  readline().split.map{|e| e.to_f }
end

def read_words(count)
  words = []
  for i in 1 .. count
    words << readline().chomp
  end
  words
end

def bit_count(value)
  byte = value

  count = 0
  count += byte & 1 and byte >>= 1 until byte == 0

  count
end


# main
t_start = Time.now

# ここから問題に応じて
cases = readline().to_i

(1 .. cases).each do |case_index|
  n = read_ints[0]

  a_max = 0

  if n == 2
    a_max = 1
  elsif (n & 1) != 0
    a_max = n / 2 + 1
  else
    a_max = n / 2
  end

  leftmost = 0
  for i in 0 .. 64
    if (a_max & (1 << i)) != 0
      leftmost = i
    end
  end

  all_one = (1 << leftmost) | ((1 << leftmost) - 1)

  raise if all_one > n

  case_1 = bit_count(all_one) + bit_count(n - all_one)

  cut_one_bit = all_one >> 1
  case_2 = bit_count(cut_one_bit) + bit_count(n - cut_one_bit)

  puts "Case ##{case_index}: #{[case_1, case_2].max}"

  # progress
  trigger = 
    if cases >= 10
      case_index % (cases / 10) == 0
    else
      true
    end

  if trigger
    STDERR.puts("case #{case_index} / #{cases}, time: #{Time.now - t_start} s")
  end
end