LionAge II動的計画法。最後の文字と書き換え回数ごとに最大ボーナスを覚えておく。 #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; cin >> s; int k; cin >> k; int n; cin >> n; static int bonus[128][128]; for ( int i=0;</algorithm></string></iostream>…

Need For BrakeVasyaが最高の順位を取る時、Vasyaは最高点。この状態で一度ソートして、Vasyaより順位が下のレーサーに対し、低い点数を順に割り当てていく。ただし、最も低い点を割り当ててもVasyaより高順位になるレーサーは除く。 Vasyaが最低の順位を取…

The Elder Trolls IV: Oblivon切る回数はなるべく各方向に均等に分けた方が良い。ただし、セル数-1回しか切れない。 x,y,z,k = map(int,raw_input().split()) x,y,z = sorted((x,y,z)) kx = min(x-1,k/3); k -= kx ky = min(y-1,k/2); k -= ky kz = min(z-1,…

A 150 B 0 C 812 Hack 0 結果 174位 1944 → 1870 (´･ω･｀)

Array2nCn-n。 小さいnに対して実際に調べて、OEISに訊いた。 理由を考えてみる。n個の数字からn個を選ぶ重複組合せは2n-1Cn通り。選んだ数字を昇順と降順に並べることでbeautiful arrayが得られる。22n-1Cn=2nCn通り。ただし、これは全てが同じ数字の数列を…

Martian ArchitectureChrisが興味を持っている場所だけ調べる。PythonだとTLE。 #include <iostream> #include <vector> using namespace std; int main() { int n,m,k; cin >> n >> m >> k; vector<int> a(m), b(m), c(m); for ( int i=0; i<m; i++ ) cin >> a[i] >> b[i] >> c[i]; long long ans </m;></int></vector></iostream>…

Square Earth? def d(n,x,y): if y==0: return x if x==n: return n+y if y==n: return 3*n-x if x==0: return 4*n-y return -1 n,x1,y1,x2,y2 = map(int,raw_input().split()) d1 = d(n,x1,y1) d2 = d(n,x2,y2) print min(abs(d2-d1),4*n-abs(d2-d1))

A 482 B 860 C 1128 Hack +100 Cでn≦100000のところn≦1000と勘違いしている人が居たのでHack。 結果 59位 1856 → 1944 (｀･ω･´)

First Digit Law先頭が1である確率は[L,R]の範囲内で先頭が1であるものの個数を(R-L+1)で割れば求まる。ちょうどk個が1である確率を動的計画法で求めて足しあわせる。1018は入るけど、1019はsigned long longから溢れる。Pythonだとそういうことを気にしなく…

Cutting Jigsaw Puzzle約数の個数はそんなに多くないので全通り試しても間に合う。 def rotate(p): w,h = len(p[0]),len(p) r = [] for y in range(w): r += [[]] for x in range(h): r[-1] += [p[x][w-y-1]] return r A,B = map(int,raw_input().split()) P…

Presents N,K = map(int,raw_input().split()) C = [0]+map(int,raw_input().split())[1:]+[N+1] print sum([1+(C[i]-C[i-1]-1)/K for i in range(1,len(C))])-1

A 464 B 820 C 924 結果 61位 1787 → 1856 自己最高レート。

Choosing Symbol Pairs文字cの出現回数がx回ならばi,jの選び方はx2通り。 S = raw_input() print sum([S.count(c)**2 for c in set(S)])

Domino piling N,M = map(int,raw_input().split()) print N*M/2

Permutationsxの個数をCxとして、C1≧C2≧C3…が成り立てば良い。順列の個数はC1。答えは-1だけど入力にnより大きい数がくることもあり得る。 n = input() P = map(int,raw_input().split()) N = max(P) C = [0]*(N+1) A = [0]*n for i in range(n): C[P[i]] +=…

The Race1kmごとにガソリンスタンドがあり、ガソリン1リットルで1km進むと考えても答えは同じ。入力のi番目がsだったとすると、残っているガソリンはa*i-sリットル。そこで給油するので0

http://www.codeforces.com/contest/48/problem/B:title=Land Lot] def read(): return map(int,raw_input().split()) n,m = read() G = [read() for i in range(n)] a,b = read() ans = n*m for i in range(n-a+1): for j in range(m-b+1): t = sum([sum(g[…

A + 00:25 B + 00:35 C + 01:52 D +1 00:49 結果 110位 1849 → 1787 Eが解けなくて悔しい。

Parking LotLに対してnが小さいので、駐車場の状態ではなく止まっている車を記憶しておく。あらかじめ１台車を停めておくと楽。 L,b,f = map(int,raw_input().split()) n = input() P = [(-b,0,-1)] # position,length,id for i in range(n): t,l = map(int,…

T-shirts from Sponsor size = ["S","M","L","XL","XXL"] N = map(int,raw_input().split()) K = input() for i in range(K): c = raw_input() for d in [0,+1,-1,+2,-2,+3,-3,+4,-4]: t = size.index(c)+d if 0<=t<5 and N[t]>0: print size[t] N[t] -= 1 b…

Ball Game c = 0 n = input() for i in range(n-1): c = (c+i+1)%n print c+1, print

A + 00:11 B + 00:26 C + 00:34 D + 01:36 E +2 02:02 結果 81位 1745 → 1849 良い感じ。EはTLE。入力のサイズが大きい場合にcinは禁物....〆(･ω･｀ )

Phone Number動的計画法。i番目の数字がjであるときi番目以降に何通りの電話番号があるかを記憶しておく。Masha自身の番号が生成可能なら-1。 d = [int(x) for x in raw_input()] n = len(d) T = [[0]*10 for x in range(n)] T[n-1] = [1]*10 for i in range…

Anfisa the Monkey全てを同じ長さ、もしくは長さの差が１になるように切るのが最善。 k,a,b = map(int,raw_input().split()) t = raw_input() n = len(t) l = n/k if a<=l<=b-1 or a<=l<=b and n-k*l==0: for i in range(k*(l+1)-n): print t[:l] t = t[l:] …

Hyperdrive惑星を２つ経由する距離の最小値の半分。平方根の計算が重いので、なるべく減らすようにしたら通った。 #include <iostream> #include <vector> #include <cmath> using namespace std; double dist( vector<int> a, vector<int> b ) { return sqrt( pow((double)a[0]-b[0],2) + pow((</int></int></cmath></vector></iostream>…

Holidays n,m = map(int,raw_input().split()) f = [0]*(n+1) for i in range(m): a,b = map(int,raw_input().split()) for j in range(a,b+1): f[j] += 1 for i in range(1,n+1): if f[i]!=1: print i, f[i] exit() print "OK"

ColaDPにするまでもない。 #include <iostream> using namespace std; int main() { int n, a, b, c; cin >> n >> a >> b >> c; int r = 0; for ( int i=0; i<=a; i+=2 ) for ( int j=0; j<=c; j++ ) { int k = n - i/2 - j*2; if ( 0 <= k && k <= b ) r++; } cout <<</iostream>…

Indian Summer import sys print len(set(sys.stdin))-1

Repaintings n,m=map(int,raw_input().split()) x=input()-1 print max(n+m-4*x-2,1) if min(n,m)>2*x else 0

Find Color x,y = map(int,raw_input().split()) r = int((x*x+y*y)**0.5) print "black" if x*x+y*y==r*r or (r+(x>0)+(y>0))%2==0 else "white"