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