Let's Go Rolling!動的計画法。ビー玉の位置でソートして、左から順に、ビー玉をある位置で止めるときに必要な金を求める。 #include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<pair<int,int> > m(n); for ( int i=0; i<n; i++ ) cin >></n;></pair<int,int></algorithm></utility></vector></iostream>…

Vasya the Architect積み上げたレンガの重心が下のレンガの外側にあると塔が崩れる。引っかかりどころがたくさん。 誤差が怖いので整数で計算。 入力がx1>x2という場合もある。 レンガは1つずつ積む。例えば↓の入力は3個目のレンガを乗せれば安定するけど、2…

Blinds長さxの帯が何本切り取れるかをxの値を変えながら調べる。 n,l = map(int,raw_input().split()) a = map(int,raw_input().split()) ans = 0 for x in range(l,max(a)+1): ans = max(ans,sum([t/x*x for t in a])) print ans

Chess全ての置き場所を試しても余裕で間に合う。 t = raw_input() r = (ord(t[0])-ord("a"))+(ord(t[1])-ord("1"))*1j t = raw_input() k = (ord(t[0])-ord("a"))+(ord(t[1])-ord("1"))*1j move = [-1+2j,1+2j,2+1j,2-1j,1-2j,-1-2j,-2-1j,-2+1j] c = 0 for …

Army input() d = map(int,raw_input().split()) a,b = map(int,raw_input().split()) print sum(d[a-1:b-1])

A + 00:06 B + 00:22 C +1 00:42 D +6 03:28 E +1 01:10 結果 109位 1681 → 1745 Dにハマったのが痛かったが、レーティング上がったし満足。

Old Berland Language短い順に単語を割り当てていく。例えば長さが、3, 3, 3, 5, 5ならば、 000 001 010 01100 01101多倍長整数を使うと楽。 N = input() l = map(int,raw_input().split()) ans = [""]*N c = 0 d = 0 while True: p = -1 for i in range(N):…

Computer Gameそのときに詠唱可能な最も強い呪文を唱える。NOとなるのは、ボスのHPが減らないかつ新たに唱える呪文が無い場合。ボスのHPが減らないだけだと↓の入力にNOを返してしまう。 3 100 29 100 10 100 10 100 10import itertools N,max,reg = map(int,…

Towers input() l = map(int,raw_input().split()) print max([l.count(x) for x in l]), len(set(l))

久しぶりに参加。 A 480 B System Test Failed C 1098 結果 160位 1672 → 1681

Extra-terrestrial Intelligenceファイル入出力だとデバッグが地味に面倒。 input = open("input.txt","r") output = open("output.txt","w") input.readline() if len(set(input.readline().split("1")[1:-1])) <= 1: output.write("YES") else: output.wri…

Phone numbers最後以外は２個ずつに区切れば良い。 n=input() x=raw_input() y="" for i in range(n): y+=x[i] if i%2==1 and i

IQ test n=input() x=map(int,raw_input().split()) e=[]; o=[] for i in range(n): if x[i]%2==0: e+=[i+1] else: o+=[i+1] if len(e)==1: print e[0] if len(o)==1: print o[0]

Sequence of pointsM1.x = 2A0.x - M0.x M2.x = 2A1.x - M1.x = 2A1.x - 2A0.x + M0.x : Mn.x = 2(An-1.x - An-2.x + …… + A0.x) - M0.x M2n.x = 2(An-1.x - An-2.x + …… + A0.x) - Mn.x + M0.x = M0.xy座標も同様。 import sys A = [map(int,x.split()) for…

F1 Champions point = [25, 18, 15, 12, 10, 8, 6, 4, 2, 1]+[0]*50 t = input() score = {} for i in range(t): n = input() for j in range(n): name = raw_input() if name not in score: score[name] = [0]*51+[name] score[name][0] += point[j] score[…

Ring road全ての都市を行き来できるときは、一周できる。与えられた辺の方向別にコストを足して小さい方が答え。 n = input() road = [map(int,raw_input().split()) for i in range(n)] c1 = c2 = 0 p = 1 pr = 0 for i in range(n): for r in road: if r !…

忘れてた。

Checkout Assistantコンテスト中はk番目までの商品でm秒の余裕を作るのに必要な最小のお金を求めるDPでプログラムを書いていた。配列の添字が負値にもなって面倒だなと思っていたら、mにレジを通過した商品数も加えれば負にはならないと教わった。たしかに。…

World Football Cup各段階での評価項目を求めて、ソート。 import re n = input() for i in range(n): raw_input() team = {} for i in xrange(n*(n-1)/2): name1,name2,num1,num2 = re.compile("[: -]").split(raw_input()) num1,num2 = int(num1),int(num2…

#8以来の２回目。 Ａノーミス、Ｂ２ミスで、1622→1672。ギリギリ黄色。

Flag 2条件から旗は２列ごとの繰り返しになるので、偶数列と奇数列の色を用いて動的計画法。色数をcとして、O(nc2(m+c2))。C++ならば充分だけど、Pythonでは間に合わない。 id:pes_magic さんにオーダーを下げる方法を教えてもらいPythonでも通った。 Python…

Seller Bob動的計画法。i日目に2xMBを手に入れて、j日目に2xMBのメモリスティックを買いに来る客がいるならば、j日目の収入はj-1日目の収入（この客にメモリスティックを売らない）とi日目の収入+2xberllar（この客にメモリスティックを売る）のどちらか大き…

Stripe切れ目の位置ごとに合計を求めると間に合わないので、動的に計算する。 n = input() s = [int(x) for x in raw_input().split()] c = 0 l,r = 0,sum(s) for i in xrange(n-1): l += s[i] r -= s[i] if l == r: c += 1 print c

Platforms着地点について考えると（たぶん）間に合わないので、それぞれの穴について考える。 n,d,m,l = [int(x) for x in raw_input().split()] for k in xrange(n): t = ((k*m+l)/d+1)*d if ( k < n-1 and t < (k+1)*m or k == n-1 ): print t break

Triangle def rightsub(x1,y1,x2,y2,x3,y3): dx1,dy1 = x2-x1,y2-y1 dx2,dy2 = x3-x1,y3-y1 return ( ( dx1 != 0 or dy1 != 0 ) and ( dx2 != 0 or dy2 != 0 ) and dx1*dx2+dy1*dy2 == 0 ) def right(x1,y1,x2,y2,x3,y3): return ( rightsub(x1,y1,x2,y2,x3,…

Pythonゲーｷﾀ━━━(ﾟ∀ﾟ)━( ﾟ∀)━( ﾟ)━( )━( )━(ﾟ )━(∀ﾟ )━(ﾟ∀ﾟ)━━━!!!!! b,n,c = [int(x) for x in raw_input().split()] print ((b-1)*pow(b,n-1,c)+c-1)%c+1 →Time limit exceeded orz２行目は問題無いのだけど、１行目の読み込みに時間がかかる。10進数のま…

Hierarchyそれぞれの社員についてコストが最小となる直属の上司を探す。2人以上直属の上司が居ない社員が居たら階層を作れない。1人直属の上司が居ない社員が居ればコストの和が答え。全員に直属の上司が居ればコストが最大の社員以外のコストの和。applicat…

Noldbach problem n,k = [int(x) for x in raw_input().split()] prime = [] for i in xrange(2,n+1): if all((i%p!=0 for p in prime)): prime += [i] c = 0 for i in xrange(len(prime)-1): if prime[i]+prime[i+1]+1 in prime: c += 1 if c >= k: print "…

スルー。

C. Industrial Nimそれぞれのダンプの石の数の排他的論理和を計算し、0ならば後手が勝ち、0以外の場合は先手が勝つという定理がある。例えば問題文の最初の例はトラックの石の数が2, 3, 4で2^3^4=5≠0なので先手の勝ち。 今回はトラックの数が非常に多くなり…