Google Code Jam Round 1B 2014 A. The Repeater 文字列の組が与えられたとき、a→aaやaa→aという操作を繰り返して、全ての文字列を等しくする最小手数は？ 各文字ごとに何文字に揃えるのかを全探索。※↓このコードはLarge落ちた。提出ミスだった。 def minify…

Dancing With the Googlers最高点数をpとすると、合計点数の最小は、最高と最低の差が1以下の場合は3p-2、2以下の場合は3p-4である。ただし、p未満にはならない。合計点数がこの最小以上のGooglerを数える。 for i in range(input()):t=map(int,raw_input().…

A. Speaking in Tonguesqとzが分からないけど、2通りしかないので両方試せば良い。 for i in range(input()):print "Case #%s: %s"%(i+1,"".join("yhesocvxduiglbkrztnwjpfmaq"[ord(c)-97]if c!=" "else c for c in raw_input())) マッピングを求めるプログ…

Kingdom Rush手数も星も、最初から星2個を狙った方が得。星を1個だけ取るレベルをいかに減らすかという問題。各回では、星を2個取れるレベルがあるならば、そのレベルに挑戦する。星を1個しか取れないレベルしかないならば、星を2個取るのに必要な星が多いレ…

AとBをLargeまで解いて、501位で通過。

無限庭園0,0から10,10に行くために、1000,1000を経由するような大きな遠回りが無いと仮定して、迷路を実際に作って、最短路探索。一旦、通路の中央を通る経路で最短路を求め、同じ向きに2回曲がっているごとに、最短距離から2を引く。最短経路が2種類あった…

クローゼットルームSmallならばクローゼットの置き方を全て試せる。 # coding: utf-8 import copy # 全てのクローゼットに到達可能かチェック def check(M,C): T = copy.deepcopy(M) # 入り口から到達可能なマスをDにする while True: up = False for y in r…

ワイルドカード答えは、Aのいくつかの部分文字列で*を挟んだ形になっている。全て生成して、Bにマッチしないかどうか調べる。 import re def solve(A,B): n = len(A) ans = A for i in xrange(1<<n): p = "".join(A[i] if i>>j&1 else "*" for j in range(n)) p = re.sub("\*+","*",p) i</n):>…

バクテリアの増殖SmallではBは2以下、1回目は普通に計算するとバクテリアの個数は10進数で高々3000桁。AA mod CはO(log A)で計算できる。参考。Pythonならpow関数に任せれば良い。 def solve(A,B,C): if B==1: return A**A%C else: A = A**A return pow(A,A,…

アンテナ修復並べ終わった後のエレメントの長さを、E1, E2, ……, EKとすると、面積は、 なるべく大きい数同士が隣の方が得だろうと、1 3 5 8 9 7 6 4 2という風に並べたら、正解した。 import math def solve(K,E): E = sorted(E)[::-1] T = [E[i] for i in r…

問題を一通り読んでLargeが全く分からなかったので、Small狙いで解いていったら、7位ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!

ビット数動的計画法。下位の桁をNに一致させて、繰り上がりが無い場合とある場合の、f(a)+f(b)の最大値を覚えてく。もっと綺麗な方法がありそうな気がするが、この解法でもO(桁数)。 # coding: utf-8 def solve(N): M = 100 # [i][j] 下位i-1桁がNと一致し、…

最高のコーヒー後の日から順に、その日に飲むコーヒーを割り当てていくならば、一番満足度の高いコーヒーを貪欲に飲めば良い。飲むコーヒーが変わるのは、そのコーヒーが無くなるか、他のコーヒーが賞味期限前になった時なので、まとめて計算すると、Largeも…

カードシャッフル逆から計算する。例えば、サンプルの最後の例だと、[1 2 3 4 5] → [4 5 1 2 3] → [3 4 5 1 2] → [1 2 3 4 5]で、3回目のシャッフルの後で2番目にあるカードは、3回目のシャッフルの前には5番目に、2回目のシャッフルの前には4番目に、最初は…

Revenge of the Hot Dogs位置PにV個のホットドッグ屋がある時、それらを間隔Dで並べてさらに他のグループとも間隔Dなので、V*Dの幅の板を重ならないように、かつなるべく元の位置から動かさないように敷き詰めるイメージ。秒数が与えられたなら、なるべく左…

RPI問題文の通りに実装。OWPは相手のWPのうち自分との試合の分を除く必要がある。 T = input() for case in range(T): N = input() A = [raw_input() for i in range(N)] WP = [0.0]*N C = [0]*N for i in range(N): for j in range(N): if A[i][j]!=".": C[…

A small large B small large B small を通して、75点、122位。Round2進出(`･ω･´)

GoroSort揃っている数字を押さえて机を叩くという戦略を考えると、n個の間違いがあった時、期待値はn回。サンプル最後のような叩き方もできるけど、揃っていない数字をどのように分けても合計はn回になるはず。 for t in range(input()): input() C = map(in…

Candy SplittingPatrickの計算はxor。全ての飴の価値のxorが0である場合かつこの場合に限り、２つに分けた飴それぞれのxorが等しくなる。この時どのように分けても良いので、Patrickには１番安い飴を１つあげれば良い。Patrick……(´；ω；`)ﾌﾞﾜｯ for t in rang…

Magicka某マギカではない。問題文の通りに実装。10が100になるなら実行時間だけ気にすれば良いけど、Smallで1がLargeで2以上になるのはバグが入りそうで怖い。 def tostr(e): r = "[" for c in e: r += "%s, "%c if len(e)>0: r = r[:-2] r += "]" return r …

Bot Trustちょっと面倒だが、指示されたボタンに向かって相手がボタンを押すまで待機、を１秒ごとにシミュレーション。 # coding: utf-8 T = input() for t in range(T): line = raw_input().split() op = [] N = int(line[0]) for i in range(N): op += [(l…

時間はかかったけど、全問正解で通過(`･ω･´)

Round 2で敗退。Topcoderと違って解く速さで点数が変わったりしないので、来年はもっと問題の点数に気を配ろう。

動的計画法。 i番目の囚人の位置をp[i]として、i番目の囚人とj番目の囚人を解放した後、i番目とj番目の間に居る囚人を解放するのに要するコインをcoin[i][j]とすると。coin[i][j] = mini

ホタルの初期位置と移動速度の平均が重心の初期位置と移動速度になる。 時刻tでの重心の距離を求めて、微分が０になるtがtmin。 ただし、重心が移動しない場合と、tminが負となる場合にはtmin=0。 T = input() for t in range(T): v = [0.0]*6 N = input() f…

先頭から順になるべく小さい数字を割り当て、割り当てた数字の個数を基数とする。 ただし、 先頭に0はダメ 基数は2以上、"1"という入力は2になる。 T = input() for t in range(T): m = raw_input() d = {} v = [] for c in m: if c not in d: d[c] = 1 if l…